Компания Geekfactor cовместно с Getmentor.dev проводит программу подготовки к трудоустройству в зарубежные стартапы (бесплатно помогаем подготовиться к интервью и показываем резюме классным компаниям) — почитать о ней подробней и зарегистрироваться можно тут. Свой блог на Хабре мы хотим посвятить теме трудоустройства зарубеж и наша первая статья — про то, каких ошибок стоит избегать при прохождении технических интервью в зарубежные компании.
Недавно я провел свое 600-е собеседование на платформе interviewing.io (IIO). В этой статье я хочу рассказать о своем опыте, подходе к проведению собеседований и основных проблемах, которые встречались у кандидатов на технических собеседованиях.
Во время собеседований на платформе IIO мы оцениваем участников по трём критериям и ставим им от 1 до 4 баллов. 1 балл означает, что у кандидата все очень плохо в этой области, а 4 — все отлично. Обычно в начале собеседования я даю кандидатам 3 или 4 балла, и по мере продвижения встречи участники получают/теряют очки.
У каждого интервьюера, работающего на платформе, есть аспекты, на которые он обращает больше внимания. Я, например, больше всего ценю навыки общения и решения проблем, о чём и расскажу ниже.
Владение техническими навыками
В этой категории я оцениваю, насколько хорошо кандидаты умеют программировать на выбранном языке, есть ли у них серьезные трудности в составлении различных алгоритмов, нужно ли мне часто давать подсказки при написании кода.
Решение проблем
Здесь я оцениваю, насколько хорошо кандидат умеет разбивать задачу на составные части, вырабатывать стратегию по решению этих небольших задач и исправлять проблемы во время написания кода. Способность анализировать проблемы и решать их важна так же, как и навыки программирования. Может ли проблема поставить кандидатов в тупик, или же они могут самостоятельно найти её решение?
Общение
В действительности интервьюеры хотят услышать, как вы принимаете решение. Это очень важно при исправлении кода. Я обычно нанимаю специалистов для небольших команд или групп разработчиков. Поэтому для меня важно увидеть, что претендент умеет работать в команде и общаться.
Распространенные проблемы соискателей на основе моего опыта в качестве интервьюера
Я составил список основных проблем, которые встречаются у кандидатов во время технических собеседований не только на платформе IIO, но и в индустрии в целом. Надеюсь, вам пригодится.
Распространенная проблема № 1: поспешный переход к написанию кода
Эта проблема встречается у разработчиков разного уровня и различных специализаций, но все же чаще всего у специалистов «среднего» уровня с опытом работы 2–5 лет. Они выслушивают задачу, в течение примерно 30 секунд рассказывают о высокоуровневой структуре кода, а затем приступают к его написанию. Как будто речь идет о гонке на время и надо как можно быстрее завершить задачу — как можно быстрее добраться до финиша. Кто первый написал код, тот и победил.
Всё же правильно? Нет.
Сбавьте темп. Спланируйте, что вы будете делать. Расскажите о том, как вы решите поставленную задачу.
Люди, которые продумывают структуру кода на среднем уровне — с помощью псевдокода или просто заметок — затем тратят меньше времени на исправление ошибок. А вот те, кто сразу начинают программировать, сталкиваются с проблемой проектирования кода «на ходу». Они тратят много времени на рефакторинг, потому что им, например, нужно изменить передачу параметров или возвращаемое значение, или «ой, что здесь делает этот цикл?». Интервьюер быстро подмечает такие проблемы.
Конечно, тот факт, что вы потратите время на среднеуровневое проектирование кода не гарантирует успеха, но в долгосрочной перспективе может сэкономить время. Затем это время можно потратить на исправление ошибок.
К тому же я с позиции интервьюера хочу увидеть, как вы справитесь с задачей. Особенно если у вас собеседование в компании (в офисе или, как все чаще бывает в настоящее время, в дистанционном формате), потому что проведение собеседования в компании — процесс дорогостоящий. Мне нужно помогать всем кандидатам в равной степени. Если я вижу, что у вас есть предварительная структура, и замечу в ней ошибку, я могу задать наводящие вопросы, чтобы помочь вам понять, в чём проблема и подправить код на ранней стадии.
Если вы сразу начинаете программировать, я совершенно не понимаю, будет ли ваш код работать, а это ставит интервьюера не в самую лучшую позицию. Мне гораздо сложнее помочь, когда вы уже написали 100 строк на Java, и я только тогда понял, что в действительности делает ваш код.На одном из интервью в 2012 году я стал свидетелем того, как такое недостаточное планирование серьезно подвело претендента. Рекрутер привел ко мне кандидата, спросил не принести ли тому воды и вышел из кабинета. Я поздоровался, представился, и мы приступили к выполнению технического задания. Кандидат не поделился подробностями, не продумал структуру, сказал пару слов о высокоуровневом дизайне кода, ничего не записал и принялся сразу писать код на доске. (Это было мое второе и последнее собеседование с использованием доски. Ненавижу доски!) Рекрутер пришел через несколько минут, громко постучав в дверь, вошел в кабинет, передал бутылку воды и ушел. Кандидат поблагодарил за воду, открыл бутылку и начал пить. Затем его лицо исказилось — я увидел его испуганный взгляд. Он отвлекся, и у него совершенно вылетело из головы, что он хотел написать дальше, а я не мог ему помочь, потому что не знал, в чём состоит его идея. Кандидат потерял несколько минут, вновь обдумывая задачу, и начал писать код заново.
Но есть и «обратная сторона» медали: можно потратить слишком много времени на проектирование структуры кода и не успеть воплотить свой гениальный план в жизнь. Мне встречались и такие ситуации, когда кандидаты рассказывали о среднеуровневой структуре, делали заметки, вручную анализировали пример с помощью этих заметок, чтобы убедиться, что алгоритм работает, и у них оставалось всего несколько минут на выполнение задачи. Возможно, такие претенденты получат дополнительные очки за общение, но нам важно увидеть и то, как человек пишет код.
Какая же стратегия наиболее оптимальная?
Я рекомендую практиковаться. У вас должно уходить примерно 5 минут на продумывание высокоуровневого дизайна, еще 5 минут на планирование среднеуровневой структуры и оставшееся время — на написание кода. Есть и хорошая новость: чем больше вы прокачиваете навыки разработки дизайна и решения проблем, тем лучше вы справляетесь с подобными задачами. Поговорим об этом подробнее ниже.
Распространенная проблема № 2: «полумысли»
Мой многолетний опыт показывает, что это наиболее точный термин. Он означает, что вы начинаете что-то говорить вслух, а потом заканчиваете предложение про себя и меняете что-то в своем коде. Обычно это звучит так: «Возможно, я мог бы… а нет, лучше вот так».
Возвращаемся к моей придирчивости в плане навыков общения.
Интервьюеры хотят узнать, о чём вы думаете. Им важно понимать, как вы принимаете решения. Насколько правильны или неправильны ваши идеи? Почему вы хотите сделать что-то именно так? Возможно, вы заметили ошибку в коде? В чём она состоит?
Эта недостающая информация — настоящая кладезь для интервьюера. Нужно всего лишь несколько секунд, чтобы сказать что-то вроде: «Мне кажется… я думаю, что здесь можно применить поиск в глубину, но учитывая ___, я думаю, что лучше было бы ___. Как вы считаете?».
Конечно, это отнимет у вас две–три секунды, но вы поинтересуетесь моим мнением и получите поддержку. Мы сможем вместе рассмотреть какие-то варианты — и вот это называется командной работой. Я увижу, что мы сработаемся.
Распространенная проблема № 3: не задавать уточняющие вопросы
Я часто в качестве разминки задаю задачку. Например:
«У вас есть совокупность целых чисел. Напишите алгоритм, который находит два числа. В сумме они должны дать заданное значение. Когда алгоритм находит пару чисел, он перестает считать и показывает найденные значения. Если такие числа не найдены, возвратите два “пустых” значения».
Это отличный способ посмотреть, как вы работаете с алгоритмами и умеете строить предположения при решении задачи.
Я занимаюсь разработкой кода довольно долго. Если быть точным, с 1982 года. Ни в одном языке, на котором я когда-либо работал, не существует структуры данных, которая бы называлась «совокупность». Что же можно сказать о поставленной задаче?
Большинство кандидатов тут же ответят, что «совокупность» чисел — это массив. Конечно, можно решить эту задачу с помощью массива для хранения числовых значений. В этом случае трудоемкость алгоритма будет O(n^2), потому что вы будете перебирать данные экспоненциально: для каждого элемента нужно проверять оставшиеся числа. Но есть и более оптимальный способ решить поставленную задачу за O(n) время, выбрав иную структуру данных.
Не бойтесь и спросите, как лучше поступить. Если интервьюер ответит, что вам нужно решить самому, — это одно. В таком случае спросите, правильны ли ваши предположения. Спросите, есть ли альтернативный набор данных, который вы можете использовать в качестве тестовых случаев и которые могут повлиять на алгоритм.
Распространенная проблема № 4: предполагать, что интервьюеры устанавливают все правила
Подождите, что? Вы всё верно прочитали.
Да, вы находитесь на собеседовании. Но вы пришли, чтобы показать, что умеете работать в команде, а это прежде всего подразумевает открытое общение и дух сотрудничества. В первые несколько минут собеседования постарайтесь рассказать о своих ожиданиях, в том числе в плане общения и процесса работы.
Нет ничего плохого в том, чтобы обсудить эти вопросы с интервьюером:
«Во время работы над такими технически сложными заданиями я обычно одну–две минуты спокойно обдумываю проблему и делаю заметки. Чуть позже я буду готов(-а) поделиться с вами своими мыслями, чтобы узнать, чтобы вы думаете. Когда я пишу код, я также предпочитаю работать не спеша. Иногда я буду останавливаться, чтобы пояснить, что делаю. Затем мы сможем более подробно просмотреть код перед тем, как я запущу его. Вам это подходит? Совпадает ли ваше видение процесса работы над кодом с моим? Как вы предпочитаете общаться или взаимодействовать во время выполнения задания?».
Обещаю, вы станете звездой в глазах интервьюера. Большинство и вовсе не будут готовы к тому, что вы спросите у них, чего они ожидают. Это покажет, что вы умеете работать в команде. Вы сами задаёте условия: показываете себя с наилучшей стороны и одновременно демонстрируете, что учитываете мнение других. Вы сразу же говорите о своих планах и даете интервьюерам возможность для взаимодействия в процессе собеседования.
Распространенная проблема № 5: не просить о помощи
В качестве вашего интервьюера я могу лишь немного помочь вам во время выполнения задания. Естественно, я не могу просто сказать, что делать. Но я могу подсказать вам, вычесть один пункт из категории и посмотреть, справитесь ли вы в итоге с задачей. Если же молчаливо страдать и стоять на месте, тогда мы оба будем чувствовать, что это потеря времени.
Как профессиональный интервьюер и преподаватель в школе программирования, я отлично умею задавать наводящие вопросы, чтобы направить вас или ответить, но при этом не дать все решение.
Нет ничего плохого в том, чтобы признать, что у вас возникли трудности. Это не делает вас неудачником, а говорит лишь о том, что вы человек. Расскажите интервьюеру, что вы думаете и с какими проблемами вы столкнулись. Внимательно выслушайте ответ — возможно, вам дадут подсказку или посоветуют, что делать дальше.
Мои любимые полезные ресурсы
После собеседования на IIO мне нравится давать обратную связь и рекомендации о том, над чем стоит поработать. Обычно это занимает 10–20 минут, но иногда превышает час, отведённый на собеседование. Я использую это время, чтобы ответить на вопросы и более подробно обсудить разные аспекты. Я ОБОЖАЮ помогать людям на IIO. И вот что я могу порекомендовать.
Общение
Как же ужасно слушать свой голос в записи! Тем не менее, все собеседования на IIO записываются, и я часто советую кандидатам просмотреть последние несколько минут разговора, чтобы проанализировать обратную связь. Запись всегда можно остановить и вернуться к коду. (Записи, естественно, конфиденциальны и доступны только вам и интервьюеру).
Во время просмотра обратите внимание на то, что вы говорили и как. Во время работы над другими задачами найдите возможность записать себя, проговорите вслух проблему и затем снова прослушайте. Так вы научитесь более четко и ясно формулировать полноценные мысли.
Решение проблем и разработка кода на среднем уровне
Чтобы попрактиковаться в написании алгоритмов, чаще всего используют сайты HackerRank, CodeWars, LeetCode и т. д. (скоро в нашем блоге выйдет подборка таких сайтов — прим. переводчика). Только они не дают возможности научиться проектировать структуру кода.
Своим студентам я рекомендую Project Euler («Проект Эйлера»). Эйлер был математиком, поэтому на сайте представлены в основном математические задачи. Но вы можете изменить условия, чтобы вам было привычнее. Например, если вы не умеете находить простые числа, ничего страшного. Просто попробуйте найти число, которое делится на 17 без остатка, или что-то в этом роде.
Мне нравится Project Euler, потому что задачи описаны с помощью слов. Вам нужно продумать все: алгоритм, какую структуру данных использовать, особенно если вы разбиваете задачу на части.
Одна из моих любимых задач — задача № 19 из архива. В ней необходимо посчитать, сколько месяцев с января 1901 года по декабрь 1999 года начиналось в воскресенье. Вам дано количество календарных дней в каждом месяце, указано, что 1 января 1900 года выпало на понедельник, и показано, как вычислять високосные годы. Дальше дело за вами.
Чем больше вы решаете разные задачи, тем лучше вы распознаете паттерны — практика, практика и еще раз практика
Ещё один совет, который я даю студентам: решать каждое задание несколько раз. Наш исполнительный директор, Джефф Казимир, говорит, что нужно решать каждую задачу по десять раз. Но это много. Я бы сказал, что достаточно три–четыре раза, и вот почему.
В первый раз вы решаете задачу. Возможно, у вас возникнут трудности, но главное — решить задачу до конца. Во второй раз вы, возможно, придумаете новое решение, более оптимальное. Может быть и нет, но, по крайней мере, вы потренируетесь решать такого рода задачи. Теперь снова все стираете и решаете третий раз. Затем четвертый. Так вы запоминаете стратегию, с помощью которой необходимо выполнять подобные задания. «Мышечная память» поможет вам при решении других задач, когда вы начнете видеть схожие элементы: «Это же похоже на задачу о рюкзаке». Поскольку вы уже решали нечто подобное несколько раз, вам потребуется гораздо меньше времени на высокоуровневую и среднеуровневую разработку.
Одно из моих любимых заданий можно решить с помощью разных алгоритмов (поиск в глубину, поиск в ширину, динамическое программирование и т. д.). Если вы думаете, что можете решить задачу аналогичным образом, тогда решите ее три или четыре раза, используя каждый раз один из предложенных алгоритмов. Тогда вы НАУЧИТЕСЬ подмечать общие черты, и у вас будет широкий арсенал стратегий для решения заданий для технических собеседований.
Напоминаем, что компания Geekfactor помогает в трудоустройстве в крутые зарубежные стартапы на удалёнке и с релокацией. 2-го ноября стартует наша первая программа подготовки, организованная совместно с Getmentor.dev. Читайте подробности и регистрируйтесь (бесплатно и без смс).
Перевод подготовлен компанией Itrex.
Читайте также:
Комментарии (76)
anonymous
00.00.0000 00:00
Mihaelc
23.10.2021 11:20+6Заметил, что люди часто не знают, что значит экспоненциальный рост и называют таковым всё, у чего вторая производная положительная.
IBOOMeranGGI
24.10.2021 14:51+2Более того, даже с массивом эта задача решается за O(N*logN) и без дополнительной памяти, квадратная сложность - это наивная реализация, над которой даже думать не нужно)
third112
22.10.2021 19:31-7Ужас! — Картинка очень соответствует!
есть ли у них серьезные трудности в составлении различных алгоритмов
Я не один десяток лет программирую. Алгоритм можно знать, а можно не знать. Но "составлять"? Это как? — Нпр., автор упоминает поиск в ширину и поиск в глубину, если соискатель не знает, чем один отличается от другого, то вряд ли за час собеседования сможет придумать велосипед. Упомянуто решето Эратосфена для поиска простых чисел. Его нельзя не знать. И за отведенный час не придумать.
«У вас есть совокупность целых чисел. Напишите алгоритм, который находит два числа. В сумме они должны дать заданное значение. Когда алгоритм находит пару чисел, он перестает считать и показывает найденные значения. Если такие числа не найдены, возвратите два “пустых” значения».
Я занимаюсь разработкой кода довольно долго. Если быть точным, с 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) кажется слишком оптимистичной оценкой.
third112
22.10.2021 19:56+1PS Исправлюсь: совокупность из 2 чисел, м.б. названа совокупностью чисел. В этом случае надо их сложить, и если получим заданное значение, то вернуть эти числа, иначе вернуть два “пустых” значения. В этом случае можно оценить, как O(n) :)
uoak
22.10.2021 20:01+11у вас, кажется, все равно O(n^2), даже если цикл по j начинается от i+1 а не от единицы.
third112
22.10.2021 21:03-9Предстаим квадратную матрицу размером 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), но мне обычно важно на практике, что код не перебирает лишние цифры.light_and_ray
26.10.2021 13:44+1О(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) показывает полное непонимание того, что вы делаете
mayorovp
26.10.2021 15:58Я точно не помню, но своими словами O(f(n)) означает, что найдутся такие k1 и k2, что k1f(n) < f(n) < k2f(n).
Уточнение: это вы определение ϴ написали. Буква "O" задаёт только верхнюю границу (абсолютного значения).
third112
26.10.2021 20:43-2О(n^2/2-n/2) = О(n^2), и это следует из определения
Формально Вы правы, но когда улучшением алгоритма можно повысить скорость в 2 раза — это хочется отметить. В Вики отмечают:
Θ(n2.78041).
Θ(n2.7799).
В 1990 Копперсмит и Виноград[6] опубликовали алгоритм, который в модификации Вильямс Василевской[7] 2011 года умножает матрицы со скоростью O(n2.3727)
memoryallocator
22.10.2021 20:29+12Извините, но мне показалось, вы просто троллите.
Ваш код выполняется за 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
Ogra
22.10.2021 20:49+2s=set(arr) - это точно O(n) ?
pair in s - это точно O(1) ?
VorontsovIE
22.10.2021 21:59+2Это автоматически балансирующие размер хеш-таблицы.
Так что да, set(arr) - это точно O(n), если у объектов операцию хеширования писали прямыми руками.
И `key in set` - это точно O(1), если мы говорим про амортизированную сложность в среднем и не предполагаем, что тут произошла атака на алгоритм хеширования.
Politura
22.10.2021 20:30+2Но O(n) кажется слишком оптимистичной оценкой.
Первый проход по массиву: складываем все числа в hashtable
Второй проход по оригинальному массиву: для каждого числа смотрим, есть ли в хеш-таблице подходящее число для образования нужной суммы, или нет. Т.к. поиск в хеш-таблице стоит O(1), получаем итоговую сложность O(n)
Причем здесь "совокупность" и невозможность использования массива я не понял.
Ogra
22.10.2021 20:36-4Вставка в hashtable и проверка наличия не равны O(1), так что O(n) - слишком оптимистичная оценка.
Politura
22.10.2021 20:58+8Где именно не равны?
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)
DarthVictor
24.10.2021 01:29+1Первый проход по массиву: складываем все числа в hashtable
Второй проход по оригинальному массиву: для каждого числа смотрим, есть ли в хеш-таблице подходящее число для образования нужной суммы, или нет. Т.к. поиск в хеш-таблице стоит O(1), получаем итоговую сложность O(n)
Всё верно, хотя прохода хватит и одного. Достаточно в хэш таблице проверять только те числа, которые были до текущего. На оценку сложно это влиять, конечно не будет.
VorontsovIE
22.10.2021 22:02+4Ээээ.... Если вы самостоятельно не можете придумать алгоритм и лишь запоминаете готовые, это не значит, что никто не может. Особенно, если речь про такой незамысловатый алгоритм как решето Эратосфена.
Viacheslav01
23.10.2021 03:08+4"Эратосфена для поиска простых чисел. Его нельзя не знать. И за отведенный час не придумать."
Не знал, за час придумал)))
third112
23.10.2021 03:47А какие алгоритмы Вы при этом знали? Знание одних, помогает придумывать… Много еще алгоритмов изобрели?
Viacheslav01
24.10.2021 15:29+1Не, не, разговор шел, что не зная не придумать. Не в том, что надо придумывать велосипеды каждый раз, а в том, что придумать вполне можно, как его когда то придумал Эратосфен)))
Когда то изобрел двоичное дерево поиска, не потому, что умный а потому что когда учился вообще не было в доступе литературы нормальной, о том, что преподавали в университете вообще разговора не идет. Надо было быстро искать по уникальным идентификаторам uint32, пришлось выкручиваться. Потом когда переехал в питер и появился доступ к интернету нормальный, с удивлением узнал, что это оказывается классика )))
П.С. больше ничего такого не изобретал, просто вот два раза звезды сошлись )))
GarretThief
23.10.2021 21:18+2Упомянуто решето Эратосфена для поиска простых чисел. Его нельзя не знать. И за отведенный час не придумать.
И именно его за полчаса я придумал на городской олипмиаде по программированию в 10 классе, когда надо было выводить все простые числа до заданного числа. ( этом самом 10 классе я только начал в информатику, поэтому не знал алгоритмы, тк вы спрашиваете у всех)
bak
24.10.2021 02:05+1Алгоритм можно знать, а можно не знать. Но "составлять"? Это как?
Это когда читаешь условие задачи и понимаешь что не один готовый алгоритм не подходит, а чтобы решить нужно "составить" или "придумать" свой.
Например задачи которые решаются через динамическое программирование. Тогда можно не знать к примеру "Флойда — Уоршелла" и спокойно его реализовать.
third112
24.10.2021 02:26Это когда читаешь условие задачи и понимаешь что не один готовый алгоритм не подходит
Для этого нужно знать готовые алгоритмы. А еще полезно книжки посмотреть и в сетке поискать, у коллег спросить совета.
ganqqwerty
24.10.2021 03:08Ужас какой, зачем вам знать это самое решето?
third112
24.10.2021 03:18-1Решето Эратосфена является популярным способом оценки производительности компьютера.
ganqqwerty
24.10.2021 12:26+1Таааак, и вы постоянно оцениваете производительность компьютера таким образом?
third112
27.10.2021 05:52-1ИМХО чем примитивнее алгоритм, тем точнее оценка. Нпр., решение СЛУ по Гауссу не лучший тест.
some1else
24.10.2021 14:52+1Заканчиваем споры и сомнения. Если на входе "совокупность" - это упорядоченный двунаправленный список или массив, то просто движемся с двух концов, пока не получим нужную сумму. Если на данный момент сумма больше необходимого - двигаем правый элемент, если меньше - левый. O(n) в чистом виде
third112
25.10.2021 20:39Интересное решение. А как доказать его правильность или это эвристика?
mayorovp
25.10.2021 20:56А что тут доказывать-то? Для любого упорядоченного по возрастанию массива 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Это следует непосредственно из упорядоченности массива. А дальше алгоритм получается тривиально.
third112
25.10.2021 21:38-1Если 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.
mayorovp
25.10.2021 22:33А зачем должно следовать равенство? Задача алгоритма — выкинуть все варианты сравнений, где равенства точно не будет, и проверить оставшиеся.
Если мы знаем, что левый элемент совершенно точно не образует пару в оставшемся диапазоне — мы передвигаем левый указатель. И для правого элемента то же самое.
third112
25.10.2021 22:54-1выкинуть все варианты сравнений, где равенства точно не будет, и проверить оставшиеся.
Не все варианты сравнений проверяются. Почему не может быть, что на предыдущих шагах не выкинуто A[i], которое с очередным A[j] даст N?
mayorovp
25.10.2021 22:59Потому что выкидываются только те, которые заведомо не дадут такой комбинации.
third112
25.10.2021 23:24-2Не математично! Нужно показать, что не дадут. Я вижу что алгоритм работает. И не могу придумать контпримера, но это не значит, что его нет. Пока, извините, но похоже на эвристику.
mayorovp
25.10.2021 23:30Что значит "не математично"?
У цикла есть инвариант: все возможные комбинации, включающие элементы за пределами текущего диапазона, уже подсчитаны.
В начале цикла этот инвариант, разумеется, выполняется: за пределами диапазона ничего нет.
На каждом шаге инвариант сохраняется, потому что исключаемый из диапазона элемент заведомо не имеет неучтённой пары (внутри диапазона в силу условий выше, вне диапазона — в силу инварианта).
Применив сюда математическую индукцию получаем, что и в конце цикла инвариант также сохраняется. Но так как в конце цикла диапазон содержит всего один элемент — из инварианта следует, что все пары посчитаны.
Вам правда всё это расписывать требуется?
third112
25.10.2021 23:43-2Вам правда всё это расписывать требуется?
Правда, т.к. много лет работая с проф. математиками привык не доверять слишком общим утверждениям — "дьявол кроется в деталях" (с)
duke_alba
22.10.2021 20:32+1Идея правильная, но с примерами - не очень здорово. Я собирал несколько групп разработки, и всегда главным вопросом было: "как ты это будешь решать"? В процессе такого общения можно очень быстро понять: кто перед тобой.
webdi
22.10.2021 22:37+13Возможно я понял в чём ошибка подобных статей - людям не нравится, когда на них смотрят сверху вниз. Будь это соотношение "мудрый тимлид - немудрый соискатель" или "важный HR - неважный соискатель", или даже "гуру - ученик". На Хабре привыкли к более равным отношениям. А часто именно написавший статью вынужден доказывать её правильность.
И ещё (субъективно) что-то зачастили со статьями о "правильных собеседованиях".
ValentinDom Автор
22.10.2021 22:42Спасибо за мнение!
Для нас это первая публикация тут (не считая моих прошлых публикаций для Онтико :)).Расскажите, пожалуйста, о чём на тему HR Вам было бы интересно почитать? Может быть, есть примеры каких-то публикаций, которые Вам "зашли"?
webdi
22.10.2021 23:21+4И Вам спасибо.)
Возможно, была бы интересна критика HR'ов от HR'а. Лучше даже не "чистого HR", а критика от "тимлида в роли HR". Похоже, людей выматывают собеседования, особенно с разными малоквалифицированными HR'ами. Своего опыта на этот счёт пока не имею, работал в IT лет 15 назад, сейчас снова учусь.
Интересно есть ли услуга "тайный покупатель", но в роли "тайный соискатель", для проверки работы HR ?..
ValentinDom Автор
22.10.2021 23:26+1О-о, это мы можем. :)
Поделюсь идеей с коллегами - точно что-нибудь сделаем. :)
third112
22.10.2021 23:30+2Моя статья на близкую тему: "Проблема: возраст, опыт и трудоустройство" вызвала интерес.
Leka-SP
22.10.2021 23:25+8Если честно, после такого собеса, я бы просто ушёл по-английски, не в коем случае не сужу о низком уровне хард скиллов автора, а вот софт скиллс я бы подтянул, но это ИМХО.
third112
22.10.2021 23:46+2ИМХО хороший вопрос соискателю: о каком алгоритме хотите поговорить?
Допустим, он ответил: альфа-бета.
Говорите: ok, предположим, что я ничего об этом не знаю — объясните оновы и зачем нужен?
tommy_lee
23.10.2021 10:58+2И снова остался нераскрытым вопрос о реальной необходимости знаний решета Эратосфена для разработчика в компании, чей примитивный продукт можно сделать вообще на no-code платформе
panzerfaust
23.10.2021 11:21+11Распространенная проблема № 1: поспешный переход к написанию кода
На одном из интервью в 2012 году я стал свидетелем того, как такое недостаточное планирование серьезно подвело претендента
можно потратить слишком много времени на проектирование структуры кода
Господа, вы или крестик снимите или трусы наденьте. Планирование и проектирование - это то, чем люди занимаются в свои трудовые будни. Это все в человеко-часах и в человеко-днях измеряется обычно. Причем зачастую все и начинается с поделки из клея и желудей, а потом итеративно доводится до ума.
Вы ждете того же самого, но за 15 минут и применимо к очередной дурацкой задачке с литкода? И еще и пеняете, что человек в стрессовой ситуации делает не то, что вам нравится?
ganqqwerty
24.10.2021 03:06+2Я тоже всегда удивляюсь этому. В моей жизни разработчика вообще нет стресса, я бы иначе в пожарники пошёл. Откуда у меня возникнет способность пищать код под стрессом и таймером?
vgogolin
23.10.2021 13:24+8Умение решать задачи с leetcode говорит только об умении решать задачи leetcode и никак не связано с умением кандидата разгрести скольконибудьлетний проект со всеми его, не самыми эффективными, инфраструктурными решениями. Как мне кажется, интервьюеры про это часто забывают.
HellWalk
23.10.2021 14:23+5А может быть они об этом и не знают.
Когда-то тоже подгорало от дурацких вопросов на собеседованиях, сейчас же наоборот - радуюсь, что люди сами себя «раскрыли», в том плане, что они не понимают, чем хороший специалист отличается от плохого.
Жизненный опыт показывает, что намного проще немного побольше потратить время на поиск работы, чем ошибиться в выборе, и пойти работать в плохую компанию/команду.
ganqqwerty
24.10.2021 03:04+2автор говорит лично про себя. У многих других собеседующих другой подход, и в качестве причин отказа они называют именно «чересчур много вопросов», «слишком долго думал и успел решить только одну задачу», «слишком много подсказок понадобилось».
ValentinDom Автор
24.10.2021 14:53Мне нравится Ваше замечание. А есть ли способ "распознать", какой именно интервьюер перед тобой находится и что ему может быть нужно?
К сожалению, до сих пор встречаются интервьюеры, чьей целью может быть в принципе лишь самоутверждение перед кандидатом - как быть в таком случае?
i360u
24.10.2021 04:35+2Какой претенциозный бред. Человека на километр нельзя подпускать к процессу найма.
ValentinDom Автор
25.10.2021 14:41На тему задач с "Проекта Эйлера" статья как раз: https://habr.com/ru/post/585176/
longclaps
O(n^2) == экспоненциально? Однако.
GospodinKolhoznik
В военное время значение синуса может достигать 4, а экспонента принимать вид параболы.
alex_www
Именно такие собесодователи как в статье и отравили весь процесс найма.
SergMagpie
Это точно, автор один из тех заучек, для которых не важен результат, он наслаждается процессом. Когда на прошлой работе мы 10 дней готовили план подготовки плана, я принял решение валить оттуда.
kenoma
Похоже на кальку с английского, там степени экспонентами кличут.
exec77
В начале статьи так и написано, что это публикация перевода чужой статьи. К сожалению - бездумная.