Уверен, ты уже был на алгоритмическом собеседовании. А если нет, то напомню: это крышесносный квест, где тебе предстоит выложить всю подноготную университетской программы, блеснуть знанием структур данных — и за час решить пару задач.
Начинаю с юмора, потому что лично у меня, как у интервьюера, внутри всё сжимается, когда вижу, как кандидаты совершают одни и те же ошибки.
Так вот. Я расскажу тебе историю одного показательного собеседования, чтобы ты не наступил на те же грабли — и зашёл на алгоритмическое собеседование не с одной, а сразу с трёх ног.
Ну всё, погнали.
История: “Я художник я так вижу”
Как обычно перед собеседованием я сел изучить прошлые собеседования кандидата, чтобы задачки не повторялись…
Да, да. Если ты собеседуешься в большую компанию уже не первый раз, то 100% у тебя есть фидбек с прошлых собеседований, поэтому старайся не светить чем не нужно, чтобы не остаться увековеченным во внутренних сервисах компании как ошалелый кандидат.
И каково было моё удивление, когда кандидат все разы отлично проходил собеседование и не соглашался только на финальных этапах. Зачастую у кандидатов есть 1–2 провала, а тут всё без запинки.
Я очень обрадовался, потому что люблю сильных кандидатов. С ними можно обсудить вопросы за рамками стандартных обсуждений, а это как глоток свежего воздуха после десятка однотипных собесов.
И вот собеседование…
Зашёл кандидат, по правилам внутреннего документа я огласил все правила собеседования — и мы начали.
Вот условие задачки:
Дано две строки —
sиt. Нужно вернуть:true, если изsможно получитьt, удаляя символы (но не меняя порядок).
Пример 1:
Ввод: s = "abcde", t = "ace"
Вывод: true
Пример 2:
Ввод: s = "hello", t = "le"
Вывод: false
Быстрое чтение условия про себя… И звучит фраза: «Мне нужно 2–3 минуты, чтобы нарисовать на листочке идею решения, и потом я расскажу».
Для меня это вполне стандартно — дать кандидату время на подумать, поэтому я без проблем согласился.
Но вот проходит 5 минут — и он всё никак… Я уже начинаю задавать дополнительные вопросы: «Расскажи основную мысль, к чему пришёл?..»
Он в ответ просит ещё минуту, но и тогда он не готов.
Спустя 10 минут от начала я уже говорю: «Прошло достаточно времени, давай расскажи, к чему пришёл, а если нужно будет время — подумаешь дальше».
И тут он начинает: «Я считаю, что тут нужно использовать КМП или Z-функцию. Я отдаю предпочтение Z-функции, потому что она может обрабатывать в потоке, и если будет дальнейшее усложнение, то будет проще работать с ней…»
Почитай, если не знаешь, что такое КМП и Z-функция:
В общем, кратко.
Оба алгоритма помогают искать подстроки в строках и делают это линейно, т.е. за O(n). Казалось бы — чем это отличается от обычного find в твоём любимом ЯП или findAll?
И КМП, и Z-функция найдут все 3 вхождения строки t в строку s.
А вот классический findAll — только 2. Он просто не обрабатывает пересечения, поэтому одну из подстрок пропустит.
В общем, КМП и Z-функция — прикольные штуки. Но! Они требуют дополнительную память O(n), что делает их уже не такими универсальными и «лёгкими», как кажется на первый взгляд.
Да-да. Как ты уже понял — тупую задачку на два указателя попытались вскрыть мега-гига-ультра перочинным ножиком. И, само собой, ничего не вышло…
На собесах я уже воин матерый, поэтому просто сказал: “Давай условие перечитаем на всякий случай”.
Кандидат быстро перечитывает… И раздаётся смех. Сначала я подумал, что это я не сдержался. Но, по итогу, у него всё оказалось в порядке с самоиронией. Поэтому после двух минут безудержного смеха он быстро рассказал идею решения и написал код:
# Время: O(n+m)
# Память: O(1)
def fuzzy_match(s: str, t: str) -> bool:
p1, p2 = 0, 0
while p1 < len(s) and p2 < len(t):
if s[p1] == t[p2]:
p1 += 1
p2 += 1
return p1 == len(s)А сама задачка есть тут: https://algocode.io/courses/algo-big-tech/problem/fuzzy-matching
P.S. там просят сначала регистрацию
Переходим к следующей задаче
Решение первой задачки было столь изматывающим для кандидата, что его можно сравнить с раундом на боксёрском ринге, который длился 20 минут, а теперь, после небольшого перерыва, снова начинается схватка, а на таймере остаётся всего 40 минут…
И кандидат уже на опыте начинает зачитывать вопросы вслух, а не про себя:
Дан массив
nums, отсортированный в неубывающем порядке, и числоtarget. Нужно вернуть начальную и конечную позицию числаtargetв массивеnums. Если числоtargetотсутствует, вернуть[-1, -1].
Пример 1:
Ввод: nums = [1,2,2,2,2,2,5,5,8,19], target = 2
Вывод: [1,5]
Объяснение: индексация элементов начинается с нуля
И тут сразу кандидат, как из пулемёта, начинает от А до Я раскладывать решение: “Будем для решения использовать бинарный поиск. Найдём …”
Пулемётная очередь быстро закончилась, и настал ступор. Было видно по рассуждениям и тому, что он пытался сказать, что уж очень хочется ему засунуть всё в один бинарный поиск, но никак у него это не получалось.
В такие моменты люди часто говорят, что уже решали эту задачку и нужно лишь вспомнить…
Дал я 2–3 минутки на подумать, а потом спрашиваю:
Я: “А сколько бинарных поисков будем делать?”
Очень робко:
Кандидат: “Два?..”
Я уверенно говорю, что да, давай сделаем двумя, и прошу рассказать, как будем действовать дальше…
Ещё минуты за 2–3 получилось ± рассказать, как это будет работать, и оценить Big O.
У нас оставалось много времени, поэтому я задал доп. вопрос, который обычно спрашиваю, но не беру во внимание, даже если кандидат не отвечает:
Я: “Бинарный поиск ищет элемент в массиве за O(log₂ N), но можно же использовать тернарный поиск — и тогда будет работать за O(log₃ N), или квадро… Тогда за O(log₄ N)… Так?”
Кандидат: “Ну да…”
Я: “Так может, возьмём квадро-поиск? Получится оптимальней… Или может вообще N-арный написать — тогда получится O(logₙ N), а это, как известно, равно 1, и получаем O(1)!”
Кандидат: “Нет…”
Он не мог понять, в чём прикол. Видно, что он понимает, что это дичь, но объяснить не может.
Подумай, в чём тут ошибка, а потом смотри ответ.
А тут всё просто: во-первых, тернарный поиск обычно используют для других целей, но даже если мы его адаптируем, то получится O(2 × log₃ N); если квадро — то O(3 × log₄ N); а если N-арный, то O((N−1) × logₙ N), — и это уже O(N), то есть обычный линейный поиск.
В Big O принято опускать константу, поэтому O(2 × log₃ N) становится O(log₃ N).
И как раз за счёт опускания этой константы получилось проверить, может ли кандидат, понимая идею бинпоиска, попытаться придумать хотя бы воображаемое решение — но при этом правильно оценить его асимптотику.
А константа появляется, потому что в тернарном поиске у нас уже 2 серединных элемента и нужно сравнить каждый с элементом в оригинальном массиве. А в квадро поиске 3 элемента и так далее…
Через минутку я сказал, что это не очень важный вопрос, и мы вернулись к задаче… Теперь предстояло самое страшное: написать код. Особенно в бинарном поиске — это целое испытание!
Началось всё примерно с такой реализации:
def binary_search(arr: List[int], target: int, left: int, right: int) -> int:
# ...
mid = (left + right) // 2
if arr[mid] == target:
return mid
# Если элемент меньше — ищем в левой половине
elif target < arr[mid]:
return binary_search(arr, target, left, mid - 1)
...
def find_first_and_last(nums: List[int], target: int) -> List[int]:
...Как только я начинаю видеть рекурсию, я сразу задаю встречный вопрос: “Давай представим, что мы дописали решение. Сколько оно займёт по времени и памяти?”
Кандидат: “O(log N) по времени и O(1) по памяти”
Я: “Хорошо, а накладывает ли рекурсия какие-то доп. расходы на время или память?”
Кандидат: “Ааааааааа… Да, получается O(log N) по времени и O(log N) по памяти из-за стека.”
Я: “Да, тут не состыковочка: при обсуждении идеи решения выяснили, что должно быть O(log N) по времени и O(1) по памяти.”
Видно было, как кандидату становилось всё грустнее, и мне хотелось сказать: “Забей на всё, давай ты мне просто расскажешь, как это работает, я тебе помогу написать шаблончик, подебажимся в голове и пойдём в ближайший бар обсуждать графы, DFS, BFS и всё остальное…”
Но есть регламент. Да и зачастую собес я провожу не один, а ещё заходят ребята, которые только учатся проводить собеседования… Так что я начал просто наблюдать за страданиями кандидата.
Я не знаю, сколько прошло времени, но смотреть на кандидата, который понимает, как это работает, но не может написать — это самое ужасное.
Да, я могу подсказывать идеями, направлять, но это заняло слишком много времени.
Когда оставалось 2 минуты, я сказал: “Мы с тобой круто продвинулись, но не успеваем написать решение. Давай представим, что ты реализовала уже функции поиска первого и последнего вхождения. Твоя задача — написать только основную логику, как ты возвращаешь ответ:”
from typing import *
def binary_search(nums: List[int], target: int) -> int:
# возвращает позицию последнего вхождения target или -1
# считаем, что уже написано
...
def search_first_target(nums: List[int], target: int) -> int:
# возвращает позицию первого вхождения target или -1
# считаем, что уже написано
...
def search(nums: List[int], target: int) -> List[int]:
# нужно написатьПосле чего было быстро написано:
from typing import *
def binary_search(nums: List[int], target: int) -> int:
...
def search_first_target(nums: List[int], target: int) -> int:
...
def search(nums: List[int], target: int) -> List[int]:
if len(nums) == 0:
return [-1, -1]
l = search_first_target(nums, target)
r = search_last_target(nums, target)
return [l, r]Может показаться — а нафига я это сделал и не дал 2 минуты человеку подумать?
И на то есть причины:
За это я повысил балл, так как наличие финального решения — даже если не реализованы какие-то функции, но оговорено ожидаемое поведение — даёт плюсик к оценке.
Не было шансов успеть, потому что функции содержали бы много типичных ошибок.
Самое обидное для меня — писать негативный фидбек кандидату, когда ты видишь, что он старался изо всех сил.
Я круто провёл этот час. Несмотря на то, что задачки не были решены, общение было очень ламповым и приятным. С мимолётными шутками и приколами. Мы были как будто на одной волне, и я видел в кандидате себя трёхлетней давности…
Что ж, наше интервью закончилось, и я выставил свой фидбек… В моей компании проставляется грейд кандидату — от Junior до Senior. И крайне редко ставится полный “незачёт”. Но грейд был достаточно низкий по сравнению с ожиданиями кандидата, а алгоритмы являются блокирующей секцией к высокому грейду.
И даже следующие идеально пройденные секции не помогли бы — и как я проследил дальше рекрутеры вернулись с отказом.
Вывод
После этой истории у меня долго вертелась в голове мысль: «Да ведь он всё понимал. Всё знал. Просто не дожал».
И поэтому хочу поделиться с тобой советами из своего опыта, чтобы ты точно смог пройти алгоритмическое собеседование в компанию мечты и воплотил в жизнь много крутых проектов:
Не пытайся вспомнить решение задачи, даже если уже её решал. Это только мешает: вместо того чтобы просто решить ещё раз, ты тратишь много сил и “надежд” на то, что тебя осенит и ты вспомнишь давно утраченные знания.
Проговаривай всё вслух. Вообще всё! Так интервьюер сможет раньше тебе помочь и не даст пойти не туда. Не знаешь, как решить задачу? Перебирай вслух все подходы: DFS, BFS, 3 вида движения указателей, хеш-таблицу… Интервьюер сам может тебя остановить, как только ты попытаешься уйти с темы, которая имеет отношение к решению.
Заранее вспомни основные темы: два указателя, массивы, хеш-таблица, скользящее окно, точки и отрезки, бинарный поиск, стек, односвязный список, деревья и немного графов. Прорешай по 1 задачке на каждую тему за день-два до собеса — и тебе точно будет что сказать по каждой из тем.
Задавай дополнительные вопросы. Сильные кандидаты всегда в самом начале спрашивают все вводные, чтобы с первого раза рассказать верную идею решения и написать код. В общем, действуют как снайперы. Примеры вопросов: «У нас есть сложение элементов. Есть ли гарантия, что нет переполнения? Нужно ли его обрабатывать?» или «В условии нет ничего про сортировку, а в примерах она есть. Это совпадение или нет?»
Пламенный респект
Если читаешь эту статью и узнал себя как кандидата — мой респект тебе, бро! Знай — всё получится, пусть и не сразу. И больших тебе офферов!
А я удаляюсь, оставляя ссылочку на свой ТГ-канал, где рассказываю про алгоритмы:
Комментарии (41)
MonkAlex
01.06.2025 12:24У меня есть классический вопрос к тем, кто проводит алгособесы. Сколько раз вы лично сталкивались с ошибками такого рода в работе? Какого порядка улучшение вы получили при исправлении ошибки?
И сразу отвечу на свой вопрос - сталкивался дважды за 10 лет. В одном случае улучшение было с 30 секунд до "меньше секунды", в другом с 0 на 0, т.к. объем входных данных был незначительный.
FatMR Автор
01.06.2025 12:24Привет! Полностью согласен с Вами, что алгоритмы нужны далеко не везде. Но есть места, где без них никак. Например, в Huawei моя работа была основана на алгосах
И второй момент, он скорее более общий: алгоритмические собесы - часть текущего флоу. Не говорю, что это плохо или хорошо, но такова реальность. Можно не ходить в компании, где они есть, а можно готовиться - выбор каждого
MonkAlex
01.06.2025 12:24На вопрос вы не ответили, к слову.
FatMR Автор
01.06.2025 12:24Давайте еще раз посмотрим на вопрос в статье: неправильное понимание условий задачи. Это встречается регулярно: приходит бизнес, просит то и то. По итогу выясняется, что это технически сделать супер сложно и приходится договариваться.
А еще бывает, что обсудишь и сделаешь, а потом закидывают тебе доп требования, которые ломают все прошлое.
Но согласен, что в чисто виде такие ситуации не супер часты
Lite_stream
01.06.2025 12:24Почти уверен, что смысл алго задач на собесах не в этом.
Скорее всего к этому вообще можно как в чёрному ящику относится: вероятно крупные компании замеряли что-то вроде такого: брали 2 выборки людей, тех кто прошёл алго секцию и тех кто провалил её, а потом замеряли долю тех, в обеих выборках, кто, например, прошёл испытательный срок. Полагаю, что в группе тех, кто справился с алго секцией доля тех кто прошёл исп. срок заметно больше. Понятно, что можно что угодно замерять, необязательно в качестве величины брать число прошедших исп. срокFatMR Автор
01.06.2025 12:24Возможно, это имеет место быть. Тут, возможно, играет фактор, что к данным собесам нужно готовиться. Как результат, у тебя больше выдержка и терпения. Это лишь мои домыслы, но как гипотеза
vadimr
01.06.2025 12:24Тут такое дело. Понимание теории и умение писать программы – это анализ и синтез, они не всегда бывают проявлены в одном человеке. Можно очень хорошо знать теорию и быть по своей природе неспособным к написанию кода. Таким людям дорога в преподавание :)
FatMR Автор
01.06.2025 12:24Согласен, есть ребята, которые шарят за теорию и могут рассказать про то, как устроена куча, графы, но не могут закодить простую задачку.
Очень жалко ставить таким ребятам No Hire
Keeper21
01.06.2025 12:24Не думали вообще отменить алгоритмические собеседования?
FatMR Автор
01.06.2025 12:24Давайте посмотрим в историю: алгособесы пришли из США. Но в США учат их проходить в вузе.
У нас же такому учат посредственно и не везде, а спрашивают многие компании.
Глобально считаю, что навык полезный, потому что знание алгоритмов позволяет оптимизировать работу сложных систем и не допускать работу критических оптимизационных ошибок.
Я бы изменил формат собеса, чтобы он проходил только в теор форме, но рассматривалось больше кейсов. Так как важнее понимать уровень погруженности кандидата в алгоритмы, чем написание под взором другого человекаvadimr
01.06.2025 12:24Так и у нас учат в вузе, и вполне сравнимо с американскими.
Про теор. форму тоже не согласен, без практики она мертва. Лучше безобразная, но работающая программа, чем много верных наблюдений.
А погруженность в алгоритмы в большинстве случаев можно оценить по диплому.
FatMR Автор
01.06.2025 12:24Учился в ВШЭ, у нас был курс. Но не преподавали, а как их решать в ограниченное время и с учетом такого стресса
Теория и практика: дело вкуса. Часто в современных реалиях работающий код можно и с AI написать, но вот чтобы проверить - нужны знания.
Про диплом: не соглашусь с вами. Сами знаете, как у нас учеба идетvadimr
01.06.2025 12:24Учился в ЛЭТИ, знакомился с курсом MIT. Примерно одинаковый уровень, только SICP лучше написана в чисто литературном плане. Ну она такая одна.
Со стрессом у нас было всё нормально, один зачёт, помнится, в 20:00 31 декабря закончился. Другой преподаватель разрешал пользоваться шпаргалкой 10 секунд, за каждые следующие 10 секунд снижал по баллу. Я потом в его фирму работать пошёл, чёткий был деятель :)
FatMR Автор
01.06.2025 12:24Классные истории! Супер, что попались хорошие преподы. Очень рад за Вас. Мне вот так не повезло( И еще знаю ребят в похожей ситуации
kalapanga
01.06.2025 12:24алгособесы пришли из США. Но в США учат их проходить в вузе.
Вот именно, что не понимать алгоритмы, а проходить собеседования! Ситуация такая же, как с пресловутым ЕГЭ. Нужно не столько дать знания, сколько натаскать именно на прохождение этой процедуры.
FatMR Автор
01.06.2025 12:24Ниже общался с человеком на эту тему. Проблема часто лежит в некачественных интервьюерах
Lewigh
01.06.2025 12:24Самое обидное для меня — писать негативный фидбек кандидату, когда ты видишь, что он старался изо всех сил.
А мне кажется самое обидное это то что многие талантливые программисты не проходят или даже не пытаются проходит такие собеседования. Не потому что они глупые а потому что компании выбрали, по моему мнению, абсолютно идиотский, оторванный от реальности формат собеседований. И дело даже не в алгоритмах и том что человек потратит кучу времени на подготовку и даже не удостоиться чести писать какие либо алгоритмы в компании где ну уж так сильно хотят их решения. Дело в том что спортивный формата "реши задачи за время пока за тобой пристально смотрит интервьюер", не имеет ничего общего с нормальной работой где угодно. Это оторванный от реальности идиотизм. Эта стрессоустойчивость на время в реале никому не нужна а готов поспорить в нормально ситуации когда раз в год понадобиться что-то такое решить, большинство кандидатов сядут на диванчике и спокойно решат, пусть не за час а за два но решат и погоды это не сделает. У меня есть друг который для игры пишет сложные алгоритмы и структуры данных, думаю многие интервьюеры бы сели в лужу увидев такое, но самое забавное что друг при этом сам садится в лужу на не самых сложных задачах на алго-интервью.
FatMR Автор
01.06.2025 12:24Слушай, не соглашусь. В рамках алгосекций проверяются твоя возможность решать логические проблемы, оценивается твое поведение в стрессовой ситуации.
Тут более частая проблема - плохие интервьюеры. Они не умеют нормально выстроить диалог, считают себя самыми умными, дают плохие подсказки. И как результат, кандидат страдает час на этом собесе
Farongy
01.06.2025 12:24проверяются твоя возможность решать логические проблемы
Вы же сами пишете, что проверяется не логика, а натренированность быстро писать по памяти:
Я не знаю, сколько прошло времени, но смотреть на кандидата, который понимает, как это работает, но не может написать — это самое ужасное.
оценивается твое поведение в стрессовой ситуации
Зачем?
FatMR Автор
01.06.2025 12:24В статье подчеркивал, что "Не пытайся вспомнить решение задачи, даже если уже её решал"
Очень часто в разработке задачи выполняются в сжатые сроки, необходимо уметь грамотно объяснить, почему текущие функциональные требования не подойдут. Далее нужно это все сделать и проверить. А потом окажется, что ночью тебя будит железная женщина, так как баг. И его нужно бежать чинить - все это стресс. И как мне кажется, алгосекция достаточно неплохо это проверяет
Farongy
01.06.2025 12:241) Люди так не работают. Мы используем предыдущий опыт для решения текущих проблем.
2) Есть такая практика - делается откат на предыдущую версию, а затем в спокойной обстановке чинится.
vadimr
01.06.2025 12:24Не во всех обстоятельствах возможен откат и есть спокойная обстановка. Это зависит от характера работы.
Вы приехали сдавать программу заказчику, и в его условиях она не работает. Ваши действия?
Конечно, хорошо, когда можно всё отрепетировать заранее, но это не всегда осуществимо.
avost
01.06.2025 12:24Вы приехали сдавать программу заказчику, и в его условиях она не работает. Ваши действия?
Собираю "условия" и еду назад воспроизводить/моделировать их в спокойной обстановке.
А вы разворачиваете и настраиваете на мощностях заказчика девелоперское окружение, системы сборки и деплоя, подключаетесь к репозиторию с сорцами, спешно выдумываете заново и переписываете алгоритмы обработки и собираете проект заново? Серьёзно?
vadimr
01.06.2025 12:24Не всегда есть возможность воспроизвести условия.
Для задач обработки данных - скорее да. Для задач управления - скорее нет.
А вы разворачиваете и настраиваете на мощностях заказчика девелоперское окружение, системы сборки и деплоя, подключаетесь к репозиторию с сорцами, спешно выдумываете заново и переписываете алгоритмыобработки и собираете проект заново? Серьёзно?
Если окружение заказчика гораздо сложнее, чем всё это, то так и придётся делать.
Keeper21
01.06.2025 12:24ночью тебя будит железная женщина, так как баг. И его нужно бежать чинить
И как часто у вас бывают такие ситуации?
funca
01.06.2025 12:24Говорят, программисту чтобы переключиться от одной задачи к другой нужно полчаса. Поэтому не стоит менять приоритеты слишком часто. А на алгособесы нужно приходить на чистую голову.
Я периодически решаю задачки на литкоде, как хобби. Но однажды попал на такой собес в середине рабочего дня, в обеденный перерыв. Читаю условие. Понимаю, что задачка тривиальная на уровне школьной программы. Но мозг продолжает крутить по инерции детали с предыдущего митинга и отказывается вгружать новый контент. Читаю второй раз, третий - все равно не заходит. Понимаю, что ничего адекватного сходу предложить не могу и пробую галлюционировать. Что-то в духе - а давай разберем строку регулярным выражением. Но не могу вспомнить синтаксис для рекурсивных регеспов в pcre. Снова тупик. В итоге первые минут 20 перекидывался с интервьюером какими-то шутейками.
Со второй задачи включаюсь, на третьей начинаю входить во вкус. Но всем уже понятно, что времени на все не хватает и интервью формально провалено. Вечером, чтобы закрыть гештальт решаю все разными способами: наивным, быстрым, красивым - ясно вне зачёта.
apcs660
01.06.2025 12:24Никогда не проходил алгоритмическое собеседование за 25 лет в отрасли. Повезло.
Да пожалуй, и не пойду уже. На практике спокойно решать, это одно, а через кофемолку как студенту проходить - спасибо. Лучше компанию открою, это проще. Лень писать код, особенно когда понятно что писать.
из баловства, задачки решали, 15-20 лет назад..
Одна задачка запомнилась из начала 2000х - у тебя два стеклянных шарика, нужно создать алгоритм поиска этажа здания начиная с которого, шарик при падении вниз, разбивается. Этажность здания от 2х до 100 этажей.
А вторая задачка с шахматной доской почти не требует знаний, кроме базовых школьных, и нам ее дали на лекции по математике - кто решит за две минуты с доказательством, пятерка за семестр.
Один студент решил за пять минут, я - нет.
Alexandroppolus
01.06.2025 12:24Одна задачка запомнилась из начала 2000х - у тебя два стеклянных шарика, нужно создать алгоритм поиска этажа здания начиная с которого, шарик при падении вниз, разбивается. Этажность здания от 2х до 100 этажей.
Более интересный вариант - когда шариков несколько. Там ведь надо минимизировать число бросков. Или, наоборот, сколько этажей можно окучить, при заданном лимите бросков (имея на руках K шариков).
А вторая задачка с шахматной доской
Что там?
apcs660
01.06.2025 12:24по хорошему, ее нужно давать визуально. И прокатывает эта задача один раз, но мне не жалко. Мне ее дали в 1993м году.
Берите ручку и рисуйте в тетрадке, задачка визуальная.
Обещаем ценный приз, например поступление на работу без остальных этапов интервью.
1 рисуем квадрат, 8 на 8. Это шахматная доска.
2 доминошка размером 1х2 клетки. Очевидно что доминошками можно закрыть шахматную доску полностью, без пропусков. 8 рядов по 4 доминошки.
3 отпиливаем две клетки в шахматной доске - 8ю в первом ряду и первую клетку в 8м ряду, остается 62 клетки.
Можно ли полностью закрыть доминошками оставшиеся 62 клетки? Две минуты пошли! Ответ без доказательства не принимается.
Alexandroppolus
01.06.2025 12:24А, эту знаю, классика всё таки. Есть ещё вариант, где отпилили только одну клетку в углу, и надо закрыть оставшуюся доску "триминошками" (дощечками 1х3)
Metotron0
01.06.2025 12:24Давай представим, что ты реализовала уже функции поиска
Да ведь он всё понимал
Тут не сходится
BlackArcher
"Так может, возьмём квадро-поиск? Получится оптимальней…"
Речь же про асимптотику, с ее точки зрения все логарифмы с константным основанием эквивалентны, это тоже стоило в пояснении упомянуть, чтобы не запутать случайно
FatMR Автор
Спасибо за комментарий! Я в том моменте хотел указать, как интервьюер может попробовать проверить кандидата на знание констант
vadimr
Что-то я не догоняю. Что у вас будет в качестве предиката при "квадропоиске"?
Бинарный поиск же не потому бинарный, что программисты любят нули и единицы, а потому, что у числовой оси два направления.
FatMR Автор
В квадропоиске будет 3 мид-элемента. И благодаря этому в 4 раза сократим область поиска, а не в 2, как в бинарном
vadimr
Так 3 мид-элемента – это точно те же 2 последовательных двоичных поиска.
Вам предикат всегда даёт 2 результата, истину или ложь.
FatMR Автор
Да, так и есть. Тут изначально вопрос был направлен на то, понимает ли кандидат смысл бинарного поиска и его различных интерпретаций. А также ошибок в логических рассуждениях о нем