1

function removeZeros(arr) {
    let writeIndex = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== 0) {
            arr[writeIndex++] = arr[i];
        }
    }
    arr.splice(writeIndex, arr.length - writeIndex);
}

function isPalindrome(s) {
    function isAlphabetic(symbol) {
        return symbol.toLowerCase() != symbol || symbol.toUpperCase() != symbol || !isNaN(Number(symbol));
    }

    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        while(left < right && !isAlphabetic(s[left])) left++;
        while(left < right && !isAlphabetic(s[right])) right--;

        if (s[left++].toLowerCase() !== s[right--].toLowerCase()) return false;
    }

    return true;
}

function findTwoMaximums(arr) {
    if (arr.length === 0) return [];
    if (arr.length === 1) return arr;

    let fstMax = -Infinity;
    let sndMax = -Infinity;

    for (let elem of arr) {
        if (elem > fstMax) {
            sndMax = fstMax;
            fstMax = elem;
        } else if (elem > sndMax) {
            sndMax = elem;
        }
    }

    return [fstMax, sndMax];
}

// TASK: Дан граф, является ли он бинарным деревом. Время: О(число вершин)
function isBinaryTree(graph) {}

// TASK: Является ли дерево - бинарным деревом поиска
function isBinarySearchTree(tree) {}

// TASK: слияние 2 / k отсортированных списков
function merge2(arr1, arr2) {}
function mergeK(arrOfArrs) {}

function median(v1, v2, v3) {
    if (v1 > v2) {
        if (v2 > v3) {
            return v2;
        } else if (v1 > v3) {
            return v3;
        } else {
            return v1;
        }
    } else {
        if (v1 > v3) {
            return v1;
        } else if (v2 > v3) {
            return v3;
        } else {
            return v2;
        }
    }
}

// TASK: Найти строку S' в строке T, которая является анаграмой S.
function findSubstring(T, S) {}

function maxSubstr(str) {
    let startIndexRes = 0;
    let lengthRes = 0;

    let startIndexCur = 0;
    let lengthCur = 0;

    let position = {};

    for (let i = 0; i < str.length; i++) {
        if (!position[str[i]] || startIndexCur > position[str[i]]) {
            position[str[i]] = i;
            lengthCur++;
            continue;
        }

        if (lengthCur > lengthRes) {
            lengthRes = lengthCur;
            startIndexRes = startIndexCur;
        }

        startIndexCur = position[str[i]] + 1;
        lengthCur = i - position[str[i]];
    }

    if (lengthCur > lengthRes) {
        lengthRes = lengthCur;
        startIndexRes = startIndexCur;
    }

    return s.slice(startIndexRes, startIndexRes + lengthRes);
}

const bannerList = [
    {w: 10, banner: {id: 1}},
    {w: 2, banner: {id: 2}},
    {w: 1, banner: {id: 3}}
];

function getBanner() {
    const random = Math.random();
    const sumWeight = bannerList.reduce((sum, item) => sum + item.w, 0);
    const index = bannerList
        .map(item => item.w / sumWeight)
        .reduce((prev, prob, i) => {
            prev.push(i === 0 ? prob : prev[i - 1] + prob);
            return prev;
        }, [])
        .findIndex(value => random < value);
    return bannerList[index].banner;
}

function sortTouristRoute(tickets) {
    const notFirstCities = new Set();
    const fromIndices = new Map();

    tickets.forEach((ticket, index) => {
        notFirstCities.add(ticket.to);
        fromIndices.set(ticket.from, index);
    });
    let cityIndex = tickets.findIndex(ticket => !notFirstCities.has(ticket.from));

    for (let i = 0; i < tickets.length; i++) {
        const ticket = tickets[cityIndex];
        const ticketSwap = tickets[i];
        tickets[i] = ticket;
        tickets[cityIndex] = ticketSwap;
        fromIndices.set(tickets[cityIndex].from, cityIndex);
        cityIndex = fromIndices.get(ticket.to);
    }
}

// TESTING

const tickets = [
    { from: '3', to: '4' },
    { from: '2', to: '3' },
    { from: '4', to: '5' },
    { from: '0', to: '1' },
    { from: '1', to: '2' },
    { from: '6', to: '7' },
    { from: '5', to: '6' },
];

sortTouristRoute(tickets);
console.log(tickets);