Interview task: Mountain Peak | JS

[@AzamatAbduvohidov99]

Thank you from Uzbekistan👍👍👍

[@xOceanSpirit]

Хорошие обучающие ролики с подробным разбором и визуализацией процесса выполнения алгоритма. Наверно лучшее, что я встречал. Многим другим как раз не хватает умения объяснить и показать решение.

[@frontendscience]

Благодарю! Приятно слышать! Рад что полезно!

[@sergeiosokin300]

Как всегда доходчиво и понятно, ещё и анимацией подкрепили, спасибо!

[@frontendscience]

Класс! Рад, что оценили - я действительно попыхтел над ней)

[@КарэнАкопьян]

Спасибо за задачу и подробное решение Сергей!

[@igormuryy5722]

Автолайк, бесконечно благодарен Вам!

[@frontendscience]

Авто-благодарность! :)

[@igormuryy5722]

@@frontendscience Ждем следующие видео!😉

[@denisoleksyuk5346]

Я как раз начал интересоваться и искать что-то по алгоритмам на жс, видео такие очень заходят)) Вот моё решение к стати, но ваше нравиться больше. ```js const fn = (arr) => { let start = 0; let middle = Math.floor(arr.length / 2); let end = arr.length - 1; while (arr[middle] < arr[middle - 1] || arr[middle] < arr[middle + 1]) { if (arr[middle - 1] > arr[middle]) { end = middle; middle = Math.floor((start + end) / 2); } else if ((arr[middle + 1] > arr[middle])) { start = middle; middle = Math.floor((start + end) / 2); } } return middle; };```

[@frontendscience]

Nice!

[@ДмитрийКолышницын-с2л]

Отличный полезный видос!!!!

[@frontendscience]

Благодарю за поддержку!

[@EvilYou]

Решил так: function peakIndexInMountainArray(arr) { let left = 0; let right = arr.length - 1; let center = Math.floor( (right - left) / 2) + left; while (left < right) { if (arr[center] < arr[center + 1]) { left = center + 1; } else { right = center; } center = Math.floor( (right - left) / 2) + left; } return center; }

[@ВайТай-и7ы]

function peak(arr) { let max = Math.max(...arr); return arr.findIndex((num) => num === max); }

[@frontendscience]

Благодарю за решение! Выглядит лаконично ) Только вот сложность линейная выходит.

[@ІльченкоАртем]

Спасибо Вам за крутые видео!!!!!!

[@frontendscience]

И Вам спасибо ☺️

[@stastikhomirov8075]

Добрый день! Спасибо за интересное видео. У меня есть вопрос: данная функция будет работать, если там четко идет повышение и снижение. А если представить, что там несколько раз идет снижение-повышение? Вроде - 5-6-10-13-11-10-14-15-12-10-7-6. Тогда функция вернется после первого же раза, как попадет на снижение и не будет проверять дальше, есть ли там еще повышения?

[@frontendscience]

Да есть такая задача. Там по условию может быть много пиков и надо найти самый высокий. Там уже совсем другой алгоритм нужно применять, этот работает быстро но только с одним пиком

[@stastikhomirov8075]

@@frontendscience спасибо за ответ! Получается, там нужно создать еще одну переменную, куда будет добавляться каждое большее, чем предыдущее число, и затем сравниваться со след числом, так, пока не пройдет весь массив, а затем, выдаст последний внесенный в переменную результат?

[@frontendscience]

Неееее ) если бы все было так просто..... Данный алгоритм бинарного поиска не подойдет для решения задачи с множеством пиков. Самый простой вариант - пройтись по всему массиву и считать пики (элементы где мы от возрастающего тренда переходим к убывающему). Запоминаем эти пики - а потом из них находим максимальный. Но есть и более оптимальные варианты решения. Возможно разберу такую задачу в видео в будущем.

[@stastikhomirov8075]

@@frontendscience ну да. Не зачем менять переменную постоянно, если можно все переходы с бОльшего на меньшее внести в массив и уже там найти самое большое число. Логично) Жду разбора такой задачи) Спасибо)

[@carthago_delenda_est]

