Комментарии 76
O(n^2) == экспоненциально? Однако.
В военное время значение синуса может достигать 4, а экспонента принимать вид параболы.
Именно такие собесодователи как в статье и отравили весь процесс найма.
Похоже на кальку с английского, там степени экспонентами кличут.
Более того, даже с массивом эта задача решается за O(N*logN) и без дополнительной памяти, квадратная сложность - это наивная реализация, над которой даже думать не нужно)
Ужас! — Картинка очень соответствует!
есть ли у них серьезные трудности в составлении различных алгоритмов
Я не один десяток лет программирую. Алгоритм можно знать, а можно не знать. Но "составлять"? Это как? — Нпр., автор упоминает поиск в ширину и поиск в глубину, если соискатель не знает, чем один отличается от другого, то вряд ли за час собеседования сможет придумать велосипед. Упомянуто решето Эратосфена для поиска простых чисел. Его нельзя не знать. И за отведенный час не придумать.
«У вас есть совокупность целых чисел. Напишите алгоритм, который находит два числа. В сумме они должны дать заданное значение. Когда алгоритм находит пару чисел, он перестает считать и показывает найденные значения. Если такие числа не найдены, возвратите два “пустых” значения».
Я занимаюсь разработкой кода довольно долго. Если быть точным, с 1982 года. Ни в одном языке, на котором я когда-либо работал, не существует структуры данных, которая бы называлась «совокупность». Что же можно сказать о поставленной задаче?
Большинство кандидатов тут же ответят, что «совокупность» чисел — это массив. Конечно, можно решить эту задачу с помощью массива для хранения числовых значений. В этом случае трудоемкость алгоритма будет O(n^2), потому что вы будете перебирать данные экспоненциально: для каждого элемента нужно проверять оставшиеся числа. Но есть и более оптимальный способ решить поставленную задачу за O(n) время, выбрав иную структуру данных.
Если "перебирать данные экспоненциально", то трудоемкость НЕ будет O(n^2). Но откуда O(n^2)? Понятно, что a+b=b+a, следовательно вложенный цикл должен начинаться не с самого первого числа:
for i:=1 to n-1 do
for j:=i+1 to n do
if A[i]+A[j]=x then // x -- заданное значение
begin
a := i; b = j; exit; end;
a := 0; b :=0; // два “пустых” значенияНо O(n) кажется слишком оптимистичной оценкой.
PS Исправлюсь: совокупность из 2 чисел, м.б. названа совокупностью чисел. В этом случае надо их сложить, и если получим заданное значение, то вернуть эти числа, иначе вернуть два “пустых” значения. В этом случае можно оценить, как O(n) :)
Предстаим квадратную матрицу размером n на n. Код
for i:=1 to n-1 do
for j:=i+1 to n do
write(A[i,j])напечатает ровно n2/2-n/2 элементов. При этом есть теоретики, которые скажут, что
О(n2/2-n/2)= О(n2), но мне обычно важно на практике, что код не перебирает лишние цифры.
Даже на практике разница между ϴ(N2) и ϴ(N) намного важнее чем разница между N2 и N2/2
О(n^2/2-n/2) = О(n^2), и это следует из определения. Я точно не помню, но своими словами O(f(n)) означает, что найдутся такие k1 и k2, что k1*f(n) < f(n) < k2*f(n). Сама f(n) между двумя функциями может изгибаться как угодно
но мне обычно важно на практике, что код не перебирает лишние цифры.
Ассимптотическая сложность алгоритма не имеет к этому никакого отношения. Коэфиценты k1 и k2 могут быть сколь угодно большими или маленькими
Если хотите посчитать число операций, зачем вам вообще тогда нужно O? Просто считайте: n^2/2-n/2, а O(n^2/2-n/2) показывает полное непонимание того, что вы делаете
Я точно не помню, но своими словами O(f(n)) означает, что найдутся такие k1 и k2, что k1f(n) < f(n) < k2f(n).
Уточнение: это вы определение ϴ написали. Буква "O" задаёт только верхнюю границу (абсолютного значения).
О(n^2/2-n/2) = О(n^2), и это следует из определения
Формально Вы правы, но когда улучшением алгоритма можно повысить скорость в 2 раза — это хочется отметить. В Вики отмечают:
Θ(n2.78041).
Θ(n2.7799).
В 1990 Копперсмит и Виноград[6] опубликовали алгоритм, который в модификации Вильямс Василевской[7] 2011 года умножает матрицы со скоростью O(n2.3727)
Извините, но мне показалось, вы просто троллите.
Ваш код выполняется за O(n^2). То, что вложенный цикл начинается с i + 1, на оценку не влияет.
Решение за O(n):
val_to_pos = {x: i for i, x in enumerate(arr)}
for i, x in enumerate(arr):
pair = target - x
pair_pos = val_to_pos.get(pair)
if pair_pos == i and must_be_distinct:
continue
if pair_pos is not None:
return (x, pair)
return None
s=set(arr) - это точно O(n) ?
pair in s - это точно O(1) ?
Это автоматически балансирующие размер хеш-таблицы.
Так что да, set(arr) - это точно O(n), если у объектов операцию хеширования писали прямыми руками.
И `key in set` - это точно O(1), если мы говорим про амортизированную сложность в среднем и не предполагаем, что тут произошла атака на алгоритм хеширования.
Но O(n) кажется слишком оптимистичной оценкой.
Первый проход по массиву: складываем все числа в hashtable
Второй проход по оригинальному массиву: для каждого числа смотрим, есть ли в хеш-таблице подходящее число для образования нужной суммы, или нет. Т.к. поиск в хеш-таблице стоит O(1), получаем итоговую сложность O(n)
Причем здесь "совокупность" и невозможность использования массива я не понял.
Вставка в hashtable и проверка наличия не равны O(1), так что O(n) - слишком оптимистичная оценка.
Где именно не равны?
https://en.wikipedia.org/wiki/Hash_table
Time complexity in big O notation
Algorithm Average Worst case
Space O(n)[1] O(n)
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)O(n) будет только тогда, когда хранилище сильно несбалансированно и его надо увеличивать, или хеш-функция неподходящая. Если важна скорость, для частных случаев это можно учесть и сделать так, что O(1) будет практически всегда.
Поэтому в любых задачах где надо оценить сложность, для хеш-таблиц всегда дают оценку O(1)
Первый проход по массиву: складываем все числа в hashtable
Второй проход по оригинальному массиву: для каждого числа смотрим, есть ли в хеш-таблице подходящее число для образования нужной суммы, или нет. Т.к. поиск в хеш-таблице стоит O(1), получаем итоговую сложность O(n)
Всё верно, хотя прохода хватит и одного. Достаточно в хэш таблице проверять только те числа, которые были до текущего. На оценку сложно это влиять, конечно не будет.
Ээээ.... Если вы самостоятельно не можете придумать алгоритм и лишь запоминаете готовые, это не значит, что никто не может. Особенно, если речь про такой незамысловатый алгоритм как решето Эратосфена.
"Эратосфена для поиска простых чисел. Его нельзя не знать. И за отведенный час не придумать."
Не знал, за час придумал)))
А какие алгоритмы Вы при этом знали? Знание одних, помогает придумывать… Много еще алгоритмов изобрели?
Не, не, разговор шел, что не зная не придумать. Не в том, что надо придумывать велосипеды каждый раз, а в том, что придумать вполне можно, как его когда то придумал Эратосфен)))
Когда то изобрел двоичное дерево поиска, не потому, что умный а потому что когда учился вообще не было в доступе литературы нормальной, о том, что преподавали в университете вообще разговора не идет. Надо было быстро искать по уникальным идентификаторам uint32, пришлось выкручиваться. Потом когда переехал в питер и появился доступ к интернету нормальный, с удивлением узнал, что это оказывается классика )))
П.С. больше ничего такого не изобретал, просто вот два раза звезды сошлись )))
Упомянуто решето Эратосфена для поиска простых чисел. Его нельзя не знать. И за отведенный час не придумать.
И именно его за полчаса я придумал на городской олипмиаде по программированию в 10 классе, когда надо было выводить все простые числа до заданного числа. ( этом самом 10 классе я только начал в информатику, поэтому не знал алгоритмы, тк вы спрашиваете у всех)
Гениально! Но полагаете, что не нужно знать известных алгоритмов, а каждый раз придумывать свой? BTW в Вики ряд модификаций — какую Вы придумали?
Алгоритм можно знать, а можно не знать. Но "составлять"? Это как?
Это когда читаешь условие задачи и понимаешь что не один готовый алгоритм не подходит, а чтобы решить нужно "составить" или "придумать" свой.
Например задачи которые решаются через динамическое программирование. Тогда можно не знать к примеру "Флойда — Уоршелла" и спокойно его реализовать.
Ужас какой, зачем вам знать это самое решето?
Решето Эратосфена является популярным способом оценки производительности компьютера.
Заканчиваем споры и сомнения. Если на входе "совокупность" - это упорядоченный двунаправленный список или массив, то просто движемся с двух концов, пока не получим нужную сумму. Если на данный момент сумма больше необходимого - двигаем правый элемент, если меньше - левый. O(n) в чистом виде
Интересное решение. А как доказать его правильность или это эвристика?
А что тут доказывать-то? Для любого упорядоченного по возрастанию массива A верно следующее:
Если A[i] + A[j] < N, то для любого i < k < j верно что A[i] + A[k] < N
Если A[i] + A[j] > N, то для любого i < k < j верно что A[k] + A[j] > N
Это следует непосредственно из упорядоченности массива. А дальше алгоритм получается тривиально.
Если A[i] + A[j] < N, то для любого i < k < j верно что A[i] + A[k] < N
Если A[i] + A[j] > N, то для любого i < k < j верно что A[k] + A[j] > N
Из этих верных утверждений не следует (не видно, что следует), что A[i] + A[k] = N или A[k] + A[j] = N.
А зачем должно следовать равенство? Задача алгоритма — выкинуть все варианты сравнений, где равенства точно не будет, и проверить оставшиеся.
Если мы знаем, что левый элемент совершенно точно не образует пару в оставшемся диапазоне — мы передвигаем левый указатель. И для правого элемента то же самое.
выкинуть все варианты сравнений, где равенства точно не будет, и проверить оставшиеся.
Не все варианты сравнений проверяются. Почему не может быть, что на предыдущих шагах не выкинуто A[i], которое с очередным A[j] даст N?
Потому что выкидываются только те, которые заведомо не дадут такой комбинации.
Не математично! Нужно показать, что не дадут. Я вижу что алгоритм работает. И не могу придумать контпримера, но это не значит, что его нет. Пока, извините, но похоже на эвристику.
Что значит "не математично"?
У цикла есть инвариант: все возможные комбинации, включающие элементы за пределами текущего диапазона, уже подсчитаны.
В начале цикла этот инвариант, разумеется, выполняется: за пределами диапазона ничего нет.
На каждом шаге инвариант сохраняется, потому что исключаемый из диапазона элемент заведомо не имеет неучтённой пары (внутри диапазона в силу условий выше, вне диапазона — в силу инварианта).
Применив сюда математическую индукцию получаем, что и в конце цикла инвариант также сохраняется. Но так как в конце цикла диапазон содержит всего один элемент — из инварианта следует, что все пары посчитаны.
Вам правда всё это расписывать требуется?
Идея правильная, но с примерами - не очень здорово. Я собирал несколько групп разработки, и всегда главным вопросом было: "как ты это будешь решать"? В процессе такого общения можно очень быстро понять: кто перед тобой.
Возможно я понял в чём ошибка подобных статей - людям не нравится, когда на них смотрят сверху вниз. Будь это соотношение "мудрый тимлид - немудрый соискатель" или "важный HR - неважный соискатель", или даже "гуру - ученик". На Хабре привыкли к более равным отношениям. А часто именно написавший статью вынужден доказывать её правильность.
И ещё (субъективно) что-то зачастили со статьями о "правильных собеседованиях".
Спасибо за мнение!
Для нас это первая публикация тут (не считая моих прошлых публикаций для Онтико :)).
Расскажите, пожалуйста, о чём на тему HR Вам было бы интересно почитать? Может быть, есть примеры каких-то публикаций, которые Вам "зашли"?
И Вам спасибо.)
Возможно, была бы интересна критика HR'ов от HR'а. Лучше даже не "чистого HR", а критика от "тимлида в роли HR". Похоже, людей выматывают собеседования, особенно с разными малоквалифицированными HR'ами. Своего опыта на этот счёт пока не имею, работал в IT лет 15 назад, сейчас снова учусь.
Интересно есть ли услуга "тайный покупатель", но в роли "тайный соискатель", для проверки работы HR ?..
Моя статья на близкую тему: "Проблема: возраст, опыт и трудоустройство" вызвала интерес.
Если честно, после такого собеса, я бы просто ушёл по-английски, не в коем случае не сужу о низком уровне хард скиллов автора, а вот софт скиллс я бы подтянул, но это ИМХО.
ИМХО хороший вопрос соискателю: о каком алгоритме хотите поговорить?
Допустим, он ответил: альфа-бета.
Говорите: ok, предположим, что я ничего об этом не знаю — объясните оновы и зачем нужен?
И снова остался нераскрытым вопрос о реальной необходимости знаний решета Эратосфена для разработчика в компании, чей примитивный продукт можно сделать вообще на no-code платформе
Распространенная проблема № 1: поспешный переход к написанию кода
На одном из интервью в 2012 году я стал свидетелем того, как такое недостаточное планирование серьезно подвело претендента
можно потратить слишком много времени на проектирование структуры кода
Господа, вы или крестик снимите или трусы наденьте. Планирование и проектирование - это то, чем люди занимаются в свои трудовые будни. Это все в человеко-часах и в человеко-днях измеряется обычно. Причем зачастую все и начинается с поделки из клея и желудей, а потом итеративно доводится до ума.
Вы ждете того же самого, но за 15 минут и применимо к очередной дурацкой задачке с литкода? И еще и пеняете, что человек в стрессовой ситуации делает не то, что вам нравится?
Умение решать задачи с leetcode говорит только об умении решать задачи leetcode и никак не связано с умением кандидата разгрести скольконибудьлетний проект со всеми его, не самыми эффективными, инфраструктурными решениями. Как мне кажется, интервьюеры про это часто забывают.
А может быть они об этом и не знают.
Когда-то тоже подгорало от дурацких вопросов на собеседованиях, сейчас же наоборот - радуюсь, что люди сами себя «раскрыли», в том плане, что они не понимают, чем хороший специалист отличается от плохого.
Жизненный опыт показывает, что намного проще немного побольше потратить время на поиск работы, чем ошибиться в выборе, и пойти работать в плохую компанию/команду.
автор говорит лично про себя. У многих других собеседующих другой подход, и в качестве причин отказа они называют именно «чересчур много вопросов», «слишком долго думал и успел решить только одну задачу», «слишком много подсказок понадобилось».
Какой претенциозный бред. Человека на километр нельзя подпускать к процессу найма.
На тему задач с "Проекта Эйлера" статья как раз: https://habr.com/ru/post/585176/
Пять распространенных проблем кандидатов (по результатам 600 технических собеседований)