За время работы в Google я провёл более двух сотен интервью. И главное, что я вынес из этой работы — проводить качественные собеседования очень непросто. Все дело в сигналах, которые мы посылаем и получаем. И у интервьюера, и у самого кандидата есть меньше часа, чтобы выложиться на полную. Порой, по разным причинам, мы получаем друг от друга ложные или неточные сигналы. Такова уж человеческая природа.
С годами я выработал вопрос по кодингу, который мне самому очень нравится. Это до жути простой и в то же время заковыристый вопрос. Решение занимает не более 30 строк кода, но зато даёт мне все нужные сигналы для вынесения верной оценки кандидату. Кроме того, мой вопрос отлично масштабируется и подходит как стажёрам, так и опытным инженерам. Здесь я не стремлюсь доказать, что мой вопрос лучше какого-то другого. Я лишь хочу объяснить, как он помогает мне как интервьюеру и на что я обращаю внимание на собеседовании по программированию.
В этой статье будут вещи, с которыми вы можете не согласиться. Это нормально. Это просто моё мнение, а так как я уже вышел на пенсию, то больше не представляю опасности ни для интервьюеров, ни для инженеров Google при принятии решений о найме! ;-)
Пара слов обо мне
Когда я был начинающим инженером, я регулярно читал сайт joelonsoftware.com. Одной из статей, которая оставила у меня неизгладимое впечатление, был гайд по проведению собеседований. Самое важное решение, которое ты можешь принять менее чем за час, — нанимать или не нанимать, исходя из того, умён ли человек и может ли он довести дело до конца. Позволяет ли собеседование убедиться и в том, и в другом?
Лично я пришел в кодинг из электроники. Записался на курсы по структурам данных и даже написал программу решения лабиринта для нашего выпускного проекта Micromouse. У меня не было формального образования в компьютерной сфере, и хотя программа работала отлично (заставить электроаппаратуру работать было на порядок сложнее!), я не смог бы назвать алгоритм, который я использовал. Поэтому я предпочитаю держаться подальше от вопросов, которые проверяют, проходил ли кандидат конкретные курсы по CS. Это не моя самая сильная сторона.
Обычно я провожу собеседования с инженерами-программистами общего профиля, фронтенд-инженерами или занимаюсь оценкой качества кода для руководителей и менеджеров.
Проводя собеседование по кодингу, я стремлюсь определить, насколько человек соответствует требованиям моей команды инженеров в решении ежедневных задач по тестированию, программированию и отладке. То, как кандидат подходит к проблеме и решает её, важнее, чем его диплом.
Внимание, вопрос!
У нас есть массив, отсортированный по возрастанию:
a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
То есть:
f(a, 12) = 12
f(a, 13) = 12Во-первых, отмечу, что этот вопрос очень прост для понимания. Конечно, при условии, что вы кое-что смыслите в программировании. Не нужно быть семи пядей во лбу, доктором математических наук, чтобы осмыслить его – поэтому вопрос достаточно честный ко всем кандидатам. Кроме того, его не требуется дополнительно объяснять – а это занимало бы драгоценные минуты нашего собеседования.
Массив, фигурирующий в задаче, составлен нарочно таким образом, чтобы не включать 0 и отрицательные числа – это не добавило бы к решению задачи ровным счетом ничего. Элементов в массиве 11, что дает нам пространство индексов от 0 до 10. 10 легко делится на 2, поэтому среднюю точку можно определить без проблем – это число 12. Оно находится ровно посередине списка – это наш первый тест-кейс. А следующий пример, число 13, требует провести поиск уже в другой половине элементов. Все эти маленькие тонкости будут направлять интервью в нужное русло.
Первым делом я предлагаю кандидатам придумать собственные тест-кейсы, наподобие тех, что я озвучил выше. На первый взгляд может показаться, что этот вопрос неуместен на собеседовании по программированию, однако на деле он позволяет понять, насколько хорошо кандидат знаком с TDD и граничными условиями. Как правило, после небольших подсказок, кандидат приходит к следующему списку:
f(a, 12) = 12 // Найдено заданное число
f(a, 13) = 12 // Найдено меньшее число
f(a, 2) = -1 // Число слишком мало и выходит за границы массива
f(a, 22) = 21 // Число слишком велико и выходит за границы массива
f(a, 3) = 3 // Левая граница массива
f(a, 21) = 21 // Правая граница массива
f([], x) = -1 // Массив пуст
f(null, x) = -1 // Неверные аргументыВерьте или нет, большинство разработчиков не в состоянии составить этот список до конца. Кто-то забывает о границах массива. Кто-то игнорирует слишком большие или малые значения x. Некоторым кандидатам не приходит в голову проверить вводимые данные на правильность. Отдельные уникумы и вовсе занимаются брутфорсом: f(a, x), где x = Int.MIN до Int.MAX.
Еще кое-кто не понимает, чего я от них добиваюсь таким вопросом.
А на деле из каждой реакции, каждого «сигнала» я получаю массу дополнительной информации о кандидате.
Затем мы переходим к обсуждению алгоритма. Да, можно написать что-то вроде цикла for для O(n). Если я собеседую молодого и зеленого стажера, это вполне приемлемый ответ. Одно время я занимался собеседованием студентов колледжей, и могу вам сказать: хорошо составленный цикл и умение отладить его для всех тест-кейсов – это гарантированный оффер.
Что касается более опытных кандидатов – от них я хотел бы видеть реализацию двоичного поиска: O(log n). Сначала мы обсуждаем алгоритм, я убеждаюсь, что человек мыслит в правильном направлении, и лишь затем прошу написать код. Если всё идет по плану, можно запустить готовый вариант и произвести отладку для всех восьми тест-кейсов. Я в этот момент отхожу в сторонку и наблюдаю.
Добро пожаловать обратно
Итак, долго ли вы писали код? Процесс занял полчаса? Или даже целый час? А алгоритм заработал как надо с первого раза? Вычисление средней точки корректно работает для элементов из обеих половин? Вы прибегли к итеративному решению? А учли ли возможность попасть в бесконечный цикл? Или же вы выбрали рекурсивный подход? А вспомогательный метод создали? Как вы находите меньшее значение? Проходит ли ваш код все 8 тестов, или пришлось добавить специальные if/else для ряда случаев? Не переживайте. В первый раз, когда я решал эту задачу, я страдал не меньше вашего.
Омлетный тест
Много лет назад я прочитал книгу «Становление шеф-повара». В ней рассказывалось о трёх путях превращения человека в мастера-шефа. Один из них заключался в сдаче экзамена на звание сертифицированного шефа. Другой подразумевал, что можно, подобно Майклу Саймону, быть опытным поваром, а затем построить ресторанную империю, обеспеченную пачкой ТВ-шоу. А еще есть путь Томаса Келлера. Он начинал посудомойщиком, затем обучался у французских мастеров-шефов, и в итоге смог стать одним из лучших поваров в мире.
Я всегда считал, что между поварами и программистами есть сходство. У опытного шеф-повара есть характерные признаки. То, как они готовят, жарят-парят-сервируют. То, как они держат нож и режут овощи. У них крайне мало лишних движений, во всём присутствует плавность, а в результате, естественно, получается отличное блюдо.
В фильме The Hundred-Foot Journey (примечание переводчика: в России известен под названием «Пряности и страсти») главного героя, Хасана Кадама, попросили приготовить омлет. С одного укуса мадам Мэллори (её играла Хелен Миррен) понять, стоит ли ему работать у нее на кухне.
Я думаю, это справедливо и для программистов. Мой вопрос на собеседовании – это тот же самый «омлетный» тест. Я ищу признаки опытного программиста в том, как человек подходит к решению популярной, широко известной проблемы.
Решение
На самом деле, возможных решений этой задачки масса. Вот, к примеру, самый примитивный итеративный подход:
function f(a, x) {
if (a == null || a.length == 0) return -1;
var answer = -1;
var low = 0;
var high = a.length — 1;
while(low <= high) {
var mid = Math.floor((low + high) / 2);
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid — 1;
}
}
return answer;
}Что касается двоичного поиска – он выглядит примерно как while(low <= high), делим на две части, пока не найдем искомое число.
Оператор сравнения «меньше или равно» – это важный момент, поскольку в конечном итоге массив чисел свернется до размера 1, и содержимое цикла нужно будет исполнить. Инкрементировать/декрементировать среднюю точку тоже важно, поскольку иначе есть риск попасть в бесконечный цикл.
Найти же следующее наименьшее число – чуть более сложная задача. Грамотным решением будет объединить линейный поиск с двоичным, инициализировать answer как -1, затем обновлять значение переменной всякий раз, когда a[mid] будет меньше, чем x. Если x не удастся найти, ответом всегда будет наименьшее обнаруженное значение.
Еще более опытные специалисты могут добавить дополнительные проверки для проверки граничных значений x.
// Например, вот так:
if (a == null || a.length == 0) return -1; // f(null, x), f([], x)
if (x < a[0]) return -1; // f(a, 2)
if (x == a[0]) return a[0]; // f(a, 3)
if (x >= a[a.length — 1]) return a[a.length — 1]; // f(a, 21), f(a, 22)Зачем использовать двоичный поиск
Двоичный поиск относится к одной из самых сложных «простых» проблем программирования. Алгоритм выглядит тривиально, но реализовать его — сущий ад. Джон Бентли, бывший профессор CMU, в своей книге Programming Pearls написал, что только 10% профессиональных программистов способны правильно его реализовать, в том числе и аспиранты.
«Я был поражен: учитывая достаточное количество времени, только около десяти процентов профессиональных программистов смогли правильно составить эту небольшую программу».
В своей книге он написал, что специалистам потребовалось 16 лет, чтобы написать алгоритм без ошибок!
« ... в разделе 6.2.1 книги «Сортировка и поиск», Кнут отмечает, что, хотя первая реализация двоичного поиска и была опубликована в 1946 г., первый опубликованный вариант без ошибок появился только в 1962 году».
Джон Бентли, «Жемчужины программирования» (издание первое)
Но погодите-ка, в приведенном выше решении все же есть одна небольшая ошибка. Сумеете её найти?
В 2006 году Джошуа Блох, главный Java-архитектор Google, автор книги «Эффективный Java» и бывший аспирант Бентли, раскрыл, что в течение девяти лет Java содержала скрытый баг! Вычисление средней точки приводило к выходу за границы массива при работе на больших объемах данных!
var mid = Math.floor(low + high) / 2); // плохо
var mid = low + Math.floor((high — low) / 2); // хорошоРеализовать элементарный двоичный поиск на удивление сложно. Добавление изюминки в виде следующего наименьшего числа только усиливает сложность. В случае с поиском числа 13, когда ты отлаживаешь два или три уровня глубины двоичного поиска, не так-то просто удержать в голове младшие, старшие, средние значения и стек.
Рабочее решение должно состоять примерно из 30-40 строк кода. Это достаточно немного для часового интервью, при этом можно без труда вычитать код и сделать пометки на полях. Такой вопрос охватывает весь жизненный цикл работы программиста — от тест-кейсов до написания кода и его отладки. В целом собеседование достаточно «простое», чтобы комиссия по найму могла понять уровень кандидата и оценить мою рекомендацию.
Нанимать или не нанимать?
Идеального способа оценить кандидата не существует. Я наверняка был слишком суров или слишком мягок к нескольким кандидатам по итогам решения моего вопроса. Я ведь тоже человек.
Как и в приведенной выше аналогии с поваром, я ищу в человеке признаки важнейших навыков, сродни умению повара резать овощи или стоять у плиты. Как минимум, компилятор не должен ругаться на примитивные ошибки.
Вот список самых простых сигналов, которые я жду от кандидата:
Адекватные имена переменных и функций.
Find_X_Or_Next_Smallest_Impl_Factory_Builder_Singleton(...)однозначно не проходит.Скобки, обрамляющие функции, циклы и условия, закрыты, а весь нужный код помещен внутри.
Кандидат в курсе, что индексы массива начинаются с 0, а заканчиваются на количестве элементов массива — 1.
Переменные инициализируются с корректными начальными значениями и находятся в правильных областях видимости.
Кандидат использует == в условиях, а не просто =. Скобки открываются и закрываются там, где надо.
В коде правильно сделаны отступы и/или точки с запятой
Код читаемый и ясный. Как бы вы написали: if (a[mid] < x) или if (x > a[mid])? Один из вариантов читается намного проще.
И еще парочка сигналов другого рода:
Полнота в определении всех тест-кейсов.
Общее понимание процесса: от постановки задачи до тестирования и реализации.
Умение пользоваться доской для визуализации двоичного поиска, дебага и объяснения работы своего кода.
Общие коммуникационные навыки.
Умение не зацикливаться на ошибках и быстро двигаться вперед.
Умение писать простой код без спагетти из тысячи if/else.
Мои ожидания для каждого уровня кандидата
От сильного стажёра или инженера уровня L3 я ожидаю, что он сможет справиться с двоичным поиском за час с небольшой помощью, особенно с тестовыми случаями и отладкой, при этом делая уверенные шаги на этом пути с минимальными синтаксическими ошибками.
Что касается инженеров среднего уровня L4, то они должны быть в состоянии определить большинство тестовых случаев, реализовать рабочее решение двоичного поиска с незначительными ошибками и отладить его с минимальной помощью. Сильные кандидаты закончат с достаточным количеством времени для второго вопроса.
Что касается старшего инженера L5, то он должен быть в состоянии провести собеседование до конца и закончить его с достаточным количеством оставшегося времени для вопроса о проектировании систем. Скорее всего, такие кандидаты напишут предварительные условия и будут знать об ошибке переполнения средней точки. Могут быть мелкие недочёты/ошибки, но прогресс должен быть быстрым.
По сути, я всегда оцениваю, нанял бы я этого человека для работы в своей команде или нет, и на кого из членов команды он/она больше всего похож? Свидетельствует ли их код и поведение о том, что они умны и могут доводить дело до конца? Лучшее, что я могу прочитать или написать в пакете документов при приёме на работу, — это то, что собеседование было похоже на дискуссию с коллегой-инженером из Google.
Послесловие
Благодарю вас за то, что вы дошли до этого раздела статьи. Надеюсь, она показалась вам занимательной и познавательной. Моя цель — не похвастаться своим потрясающим вопросом на собеседовании, потому что, честно говоря, он до безобразия прост, а подчеркнуть, что для принятия решения вовсе не обязательно ставить суперсложные задачи. Вместо того чтобы сосредотачиваться на том, знают ли кандидаты то же самое, что и вы, посмотрите со стороны не только на то, какой код они пишут, но и на то, как они его пишут. Стиль и темп, в котором они работают и дебажат, — это сигналы, важные признаки мастерства. Есть ли в вашем вопросе на собеседовании по кодингу тест-кейсы? А если бы были, собеседования стали бы более информативными? Можно ли получить те же сигналы с помощью более простых вопросов? Комиссия по найму была бы очень признательна за исследование в данном направлении!
Насколько мне известно, один из моих старых товарищей по команде до сих пор использует этот вопрос. Он любит его за простоту и широту охвата, а также за точность его «срабатывания» при составлении итоговой рекомендации.
Благодарности
Я сам узнал об этом вопросе от коллеги из Google. К сожалению, за давностью лет я уже не помню его имя. В любом случае – спасибо тебе!
Комментарии (260)
zlat_zlat
08.12.2023 03:19+64Наверное, я туповат, но формулировка "ближайшее наименьшее число" не очень ясна. Может, стоило написать "ближайшее число, которое меньше или равно заданному"? По крайней мере, судя по тест-кейсам, предполагается именно это. Эх, не быть мне L5, "некоторые просто не понимают, чего я от них добиваюсь" )
Akina
08.12.2023 03:19+11формулировка "ближайшее наименьшее число" не очень ясна.
Она вообще какая-то противоречивая. Т.к. оба определения - и "ближайшее", и "наименьшее",- по тексту совершенно равноправны. Хотя по смыслу нужно наименьшее из ближайших. При обратном приоритете вообще ничего не получится - наименьшее в это массиве всегда первое, вне зависимости от чего-либо (при условии, что массив соответствует условию).
Я бы, наверное, сказал "наибольшее число, не превышающее заданное".
saboteur_kiev
08.12.2023 03:19Т.к. оба определения - и "ближайшее", и "наименьшее",- по тексту совершенно равноправны. Хотя по смыслу нужно наименьшее из ближайших
Так вроде приоритет правильно указан - сперва ближайшее, потом среди ближайших наименьшее, если есть равноправно удаленные ближайшие.
Akina
08.12.2023 03:19+4Так вроде приоритет правильно указан - сперва ближайшее, потом среди ближайших наименьшее, если есть равноправно удаленные ближайшие.
По правилам русского языка - всё с точностью до наоборот. Если считать определения неоднородными, то первое относится к комбинации второго определения и существительного. И получается "ближайшее из наименьших". А поскольку в сортированном [по возрастанию] массиве "наименьшее число" - это без вариантов первое число массива, то дополнительное "ближайшее" вообще лишено смысла, ибо ему приходится выбирать гарантированно из одного варианта. Ну или из ничего, если массив пуст.
Эта нелогичность и заставляет считать определения однородными.
В случае же неоднородных определений должно быть написано наоборот - "наименьшее ближайшее число". Тогда всё ровно - ближайших либо одно, либо два, и из них наименьшее.
Впрочем, по смыслу эти определения и правда неоднородны, ибо рассматривают разные свойства числа - "ближайшее" рассматривает местоположение, а "наименьшее" - значение.
saboteur_kiev
08.12.2023 03:19ну вот для числа 13, ближайшее наименьшее будет 12, а не 14.
А для числа 8, ближайшее наименьшее будет 9 (а не 6)zlat_zlat
08.12.2023 03:19+2Я по-прежнему не понимаю, почему для 2 ближайшее наименьшее найдено не будет, а для 22 - пожалуйста. В остальном вы правы, моя переформулировка не является верной.
d_ilyich
08.12.2023 03:19+1Нужно найти число, которое
а) меньше или равно входному
И
б) содержится в массивеЕсли входное число (22) превышает максимальный элемент (21), то очевидно, что максимальный элемент и будет ответом.
Если входное число (2) меньше минимального элемента (3), то очевидно, что массив не содержит искомого числа, значит ответ == -1Akina
08.12.2023 03:19+11Нужно найти число, которое
а) меньше или равно входному
Это откуда такое? Читаем задание:
которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
Ткните мне пальцем в требование, чтобы результат не превышал заданное число... я лично такого требования не нахожу. А потому кейс
f(a, 2) = -1 // Число слишком мало и выходит за границы массивалично мне кажется не соответствующим исходному заданию. Для переданного числа 2 ближайшее, и оно же наименьшее, одно - это число 3, первый элемент массива. И ошибки - как-то не видно. Так что откуда -1 в ответе - ну совсем непонятно.
Впрочем, это вполне обычное состояние, когда по мере решения задача начинает обрастать кучей дополнительных и не озвученных в исходном задании условий. А уж для заданий программисту, особенно поставленных в рабочем порядке, это вообще скорее норма, чем исключение.
d_ilyich
08.12.2023 03:19Ткните мне пальцем в требование, чтобы результат не превышал заданное число... я лично такого требования не нахожу.
Я так понял русскоязычную формулировку, а дальнейший текст это подтвердил. Оригинальная (англоязычная) формулировка мне нравится меньше, но примеры всё же позволяют [мне] догадаться. Хотя, да, я бы всё равно уточнил.
Возможно, формулировка специально дана в таком виде, чтобы посмотреть на реакцию кандидата.
saboteur_kiev
08.12.2023 03:19+1Не прошли собеседование =)
Ближайшее, а не "меньшее или равное".
Из ближайших - меньшее, если ближайших несколько на равном удалении.Не знаю, лично для меня формулировка совершенно очевидна и даже не вижу возможности двумысленного толкования
d_ilyich
08.12.2023 03:19+8В оригинале
Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.
И в моём восприятии это даже хуже, чем "ближайшее наименьшее число"
AcckiyGerman
08.12.2023 03:19+3Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.
я бы написал
return x, x - 1, в задании ведь нигде не сказано, что число должно браться изa. Потом бы мне не дали оффер, и я написал бы статью о интервьерах, которым не нравится, что их ловят на неточных заданиях )))
ciuafm
08.12.2023 03:19+2А почему вы взяли целое? Нигде ведь не указано....
ZirakZigil
08.12.2023 03:19Потому что для вещественных (можно и комплексные докинуть, не жалко) чисел не существует next. Так что берём такие, для которых это понятие имеет смысл.
Tsimur_S
08.12.2023 03:19+3Потому что нормальная формулировка - next smaller element. А тут просто вообще от балды написано.
Ivan22
08.12.2023 03:19а почему next а не previous???
V1RuS
08.12.2023 03:19+1наверное потому, что next smallest означает previous (или должно означать по мнению автора текста; я не настолько хорошо знаю английский)
faiwer
08.12.2023 03:19+1Так слишком понятно. Кандидат не запутается. Но судя по тестам OP хотел: the closest equal or smaller number.
saboteur_kiev
08.12.2023 03:19+2просто ваш английский видимо слишком запутан ассоциацией что next это всегда следующий. А в оригинале это просто соседний, неважно в какую сторону. Girl next door, это не обязательно она живет справа.
faiwer
08.12.2023 03:19ИМХО, это кривая формулировка. Next (в смысле closest) подразумевает что искомый элемент в массиве есть, у него есть конкретная позиция, и надо взять ближайший к этой позиции. А учитывая что это не так (элемента в массиве нет), то получается какая-то ерунда.
cdscds
08.12.2023 03:19Как по мне, в задании указано: "Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки. " - функция должна возвращать два числа: "Х" и "ближайшее наименьшее число" или "-1" в случае ошибки. Явно же не указано, что возврат подразумевает одно из чисел.
То естьf(a, 12) = 12, 10
k4ir05
08.12.2023 03:19+1Явно же не указано, что возврат подразумевает одно из чисел.
Так там же перечисление с "или". Откуда вы взяли "и"?
Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.
x, наименьшее соседнее число или -1.
Andy_U
08.12.2023 03:19x, наименьшее соседнее число или -1.
Тогда функция, если X is not None, возвращающая X, иначе если существет следующее наименьшее соседнее число, то его, иначе -1, это решение?
Ну, кривая же формулировка. Только по test-caze'ам и восстанавливать правильную.
Ionenice
08.12.2023 03:19+1Так там ещё
У нас есть массив, отсортированный по возрастанию
a = […]
напишите f(a, x)Поэтому мы пошлём null
f(null, x) = -1 // Неверные аргументы
А можно туда и колбэк послать? Не говоря ещё и про сортировку
rinac
08.12.2023 03:19+36Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
Изи
f(a,x) = x
В следующий раз не ленитесь.
PVoLan
08.12.2023 03:19+9Разворачивая вашу мысль для тех, кто не понял:
В задании вообще ничего не сказано о том, что возвращаемый результат функции должен быть элементом массива. Кое-как об этом можно догадаться по тестовым примерам, но, мягко говоря, с трудом.
И, например, совершенно не очевидно что f(a,2)=-1 - на первый взгляд f(a,2)=2 вполне валидно. Из условия задачи вообще не следует, что х за пределами массива является ошибкой.
dark_gf
08.12.2023 03:19-1Абсолютно верно, а вообще нельзя получить верное решения задавая не верный вопрос.
PS: я бы сказал задающему такую задачу что что к Вас ошибка в примерах и пускай сам думает в чем трабла.
Pshir
08.12.2023 03:19К сожалению, в реальности вы в неравных условиях. Задающий задачу уже работает в Гугл, получает огромную зарплату и имеет ещё более огромное ЧСВ, не умея корректно формулировать элементарную задачу. А получение вами работы зависит от абсолютно субъективного мнения этого самого задающего о вас.
dark_gf
08.12.2023 03:19Тут как посмотреть, не только компания выбирает работника, но и работник выбирает где ему работать.
Ну и в больших компаниях заведено правило фидбека на интервьюера даже если ты не прошёл.
Dolios
08.12.2023 03:19не умея корректно формулировать элементарную задачу
Почему вы решили, что не умеет, а не делает это специально? В обычной ситуации задачи тоже часто недоформулированы и содержат двусмысленные формулировки. И как раз смотрят, в том числе, на то, как человек себя поведет - добъётся ясности или побежит программировать как понял, выдав не то, что нужно, в итоге. Если программист на интервью получил задачу, ничего не спросил и пошёл писать код, это жирнейший минус и, скорее всего, проваленное интервью.
Pshir
08.12.2023 03:19В статье именно так и произошло. Автор криво-косо что-то написал, назвав это задачей. Потом ничего не уточнил и побежал писать код. Получается, что автор статьи провалил интервью и как интервьюер, и как соискатель?
Akina
08.12.2023 03:19+14f(a, 2) = -1 // Число слишком мало и выходит за границы массиваf(a, 22) = 21 // Число слишком велико и выходит за границы массиваf(a, 3) = 3 // Левая граница массиваf(a, 21) = 21 // Правая граница массиваА при чём тут вообще границы массива? Предметная область не определена. Формулировка задания ни полслова о границах не говорит. Получается, что либо задание не соответствует задаче (иначе откуда такая забота о границах?), либо финально от кандидата требуют не "реши задачу". а "угадай, что я задумал".
f([], x) = -1 // Массив пустНу вообще-то у нас есть начальное условие "У нас есть массив, отсортированный по возрастанию". Кто бы мне рассказал, как может быть сортирован пустой массив.
Как правило, после небольших подсказок, кандидат приходит к следующему списку
Интересно, почему кейс с несоответствием первого аргумента рассмотрен, а второго - нет..
plFlok
08.12.2023 03:19+3с пустым массивом ещё ладно, он проходит проверку на source == source.sorted()
но вот когда просят тест-кейс на невалидные типы данных, типа nullable при лайвкодинге на языках с null-safety - это вообще странно. но такое наблюдаю часто.
SamaRazor
08.12.2023 03:19+5Пустой массив вполне себе отсортирован, на нем установлено отношение порядка.
Для него работает правило "каждый последующий элемент не меньше предыдущего".
GospodinKolhoznik
08.12.2023 03:19-2каждый последующий элемент не меньше предыдущего
В такой формулировке получается, что в пустом массиве существует некий "предыдущий". Поэтому лучше так: "каждый элемента массива не меньше всех предыдущих"
mayorovp
08.12.2023 03:19+4Не получается.
Квантор всеобщности на пустом множестве даёт истину.
GospodinKolhoznik
08.12.2023 03:19Ну вы серьезно!? Да, я некорректно выразился, думал, что это очевидно и поэтому написал небрежно. Я имел ввиду если в массиве множество предыдущих элементов пусто. При этом сам то массив может быть и не пустым, а состоять из одного элемента, например.
Как вы будете применять квантор всеобщности в этом случае?
Зато вас заплюсовали, местная аудитория поражает своей глубиной мышления, и умением проверять массивы на граничные случаи)))
mayorovp
08.12.2023 03:19Так же. Формулировка "каждый последующий [...] предыдущего [...]" означает применение квантора всеобщности к множеству последовательных пар индексов.
У массива из одного элемента это множество такое же пустое как и у пустого массива.
GospodinKolhoznik
08.12.2023 03:19-3Вы берете массив из одного элемента, применяет к нему рекуррентно правило "каждый последующий элемент не меньше предыдущего" уже на первом же шаге у вас существует последующий элемент - это единственный элемент массива*, а значит, чтобы массив был отсортирован должен существовать предыдущий, а его не существует.
(*) В противном случае надо отдельно определить, является ли первый элемент массива последующим или нет, и вообще по-хорошему надо определить, что такое последующий элемент. Вот вы наверное считаете, что первый элемент не может быть последующим, но это не очевидно и зависит от договоренностей.
P.S. экой вы, батенька, токсик. Минусовать в математическом споре о трактовках понятий - это сильно.
GospodinKolhoznik
08.12.2023 03:19-1Формулировка "каждый последующий [...] предыдущего [...]" означает применение квантора всеобщности к множеству последовательных пар индексов
Ну только если только в такой трактовке про "последовательные пары индексов". Ну это уже какое то домысливание... Тогда лучше так и прописать условие, что "для всех последовательных пар индексов выполняется..." И ещё определить что такое последовательная пара. В общем либо неоднозначность, либо сильное переусложнение формулировки. Поэтому лучше пользоваться формулировкой "каждый элемент не меньше всех предыдущих " тут нет никаких неоднозначностей и домысливаний.
k4ir05
08.12.2023 03:19Но ведь в нём каждый элемент имеет неопределёное значение. А для неопределённых значений неопределена операция "<".
mayorovp
08.12.2023 03:19+1Нельзя так свободно пользоваться отрицанием под квантором всеобщности. Отрицание превращает его в квантор существования.
Иными словами, если вы желаете указать, что к неопределённым элементам неприменима операция "<".- вам надо предъявить такой элемент, недостаточно сказать что они там все такие.
k4ir05
08.12.2023 03:19Ну я чисто с практической точки зрения.
irb(main):005> a = [] irb(main):006> a[0] < a[1] (irb):6:in `<main>': undefined method `<' for nil:NilClass (NoMethodError)mayorovp
08.12.2023 03:19+1У вас в массиве нет 0 и 1 элементов, с чего вы вообще пытаетесь их сравнить? Условие "каждый последующий элемент не меньше предыдущего" ничего не требует относительно элементов с индексами 0 и 1 на пустом массиве.
Число практически пройдитесь по пустому массиву циклом и проверьте это условие в цикле.
k4ir05
08.12.2023 03:19-2У вас в массиве нет 0 и 1 элементов, с чего вы вообще пытаетесь их сравнить?
Так и я о том же. "каждый последующий элемент не меньше предыдущего". Как это понимать в случае с пустым массивом?
Условие "каждый последующий элемент не меньше предыдущего" ничего не требует относительно элементов с индексами 0 и 1 на пустом массиве.
КМК, это требует как минимум, их наличия. Если их нет, то какие могут быть дальнейшие рассуждения о них?
Иначе ведь к такому массиву одновременно применимо и условие "каждый последующий элемент не больше предыдущего".
Число практически пройдитесь по пустому массиву циклом и проверьте это условие в цикле.
Чисто практически это невозможно.
a.each_index { |i| puts a[i] < a[i+1] } => []
Cerberuser
08.12.2023 03:19+1Иначе ведь к такому массиву одновременно применимо и условие "каждый последующий элемент не больше предыдущего".
Совершенно верно. Поэтому пустой массив (как и массив из одного элемента) является отсортированным независимо от критерия сортировки - по возрастанию ли, по убыванию или с произвольным нетривиальным компаратором, неважно.
Чисто практически это невозможно.
Ну как же "невозможно", если вы ровно это и сделали в коде ниже? (Другой вопрос, что этот код не совсем верен, потому как на реальном отсортированном массиве в конце будет проверка
something < nil, которая выбросит ошибку)k4ir05
08.12.2023 03:19Ну как же "невозможно", если вы ровно это и сделали в коде ниже?
Разве? Я только попытался. Блок не выполнялся даже, значит проход по массиву не осуществлён.
Другой вопрос, что этот код не совсем верен, потому как на реальном отсортированном массиве в конце будет проверка
something < nil, которая выбросит ошибкуНа заполненном массиве да, он не сработает. Но для пустого массива этот блок вообще не имеет смысла, так что без разницы на сколько верен там код.
Cerberuser
08.12.2023 03:19Блок не выполнялся даже, значит проход по массиву не осуществлён.
Ну как это не осуществлён? Цикл же завершился. А то, что в нём не было ни одной итерации - это уже несущественно.
AgentFire
08.12.2023 03:19Вы с ним по разному смотрите на формулировку "каждый элемент ...". Он считает, что должен существовать хотя бы один элемент массива, к которому правило было бы успешно применено, а вы - нет.
Лично мне импонирует его вариант, а не ваш, ибо в случае с вашим любой пустой массив подходит под любую арбитрарную формулировку, например "каждый элемент массива должен присылать мне по 100 биткоинов". И пустой массив, по вашему мнению, это вполне реализует, что выглядит довольно абсурдно.
Cerberuser
08.12.2023 03:19И тем не менее, математически это именно так - любое утверждение с квантором всеобщности (т.е. "каждый элемент имеет свойство X") тривиально верно для пустого множества, а значит, и для пустого массива.
AgentFire
08.12.2023 03:19Да, но чтобы в подтверждение своих слов можно было приводить некую математическую теорию, нужно сперва обоюдно договориться, что в контексте дискуссии это дозволено делать. Я бы, например, на такое определение не согласился, т.е. у меня свои собственные взгляды на логику.
И не только у меня, например, в шарповом фреймворке linq функция All() (да и Any() тоже) пошлет эту вашу математику нафиг, если в перечислении не будет ни одного элемента.
А разговор то наш алгоритмический гораздо ближе к программированию, нежели к математике.
faiwer
08.12.2023 03:19А при чём тут вообще границы массива?
Просто типовая ошибка у начинающего будет на пограничных случаях. Когда, скажем, все элементы больше или все элементы меньше. На то собственно тесты и нужны, чтобы покрывать всякие хитрые кейсы.
от кандидата требуют не "реши задачу". а "угадай, что я задумал".
Собственно на любом собеседовании так. Нарочито дают размытое объяснение, чтобы выяснить насколько кандидат в состоянии прояснить ситуацию задавая правильные вопросы. Очень полезный навык в разработке.
как может быть сортирован пустой массив.
А что не так? Пустой массив всегда отсортирован.
Интересно, почему кейс с несоответствием первого аргумента рассмотрен, а второго - нет..
Кажется интервьювер немного
дурачокстранный
KirillBelovTest
08.12.2023 03:19+14Я когда начинал читать - то ожидал не два уровня, а побольше. Что на первом решают в лоб за один проход. На втором - двоичным поиском, а на третьем какая-нибудь магия вроде кода Грея или еще какой-то малоизвестной штуки. Увы, ожидания не оправдались.
dopusteam
08.12.2023 03:19+11Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
По формулировке вообще непонятно, что нужно сделать.
Lodary
08.12.2023 03:19+14Автор еще и сам же удивляется:
Еще кое-кто не понимает, чего я от них добиваюсь таким вопросом.
Действительно, почему бы это :)
calculator212
08.12.2023 03:19+8Я не совсем знаю, как именно у вас проходит собеседование, но по хорошему стоит предпреждать кандидатов об алгоритмической секции, т.к. много людей могут реализовать бинарный поиск, но по памяти это могут сделать довольно мало людей, т.к. по сути это бесполезное для работы знание. С тем же успехом можно просить людей реализовать быстрое преобразование Фурье или поиск в глубину/ширину. Да это покажет что собеседник разбирается в алгоритмах. Я согласен, что человек должен был бы сказать что тут нужно применить бинарный поиск и написать возможные тест кейсы, но на мой взгляд полезнее увидеть что человек понимает алгоритм и если что сможет его реализовать, а не просто выписать заученное решение с литкода, но если вы разрешаете гуглить во время собесов то это скорее норм, т.к. большую часть кода человек будет брать из готовых источников, либо хотя бы из готовых формул или схем
Я сам узнал об этом вопросе от коллеги из Google.
Я бы не хотел обижать, но для faang такие вопросы норма, т.к. они очень хорошо платят + есть шанс вырасти до зп 500к$+ и у них еще явно прописаны рекомендации для подготовки кандидатов. У нас во многих компаниях (не во всех), тоже тащат алгоритмическую практику, но кандидат узнает на собесе и само собой многие отсеиваются, т.к. ты пришел поговорить о работе, а тебя просят красно-черное и свою очередь, а ты последний раз сталкивался с таким на паре 10 лет назад и тебя не предупреждали что это будет нужно на собесе, ну как бы не совсем нормальное отношение к кандидату. В целом как бы собеседующий определяет вопросы, но по факту вы так можете потерять реально много подходящих кандидатов, но если вакансия просто для поиска хороших кадров, а работа не горит, то наверное такое "допустимо" делать
MiraclePtr
08.12.2023 03:19+9Юмор ситуации ещё в том, что автор сам говорит - алгоритм только кажется простым, а на самом деле правильно реализовать его очень сложно, вплоть до того, что его неправильные реализации попадали в книги и в стандартные библиотеки. И тут представим ситуацию, приходят два кандидата. - один пишет алгоритм с ошибками, а потом мучительно их ищет и исправляет с подсказками, а другой приходит и сразу пишет правильно. Значит ли это то, что второй разработчик более скилловый, как это покажется интервьюверу? Нет, более вероятно это значит что второй кандидат просто недавно решал такую задачу где-нибудь на литкоде или читал статью про нее.
То же самое про другие задачи на подобных собеседованиях, да, там обычно бывает что-нибудь уровня изи-медиум с литкода, и как обожают утверждать адепты подобных собеседований "да любой разработчик такое решит просто немного подумав". Это так, вот только нюанс в том, что один человек, дрочивший литкод и будучи натасканным на подобные задачки, сразу распознает знакомый тип задачи, выдаст решение и пойдет обсуждать дальше с интервьювером, а другой человек, который с таким не сталкивался в последние N лет, будет доходить до такой же идеи 10-20-30 минут (особенно с учётом стресса на интервью), в итоге либо потеряет время, которое на собеседованиях ограничено, и из-за этого не дойдет до следующих шагов по плану интервью, либо ему потребуются подсказки. Говорит ли это, что столкнувшись с совершенно другой задачей в реальной работе первый кандидат справится с ней лучше, чем второй? Вообще нет. Но впечатление о втором кандидате в глазах интервьювера будет испорчено, а о первом - скорее всего положительно, и шансов пройти дальше у него гораздо больше. Вот и получается, что на таких интервью преимущество имеют те, кому совершенно случайно повезло наткнуться на схожие задачки в работе или те, кто целенаправленно часами дрочил литкод. Все остальные находятся в заведомо проигрышем положении по сравнению с конкурентами, и именно поэтому вполне разумно не любят собеседования такого типа.
Ioanna
08.12.2023 03:19+1Надо вводить Литкод в ежедневную привычку, как зарядку. Проснулся - завтрак, урок в Дуолинго и задача в Литкод, а потом уже за работу)
artemisia_borealis
08.12.2023 03:19+1Только решение писать от руки на перфокарте. Лучше чернильным карандашом
wataru
08.12.2023 03:19+3Я не совсем знаю, как именно у вас проходит собеседование, но по хорошему стоит предпреждать кандидатов об алгоритмической секции
Это же собеседование в гугл. Там еще рекрутер выдает ссылку на книжки и курсы:
За время работы в Google я провёл более двух сотен интервью.
Aniro
08.12.2023 03:19+33Довольно интересно, что вы рассматриваете в тест кейсах null в качестве некорректных данных, но не рассматриваете очевидный кейс - неотсортированный массив. А если массив проверять, то вся магия бинарного поиска сразу ломается, ибо проверка исходных данных все равно займет O(n). Поэтому применение бинарного поиска одновременно с проверкой всех граничных условий не имеет смысла - вы либо уверены в своих данных, либо нет.
shornikov
08.12.2023 03:19+1Интересно послушать умников, на счет указания уже отсортированного массива в условиях задачи.
Как по мне - доверять такому можно, только если ты сам предварительно отсортировал его (как вариант получил из базы с order by).
Если данных мало - я бы еще раз его отсортировал для гарантии, а если много...
тем более: лопатить цифры неделю, чтобы потом оказалось, что входные данные были не нормализированы.
Fedorkov
08.12.2023 03:19если ты сам предварительно отсортировал
Даже в этом случае параметры метода стоит проверять ассертом, который как минимум отрабатывает под дебагом.
fshp
08.12.2023 03:19Сортировка отсортированного массива в лучшем случае займет O(n). За это же время работает перебор неотсортированного массива.
shornikov
08.12.2023 03:19В случае этой задачи выходит что либо давайте нам на вход любой массив, либо поклянитесь мамой )
Но в общем случае сортировка массива может быть одной из самых лёгких операций в функции
vvbob
08.12.2023 03:19+1Ну, не обязательно. Бывают ситуации когда в одних данных мы уверены, а вот в других нет.
Как пример - массив мы получили из подконтрольной нам БД, отсортированный по индексу, и мы довольно уверенны в том что там нормальная сортировка. А другие параметры получили из реста, и тут нам прилететь может все что угодно.
titbit
08.12.2023 03:19+3Да на любой простой задачке можно на собеседовании развернуть такую кучу вопросов, уточнений и даже придирок, что это ничем не будет отличаться от описанной. Так что задача может быть в принципе любой, главное это разговоры вокруг про условия, про способы решения, про ревью и тесты, про производительность и другие особенности ну и т. д.
brom_portret
08.12.2023 03:19-2я бы начал искать с середины массива:
def find(a, x): if not isinstance(a, list) or not len(a): return -1 pos = len(a) // 2 step = 1 res = -1 if a[pos] > x: step = -1 else: res = a[pos] while True: pos += step if pos == -1 or pos == len(a): break if a[pos] <= res: return res if a[pos] <= x and a[pos] > res: res = a[pos] return resили на js:
function find(a, x) { if (!Array.isArray(a) || a.length === 0) { return -1; } let pos = a.length >> 1; let step = 1; let res = -1; if (a[pos] > x) { step = -1; } else { res = a[pos]; } while (true) { pos += step; if (pos === -1 || pos === a.length) { break; } if (a[pos] <= res) { return res; } if (a[pos] <= x && a[pos] > res) { res = a[pos]; } } return res; }
А ваше решение имеет проблемы:// про плюсы отбития блоков пустыми строками вы похоже не слышали function f(f, a) { // а что если здесь не массив а объект? // кроме того условие и код в одну строчку это плохой стиль if (a == null || a.length == 0) return -1; // Общепринятая семантика это result, а не answer // и почему var, а не let? var answer = -1; var low = 0; var high = a.length — 1; while(low <= high) { // Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1 // и как то сложно, я таки не понимаю зачем это делать в цикле. var mid = Math.floor((low + high) / 2); if (a[mid] == x) { return x; } // нафига тут else если перед ним return? else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid — 1; } } return answer; }В итоге я бы вас не взял с таким решением
mayorovp
08.12.2023 03:19+5Вы это серьёзно? Предлагаете заменить логарифмический алгоритм на линейный из-за проблем с … оформлением?! Да ещё и разновидности "вкусовщина"?
про плюсы отбития блоков пустыми строками вы похоже не слышали
От чего отбивать-то его предлагаете? Это ж начало блока кода...
кроме того условие и код в одну строчку это плохой стиль
Пока код короткий - сойдёт.
Если перенести тело на следующую строчку - то окажется, что не писать фигурные скобки - плохой стиль, а если написать ещё и фигурные скобки - это будет три строки на, в общем-то, избыточную проверку.
и почему var, а не let?
let при определённом положении звёзд может оказаться медленнее, в этом году даже пришлось стандарт править чтобы у браузеров появился шанс это замедление убрать.
Не то чтобы это замедление было и правда важно, но и считать использование var чем-то плохим в критичном к производительности коде не стоит.
Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1
Вот тут вы правы, Math.floor - тяжёлая операция, не фиг её делать лишний раз.
и как то сложно, я таки не понимаю зачем это делать в цикле.
А вот этого высказывания уже я не понимаю. low и high меняются между итерациями цикла, где ещё можно вычислить mid?
нафига тут else если перед ним return?
Чтобы подчеркнуть альтернативность трёх веток кода.
brom_portret
08.12.2023 03:19я нигде не предлагал заменить предложенный алгоритм на мой. Просто написал простой алгоритм который первый пришел в голову, а потом рассмотрел предложенное решение. Не надо выдумывать.
код должен легко читаться, отбивки помогают этому, и это прописано в довольно большем количестве коудстайлов. Если человек не думает о читатебельности этого кода, я бы не стал его брать
дополнительный нестинг усложняет читабельность, это всем известный факт который указан в книках по рефакторингу.
mayorovp
08.12.2023 03:19+2Вы так и не ответили, откуда именно вы собрались отбивать функцию f.
дополнительный нестинг усложняет читабельность, это всем известный факт который указан в книках по рефакторингу.
Это всего лишь вкусы авторов книг по рефакторингу.
brom_portret
08.12.2023 03:19-2я имел в виду отбитие блоков внутри функции.
хорошая практика что любой блок который занимает более одной строки отбивается пустыми строками. Хорошая практика никогда не писать if (foo) return 1, читается проще.
Как-то так:function f(x, a) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let result = -1;
let low = 0;
let high = a.length — 1;
let mid;
while (low <= high) {
mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
}
if (a[mid] < x) {
result = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
Обратите внимание, что я также вынес объявление mid за пределы цикла.
P.S. Ну да, авторы руководств по рефакторингу дураки, а вы нет.mayorovp
08.12.2023 03:19+1Отбивать цикл от переменных цикла - глупо, это один логический блок.
Из трёх альтернативных веток кода отбивать одну от двух других - тоже глупо. Вы же блок if от else не отбили? Тогда почему ветка
==xоказалось отбита от ветки<x?С необходимостью отбить
return result;я бы тоже поспорил, это логическое завершение цикла.Осталось два места где можно поставить пустые строки - после входной проверки размера массива, и после вычисления
mid. Но вторую я бы тоже не ставил, поскольку она разорвёт пополам единый цикл, и вообще вычисление mid можно считать частью последующего сравнения.PS иронично, что в попытке указать другим на недостатки в оформлении кода, вы упустили из своего кода все отступы.
brom_portret
08.12.2023 03:19-4так. еще раз по пунктам.
в приведенном решении есть несколько проблем:
1) код плохо читается
2) нет проверки на то что входное значение может быть не только null но и чем угодно, например объектом или строкой
3) использован тяжелый метод Math.floor
4) одна из переменных объявлена внутри цикла, что лишние
5) код не универсален, следовало бы оформить его чтобы мможно было переиспользовать с любым компаратором.
Поэтому конечно я бы не стал брать автора. То что я бы его не взял исключительно из-за нечитаемости кода, это ваши выдумки
p.s. и да, вы придрались к парсеру хабра, а не ко мне.mayorovp
08.12.2023 03:19+1код плохо читается
Код читается достаточно хорошо для понимания. Можно и лучше, но приведённого автором оформления достаточно.
Для сравнения, ваш код из комментария чуть выше читается ужасно. И нефиг гнать на парсер Хабра, его синтаксис и раньше был не сильно сложным в освоении, а уж в WYSIWYG-то редакторе лепить подобные отмазки должно быть стыдно.
одна из переменных объявлена внутри цикла, что лишние
Почему? В какой книге по рефакторингу вы вычитали, что объявлять переменные внутри цикла - плохо?
код не универсален, следовало бы оформить его чтобы мможно было переиспользовать с любым компаратором
Этот пункт вы вообще только сейчас упомянули.
brom_portret
08.12.2023 03:19-2В редакторе код выглядел нормально и там были отступы. Даже при последующем редактировании. Кроме того вы спросили где бы я добавил пустые строки, я вам показал. Так что ваши придирки к отсутствию индентации не имеют никакого отношения к обсуждаемому предмету.
Потому что нефиг рассчитывать на оптимизатор, я хз будет ли он выделять память для переменной каждый раз или сможет оптимизировать и вынести выделение памяти за пределы цикла. Это база, мой друг.
-
Я не пишу на js и с утра не было времени чекнуть есть ли там готовый метод findLast в js и если нет писать его реализацию. А он есть и соответственно весь этот код превращается в велосипед.
mayorovp
08.12.2023 03:19+2Потому что нефиг рассчитывать на оптимизатор, я хз будет ли он выделять память для переменной каждый раз или сможет оптимизировать и вынести выделение памяти за пределы цикла. Это база, мой друг.
А вот если бы использовали var - такого вопроса бы не стояло.
А вообще, звучит не как "база", а как глупость.
brom_portret
08.12.2023 03:19Ну зачем мы меня заставляете объяснять базовые вещи?
Использование var потенциально может привести к багам, если кто-то будет дорабатывать эту функции и заюзает переменную mid выше цикла и не обратит внимание на то что она используется где-то там в ниже в цикле и будет соответсвенно ожидать то значение которое было туда записано до цикла.
references:
https://hackernoon.com/why-you-shouldnt-use-var-anymore-f109a58b9b70
https://dev.to/mindninjax/stop-using-var-for-declaring-variables-2p3a
mayorovp
08.12.2023 03:19Вы так пишете, как будто с вынесенным из цикла let не будет точно такой же проблемы.
И да, иронично что по первой из ваших ссылок во всех примерах кода весь код записан в одну строку. Видимо, тоже парсер Хабра виноват.
brom_portret
08.12.2023 03:19ну вот вам пример
function foo() { var x = 1; const arr = [1, 2, 3, 4, 5]; for (let i = 0; i < 5; i++) { var x = arr[i]; } console.log(x); } function bar() { let x = 1; const arr = [1, 2, 3, 4, 5]; for (let i = 0; i < 5; i++) { let x = arr[i]; } console.log(x); } foo(); bar();$ node 1.js 5 1
brom_portret
08.12.2023 03:19function bar() { let x = 1; const arr = [1, 2, 3, 4, 5]; let x; for (let i = 0; i < 5; i++) { x = arr[i]; } console.log(x); } $ node 1.js 1.js:5 let x; ^ SyntaxError: Identifier 'x' has already been declaredт.е. не получится допустить баг, будет показана явная ошибка при запуске, что я и имел в виду
mayorovp
08.12.2023 03:19Вот только что именно сделает тот самый гипотетический абсолютно невнимательный человек, который эту ошибку увидит? Использует ли он другое имя для переменной, или просто удалит строку
let x;?
brom_portret
08.12.2023 03:19нормальный человек использует другую переменную, потому что ошибка максимальна ясна и понятна.
про других я не скажу, может быть всякое.
А вот кейс с var плох тем что var x = something; может назначаться не всегда, а быть еще и завернута в if, который срабатывает только при каких-то редких обстоятельствах, так что код с ошибкой пройдет и ручное тестирование, и автотесты если они не покрывают тот самый редкий if и выстрелит у вас в продакшине. Лично подтверждаю что видел не один такой случай.
mayorovp
08.12.2023 03:19Вы сейчас пишете про какой-то загадочный абстрактный код, в то время как обсуждается конкретный бинарный поиск.
brom_portret
08.12.2023 03:19я думал мы обсуждаем почему не стоит использовать var, поскольку вы написали "А вот если бы использовали var - такого вопроса бы не стояло."
brom_portret
08.12.2023 03:19я сейчас потестировал код предложенный автором на node v14 которая была под рукой. Так вот, если заменить var на let, он работает быстрее.
что касается бинарного поиска, то вот вам мой вариант, он медленнее чем код автора, но наверное если потратить чуть больше времени, можно сделать его быстрееfunction find(a, x) { if (!Array.isArray(a) || a.length === 0) { return -1; } let result = -1; let len = a.length; let pos = len >> 1; while (pos < len) { if (a[pos] == x) { return x; } if (a[pos] < x) { result = a[pos]; pos += ((len - pos) >> 1) || 1; continue; } if (pos > 0) { len = pos; pos >>= 1; } else { break; } } return result; }
brom_portret
08.12.2023 03:19в общем вот вам код которым и который я тестировал:
отсутствие ошибок и корректность метода тестирования не гарантирую, я просто развлекался в свбодное время// Orignal version but with bits shift function fv0(a, x) { if (a == null || a.length == 0) return -1; var answer = -1; var low = 0; var high = a.length - 1; while(low <= high) { var mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // Let's use let instead of var function fv1(a, x) { if (a == null || a.length == 0) return -1; let answer = -1; let low = 0; let high = a.length - 1 while(low <= high) { let mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // Let's declare mid outside of loop function fv2(a, x) { if (a == null || a.length == 0) return -1; let answer = -1; let low = 0; let high = a.length - 1 let mid; while(low <= high) { mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // My version function fv3(a, x) { if (!Array.isArray(a) || a.length === 0) { return -1; } let result = -1; let len = a.length; let pos = len >> 1; while (pos < len) { if (a[pos] == x) { return x; } if (a[pos] < x) { result = a[pos]; pos += ((len - pos) >> 1) || 1; continue; } if (pos > 0) { len = pos; pos >>= 1; } else { break; } } return result; } // Let's test let a = []; let t0 = 0; let t1 = 0; let t2 = 0; let t3 = 0; for (let i = 0; i < 1000000; i++) { for (j = 0; j < 1000; j++) { a[j] = Math.round(Math.random() * 100); } a.sort((a, b) => { if (a < b) { return -1; } if (a > b) { return 1; } return 0; }) let x = Math.round(Math.random() * 100); let startTime = Date.now(); let r0 = fv0(a, x); let endTime = Date.now(); t0 += (endTime - startTime); startTime = Date.now(); let r1 = fv1(a, x); endTime = Date.now(); t1 += (endTime - startTime); startTime = Date.now(); let r2 = fv2(a, x); endTime = Date.now(); t2 += (endTime - startTime); startTime = Date.now(); let r3 = fv3(a, x); endTime = Date.now(); t3 += (endTime - startTime); if (r3 != r0) { console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r3); } } console.log("original version", t0); console.log("original version with let", t1); console.log("original version with declared mid outside of the loop", t2); console.log("my version", t3); OUTPUT: original version 83 original version with let 71 original version with declared mid outside of the loop 52 my version 61
brom_portret
08.12.2023 03:19немножко переделал свой код:
function fv3(a, x) { if (!Array.isArray(a) || a.length === 0) { return -1; } let result = -1; let len = a.length; let pos = len >> 1; while (pos < len) { if (a[pos] == x) { return x; } if (a[pos] < x) { result = a[pos]; pos += ((len - pos) >> 1) || 1; } else if (pos > 0) { len = pos; pos >>= 1; } else { return result; } } return result; }и прогнал 2000000 итераций для строки размером 2000, в этот раз версия с let внутри цикла, как ни странно, оказалась быстрее всех, первая версия которая приходит в голову это особенности GC
original version 143 original version with let 116 original version with declared mid outside of the loop 123 my version 120
mayorovp
08.12.2023 03:19Тут числа от запуска к запуску прыгают чуть ли не в полтора раза, их бесполезно сравнивать.
brom_portret
08.12.2023 03:19хорошо, я немного переделал бенчмарк чтобы он работал быстрее и надежнее добавил еще один вариант. Таки получается что var всегда медленнее чем let:
// Orignal version but with bits shift function fv0(a, x) { if (a == null || a.length == 0) return -1; var answer = -1; var low = 0; var high = a.length - 1; while(low <= high) { var mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // Let's user let instead of var function fv1(a, x) { if (a == null || a.length == 0) return -1; let answer = -1; let low = 0; let high = a.length - 1 while(low <= high) { let mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // Let's declare mid outside of loop function fv2(a, x) { if (a == null || a.length == 0) return -1; let answer = -1; let low = 0; let high = a.length - 1 let mid; while(low <= high) { mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // Let's declare mid outside of loop and initialize it function fv3(a, x) { if (a == null || a.length == 0) return -1; let answer = -1; let low = 0; let high = a.length - 1 let mid = 0; while(low <= high) { mid = (low + high) >> 1; if (a[mid] == x) { return x; } else if (a[mid] < x) { answer = a[mid]; low = mid + 1; } else { high = mid - 1; } } return answer; } // My version function fv4(a, x) { if (a == null || a.length == 0) { return -1; } let result = -1; let len = a.length; let pos = len >> 1; while (pos < len) { if (a[pos] == x) { return x; } if (a[pos] < x) { result = a[pos]; pos += ((len - pos) >> 1) || 1; } else if (pos > 0) { len = pos; pos >>= 1; } else { return result; } } return result; } // Let's test let a = []; let t0 = 0; let t1 = 0; let t2 = 0; let t3 = 0; let t4 = 0; let startTime; let endTime; for (j = 0; j < 4096; j++) { a[j] = Math.round(Math.random() * 1000); } a.sort((a, b) => { if (a < b) { return -1; } if (a > b) { return 1; } return 0; }) for (let i = 0; i < 100000000; i++) { let x = Math.round(Math.random() * 1000); startTime = Date.now(); let r0 = fv0(a, x); endTime = Date.now(); t0 += (endTime - startTime); startTime = Date.now(); let r1 = fv1(a, x); endTime = Date.now(); t1 += (endTime - startTime); startTime = Date.now(); let r2 = fv2(a, x); endTime = Date.now(); t2 += (endTime - startTime); startTime = Date.now(); let r3 = fv3(a, x); endTime = Date.now(); t3 += (endTime - startTime); startTime = Date.now(); let r4 = fv4(a, x); endTime = Date.now(); t4 += (endTime - startTime); if (r4 != r0) { console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r4); } } console.log("original version", t0); console.log("original version with let", t1); console.log("original version with declared mid outside of the loop", t2); console.log("original version with declared and initizalized mid outside of the loop", t3); console.log("my version", t4);node 1.js && node 1.js && node 1.js && node 1.js && node 1.js original version 6730 original version with let 6398 original version with declared mid outside of the loop 6236 original version with declared and initizalized mid outside of the loop 6704 my version 7701 original version 6846 original version with let 6405 original version with declared mid outside of the loop 6326 original version with declared and initizalized mid outside of the loop 6493 my version 7682 original version 7000 original version with let 6448 original version with declared mid outside of the loop 6250 original version with declared and initizalized mid outside of the loop 6497 my version 7528 original version 6988 original version with let 6422 original version with declared mid outside of the loop 6395 original version with declared and initizalized mid outside of the loop 6508 my version 7566 original version 6887 original version with let 6373 original version with declared mid outside of the loop 6310 original version with declared and initizalized mid outside of the loop 6608 my version 7677
brom_portret
08.12.2023 03:19вот автора такого решения я бы наверное взял :)
https://habr.com/ru/companies/ispsystem/articles/779224/#comment_26248196
k4ir05
08.12.2023 03:192) нет проверки на то что входное значение может быть не только null но и чем угодно, например объектом или строкой
Ну тогда уж надо проверить, что это массив чисел, и что он отсортирован по возрастанию.
brom_portret
08.12.2023 03:19ну этого не было в условиях задачи. проверять что массив отсортирован дорого. А вот то что условиями покрыта только часть возможных неправильных аргументов это минус, где гарантия что этот чел не напишет такого в реальном проекте?
k4ir05
08.12.2023 03:19ну этого не было в условиях задачи.
Как и того, для чего нужен этот массив)
Но там явно указано, что нам дан массив.
А вообще, лучше тогда уж так:
function f(a: Array<number>, x: number): number { // ... }
brom_portret
08.12.2023 03:19-2вообще в последних версиях js есть метод findLast, так что еще один минус автору за изобретение велосипеда. И даже если метода нет, то возможно не стоило выпендриваться, а стоило писать что-то (я не тестировал но кажется должно работать):
const findLastIndex = (array, comparator) => { // или любой алгоритм по вкусу for (let i = array.length - 1; i >= 0; i--) { if (comparator(array[i])) { return i; } } return -1; } function find(a, x) { if (!Array.isArray(a) || a.length === 0) { return -1; } const result = a[findLastIndex(a, i => i <= x)]; return result == undefined ? -1 : result; }faiwer
08.12.2023 03:19findLast-O(n).brom_portret
08.12.2023 03:19а вот это действительно печально.
brom_portret
08.12.2023 03:19
Вот версия для всех случаев, сложность O(log N), точнее кажется O(log2 N) поскольку мы ищем строго первый или последний элемент в массиве в котором значения могут повторяться, в оригнальном алгоритме который автор видимо списал из википедии ищеться первое попавшеся значение, поэтому там действительно O(log N)// arr: An array that must be sorted in ascending order. // cmp: A comparator function(a) or a target value. // // The comparator function should be defined to take a single argument 'a' // and compare it internally: // It should return -1 if 'a' is less than a reference value; // It should return 0 if 'a' is equal to a reference value; // It should return 1 if 'a' is greater than a reference value; // // If 'cmp' is not a function, it is treated as a target value against // which elements of 'arr' are compared. function createComparator(x) { return function(a) { if (a < x) { return -1; } if (a > x) { return 1; } return 0; } }; function _getComparator(arg) { if (typeof arg === 'function') { return arg; } return createComparator(arg); } function findLastIndexEqual(arr, cmp) { cmp = _getComparator(cmp); let len = arr.length; let pos = len >> 1; let result = -1; let start = 0; while (pos >= start && pos < len) { if (cmp(arr[pos]) === 0) { result = start = pos; pos += (len - pos) >> 1 || 1; } else if (cmp(arr[pos]) > 0) { len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } else { pos += (len - pos) >> 1 || 1; } } return result; } function findLastIndexLessOrEqual(arr, cmp) { cmp = _getComparator(cmp); let len = arr.length; let pos = len >> 1; let result = -1; let start = 0; while (pos >= start && pos < len) { if (cmp(arr[pos]) <= 0) { result = start = pos; pos += (len - pos) >> 1 || 1; } else { len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } } return result; } function findLastIndexLess(arr, cmp) { cmp = _getComparator(cmp); let len = arr.length; let pos = len >> 1; let result = -1; let start = 0; while (pos >= start && pos < len) { if (cmp(arr[pos]) < 0) { result = start = pos; pos += (len - pos) >> 1 || 1; } else { len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } } return result; } function findFirstIndexEqual(arr, cmp) { cmp = _getComparator(cmp); let len = arr.length; let pos = len >> 1; let result = -1; let start = 0; while (pos >= start && pos < len) { if (cmp(arr[pos]) === 0) { result = pos; len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } else if (cmp(arr[pos]) > 0) { len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } else { start = pos; pos += (len - pos) >> 1 || 1; } } return result; } function findFirstIndexGreaterOrEqual(arr, cmp) { cmp = _getComparator(cmp); let len = arr.length; let pos = len >> 1; let result = -1; let start = 0; while (pos >= start && pos < len) { if (cmp(arr[pos]) >= 0) { result = pos; len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } else { start = pos; pos += (len - pos) >> 1 || 1; } } return result; } function findFirstIndexGreater(arr, cmp) { cmp = _getComparator(cmp); let len = arr.length; let pos = len >> 1; let result = -1; let start = 0; while (pos >= start && pos < len) { if (cmp(arr[pos]) > 0) { result = pos; len = pos; pos = start + (((pos - start) >> 1) || pos - 1); } else { start = pos; pos += (len - pos) >> 1 || 1; } } return result; }
brom_portret
08.12.2023 03:19Если оно O(n), никто не мешает закодить нечто вроде такого, у меня это заняло два часа. Нужно еще два часа потратить чтобы убрать лишние итерации, но мне честно говоря лень. Но факт то что написать бинарный поиск с компараторами это не проблема. Использовать с осторожностью, тестировал каждый кейс на рандомных строках длинной 400 символов со значениям [0..99] и рандомных значениях x в тех же пределах, в качестве эталона использовал простейший перебор, для каждого кейса делал 1 000 000 итераций, вроде ошибок не нашлось.
// Array must be sorted in asending order // Comparator must return: // < 0 if value less than expected; // 0 if value is equal to excepted // > 0 if value is greater than expected function findLastIndexEqual(arr, cmp) { let len = arr.length; let pos = len >> 1; let result = -1; while (pos > -1 && pos < len) { if (cmp(arr[pos]) === 0) { result = pos; pos += (len - pos) >> 1 || 1; } else if (cmp(arr[pos]) > 0) { len = pos; pos = pos >> 1 || pos - 1; } else { pos += (len - pos) >> 1 || 1; } } return result; } function findLastIndexLessOrEqual(arr, cmp) { let len = arr.length; let pos = len >> 1; let result = -1; while (pos > -1 && pos < len) { if (cmp(arr[pos]) <= 0) { result = pos; pos += (len - pos) >> 1 || 1; } else { len = pos; pos = pos >> 1 || pos - 1; } } return result; } function findLastIndexLess(arr, cmp) { let len = arr.length; let pos = len >> 1; let result = -1; while (pos > -1 && pos < len) { if (cmp(arr[pos]) < 0) { result = pos; pos += (len - pos) >> 1 || 1; } else { len = pos; pos = pos >> 1 || pos - 1; } } return result; } function findFirstIndexEqual(arr, cmp) { let len = arr.length; let pos = len >> 1; let result = -1; while (pos > -1 && pos < len) { if (cmp(arr[pos]) === 0) { result = pos; len = pos; pos = pos >> 1 || pos - 1; } else if (cmp(arr[pos]) > 0) { len = pos; pos = pos >> 1 || pos - 1; } else { pos += (len - pos) >> 1 || 1; } } return result; } function findFirstIndexGreaterOrEqual(arr, cmp) { let len = arr.length; let pos = len >> 1; let result = -1; while (pos > -1 && pos < len) { if (cmp(arr[pos]) >= 0) { result = pos; len = pos; pos = pos >> 1 || pos - 1; } else { pos += (len - pos) >> 1 || 1; } } return result; } function findFirstIndexGreater(arr, cmp) { let len = arr.length; let pos = len >> 1; let result = -1; while (pos > -1 && pos < len) { if (cmp(arr[pos]) > 0) { result = pos; len = pos; pos = pos >> 1 || pos - 1; } else { pos += (len - pos) >> 1 || 1; } } return result; } function createComparator(x) { return function(a) { if (a < x) { return -1; } if (a > x) { return 1; } return 0; } }; a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ]; console.log(a[findLastIndexLessOrEqual(a, createComparator(12))]); console.log(a[findLastIndexLessOrEqual(a, createComparator(13))]); console.log(a[findLastIndexLessOrEqual(a, createComparator(2))]); console.log(a[findLastIndexLessOrEqual(a, createComparator(22))]); console.log(a[findLastIndexLessOrEqual(a, createComparator(3))]); console.log(a[findLastIndexLessOrEqual(a, createComparator(21))]);
angly
08.12.2023 03:19+1в этом году даже пришлось стандарт править чтобы у браузеров появился шанс это замедление убрать.
Расскажите подробней?
mayorovp
08.12.2023 03:19+2Так, я ошибся, стандарт ещё не правили. Но собираются.
Это из сентябрьского митинга TC39: презентация, протокол
Summary
Years after ES6, let and const still commonly cause performance regressions vs var, and transpilers do not implement TDZ. The result is that let and const are avoided in shipped JS code.
Generally, if the committee cares about its features being adoptable, these sorts of 5+-year retrospectives will be important.
SYG proposes treating some or all cases of TDZ as simply evaluating to undefined, as var does.
Most of the committee agreed with the goal of ensuring that features like this are adoptable in practice, but there was no consensus on whether semantics changes to support that are needed.
Conclusion
A proposal may be formed on this topic in the future
brom_portret
08.12.2023 03:19Если я правильно понял, то это касается только не инициализованных значений объявленных с помощью let?
mayorovp
08.12.2023 03:19Напрямую это касается переменных, объявленных через let посреди блока, но использованных в замыкании до этого момента:
const fn = () => console.log(x); // fn() - ошибка let x = 5; fn(); // а так нормальноНо вот сама возможность подобного обращения и необходимость её отслеживать может повлиять хоть вообще на все переменные, тут всё зависит от глупости оптимизатора.
brom_portret
08.12.2023 03:19и на этом основании вы выше посоветовали не использовать let вместо var?
fshp
08.12.2023 03:19Вот тут вы правы, Math.floor - тяжёлая операция, не фиг её делать лишний раз.
Но и складывать индексы идея не лучшая, может возникнуть переполнение. Об этом в статье написано.
brom_portret
08.12.2023 03:19p.s не сразу понял что под простейшей реализацией автор все таки имел в виду двоичный поиск. и также не сразу понял что перевод. также я я не имел в виду что мое решение лучше, я его написал до того как прочитал код в качестве начального варианта который должен быть быстрее простого перебора.
Если бы я дальше работал бы над кодом то разумеется получился бы бинарый поискbrom_portret
08.12.2023 03:19и получилось бы в итоге у меня что-то типа такого:
function find(a, x) { if (!Array.isArray(a) || a.length === 0) { return -1; } let result = -1; let len = a.length; let pos = len >> 1; while (pos < len) { if (a[pos] == x) { return x; } if (a[pos] < x) { result = a[pos]; pos += (len - pos) >> 1 || 1; continue; } if (pos > 0) { len = pos; pos >>= 1; } else { break; } } return result; }mayorovp
08.12.2023 03:19Этот алгоритм попросту неправильный, вы теряете левую границу и в итоге делаете лишние итерации.
brom_portret
08.12.2023 03:19мне кажется вы ошибаетесь, посмотрите пожалуйста вот этот мой коммент https://habr.com/ru/companies/ispsystem/articles/779224/comments/#comment_26245396 - я там в сравниваю результаты на рандомных данных с результатами оригинального алгоритма предложенного автором, расхождений в результатах функции не выявляется
Если вы считаете что алгоритм таки неверный, предложите тесткейс который это докажет. Если все так как вы говорите, это должно быть легко
brom_portret
08.12.2023 03:19понял о чем вы, действительно там есть лишние итерации
brom_portret
08.12.2023 03:19или например вот так тоже неплохо
function fv4o(a, x) { let result = -1; let end = (a || []).length; let start = 0; let pos = end >> 1; while (pos < end && result != x) { if (a[pos] > x) { end = pos; pos = ((end - start) >> 1) + start; continue; } result = a[pos]; start = pos; pos = ((end - start) >> 1 || 1) + start; } return result; }
brom_portret
08.12.2023 03:19ок, таки нашел время и сделал версию которая меня вроде устраивает, но еще можно поработать и оптимизировать
function fv4o(a, x) { if (a == null || a.length == 0) { return -1; } let result = -1; let end = a.length; let start = 0; let pos = end >> 1; // Relative position let abspos = pos; // Absolute position let item = 0; while (abspos < end) { item = a[abspos]; if (item == x) { return x; } if (item <= x) { result = item; start = abspos; } else { end = abspos; } pos = (end - start) >> 1 || 1; abspos = pos + start; } return result; }
kekoz
08.12.2023 03:19+2Поскольку практически все ваши “претензии” автору основаны на ваших же вкусовых предпочтениях, я не буду устраивать критику этой “критике”, это пустое. Но о том, что бросилось в глаза, таки спрошу:
// а что если здесь не массив а объект?
Возьмём в качестве примера код, который используется буквально везде — стандартную библиотеку C. Выбирайте на свой вкус, самые популярные — BSD libc, GNU glibc, musl. Загляните в исходный код практически любой функции модуля
string.h.Вот несколько примеров:
char * strcat(char * __restrict s, const char * __restrict append) { char *save = s; for (; *s; ++s); while ((*s++ = *append++)); return(save); } int strcmp(const char *s1, const char *s2) { while (*s1 == *s2++) if (*s1++ == '\0') return (0); return (*(const unsigned char *)s1 - *(const unsigned char *)(s2 - 1)); } char * strdup(const char *str) { size_t len; char *copy; len = strlen(str) + 1; if ((copy = malloc(len)) == NULL) return (NULL); memcpy(copy, str, len); return (copy); }Не смущает, что нигде не проверяется, являются ли “строками” входящие “строки”? Если хотите, могу очень доступно объяснить, почему не проверяется.
А в вашем коде я вижу одну из причин того, почему многие современные приложения такие “тяжёлые”, веб-страницы с тремя параграфами текста и парой кнопок грузят свои десятки мегабайт по несколько секунд, и прочий code bloating. Ваш код делает работу, которая никому не нужна, которой не было в ТЗ, вы не делаете отличий между generic-кодом и частным случаем, вы возводите свои весьма поверхностные представления о безопасности кода в безумный абсолют “все параметры всех функции должны быть проверены на всё”.
В итоге я бы вас не взял с таким решением
brom_portret
08.12.2023 03:19я пока не опубликовал финальное решение. то что в посте указано то что входной параметр массив или null я не заметил, это довольно странное условие в случае js. Но кстати его код проверяет еще и на undefined не очевидным образом, чего не было в условиях задачи. По поводу libc я не скажу что это хороший код, там много трэша. Вот посморите на getaddrinfo, https://codebrowser.dev/glibc/glibc/sysdeps/posix/getaddrinfo.c.html, разве это похоже на хороший код? Но даже там условия и циклы часто отбиты.
По поводу
if (foo ) {
}
явные начало и конец блока лучше чем не явные, читать проще и меньше ошибок в итоге
А теперь сравните с кодом из скажем ZFS https://github.com/openzfs/zfs/blob/master/module/avl/avl.c
По поводу кода предложенного автором - там вообще нет ни одной отбивки, все единым блоком кода. То есть явные проблемы с читаемостью. Даже в ваших примерах из glibc есть отбивки
brom_portret
08.12.2023 03:19-1и вообще разве отбивки это основное? Там блин var!!! и Math.floor!!!. Этого уже достаточно кмк
brom_portret
08.12.2023 03:19Вот вам мой допиленный вариант:
function fv4o(a, x) { if (a == null || a.length == 0) { return -1; } let result = -1; let end = a.length; let start = 0; let relpos = end >> 1; // Relative cursor position from start let abspos = relpos; // Absolute cursor position let item; while (abspos < end) { item = a[abspos]; if (item == x) { return x; } if (item <= x) { result = item; start = abspos; } else { end = abspos; } relpos = (end - start) >> 1 || 1; abspos = relpos + start; } return result; }
brom_portret
08.12.2023 03:19ну вот вам еще такое решение
function fv4o(a, x) { let result = -1; let end = (a || []).length; let start = 0; let pos = end >> 1; while (pos < end && result != x) { if (a[pos] > x) { end = pos; pos = ((end - start) >> 1) + start; continue; } result = a[pos]; start = pos; pos = ((end - start) >> 1 || 1) + start; } return result; }}
brom_portret
08.12.2023 03:19Хорошее решение на мой взгляд выглядело бы как-то так:
https://habr.com/ru/companies/ispsystem/articles/779224/#comment_26248196
antonkrechetov
08.12.2023 03:19Не смущает, что нигде не проверяется, являются ли “строками” входящие “строки”?
А как это вообще проверить в C?
kekoz
08.12.2023 03:19Для начала дай определение для “строка” (или возьми в стандарте :)). Чтобы продолжать разговор об этом, необходимо убедиться, что мы имеем в виду одно и то же.
НО!
Ты не на то обращаешь внимание. Я видел слишком много неофитов, которые считают, что тут надо проверять хотя бы на NULL. Не надо!
sdramare
08.12.2023 03:19Ну пример то так себе - сколько прописей памяти это породило. Всякие Rust не просто так появились.
s13nder
08.12.2023 03:19+7Исходя из посталвенных условий это скорее задача для определения нахождления кандидата на 1 волне с вами и угадывает ли он что вы от него хотите.
unclejocker
08.12.2023 03:19+1Я в другом подобном обсуждении уже писал, что когда у вас, как у FAANG, за воротами очередь кандидатов стоит и когда у вас десятки тысяч сотрудников - можно позволить себе отбирать тех, на одной волне с командой. А потом уже смотреть как они код писать умеют.
Nalivai
08.12.2023 03:19+2В итоге собрать гомогенную команду в которой все радостно думают одинаково, совершают одинаковые ошибки, и не способны их друг у друга заметить. Все получают триста какосеков, а сайты с текстом и двумя картинками потом грузятся по 7 секунд.
unclejocker
08.12.2023 03:19Пока это не влияет на бизнес - нет проблемы (ну кроме как для пользователей). А у гугла бизнес идет хорошо т.к. они заняли определенную нишу и по факту никто туда уже влезть не может. А свежие идеи они покупают вместе с командами. Т.е. изнутри инновации не особо нужны.
panzerfaust
08.12.2023 03:19+2Порой, по разным причинам, мы получаем друг от друга ложные или неточные сигналы.
И далее по тексту выясняется, что от интервьюера все сигналы по умолчанию кошерные, а не прав может быть только кандидат.
ChePeter
08.12.2023 03:19Тут многие в примерах смело используют функцию вычисления длины массива, но в некоторых языках это уже просмотр всего массива.
MiraclePtr
08.12.2023 03:19+1со списками не путаете?
creker
08.12.2023 03:19В сях массив таки придется весь пройти, чтобы длину получить. И тогда бинарный поиск тут уже будет бесполезен, как и сам факт отсортированности массива.
mayorovp
08.12.2023 03:19+3Это только если массив нуль-терминированный или вроде того.
А обычно эта длина передаётся дополнительным параметром.
ChePeter
08.12.2023 03:19-1Про то и все посты, что для профи задача некорректная
mayorovp
08.12.2023 03:19Так что тут некорректного-то?
brom_portret
08.12.2023 03:19-1прежде всего некорректный здесь вы, потому что выше убеждаете людей что var лучше чем let, потому что в некоторых случаях оно медленнее, чем сразу выдаете в себе дилетанта лол
Aniro
08.12.2023 03:19+3Тогда это уже не массив. Это или нуль-терминэйтед стринг или связный список или еще что-то, но не массив.
ChePeter
08.12.2023 03:19-3В С как раз массив так и хранят как нуль-терминетед последовательность указателей. Иногда. Но можно и не так.
Но если часто что-то сортировать, то наверно лучше хранить в дереве или еще как. И тогда задачка станет совсем другой. ))
sasha_semen
08.12.2023 03:19+3Я всегда думал что в С массив это указатель на первый элемент. И никаких нуль терминетед и в помине нет, что malloc выдаст так и будет.
wataru
08.12.2023 03:19Вы со строками путаете. Нет никаких нул-терминаторов в массиве. Даже если у вас двумерный массив указателями на указатели - передают везде размер массива.
fshp
08.12.2023 03:19-1Чем должен оканчиваться массив интов в вашем представлении? Хуем моржовым?
Зачем вы продолжаете спорить о том, в чём явно не разбираетесь?
Kerman
08.12.2023 03:19+2int result = a.LastOrDefault(n => n < x);if (result == 0) result = -1;return resultКажется, я уложился в 30 строчек.
Делать сходу двоичный поиск, без требований - это признак незрелости программиста. Premature optimization.
Оптимизация делается ТОЛЬКО по результатам замеров и профилирования. Иначе алгоритмы усложняются и код становится нечитаемым. А читаемость кода для львиной части кода гораздо важнее скорости.
Fedorkov
08.12.2023 03:19+5Можно даже в одну строку (плюс корректная обработка нулей в исходном массиве).
a.LastOrDefault(n => n <= x, -1);
wataru
08.12.2023 03:19+1Выбор алгоритма - это не преждевременная оптимизация. Если везде все писать как попало, то у профайлер вам ничего не покажет - будет равномерно тормозить вообще все чуть-чуть не тривиальное.
vvbob
08.12.2023 03:19+6Автор почему-то подразумевает что двоичный поиск априори лучше тупого перебора в лоб, что может быть совсем даже и не так. Если массив целиком влезает в кеши, да даже если и не целиком, то вполне может оказаться что перебор отрабатывает быстрее двоичного поиска, который будет постоянно сбрасывать кеш если данных много, или просто будет более громоздким и менее понятным чем перебор, а работать так-же по скорости, при небольшом размере массива.
mayorovp
08.12.2023 03:19Только вот двоичный поиск редко когда требует больше записей в кеше чем поиск линейный, так что если он и окажется медленнее - то уж точно не из-за кеша.
creker
08.12.2023 03:19+3Зато двоичный поиск генерирует кэш промахи и сбивает логику префетчинга, а на этом часто весь перформанс и умирает. Подобное надо бенчить на конкретных продовых данных.
mayorovp
08.12.2023 03:19+3Кеш-промахи и префетчинг тут точно ни при чём.
Повторюсь, есть крайне мало ситуаций, в которых линейному поиску потребовалось бы затронуть меньше памяти. А значит, все эти эффекты могут лишь уменьшить выгоду от двоичного поиска, но никак не сделать его хуже линейного.
Вот с чем правда у двоичного поиска плохо - так это с предсказанием переходов. Условный оператор внутри цикла попросту непредсказуем, он будет останавливать конвейер в среднем на каждой второй итерации (а попытка спекулятивно исполнить обе ветки быстро упрётся в тот же выбор уже на следующей итерации).
wataru
08.12.2023 03:19Есть же branch-free реализации бин-поиска. Даже тут на хабре статью видел как-то.
rafuck
08.12.2023 03:19Вы про тернарный оператор вместо if?
wataru
08.12.2023 03:19Нет. Суть в том, что размер отрезка каждый раз делиться на 2, а вот начало смещается в середину или нет в зависимости от условия. Можно математическую формулу с умножением на bool делать, можно выбирать значение из массива по индексу 0 или 1. Но это не особо эффективно будет, хоть ветвлений и нет. Самое быстрое - заставить компилятор какой-нибудь cmov использовать.
faiwer
08.12.2023 03:19+1Подобное надо бенчить на конкретных продовых данных
Боюсь не получится найти такие данные, где binary search проиграет. Разве что если там 3-5 элементов в массиве.
Fedorkov
08.12.2023 03:19+5Если массив целиком влезает в кеши, да даже если и не целиком, то вполне может оказаться что перебор отрабатывает быстрее двоичного поиска, который будет постоянно сбрасывать кеш если данных много
У вас нестыковка в суждении.
На маленьких массивах рулит обычный перебор из-за простоты тела цикла и из-за спекулятивных вычислений. На больших рулит логарифмическая асимптотика. А кэш может склонить чашу весов только на пограничных объёмах, если они окажутся больше размера кэша (что вряд ли возможно для данной задачи на современных процессорах).
ZirakZigil
08.12.2023 03:19Ещё большую роль играет сочетание двух вещей: необходиомость сортировки перед поиском и предполагаемое число поисков. Если сортировать надо, и число запросов невелико, то даже на больших объёмах данных гораздо быстрее будет нужное количество раз линейно поискать (бонусом, простые данные типа чисел очень сильно ускоряются векторными инструкциями).
KirillBelovTest
08.12.2023 03:19В общем хоть меня и удивляет популярность такой достаточно простой задачи, но я сначала дошел до условия, решил задачку, а потом продолжил читать. Не думал, что мое наивное решение и будет тем самым, которое ожидает автор статьи. Но хочу показать свое решение в коментах, так как оно оригинально тем, что сделано на WL:
f[arr : {a1_Integer, ___Integer}, x_Integer, default_Integer : -1] /; x < a1 := default f[arr : {___Integer, an_Integer}, x_Integer, default_Integer : -1] /; x >= an := an f[arr : {__Integer}, x_Integer, default_Integer : -1] := With[{halfLen = Round[Length[arr]/2]}, If[arr[[halfLen]] < x, f[arr[[halfLen + 1 ;; ]], x, arr[[halfLen]]], f[arr[[ ;; halfLen]], x, default] ] ] f::argex = "Argument exception"; f[args___] := (Message[f::argex]; Defer[f[args]])На скриншоте код и результаты тестов. Результаты не уместились, но тестов больше чем в самой статье, т.е. они те же самые, а еще включают то, что не было учтено.
faiwer
08.12.2023 03:19+3__Integer&args___Какой замечательный язык. У этих
___(3 штуки аж) есть какая-то история?KirillBelovTest
08.12.2023 03:19+4Да, конечно. Это такой синтаксис шаблонов/паттернов/образцов в WL. Во многих языках программирования, в которых есть паттерн-матчинг есть такая штука как wildcard. То есть
"_". Так вот в WL шаблоны могут состоять из разных вариаций wildcard. Вот несколько примеров. Сравнение происходит при помощи функцииMatchQ[expression, pattern]:MatchQ[x, _] == True (*одиночное подчеркивание - все что угодно*) MatchQ[f[x], f[_]] == True (*это значит выражение слева это f с любым аргументом*) MatchQ[f[x, y], f[_]] == False MatchQ[f[], f[_]] == False MatchQ[f[1, 2, 3, 4], f[__]] == True (*два подчеркивания от одного до бесконечности элементов*) MatchQ[f[], f[__]] == False MatchQ[f[], f[___]] == True MatchQ[f[x], f[___]] == True MatchQ[f[x, y, z], f[___]] == True (*три подчеркивания любое число элементов от 0 до беконечности*)Кроме трех вариантов wildcard есть еще возможность указывать диапазон количества элементов или конкретное значение, но это я оставлю на потом. И так мы рассмотрели возможность матчить произвольное выражение с шаблоном, который соответствует одному "чему угодно", одному и более или нулю и более штук "чего угодно". Но что если я хочу чтобы это было не что угодно, а только выражения/объекты с определенными типами? Тогда после подчеркивания я могу напрямую указать этот тип. Как понять какой тип у выражения в языке с динамической типизацией? При помощи функции Head. Это значит что
Head[1] == Integer Head[1.0] == Real Head[1/3] == Rational Head[1 + I] == Complex Head["string"] == String Head[x] == Symbol Head[f[x]] == f Head[f[x][y][z]] == f[x][y] Head[Head[f[x][y][z]]] == f[x]И я могу взять любой результат, который возвращает Head и вставить его сразу после одного/двух/трех символов подчеркивания. То есть вот так:
MatchQ[1, _Integer] == True MatchQ[1.5, _Integer] == FalseТо есть это wildcard с проверкой типов, но не все так просто.
Вот например как можно проверить что у нас массив только целых:
MatchQ[{1, 2, 3, 4}, {__Integer}] == TrueА вот так я могу проверить, что у меня есть массив где сначала идут целы числа, потом рациональные, а потом комплексные. При этом комплексных может не быть совсем
MatchQ[{1, 2, 3, 1/3, 1/5, 1/7, I, I/3}, {__Integer, __Ratonal, ___Complex}] == True MatchQ[{1, 2, 1/5}, {__Integer, __Ratonal, ___Complex}] == TrueА еще wildcard можно связать с именем вот так:
MatchQ[f[1], f[x_]] == TrueВ MatchQ это бесполезно, но в функции, которая вытаскивает что-то по шаблону - это полезно:
Cases[{f[1]}, f[x_] :> x] (* => {1} *)Т.е. выше я связал значение 1 из выражения с символом x и смог извлечь это значение. Если использовать несколько подчеркиваний, то будет вот так:
Cases[{f[1, 2, 4]}, f[x__] :> {x}] (* => {{1, 2, 4}}*)Это небольшая часть паттерн матчинга в WL но нам пока достаточно. Теперь перейдем к главному - шаблоны можно использовать в в определениях функций, т.е. создав функцию вот так:
f[x_] := x + 1Я говорю математике о том, что как только она встречает выражение, которое матчится с:
MatchQ[f[1], f[x_]] == TrueТо сразу же происходит замена на правую часть определения функции - т.е. на x + 1. Определив так функция - я отсекаю все шаблоны, которые не матчатся с шаблоном f[x_]. Вызвав функцию на том, что не матчится ни с одним из шаблонов, которые были определены - ядро WL вернет результат ввода как есть. Т.е. например:
f[x_, y_] := x + y f[1, 2, 3] (* => f[1, 2, 3] без изменений*)Ну и возвращаясь к примеру из моего комментария выше шаблон
f[arr: {a1_Integer, ___Integer}, x_Integer] /; x < a1 := ...Означает, что функция определена только на последовательности аргументов, которая представляет из себя:
Первый аргумент список, где первый элемент списка обязательно целое число, а дальше может быть от нуля до бесконечности только целы чисел. Но я не стал писать a__Integer, чтобы связать ТОЛЬКО первый элемент списка с переменной a1, а не всю последовательность.
Второй аргумент - просто целое число.
После знака
/;идет условие, которое может использовать связанные переменные
Если у вас возникнут вопросы после моего объяснения или я объяснил слишком запутанно - то напишите пожалуйста, я готов ответить на любые вопросы!
faiwer
08.12.2023 03:19+2Спасибо за такой развёрнутый ответ (лови плюс в карму). Я думал это просто дичь уровня "исторически так получилось, что разные пласты костылей наложились друг на друга", а тут целая механика чего-то вроде variadic arguments в Typescript, только на стероидах.
KirillBelovTest
08.12.2023 03:19+3Спасибо большое за оценку моих трудов =)
Кстати мой любимый книжный пример - это сортировка пузырьком при помощи шаблонов:{5, 4, 2, 6, 3, 2} //. {fst___, x_Integer, y_Integer, rst___} :> {fst, y, x, rst} /; x > y//.- сокращение для ReplaceRepeated - функция которая выполняет повторяющуюся замену:>- правило замены/;- дополнительное условие для замены, но не обязательное
В итоге этот код на первом шаге делает следующее. Берет весь список и сравнивает его с образцом:
MatchQ[{5, 4, 2, 6, 3, 2}, {fst___, x_Integer, y_Integer, rst___}] /; x > yсвязываются
fst = <ничего>;x = 5;y = 4;rst = 2, 6, 3, 2. Оказывается что5 > 4, тогда условие выполнено и на место исходного списка вставляется:{fst = <ничего>, y = 4, x = 5, rst = 2, 6, 3, 2} == {4, 5, 3, 6, 3, 2}Далее этот процесс повторяется, но теперь первый и второй элемент не проходят условие и происходит новое связывание:
fst = 4;x = 5;y = 2;rst = 6, 3, 2и т.д. пока не окажется так, что заменять ничего.
ptr128
08.12.2023 03:19+7А с чего автор решил, что двоичный поиск будет быстрее, чем векторные SIMD инструкции? К тому же даже с двухканальным доступом к памяти, не говоря уже о четырехканальном, считать такой массив последовательно будет быстрее, чем прыгать по нему двоичным поиском.
mayorovp
08.12.2023 03:19+1А код на Javascript точно сможет задействовать векторные SIMD инструкции?
ptr128
08.12.2023 03:19Если не уверены, станет ли WASM использовать конкретные SIMD инструкции, можете проверить тут. Или воспользоваться внешней библиотекой. Например, Tensorflow, где эти инструкции точно поддерживаются.
mayorovp
08.12.2023 03:19А причём тут WASM? Речь-то шла про поиск в обычном массиве Javascript.
ptr128
08.12.2023 03:19-2JS - это язык. А чем и куда он компилируется Вы не указали. Значит для Вас это значение не имеет. Вот и компилируйте, например, в WASM, если хотите поддержку SIMD инструкций. К тому же я Вам предложил альтернативу в виде Tensorflow, которая уж точно SIMD использует.
Понятно, что на ESP32 не только JS, но даже C/C++ SIMD инструкции использовать никакой компилятор не станет. Потому что там их просто нет )
Вот я и не пойму, чего Вы хотите. Машинные инструкции возникают только после компиляции. От языка же их использование не зависит вообще - только от компилятора.
mayorovp
08.12.2023 03:19-2Приведите хоть один компилятор JS, способный задействовать SIMD-инструкции в простом цикле линейного поиска по массиву.
А пока вы не привели такого примера - ваш комментарий выглядит полной чушью.
Во-первых, компиляторов JS просто не существует, максимум есть JIT.
Во-вторых, нет абсолютно никакого смысла компилировать JS в WASM. WASM - это технология, позволяющая исполняться коду на разных языках в браузерах, но JS браузеры умеют исполнять и без неё.
В-третьих, чтобы задействовать SIMD-инструкции, нужно как минимум обеспечить гомогенность массива (что уже сложно в JS), а дальше нужно использовать либо явные языковые интринсики (которых в JS нет), либо автовекторизацию (про которую я в JS ни разу не слышал).
ptr128
08.12.2023 03:19компиляторов JS просто не существует
нет абсолютно никакого смысла компилировать JS в WASM.
У Вас раздвоение личности? Мало того, что пишете от том, что нет смысла компилировать тем, чего не существует, так еще и хотите использование SIMD - но не хотите один из вариантов, когда они будут использованы. )))
как минимум обеспечить гомогенность массива
Или, как я написал изначально, воспользоваться TensorFlow. Если бы Вы эту фразу сумели прочитать, то поняли бы, что в этом случае массив будет хранится в формате вектора TF, пригодного к обработке не только SIMD, но и GPU
ptr128
08.12.2023 03:19+2компиляторов JS просто не существует, максимум есть JIT
Node.js как раз и обеспечивает высокую производительность, благодаря компиляции напрямую в машинный код средствами V8.
MiraclePtr
08.12.2023 03:19-1в Node.js/V8 как раз именно JIT, про который пишет комментатор выше.
ptr128
08.12.2023 03:19Вы заблуждаетесь. V8 не использует при исполнении JS-программ байт-код или любой промежуточный код.
Это даже на Хабре подробно рассматривалось.
MiraclePtr
08.12.2023 03:19-1А где я говорил обратное? JIT - это не обязательно про байт-код.
ptr128
08.12.2023 03:19Если хотите изменить общепринятую терминологию, то рекомендую начинать не здесь, а, например, с обсуждения в Википедии:
"JIT-компиляция — технология увеличения производительности программных систем, использующих байт-код, путём компиляции байт-кода в машинный код или в другой формат непосредственно во время работы программы.
MiraclePtr
08.12.2023 03:19Раз уж решили потыкать меня в википедию, я в свою очередь тоже вам предлагаю не изменять общепринятую терминологию, а открыть ту же самую англоязычную статью, где прямым текстом сказано кое что другое:
In computing, just-in-time (JIT) compilation (also dynamic translation or run-time compilations)[1] is compilation (of computer code) during execution of a program (at run time) rather than before execution.[2] This may consist of source code translation but is more commonly bytecode translation to machine code, which is then executed directly.
(если что commonly - это не значит "всегда" и "обязательно").
(комментарий отредактирован, убрал ссылки, т.к. невнимательно прочитал)
ptr128
08.12.2023 03:19Я не тычу, а указываю, что Википедия намного лучше адаптирована для фиксации и смены общепринятых терминологий, чем Хабр. И как только Ваше предложение будет там принято, я тоже его стану придерживаться. А до тех пор, простите, придерживайтесь общепринятой терминологии Вы.
MiraclePtr
08.12.2023 03:19(комментарий отредактирован, убрал ссылки, т.к. невнимательно прочитал)
Кстати, для вас наверное будет интересно, что сами разработчики V8 прямым текстом пишут, что сначала компилируют JS в байткод, а уже потом в машинный код (и вот тут еще есть). То есть именно то, что вы пытались опровергнуть несколькими комментариями выше :)
MiraclePtr
08.12.2023 03:19V8 не использует при исполнении JS-программ байт-код или любой промежуточный код.
Расскажите это самим разработчикам V8, которые прямым текстом пишут ровно обратное:
All JavaScript code is first compiled to ignition bytecode, and executed by interpreting it. During execution V8 tracks how the program behaves, including tracking object shapes and types. Both the runtime execution metadata and bytecode are fed into the optimizing compiler to generate high-performance, often speculative, machine code that runs significantly faster than the interpreter can.
И вот тут еще есть:
Sparkplug compiles from bytecode rather than from JavaScript source, and so doesn’t have to worry about any of that.
ptr128
08.12.2023 03:19Вы путаете использование промежуточного байт-кода при компиляции, как в LLVM или V8, и интерпретацию байт-кода (JIT).
MiraclePtr
08.12.2023 03:19В V8 javascript-код парсится и транслируется в байт-код, после чего этот байт-код интерпретируется интерпретатором Ignition. Горячие места потом компилируются не-оптимизирующим JIT-компилятором (разработчики его сами так называют) SparkPlug из байт-кода в машинный код, более горячие места компилируются быстрым оптимизирующим JIT-компилятором (опять же, его так называют сами разработчики) Maglev из байт-кода в машинный код, самые горячие места компилируются самым ядреным оптимизирующим компилятором Turbofan из байт-кода в машинный код.
Ещё раз: разработчики V8 прямым текстом пишут, что интерпретируют байт-сами неоднократно называют то что они делают в V8 при выполнении JS-кода и компиляции его в машинный код при этом словом "JIT", что в своей документации на официальном сайте, что в коммитах в Git'е, что в презентациях, ссылки я уже выше приложил. Будете с ними спорить, они тоже путают?
JerryI
08.12.2023 03:19+1В JS не используется simd и вряд ли будет. Можете посмотреть SE, там в основном негативные ответы. В общем ближайшее к JS где это можно - WASM
ptr128
08.12.2023 03:19А через TensorFlow чем плохо? Если массив будет сразу в формате вектора, то должно быть все просто прекрасно.
JerryI
08.12.2023 03:19если я не ошибаюсь там компиляция в webgl. Просто так не попишешь, пересылка очень ресурсозатратная туда и обратно. Выигрыш будет только при достаточно большом количестве данных для расчета.
ptr128
08.12.2023 03:19Ошибаетесь. Через WebAssembly есть поддержка SIMD для JS https://blog.tensorflow.org/2020/09/supercharging-tensorflowjs-webassembly.html?m=1
wataru
08.12.2023 03:19+2Бинпоиск будет абсолютно точно быстрее. Потому что всегда можно вместо проверки восьми чисел SIMD-ом, просто посмотреть на одно последнее, чтобы понять, а надо ли все восемь пропустить. А бинпоиск еще больше чисел пропустит и еще меньше проверок сделает. Плюс, в SIMD-решении обработка хвостов короче регистра. И даже если вы совсем извернетесь и как-то симдом будете искать одно нужное число из заданных 8, то там явно больше одной операции. Надо получить результат векторного сравнения, найти среди результата самый правый 0 или 1. А потом еще отдельно проверить, а вдруг искомое число в следующем блоке. И эти проверки да на каждой восьмерке чисел.
ptr128
08.12.2023 03:19посмотреть на одно последнее
И вот тут у Вас сразу же возникает два цикла обращения к памяти вместо одного, даже при двухканальном доступе к ней. На более длинном массиве и с четыреханальной памятью можно так пролететь по производительности уже в четыре(!) раза.
Если сопоставить время цикла доступа с памяти с производительностью кеша CPU, то дальше уже и сравнивать будет нечего.
wataru
08.12.2023 03:19И вот тут у Вас сразу же возникает два цикла обращения к памяти вместо одного
Нет! Вместо того, читать и сравнивать 8 чисел через симд, даже если это все параллелизируется по всем каналам памяти и происходит за одну операцию доступа к памяти и сравнения, это не быстрее, чем посмотреть только на одно 8-ое число.
Если сопоставить время цикла доступа с памяти с производительностью кеша CPU,
На больших массивах бинпоиск, очевидно, будет на порядки быстрее. Потому что там во много раз меньше обращений к памяти, пусть каждое из них и будет помедленнее в бинпоиске. А еще сильно меньше сравнений.
На маленьких массивах доступ к памяти итак будет быстр в обоих случаях, потому что оно все целиком загрузиться в кеш еще на первом обращении к памяти.
ptr128
08.12.2023 03:19посмотреть только на одно 8-ое число.
А с чего Вы взяли, что посмотрев только одно число, решите задачу в общем случае?
На больших массивах двоичный поиск точно будет эффективней, так как избавит от необходимости вообще читать из памяти бОльшую часть массива. А когда весь массив может быть считан за одно многоканальное чтение из памяти - двоичный поиск может только навредить, приведя к лишним циклам обращения к памяти.
целиком загрузиться в кеш еще на первом обращении к памяти.
Если Вы обратились изначально к числу не в первом машинном слове, то далеко не факт. Зависит от выравнивания. И если потребуется обращение к первому машинному слову, возникнет ещё один цикл обращения к памяти.
Именно по этой причине в GCC qsort() не использует quicksort алгоритм для массивов короче четырех машинных слов. Выгодней считать его в кеш целиком одним обращением к памяти.
wataru
08.12.2023 03:19А с чего Вы взяли, что посмотрев только одно число, решите задачу в общем случае?
Ну вот как ваше предполагаемое SIMD решение работает? Читает весь массив по 8 чисел SIMD операциями и сравнивает их с искомым. Потом смотрит на массив результата и как-то за счет этого вычисляет тут ли есть искомый индекс. Как его можно ускорить: смотрим на каждое 8-ое число, за счет этого вычисляем, если в этой 8-рке искомый индекс. Это будет быстрее.
А когда весь массив может быть считан за одно многоканальное чтение из памяти - двоичный поиск может только навредить, приведя к лишним циклам обращения к памяти.
Нет, он и в двоичном поиске будет считан за одну операцию с памятью, потому что там весь массив - 64 байта условных и считается за раз при первом же обращении к памяти.
Если Вы обратились изначально к числу не в первом машинном слове, то далеко не факт.
Ну хорошо. Допустим. Тогда бинпоиск + обращение к 0-вому числу в массиве перед ним всегда будет не медленнее SIMD решения. Без этого 0-вого обращения, оно будет быстрее для массивов от 8 чисел.
ptr128
08.12.2023 03:19Ну вот как ваше предполагаемое SIMD решение работает? Читает весь массив по 8 чисел SIMD операциями и сравнивает их с искомым.
Это Вы придумали. А я решаю задачу из статьи. Где у меня положительные числа меньшие 255. Unsigned byte. И длина массива меньше 64 элементов, 512 бит. Поэтому я гружу в 512-битный регистр весь массив и одной командой VPCMPUB нахожу искомое значение.
wataru
08.12.2023 03:19Где в условии это сказано? Там есть один пример входных данных, но в условии это a - параметр функции. И уже в примерах есть и пустой массив и даже null вместо a.
Далее, вы не одной командой находите искомое значение - вы получите маску из 0 и 1. До 64 бит. И вам надо в этой маске найти крайний 0, или 1.
Потом, ну заменим 8 на 64, все мои рассуждения остаются в силе.
ptr128
08.12.2023 03:19Найти первый установленный бит - ещё одна машинная команда. Итого, у меня три машинных команды. А теперь попрошу Ваш код на ассемблере в студию. Вот и сравним.
wataru
08.12.2023 03:19Найти первый установленный бит - ещё одна машинная команда
Есть такая команда для симд регистров? Так что еще мов какие-то будут. Плюс отдельная проверка на не найденный ни один установленный бит.
Ну ладно. Согласен, в некотором очень узком диапазоне размера входных данных SIMD будет побыстрее.
ptr128
08.12.2023 03:19Есть такая команда для симд регистров?
VPLZCNTQ
И я сразу говорил, что выигрыш будет именно на предложенном в задании массиве. Однозначно на массиве размером свыше 512 бит (64 байта) выиграет двоичный поиск.
ptr128
08.12.2023 03:19+1Кстати, посчитал, на массиве любого размера, как только остаток при двоичном поиске оказывается меньше 512 бит (в большинстве случаев, даже 1024 бита), на завершающем этапе SIMD быстрее, чем продолжение двоичного поиска.
Sazonov
08.12.2023 03:19Задача крайне похожа на ту, которую даёт thinkcell. Только там на плюсах и надо написать такой контейнер поверх std::map. Функция поиска тривиальная, а вот со вставкой надо повозиться.
adeshere
08.12.2023 03:19Первый вопрос: уверены ли мы, что массив всегда отсортирован? Если есть чисто теоретический шанс, что нет - то это влечет целую кучу других вопросов
Второй вопрос: штатная ли ситуация - получение пустого массива? Если да, то я бы предложил подумать про вариант с двумя разными кодами возврата, чтобы вызывающей программе было проще различать ситуацию пустого массива и слишком маленького числа. Если, конечно, функция готовится для новой системы, а не рефакторит уже имеющуюся с жестко зафиксированным интерфейсом
Третий вопрос: типичный размер массива? В зависимости от этого, двоичный поиск может быть бессмысленным. Или, наоборот, не-двоичный...
Четвертый вопрос: насколько часто входное значение будет меньше min или больше max? Если это достаточно типичная ситуация, а размер массива сильно ненулевой, то я бы сделал две эти проверки еще на входе
Пятый вопрос: а как часто будет использоваться функция, и должна ли она работать за разумное время, или же это одноразовый кейс и важнее простота кода и скорость его отладки? С учетом этого, обсужу с интервьюером выбор алгоритма решения
Ну а уже после этого займусь кодированием, то есть напишу "обертку", внутри которой вызову чуть подправленную функцию из своей собственной библиотеки. Так как по какому-то недоразумению там
уже есть такая процедура
которая решает почти в точности эту задачу, только не с числами, а с датами ;-) Правда, мне там придется добавить integer в качестве допустимого входного типа, так как я пишу на фортране, и у меня нет обобщенного типа - все варианты надо расписывать явно. А дата сейчас в силу legacy-причин оформлена, как структура, а не как число. Соответственно, все операторы сравнения перегружены для работы с этой структурой. Так что в код функции заглянуть все же придется ;-)
ALexhha
08.12.2023 03:19+1У нас есть массив, отсортированный по возрастанию.
a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
...
Не нужно быть семи пядей во лбу, доктором математических наук, чтобы осмыслить его – поэтому вопрос достаточно честный ко всем кандидатам. Кроме того, его не требуется дополнительно объяснять – а это занимало бы драгоценные минуты нашего собеседования.
может я конечно тупой, но из поставленной задачи не понятно, что же автор хочет получить на выходе. Что за ближайшее наименьшее число ?
f(a, 12) = 12почему для 12 ближайшее наименьшее число 12, а не 10 ?
AxeFizik
08.12.2023 03:19+4Потому что нужно вернуть или X, или ближайшее наименьшее число или -1.
Но в условии не сказано, что ответ должен быть числом из массива, так что можно всегда возвращать X :)
zynaps76
08.12.2023 03:19Примерно понимая, чего от тебя хотят на собесе, перебор вариантов был такой:
Перебор значений в лоб: запорят за сложность (жрет cpu);
Можно откусывать левый/правый слайс и кормить им рекурсию: запорят за объем памяти + рекурсия на ровном месте (более сложный код);
Ну ок, тогда оперируем слайсами через индексы. Более оптимального ничего не придумал.
Тесты must have. Хоть наколеночные - любые.
Python code as is (не причесывал)
a = [3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21] NEGATIVE = -1 def middle(x, y): delta = y - x return int(x + delta / 2) if delta > 1 else x def f(arr, x): return find_near(arr, x) if arr and isinstance(arr, list) else NEGATIVE def find_near(arr, x): start, end = 0, len(arr) while end - start > 1: middle_idx = middle(start, end) mid_val = a[middle_idx] if mid_val == x: start = middle_idx break elif mid_val > x: end = middle_idx else: start = middle_idx val = arr[start] return val if val <= x else NEGATIVE if __name__ == '__main__': class EmptyObj: pass payload = [ [a, 12, 12], [a, 13, 12], [a, 2, -1], [a, 22, 21], [a, 3, 3], [a, 21, 21], [[], 1, -1], [None, 1, -1], [EmptyObj(), 1, -1], ] for a, val, exp_val in payload: res = f(a, val) print(f"f({a}, {val}) = {res} (exp: {exp_val})") assert res == exp_valЧем понравилось: абсолютно не надо готовиться. Задача вполне достойная, состоит из элементарных сущностей и не надо повторять вычернутые алгоритмы и структуры.
Вот прям унес бы к себе, но мы не мучаем по часу на 1 задачку. :( А тут со стрессом час запросто уйдет. У меня ушло 35 минут без какой-либо подготовки [и чтения статьи, разумеется], но я дома и был спокоен, как удав. )
Lexicon
08.12.2023 03:19+412 лет прошло, как пропагандирую отказ от задачек, неужели с ходом лет до людей так и не дошло, насколько это неэффективная трата времени? Я еще понимаю когда так отсеивают кандидатов гиганты, заставляя HRов рассылать задачки, но блин тратить свое личное время каждый раз на то, чтобы в сути "подбросить кубик"?
Неужели есть кто-то, кому нравится час сидеть уставившись в ноутбук, чтобы не отвлекать кандидата или лезть к кандидату в голову "а ты тооооочно проверил всееее варианты инпууута?".
- люблю на выходных решать задачки литкода
- несу презервативы и трудовой договорНаверняка, многие еще не дочитав задачку, знают, что, в сути хочет увидеть ее автор. Почему не получить устный ответ и не потратить 50 минут на что-то другое?
zynaps76
08.12.2023 03:19этот гугл: моего отца так нанимали, меня так нанимали и я так нанимать буду! они от шариков в боинге и чугунных люков, сравнительно не так и давно откзались. :)
ps тоже считаю, что задачку можно написать кодом, псевдокодом, голосом или рисунком. не вижу проблем продолжить диалог и накидать вопросов дальше.
Nurked
08.12.2023 03:19-5Если честно, вообще не понимаю зачем всё это в 2024 году. Это та же проблема калькулятора. Нас в третьем классе учили решать сложные арифметические задачи. При этом насмерть запрещали пользоваться калькулятором. Что в итоге? Я прочитал "Вы должно быть шутите, мистер Фейнман" и удивился тому, как это применимо в жзини. Я могу прикинуть, сколько будет треть от 25000. Да, это всё круто. Но когда дело доходит до дела, я лучше возьми в руки калькулятор. Или ещё лучше - excel spreadsheet, там даже проще.
Так же и подобные задачи в современном мире решаются просто запихиванием этого в чатГПТ.
def f(a, x): if not a or x is None: return -1 left, right = 0, len(a) - 1 result = -1 while left <= right: mid = (left + right) // 2 if a[mid] <= x: result = a[mid] left = mid + 1 else: right = mid - 1 return result if result != -1 else -1 # More complicated test cases test_cases = [ ([100, 200, 300, 400, 500, 600, 700, 800, 900, 1000], 350), ([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33], 28), ([10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500], 350), ([100, 1000, 10000, 100000, 1000000, 10000000], 555555), ([3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60], 28), ([5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100], 77), ([10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000], 875), ([1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100], 83), ([2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101], 66), ([10, 110, 210, 310, 410, 510, 610, 710, 810, 910, 1010, 1110, 1210, 1310, 1410, 1510, 1610, 1710, 1810, 1910, 2010], 2000) ] # Running the test cases test_results = [(array, x, f(array, x)) for array, x in test_cases] test_resultsArray: [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000], x = 350, Result: 300
Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33], x = 28, Result: 27
Array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500], x = 350, Result: 300
Array: [100, 1000, 10000, 100000, 1000000, 10000000], x = 555555, Result: 100000
Array: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60], x = 28, Result: 27
Array: [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100], x = 77, Result: 75
Array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000], x = 875, Result: 850
Array: [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100], x = 83, Result: 82
Array: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101], x = 66, Result: 65
Array: [10, 110, 210, 310, 410, 510, 610, 710, 810, 910, 1010, 1110, 1210, 1310, 1410, 1510, 1610, 1710, 1810, 1910, 2010], x = 2000, Result: 1910
Могу ли я сесть, и написать это сам? Да, вполне. На самом деле, могу сказать, что я бы потратил на это пару часов. Язык бы был другой, но какая разница. Но работа у меня почасовая, с упором на закрытые тикеты. Тратить два часа на такой алгоритм мне вообще будет бесполезно.
Хорош ли алгоритм ГПТшки? Не знаю, наверное нет. Тут все говорят об edge cases, и готовы устраивать дебаты по поводу этих кейсов. Но ты никогда не узнаешь, что у тебя есть edge cases, пока не посмотришь на приходящие данные. У тебя не может быть сферических коней в ваккуме. А когда ты их определишь, то можно тот же код запизнуть в ГПТ, и сказать ему поправить этот код.
Подобные вопросы сейчас - это как вычисление квадратного корня из двух тысяч без калькулятора. Да, могу. Но не буду. Ибо это не надо. Знать - знаю. Но действовать по этому поводу - бесполезно.
Это как чувак, который снял видео о том, как сделать куринный сендвич с нуля. Он пол-года выращивал всё от начала до конца. Начиная с пшеницы и курицы, заканчивая сбором морской воды, чтобы выделить соль. После сбора всех ингридиентов сам приготовил хлеб, и нарезал овощи. А после - заснял свою реакцию на камеру. И в итоге он сказал "Так себе", и со слезами выключил трансляцию. Он потратил толи три, толи шесть тысяч долларов на то, чтобы поддерживать ферму в рабочем состоянии и выращивать ингридиенты. Так делать можно, но мы этим не занимаемся, ибо мы уже изобрели способы делать это лучше и намного более эффективно.
wataru
08.12.2023 03:19+3Так же и подобные задачи в современном мире решаются просто запихиванием этого в чатГПТ.
Очень плохая идея. Никогда не спрашивайте у этих нейросеток что-то по теме, в которой вы не эксперт. Они вам очень убедительно и правдоподобно нагалюционируют бред, и вы никак этого не сможете заметить. И баг в таком сгенеренном коде будете искать неделями.
Nurked
08.12.2023 03:19-3Очень даже неправильный подход. ГПТ как раз и был тренирован на открытых данных из Реддита и Стака. Эта штука понарешала столько подобных задач, что ему уже тошнить начинает.
Попробуйте.
То, чего эта штука решать не умеет - это нетиповые реальные задачи, которые возникают у тебя в проде, когда ты пытаешься соеденить NEC SV9500 и Asterisk, или пытаешься загрузить проприетарную прошивку на самодельный принтер.
А все эти сферические кони в вакуме для ГПТ как орешки.
wataru
08.12.2023 03:19+4Очень смешно. А еще в этих открытых данных наверняка все расписано про кулинарию. И тем не менее эти нейросетки считают, что яйца можно расплавить.
Попробуйте
Пробовал. Иногда дело выдает. Иногда очень правдоподобный бред. Например, я попросил его найти максимум среди k последних элементов в потоке данных, а он нашел k-ый максимальный среди всех. И та и другая задачи - с литкода. И если ему переформулировать задачу вот прям как там написано (sliding window max), то он выдает решение. Если своими словами написть - нет.
Еще пробовал задачу, которую сам решал по работе и сейчас на интервью спрашиваю. Она фактически как задача с литкода, только не баянистая. Вообще бред получил в ответ.
Еще спрашивал по работе, например, как можно через виндовое апи MediaFoundation проверить, а не используется ли камера другим приложением. Оно выдумывает несуществующие классы и методы. Или еще хуже, выдумывает несуществующее поведение. Тогда код компилируется но делает не то, что ожидается. Но при этом красиво аргументирует и даже ссылки на документацию дает (правда по ссылкам написано совсем не то). Не справилось даже после подсказок, какой интерфейс использовать. А ведь это очень попсовая задача - гуглиться за 5 минут с примерами и кодом.
Если вот именно ваша задача достаточное количество раз именно в той или очень близкой формулировке встретилась в этих открытых данных, да еще там решения были правильные (вы, может быть, удивитесь, но бездумно копировать код со Стака - тоже плохая идея), то вам повезло. Если вам не повезло, то сеть не скажет "я не знаю". Она не способна это сделать по построению. Она вам нагалюционирует очень правдоподобный бред. Который вы, не будучи специалистом никак не разберете.
Dolios
08.12.2023 03:19+2Реализация переусложнена, поэтому содержит пляски с бубном. А еще там есть опасность переполнение получить при расчете mid.
def f(a, x): l, r = -1, len(a) while r - l > 1: mid = l + (r - l) // 2 if a[mid] <= x: l = mid else: r = mid return a[l] if l >= 0 else -1Не запускал, но всё должно работать.
Рекомендуется к прочтению вот это
Spaceoddity
08.12.2023 03:19-3f([], x) = -1 // Массив пустВот это я вообще не понял. У нас массив не может быть пуст по определению. У нас входные данные - это константа.
А уж если решили закладываться на валидацию всего и вся, то:
omaxx
08.12.2023 03:19+1Если вопрос звучит как "напишите функцию", а не "реализуйте алгоритм", то будет ли считаться читерством вариант просто использовать функцию bisect.bisect_right() из стандартной питоновской библиотеки?
ilih
08.12.2023 03:19+2Требования к функции делают её непригодной к использованию в реальной жизни: невозможно отличить ошибку от найденного значения.
f([-1], 0) == -1
Если бы возвращала индекс вместо значения, то имела бы право на существование.faiwer
08.12.2023 03:19+1Мне кажется, если это в более мягкой форме выразить во время собеседования, то это жирный плюс в оценке кандидата. Пока тут устраивают нелепые срачи
varvsletили рассуждают про кеш-промахи, нормальная сигнатура функции - это действительно важная вещь. Элемент продуктового мышления.
Sergey_zx
08.12.2023 03:19+1Самый простой и, при этом, быстрый метод это составление таблицы с выходными данными. Там можно ещё и оптимизировать по типу данных. Например, если диапазон значений в char, или short укладывается.
Для небольших не константных таблиц - динамическое обновление/генерация выходной таблицы.
И только для больших и не константных массивов, если к данным никак не применить хеши, то бинарный поиск.
MegaMANGO
08.12.2023 03:19Ну нанимайте теперь каждого второго школьника в гугл =). С этой задачей справится почти кто угодно. А вообще, стоит заранее уточнить, какие в среднем значения n: на относительно маленьких, как в примере, дв поиск будет или не сильно быстрее, или даже дольше. Заморачиваться с O(), как по мне, стоит только если в условии сказаны ограничения для n, а их особо-то и нет ????
bigov
08.12.2023 03:19В четвертой строке решения начальному значению лучше присвоить не 0, а значение нулевого элемента массива.
xxxDef
08.12.2023 03:19Почему никто не говорит о банальной возможной оптимизации границ поиска.
Если разница между первым числом в массиве и искомым (df=x-a[min]) меньше чем число элементов в массиве, то правая граница будет не на последнем элементе, а на расстоянии df от первого элемента. Слева границу можно подвинуть таким же образом. И делать это на каждой итерации двоичного поиска, а в некоторых случаях и вместо него
Dolios
08.12.2023 03:19А почему вы решили, что числа в масиве уникальные? Про это ни слова не сказано.
В вашем варианте сложность всё равно будет O(log n), но код будет тяжелее читать и понимать. Это нужно обосновать, иначе получим такую же преждевременную оптимизацию, как у автора, с выходом из цикла по условию
a[mid] == x.
ptr128
08.12.2023 03:19Хорошим вопросом был бы "а для какого количества чисел требуется такой поиск в массиве?". И тут возникает простор для индексации массива, например, BRIN
shasoftX
От синьора стоит ожидать что он вообще не будет заморачиваться с двоичным поиском. Потому что в условии задачи про скорость работы ничего не сказано.
souls_arch
При текущих исходных данных бинарка не только не нужна, но и вредна. В скорости работы и потраченных ресурсах разница будет ничтожна при текущем n (и, скорее всего, линейный поиск окажется и быстрее и менее жручим, чем бинарный при таком малом значении n). А вот читаемость и поддерживаемость кода ухудшится, задача займет дополнительное время на ненужный функционал, который, может быть, никогда не пригодится.
Первый вопрос, который бы задал я, это - а зачем нам это всё, какую цель мы преследуем и какие сроки имеем? И уже из ответа проистекало бы всё остальное.
MiraclePtr
Я даже больше скажу - линейный алгоритм очень CPU-cache-friendly, а когда данные не влезают в кэш - очень упреждающее-чтение-friendly, в отличие от "непредсказуемого" с точки зрения процессора бинарного поиска, который прыгает по памяти туда-сюда. Поэтому соглашусь, все очень неочевидно.
Greenback
От хорошего инженера ждут что код соответствует принципам:
reliability
scalability
compliance with requirements
Видно что первые два принципа похожи на NFR (non-functional requirements), но при этом они как бы вне техзадания (3й пункт), в котором может быть куча требований. Потому что любой код по умолчанию обязан быть надежным и скейлиться (учитывать time/../space complexity) если в требованиях явно не указано обратное.
larasage
В питоне линейный поиск - 0.070, приведенный автором "примитивный" - 0.053. При тысяче прогонов с x от 1 до 25
dyadyaSerezha
А разве пример на питоне?
Andy_U
На самом деле, вопрос правильный, так-как в Питоне фигурные скобки - это set.
Опс, Исправили, пока я писал?
dyadyaSerezha
И главное, минус поставили непонятно за что. А в питоне вообще нет понятия "нативный непрерывный массив" (только через модуль array).
larasage
переписал на питоне. Постарался один в один. Разумеется список, а не массив.
dyadyaSerezha
Список на питоне, это далеко не массив в С/С++/С# и т.п. Для питона почти всегда двоичный поиск будет быстрее.
Dolios
Про размер входного массива ничего не сказано же. Или я что-то пропустил? Ожидается, что вы как раз выясните все ограничения.
xSVPx
Вроде бы 10 элементов размер...
Dolios
Где? Это тестовый пример на котором задачу объясняли, реальный размер входных данных не написан. Как раз и ожидается, что один из первых ваших вопросов будет про реальные входные данные.
wataru
Не правда. Часто даже навороченный логарифмический алгоритм оказывается быстрее линейного при очень маленьких ограничениях. Например, вот тут уже при n=4 хитрый алгоритм оказывается быстрее. Я мерял.
Тут же самый примитивный бинарный поиск с одним сравнением. Для заданных 11 чисел бин поиск 100% быстрее. Потом, ничего не мешает написать отдельный вариант для коротких массивов и выбирать, какой из двух запускать в рантайме.
sasha_semen
Да откуда же сколько ресурсов возьмется на написание всех этих версий, а главное на их поддержку?
wataru
Если вам действительно важна производительность во всех случаях, то написать 2-3 разных алгоритма - не проблема. Если же вам достаточно, что ваша программа не станет вдруг падать при внезапном повышении нагрузки, то пишите только бинпоиск и не парьтесь.
sasha_semen
Вначале пишут что-бы работало, а потом уже профилируют и рефакторят узкие места. В SAP по крайней мере. Не думаю что в разработке для реального мира выделяют в три раза больше рабочего времени для написания двух-трех разных алгоритмов. Поэтому никто не будет писать двоичный поиск для разового поиска в небольших данных, а если и будут, то только там, где обычный будет ощутимо медленно работать.
wataru
В начале решают, что вообще и как будут писать. Выбор правильного алгоритма - это не преждевременная оптимизация. Да, обычно не пишут несколько версий, а пишут самый оптимальный алгоритм. А уже потом, если надо, допиливают с несколькими вариантами.
Если делать не так, то у вас будет тормозить вообще все равномерно.
sasha_semen
В идеальном мире? В реальном qsort никто руками не пишет. И оптимальный по производительности это не оптимальный вообще.
wataru
И бинпоиск для поиска в массиве никто не пишет, использут какой-нибудь lower_bound из стандартной библиотеки. Но вот когда бинпоиск нужен для поиска по ответу, когда у вас и массива-то никакого нет вообще - его приходится писать руками. Плюс на интервью хочется, все-таки, посмотреть как кандидат решает сложную задачку. Особенно в фаанге-то. Потому что какой-нибудь джон переложить выпускники курсов "мидл с нуля за 2 месяца" еще смогут, а вот что-то посложнее - уже нет. Поэтому приходится заставлять кандидата делать что-то интересное, даже если ему придется делать это редко (а ему придется, в гугле-то, по личному опыту заявляю).
Asker1987
Просто знай, что я уже раз в 20-й натыкаюсь на тебя в разных статьях и везде плюсую. Ты как воин света в одиночку защищаешь саму необходимость думать в программировании. Везде сплошные антиалгоритмисты. Никогда не думал, что доживу до этого момента, когда 99% программистов будут отрицать алгоритмы как явление...
sasha_semen
Каждому алгоритму своё мнение. Я вот с пяток сортировок с нуля смогу реализовать, а толку то? За последний год не то что сортировку - поиск в массивах из тысяч элементов не кодил. Это я еще молчу про хеш таблицы на миллионы записей, эти вообще только раз использовал.
Kelbon
Нет, именно для этого существует абстракция итераторов и STL. lower_bound / partition_point работает на random access итераторах за O(logN) (и forward итераторах с нюансами, но это тут неважно).
random access range очень легко выдумать например из последовательности чисел
wataru
Конечно, можно и стандартные lower_bound натянуть на глобус, но так обычно не делают. Один while написать и короче этих random-access итераторов, и читабельнее сильнее.
Asker1987
В реальном мире"программисты" вроде тебя до сих пор думают, что используется qsort из коробки. Меня даже на собеседовании один тимлид спрашивал про qsort в java collections, на что я ему ответил: там нет qsorta, я не проверял, но я точно могу сказать что это не qsort хотя у обоих сложность O(nlogn). На что он возмутился и утверждал, что qsort. Потом он погуглил и удивлённо обнаружил, что я прав. Откуда я знал? Да хз, просто для меня было очевидно, что при прочих равных надо использовать устойчивую сортировку, и в коробке не может быть qsort так как это неустойчивая сортировка. Но "программисты" не знают зачастую о свойствах устойчивости.
ЗЫ на работу меня тогда естественно не взяли. Задача на собеседовании - ответить достаточно хорошо, но чуть хуже чем интервьюер))
mayorovp
Насколько я помню, там double pivot introspecting sort. Который суть всё тот же qsort, только с оптимизациями.
Да у них в актуальном JDK даже файл реализующий алгоритм называется DualPivotQuicksort.java
Dolios
Нет, вначале выясняют, какого размера коллекция придет в проде.
dyadyaSerezha
Некорректный пример для полигона. Там куча других операций при поиске делается, которые перекрывают скорость доступа к собственно элементу массива.
wataru
"Другие" операции делаются и в наивном и в логарифмическом алгоритмах. В логарифмическом их гораздо больше, к тому же.
dyadyaSerezha
Еше раз - чем больше других операций, тем больше влияет собственно количество итераций, а не скорость чтения элемента из массива.
CrazyElf
Как-раз синьор таки должен сам спросить у интервьюера все параметры задачи, которые явно не прописаны. А которые прописаны - уточнить, правильно ли он их понял. Это тоже показывает уровень. Да, если в результате выяснится, что речь не идёт о гигабайтах данных, то можно и перебором решить. А если задача должна масштабироваться, то алгоритм уже другой. А если супер-масштабироваться, то опять другой. Но всё это идеальный синьор в вакууме должен выяснить и рассказать сам. В том то и суть правильного собеседования.
shasoftX
Уточнить на каком языке должен быть написан алгоритм, на каком устройстве запускаться и т.д. Т.е. времени на само написание кода у него уже и не останется. Зато будет отличное подробнейшее ТЗ для джунов.
CrazyElf
Как будто что-то плохое... )) В идеале задача и должна быть так поставлена, чтобы по ТЗ её уже любой джун мог запрограммировать )) Суть синьора во многом именно в том, чтобы хорошо декомпозировать и описать задачу. А что касается языка, то на таких собесах бывает вообще пишут код на псевдокоде в нотепаде. Потому что по конкретному языку и его теории - это отдельное собеседование, а тут про алгоритмы.
sasha_semen
Да, правильный синьер должен интервьюера загнать в тупик, ну или схантить на худой конец.
dyadyaSerezha
От сеньора стоит ожидать как минимум замечание, что типы параметров не определены и а.length вполне может выкинуть исключение, так же как и а[i], и любая операция сравнения (больше, равно, меньше), если эти операции не определены для данного переданного типа.
Автору: не хватает как минимум еще двух тестов - с передачей неправильных типов для первого и второго параметров.
akakoychenko
Неправильно;)
Синьор должен перед решением уточнить, что от него хотят, или, для чего и где это будет использоваться.