function peak(arr) { const maxValue = Math.max(...arr); return arr.indexOf(maxValue); }

[@frontendscience]

Хорошее короткое решение, но работать будет в 2 раза медленнее, чем с бинарным поиском.

[@МаксимЛибер-ф2н]

@@frontendscience Скажите, а какой примерно длинны должен быть массив, чтобы было целесообразно применять бинарный поиск а не math.max. Я понимаю, что на собеседовании такой вопрос задают исключительно для проверки знаний, но все же

[@kawaikaino5277]

@@МаксимЛибер-ф2н Добавлю к вопросу. Есть ли смысл разбивать такие массивы, чтобы успешно применять к ним(или одному из них) Math.max и не терять скорость выполнения?

[@frontendscience]

Проверить очень легко - запустить пару тестов на jsbench.me/. Относительна разница значительная: 100 элементов: binary 8.2% faster 1000 элементов: binary 25,77% faster 10000 элементов: binary 78,07% faster 100000 элементов: binary 97,29% faster Ну а дальше это уже вопрос выбора. Если ты понимаешь что задержка в 1 секунду при расчете не сильно усложнит жизнь пользователю, и тебе приятнее видеть короткий и легко поддерживаемый код - то конечно стоит использовать его. Если объемы данных большие или тебе очень критично дать быстрый ответ - значит используешь бинарный поиск.

[@frontendscience]

Смысла нет - так как все равно прийдется пройтись по всем кускам и найти самый высокий элемент. При разбиении выйдет еще больше операций + памяти в 2 раза больше будет использовано.

[@ДмитрийКолышницын-с2л]

Хотелось бы разбора чего-то очень сложно и абстрактного, если это возможно...

[@frontendscience]

Сложное у нас есть: kzbin.info/www/bejne/hJK9ooapltiVjJo А что значит абстрактное?

[@ДмитрийКолышницын-с2л]

@@frontendscience ))) эх чтоб я знал...... Может применение генераторов в проектах или т.п

[@jorgenUA]

Серёга, расскажи, pls, как английский учить для разработчика - без этого никуда в Украине.

[@Denis-rh9jp]

let arr = [2,3,11,2,3,29,3]; let max = arr[0]; for(let i = 0;i

[@dmitry311212]

При решении рассуждал так: так как пик массива - это максимальное число, то элементы рядом с ним (справа и слева) будут меньше поэтому написал такую функцию: let peakIndexInMountainArray = function (arr) { // находим максимальное значение массива let peak = Math.max.apply(null, arr); // возвращаем индекс значения return arr.indexOf(peak); };

[@frontendscience]

Да решение правильное! И компактное. Но сложность тут будет линейная.

[@carved1883]

unction mountainPeak(array){ let left = 0; let right = array.length - 1 let mid; while(left array[mid]){ return right }else{ return left } } }

[@wisarty]

Дякую

[@serhii_jameson]

Кстати почему вы не предлагаете рекурсивный вариант решения? Там и с указателями не нужно возиться, только и передавай себе отслайсаный массив.

[@frontendscience]

наверное потому что этот вариант наиболее оптимален по сложности в отличие от рекурсивного

[@alexanderafonin1688]

Я же правильно понимаю, что у алгоритма есть изъян? Если у нас есть несколько пиков ([1,5,2,1,8,0]) - мы можем пропустить нужный, верно? Вроде бы об это не упомянули в видео..

[@frontendscience]

Изъяном это бы было если бы в условии задачи подразумевались несколько пиков. В условии этой задачи есть всего один пик в массиве. Задача с несколькими пиками уже будет решаться по другому - и выйдет с другой сложностью по времени.

[@talivel118]

Здравствуйте, у меня такой вопрос. Вообщем уже пару деньков прохожу ваши видео, но как то уже хочется осваивать чего-то новое, разные фреймворки, обязательно ли пересмотреть все видео, или же 10 штук пойдёт?

[@frontendscience]

Алгоритмы и фреймворки это вещи которые можно изучать параллельно. Не нужно откладывать.

[@talivel118]

@@frontendscience Понял, спасибо, буду всего понемножку)

[@frontendscience]

@@talivel118 Успехов! 👍

[@maxim7603]

так сделал const peakIndexInMountainArray = (arr) => { if(arr.length === 1) { return 0 } const isUp = (i) => { return i === 0 ? true : arr[i] > arr[i-1] } if(!isUp(1)) { return 0 } let start = 0 let end = arr.length - 1 let max = arr[0] let maxIdx = 0 while(end >= start) { let i = Math.floor((end + start) / 2) let num = arr[i] if(isUp(i)) { start = i + 1 } else { end = i - 1 } if(num > max) { max = num maxIdx = i } } return maxIdx }

[@ericbracket516]

Как уже указали в комментариях, есть короткое решение через Math.max(). Тогда какой смысл в этом длинном решении как в видео?

[@frontendscience]

Потому что на собеседованиях как раз спросят вариант с бинарным поиском - оптимальный, который в 2 раза быстрее работает чем Math.max().

[@eghishemanukyan3021]

good

[@satanist70]

Пока только учусь, наверно с точки зрения сложности алгоритна плохо, но вот краткое решение вроде как: let arr = [1,2,3,4,3,2,1]; let arrTwo = [11,13,14,15,6,4,2]; let arrThree = [10,9,8,7,6]; let getMaxMountain = (arr) => { for(let i = 0; i < arr.length; i++) { if(arr[i] > arr[i + 1] && arr[i] > arr[i - 1]) { return i; } } return 0; }; console.log(getMaxMountain(arr)); // 3 console.log(getMaxMountain(arrTwo)); // 3 console.log(getMaxMountain(arrThree)); // 0

[@frontendscience]

Да отлично! С задачей справился. Сложность тут вышла линейная.

[@satanist70]

@@frontendscience Спасибо большое, очень приятно )

[@aboba86468]

@@satanist70 Решение неверное, если массив будет монотонно возрастающим: let arr = [11,13,14,15]; // expected: 3; actual: 0

[@awenn2015]

@@frontendscience какая разница вообще какая там сложность ?

[@frontendscience]

@@awenn2015 большая разница! Когда приходится оперировать огромными объемами данных, очень хорошо чувствуется разница по времени выполнения скрипта!

[@akudryashov85]

function findMountainPick(arr) { const neighbour = (index, direction) => arr[index + direction] ?? arr[index] + direction let start = 0 let end = arr.length - 1 while (start neighbour(mid, +1)) { return mid } if (neighbour(mid, -1) < arr[mid]) { start = mid + 1 continue } if (arr[mid] > neighbour(mid, +1)) { end = mid - 1 } } }

[@frontendscience]

Классно. -благодарю за решение!

[@kozubskyi]

let piima = arr => arr.indexOf(Math.max(…arr)) ⬆️ так вроде намного проще

[@frontendscience]

Проще в плане чего? Считал сложность своего алгоритма?

[@frontendscience]

@@ТестТест-и4ж ты мне не хами, а почитай что такое BIG O. Еще одно сообщение в таком тоне и ты полетишь в бан!

[@xOceanSpirit]

@@ТестТест-и4ж суть видео была не в том как проще для ленивой жопы решить задачу, а в нахождении оптимального алгоритма.

[@veloster9616]

Привет, я не особо хорошо разбираюсь в программировании на JS, но почему нельзя найти сначала максимум из массива и потом вернуть индекс максимума?

[@frontendscience]

Сложность данного алгоритма решения будет линейная. Сложность решения из видео - логарфмическая. Рекомендую посмотреть: kzbin.info/www/bejne/fKaXc62Hg7Njh9U

[@veloster9616]

@@frontendscience да, я только посмотрел Ваш ролик и Вы там говорили, что, если данных немного, то смысл от алгоритмизации и оптимизации)

[@frontendscience]

leetcode это платформа как раз для тренировки знаний алгоритмов. Там все задачи подразумевают большие объемы данных - поэтому и решения должны быть наиболее оптимальными

[@Denis-rh9jp]

а просто по дефолту искать самое большое число нельзя? оно же и будет пиком

[@Vladislav-K]

Этот вопрос могут задать junior или middle разработчику?

[@frontendscience]

Это считается easy задача на leetcode. Но в наших краях, где тех собеседования не построены только на алгоритмах, думаю такое могут спросить на middle+/senior. Я имею ввиду решение именно через бинарный поиск.

[@ВероникаСампетова-ц8ж]

var peakIndexInMountainArray = function(arr) { let left = 0; let right = arr.length; while (left < right) { let middle = Math.floor((left + right) / 2); let max = arr[middle] if((max > arr[middle - 1] || arr[middle - 1] === undefined) && (max > arr[middle + 1] || arr[middle + 1] === undefined)) { return middle; } else if(max < arr[middle - 1]) { right = middle; max = arr[right]; continue; } else if(max < arr[middle + 1]) { left = middle max = arr[left]; continue; } left++ } };

[@frontendscience]

Класс! Отличное решение! Благодарю!

[@melancholyhill3962]

Зачем max = arr[right]; и max = arr[left];? думаю это будет лишним. А так то отличный пример!

[@РомаВарнаков]

это Java Script?

[@frontendscience]

Да.

[@Denis-rh9jp]

макс это пик

[@Sleep88Walker]

Думал что цифры могут повторяться потому код получился сложнее... let mount = [1, 2, 3, 3, 4, 6, 7, 8, 9, 9, 12, 21, 21, 23, 23, 25, 24, 23, 21, 21, 19, 18, 15, 14, 14, 14, 12, 11, 8, 7, 6, 4, 3, 2, 0]; let superMount = [1,544,533,533,431,429,428,427,426,425,424,423,422,421,420,399,398,397,396,350,100,99,98,97,96,95,94,93,9,8,7,6,5,4,3,2,1]; let errorMount = [1,544,544,545,544,548,500,501,502,425,424,423,422,421,420,399,398,397,396,350,100,99,98,97,96,95,94,93,9,8,7,6,5,4,3,2,1]; function binarySearch(arr) { let watchdog=0; let a = 0; let b = arr.length - 1; let current; let upDown; do { watchdog++; current = Math.floor((a + b) / 2); upDown = upOrDown(current, arr); if (upDown===666) return 'error'; console.log(`a=${a}, b=${b}`); if (upDown > 0) a = current; if (upDown < 0) b = current; }while (upDown != 0 && watchdog arr[i]) rIsHigher = true; else if (arr[i + rShift] < arr[i]) rIsHigher = false; else rShift++; if (arr[i - lShift] > arr[i]) lIsHigher = true; else if (arr[i - lShift] < arr[i]) lIsHigher = false; else lShift++; if (lShift>i || (rShift+i+1)>arr.length) { console.log('Error') return -1; } if (!(lIsHigher === null || rIsHigher === null)) { if (!lIsHigher && !rIsHigher) { console.log(`We are on top!`); return 0; } if (lIsHigher && !rIsHigher) { console.log(`We are going down`); return -1; } if (lIsHigher === false && rIsHigher === true) { console.log(`We are climbing up`); return 1; } if (lIsHigher && rIsHigher) console.log(`We are in pit! Impossible!!`); return 666; } } while (watchdog

[@frontendscience]

Благодарю за решение. Но что-то где то не так работает. Проверял на примере [0,2,1,0]. Вместо индекса 1 функция вернула 2

[@Sleep88Walker]

@@frontendscience Да, поторопился, на работе лежит более стабильная и более элегантная))

[@Sleep88Walker]

@@frontendscienceа...я возвращаю не индекс а само значение...переделать не трудно

[@frontendscience]

@@Sleep88Walker а, тогда понятно! 👍

[@uchi_v]

const peakOfTheMount = (arr) => { let count = 0; let result = 0; arr.forEach((item, index) => { count = Math.max(item, count); if (count == item) result = index; }) return result; }

[@frontendscience]

Благодарю за решение! Компактно )

[@yurii8710]

function findIndex(arr){ let temp = arr[0] let index for(let i = 0; i < arr.length; i++){ if(arr[i] >= temp){ temp = arr[i] index = i } else { break } } return index }

[@frontendscience]

Благодарю за решение!

[@Sleep88Walker]

Допилил вроде до ума вариант с возможным дублированием элементов... P.S второй раз в жизни использовал рекурсию. let m1 = [1, 2, 3, 3, 4, 6, 7, 8, 9, 9, 12, 21, 21, 23, 23, 25, 24, 23, 21, 21, 19, 18, 15, 14, 14, 14, 12, 11, 8, 7, 6, 4, 3, 2, 0]; let m2 = []; let m3 = []; let m4 = []; let m5 = [0, 1, 2]; let m6 = [2, 1, 0]; let m7 = [0, 1]; let m8 = [1, 0]; let m9 = [1, 1]; let m10 = [5]; let m11 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]; let m12 = []; let mErr = [1, 544, 544, 545, 544, 548, 500, 501, 502, 425, //Special array with many peaks 424, 423, 422, 421, 420, 399, 398, 397, 396, 350, 100, 99, 98, 97, 96, 95, 94, 93, 9, 8, 7, 6, 5, 4, 3, 2, 1]; let mounts = [m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12, mErr]; //seeding large arrays for (let i = 0; i < 1000; i++) m2[i] = i; for (let i = 0; i < 1000; i++) m3[i] = 2000 - i; for (let i = 0; i < 10000; i++) m4[i] = i + 10000; for (let i = 10000; i < 30000; i++) m4[i] = 30000 - i; function binarySearch(arr) { if (!Array.isArray(arr)) return "Array is required"; if (arr.length < 1) return "Array can't be empty"; console.log(` Let's find peak of array with ${arr.length} elements!`); let watchdog = 0; let a = 0; let b = arr.length - 1; let c; let lh; let rh; do { watchdog++; c = Math.floor((a + b) / 2); lh = lHigher(c, arr); rh = rHigher(c, arr); console.log(`a=[${a}]${arr[a]} ${lh ? "\\" : "/"} c=[${c}]${arr[c]} ${rh ? "/" : "\\"} b=[${b}]${arr[b]}`); if (lh && rh) return "We are in pit. Impossible!" else if (!lh && !rh) return c; else if (lh) b = c; else a = c + 1; } while (watchdog < 100) return c; } function rHigher(i, arr) { if (arr.length === i + 1) return false; //За границей не может быть числа больше... if (arr[i + 1] > arr[i]) return true; else if (arr[i + 1] < arr[i]) return false; else return rHigher(i + 1, arr);//ееее рекурсия } function lHigher(i, arr) { if (i === 0) return false; if (arr[i - 1] > arr[i]) return true; else if (arr[i - 1] < arr[i]) return false; else return lHigher(i - 1, arr); } mounts.forEach(m => { let res = binarySearch(m); console.log(`=====Result is [${res}]${m[res]!==undefined?m[res]:''}=====`); });

[@das8434]

Решение, я пока что не смотрел. но вот что у меня получилось: let arr1 = [1, 2, 3, 4, 3, 2, 1]; let arr2 = [11, 13, 14, 15, 6, 4, 2]; let arr3 = [10, 9, 8, 7, 6]; let peakIndexInMountainArray = function(arr) { for(let i = 0; i < arr.length; i++) { let curr = arr[i]; if(arr[0] > arr[1]) { return arr.indexOf(10); } else { if(arr[1] > arr[2]) { return arr.indexOf(9) } else { if(arr[2] > arr[3]) { return arr.indexOf(8); } else { if(arr[3] > arr[4]) { return arr.indexOf(7) } else { if(arr[4] > arr[5]) { return arr.indexOf(6); } else { if(arr[5] > arr[6]) { return arr.indexOf(4) } else { if(arr[6] > arr[7]) { return arr.indexOf(2) } } } } } } } } }; console.log(peakIndexInMountainArray(arr3)); Единственным недостатком, как по мне является то что мне нужно каждый раз менять числа в indexOf

[@Denis-rh9jp]

а просто по дефолту искать самое большое число нельзя? оно же и будет пиком

[@andreyko_o9014]

можно,но смысл в том,чтобы решить оптимально а не просто решить