Comments 1270
Слышал шутку, что яндекс вообще на любую позицию по алгоритмам гоняет
Слышал шутку, что яндекс вообще на любую позицию по алгоритмам гоняет
Бедные курьеры...
Не курьеры, а коммивояжеры.
Авторитетно, как яндекс-курьер получивший оффер, заявляю.
ПС
: sarcasm:
Я не настоящий сварщик, я маску нашёл, но насколько я понимаю, под словами "задача коммивояжёра" и "задача о рюкзаке" могут подразумеваться несколько разные вещи, в том числе NP-полные задачи, так что сведение одной к другой неочевидно в таком простом заявлении, как ваше :)
Но если брать формулировку по «knapsack problem» и «travelling salesman problem» в английской вики — то я не вижу как решение второго свести к решению первого (без многократного повторения или увеличения размерности задачи).
Лично я дипломированный трубочист (серьёзно), так что давайте поговорим :)
Руку на отсечение не дам, но вроде бы, в обоих случаях задачи разрешимости NP-полны, и не всегда ясно, когда говорят просто про рюкзак (коммивояжёра), имеются ли в виду оптимизационные задачи или речь про разрешимость.
Насколько я вижу по вики (да и всегда думал) — задачи имеют разное название потому что это разные задачи. Там где задачи явно сводятся к другим обычно это пишут, например тут
The knapsack problem is a generalization of subset-sum.
Если не пишут значится что не сводится одно к другому
Рюкзак и коммивояжёр оба NP-полные, значит оба сводятся друг к другу.
Не согласен с такой формулировкой. Если на си можно написать компилятор идриса а а на идрисе компилятор си это не означает что между ними нет разницы.
Лично я дипломированный трубочист (серьёзно), так что давайте поговорим :)
Если вы чистите трубы только тем, кто не может прочистить их сам, у меня к вам есть один вопрос. :)
Я не настоящий курьер, я рюкзак нашёл! У подъезда, вместе с велосипедом
Сколько теннисных мячей поместится в сумку
В голос, спасибо! :)
Через много лет, когда стал Solution Architect, также было интервью по этой позиции, и угадайте каким был первый вопрос?:)
Не, ну это ещё можно вытерпить. Хуже, когда хрюша идёт по опроснику и спрашивает «Какой алгоритм сортировки лучший?».
Это ещё что... Когда проходил собеседование на менеджера продукта, для какой-то важной оптимизированной операции решил использовать бинарный поиск по постоянно поддерживаемому сортированному набор строк (вполне умещались в RAM). А собеседовавший меня менеджер проекта (хотя там ещё был аналитик, не считая HR) завернул мой вариант, обосновав, что тогда потребуется индекс, а операции над ним дорогие при таких объёмах данных и требованиях к производительности. И что характерно, аналитик его не поправил. После этого я уже не стремился в их команду, потому что либо каждый должен заниматься своим делом, либо должен хотя бы знать то, о чём говорит, и понимать, что говорят другие, либо не участвовать в решении при недостатке компетенции. А уж с чем-то минимально сложным с максимальным приближением к реальному практическому решению тот товарищ вообще не совладал (это уже из опыта их приёма выполненного мною тестового задания для самостоятельной работы).
бинарный поиск по постоянно поддерживаемому сортированному набор строк
какая по вашему будет сложность вставки в такой список? и устроит ли она вас? мне кажется, что вас хоть и не поняли, но вариант вы предложили так себе. хотя и возможно, что если уточнить задачу и ваше предложение, то окажется, что всё хорошо
И ЗП меньше среднего, прям как в Яндекс доставке!
После прочтения предыдущих комментов и поста, а потом вашего коммента, в голове само всплыло название следующего сервиса: Яндекс.Девопс. Ну, знаете, сдача админов, которые почти прошли собеседование, в аренду клиентам Я.Облака.
Ну, чтобы просто результаты собеседований хоть как-то применить, даром, что они по алгоритмам!
На многие вопросы из первой части я ответил с большим трудом, а на некоторые ответов вообще не знал, что наверняка и послужило поводом меня слить)
Такое впечатление, что в яндексе хорошо умеют проверять знание алгоритмов — вот и ищут специалистов где светлее, а не за углом где потеряли.
Правда это было достаточно давно, что бы Яндекс не мог засудить меня за разглашение, ибо соглашение о неразглашении истекло.
Меня не взяли водителем беспелоднега хотя я идеально соответствую требованиям вакансии. Про алгоритмы, с.ка, даже не спросили...
И еще кучу беспонтовых вопросов
В моем случае это правда: соискал позицию тестера. Правда, отшили после двух и "зошто" не случилось.
Они проверяют не эрудицию (знания) а ум - умение думать
Задачки нормальные, но зачем столько? Трёх-четырёх достаточно. Я бы уже на втором таком интервью вежливо распрощался, если я захочу порешать задачки, я пойду на hackerrank или leetcode.
В свое время я не успел решить одни задачки на время, честно сказал интервьюеру, что если им так нравится, они могут сами решать олимпиадные. В ответ получил оффер.
Они созданы, чтобы проверять знание кандидатом базового синтаксиса. Конечно, немного думалка тоже проверяется, но алго-думалка с обычной не совсем коррелирует и даже скорее совсем не коррелирует.
Такая крупная компания, могли бы сесть, подумать с менеджерами и выдать идеальный ответ — организовать специальный отдел девелоперов-математиков, найти подходящих людей и ставить им задачи.
А не задавать это ВСЕМ подряд, учитывая что такие вопросы задают даже менеджерам (вот они точно будут писать новые реализации хеш-тейблов?)
Но там не задают задачу на написание хеш таблицы. Максимум на использование. И полностью рабочее бинарное само-балансирующееся дерево — тоже не задают. Максимум тривиальное дерево. Просто для проверки, что кандидат может представить структуру и хоть чуть-чуть понимает, как работают указатели.
И на софт скилах не выедешь, как можно сделать в разговоре за жизнь.
И можно разных кандидатов сравнивать друг с другом. По формализуемым признакам.
Предложите альтернативный вариант. Чтобы не хуже было хотя бы по этим критериям.
Какой варинат решения прелагаете? Спрашивать еще сложнее? Рюкзак модифированный так чтобы его случайный человек не узнал пойдет? Так отсеются вообще все. Случайный мидл даже после сидения на литкоде не справится же.
Более-менее нормальный подход — давать относительно несложные (не примитивные, но и не настолько сложные, чтобы отсеять вообще всех, кроме гениев и тех, кто подобное решал) задачи, где надо не алгоритмы помнить (то есть надрочиться на литкоде не поможет), а головой подумать, плюс и прикладной смысл чтобы был, и дать человеку ее решать в привычной среде — просто расшарив экран. Пусть гуглит что хочет (кроме прямого решения задачи, конечно), вообще разрешено все (как и что человек гуглит — это вообще о многом сразу говорит!). И посмотреть, КАК человек это все делает. Такое, типа, парное программирование.
Тут, конечно, формальных баллов не начислишь, все субъективно. Но уровень сразу виден, уже через пять минут на самом деле.
давать относительно несложные (не примитивные, но и не настолько сложные, чтобы отсеять вообще всех, кроме гениев и тех, кто подобное решал) задачи, где надо не алгоритмы помнить
Ну посмотрите же задачи из статьи. Где там хоть одна, где надо алгоритмы помнить? Максимум, знать, что есть такая структура данных — хеш-таблица.
А примерчик ещё проще чем в статье можно? Там все еще проще вырождается в однострочник или физзбазз.
IDE или не IDE дискуссионно.
Самое плохое в этом всем — то, что в подобных конторах собеседуемому код надо писать не в IDE, а на доске или в условном notepad-е. Это вообще бессмысленное занятие — примерно как проверять, умеет ли оператор экскаватора копать лопатой. Что вы, блин, так проверяете, знание синтаксиса языка? В вакансии на миддла-сеньора, бгг? Еще проверьте, знает ли он алфавит тогда.
Ну так в отличие от ИДЕ от вас не требуется написать компилируемый код, а иногда не требуется и брать существубщий ЯП — достаточно просто набросать алгоритм, чтобы было понятно что куда и как. Вангую что никто не будет докапываться если в каком-нибудь SelectMany букву забудете или порядок аргументов какой-нибудь функции перепутаете. Главное как вы будете рассуждать и какие уточняющие вопросы задавать.
Если от вас требуют написать без ИДЕ на бумажке идеально компилирующийся код без ошибок — то это вполне хороший фактор чтобы туда не идти. Так что не вижу ничего плохого в том чтобы получить на такое отказ.
Но вопрос в основном в театре абсурда, когда тебе на 10 интервью задают то одни то другие алгоритмы И НИЧЕГО по технологиям
А в разговоре за жизнь можно много чего узнать. Что человек сделал, зачем, почему.
пишет алгоритмы а не программы
Что? По определению, любая программа — алгоритм. Если вы придираетесь к тому, что там на интервью спрашивают заумные алгоритмы, которые в реальной работе не пригодятся — то вы не правы.
Вам так сложно представить, что в яндексе может возникнуть задача взять общие элементы из двух списков (задача из статьи с интервью)?
Я за свою недолгую пока карьеру в гугле много раз использовал и математику и писал хитрую структуру данных, и динамическое программирование. Не каждый день конечно, но эти вещи реально пригождаются. И самое печальное, что если этого всего не знать, то даже мысль не возникнет о том, что вот тут можно было "алгоритм" впендюрить и получить более быстрый и простой код. До этого немного поработал в яндексе, и там пришлось, например, использовать trie для ускорения процесса в несколько раз. Этой структуры нет в stl. Про нее надо хотябы знать, иначе как вообще ее нагуглить?
Сколько конкретно разработчиков в Яндекс будут решать задачи с новой реализацией хеш-тейбла?
Такая крупная компания, могли бы сесть, подумать с менеджерами и выдать идеальный ответ — организовать специальный отдел девелоперов-математиков, найти подходящих людей и ставить им задачи.
Так ведь в каждой конкретной ситуации надо смотреть и думать, что нужно. Не может быть универсального решения, т.к. где-то очень важен lookup-time (не асимптотика, а чистое время), где-то важен объём памяти, занимаемый данной структурой. Вы, кажется, не понимаете, что когда речь идёт о миллиардах, то начинает быть важна каждая мелочь.
А не задавать это ВСЕМ подряд, учитывая что такие вопросы задают даже менеджерам (вот они точно будут писать новые реализации хеш-тейблов?)
Ну всем подряд и не задают. У вас тут типичная ошибка выжившего. Те, у кого интервью прошло нормально — они на хабре статей не пишут. Тут не принято писать о том, что в Яндексе хорошие собеседования, за такое можно и минусов отгрести. Поэтому вы со стороны видите только те собесы, которые прошли отстойно. Или прошли нормально, но человеку не хватило компетенции понять, что его вообще спрашивали и какие скиллы проверяли.
— это действительно нужно (только тогда нужно давать не только самые элементарные вопросы),
— это результат того, что в компании — корпоративный культ карго, выросший из того, что раньше это было действительно распространено и на этом Яндекс что-то выигрывал у конкурентов.
Бардак с «деревом» собеседующих (изоляция процесса найма от реальных задач, как результат этого), размер компании, а также некоторые решения, которые ранее использовались Яндексом, склоняют меня к тому, что более вероятно второе. Ваш же аргумент косвенно исходит из первого, а возможность второго — игнорирует.
— это действительно нужно (только тогда нужно давать не только самые элементарные вопросы),
О, ну тут всё просто. Я провёл больше сотни собеседований и почти половина кандидатов не смогли решить даже элементарной задачи типа «эффективно удалить нули из массива». Потому что им на практике нигде не надо было работать работать с большими данными и, соответственно, задумываться про асимптотику и т.п. Поэтому к «реальным» задачам далеко не все могут перейти. Но они есть, вполне себе интересные.
это результат того, что в компании — корпоративный культ карго, выросший из того, что раньше это было действительно распространено и на этом Яндекс что-то выигрывал у конкурентов.
Ну Яндекс большой и наверняка в каких-то его уголках есть культ карго. Но в целом — вряд ли. Тут ведь ещё какое-то дело — если не использовать текущую систему найма, то какую использовать? Система с «давайте пообщаемся о прошлом опыте» — полный отстой, т.к. пролезает очень много буллшиттеров (которых потом ещё хрен уволишь).
Текущая система используется (кстати, в том же FAANG примерно всё то же самое при найме — регулярно прохожу собесы чтобы «знать рынок») не потому что идеальная, а потому что пока лучше ничего не придумали.
Но тут ведь система со смещённым фидбэком: если мы наняли слабого человека (т.е. человек оказался слабее, чем показалось при найме), то мы об этом узнаем; а если не взяли сильного (т.е. человек оказался сильнее, чем нам показалось) — то не узнаем. Поэтому очень сложно подобрать оптимальное количество и сложность задач.
Есть ещё интересное соображение: если давать много простых задач, то можно не успеть дать сложные (и недооценить кандидата). И это действительно правда, изредка так и бывает. Но если дать сразу сложную задачу и кандидат её не решит — тут всё намного хуже. Т.к. если кандидат не решил сложную задачу — это не значт, что он не подходит, мб он пойдёт на должность ниже. Надо разибраться с причиной того, почему конкретно человек не смог решить задачу — а это ну очень сложно. Я видел как люди на собесе очень хорошо всё рассказывают по плану задачи, но не хватает времени написать код. Их берут в штат, и оказывается, что люди и код-то толком писать не умеют. Это было бы отлично видно, если бы дали простую задачу, но т.к. дали сложную — то подумали, что «перемудрили с задачей, давайте просто дадим ему не сениора, а мидла».
Все перечисленные нюансы — реальность, но другого порядка.
Вы налили тонну воды, но ответ все же дали — две задачи должно быть достаточно для общего случая.
Я не дал ответ который вы хотели услышать. Но если вы читали невнимательно, то вот мой ответ:
сколько нужно — не знаю.
На деле же, когда у компании 1000 кандидатов, а нанять надо 50-100, то интервьеров будет человек 100. Из них части попадутся знакомые знакомых, часть окажется олимпиадниками, которым ничьих знаний не будет достаточно, части будет не жалко нанимать всех, кто решит простую задачу, которую решают на первом курсе любого вуза. А ещё кандидат может одному интервьюеру понравиться, а другому нет визуально, может разволноваться с одним интервьюером, а с другим — нет и т.п. Получится рандом, усугубленный тем, что сильных кандидатов меньшинство.
Для примера пусть из 100 собеседующих 25 не наймут никого, 25 наймут любого, а 50 наймут сильного кандидата и не наймут слабого.
Пусть из 1000 кандидатов 100 сильных (кого в идеале хотел бы нанять Яндекс; каждый 10й).
Тогда при одном собеседовании на каждого кандидата будет нанято 25% (шанс попасть на лёгкого собеседующего) * 900 = 225 слабых кандидатов и 75%*100 = 75 сильных. А надо бы, чтобы соотношение было 0 на 100.
Вот и делают дублирующие собеседования.
Если на каждого кандидата по две секции и нанимают только тех, кто прошел обе, будет нанято 56 (900*0,25*0,25) слабых кандидатов и 56 сильных. Уже лучше, но соотношение всё равно плохое. Даже один слабый прогер уровня миддла может уронить продуктивность команды из 3-5 сильных мидлов.
Делаем третье собеседование. Наняли 14 слабых и 42 сильных. Ещё лучше, но большая часть сильных будет отсеяна.
Делаем четвертое и разрешаем одно собеседование провалить. Получаем 900 * (0,25 ** 4 + 0,25 ** 3 * 0,75 * 4) = 45 слабых и 73 сильных.
Много слабых. Добавляем пятое собеседование на ту же тему (одно можно завалить)
Получаем 14 слабых и 63 сильных.
Если сделать 6е, получим 4 слабых кандидата и 54 сильных.
Примерно поэтому в Яндексе обычно 6 секций +- одного и того же. В Гугле аналогично.
Нормально, что среди 942 отсеянных находятся те, кто пишет статьи на хабр о том, какие неадекваты в Яндексе. Согласно модели шанс, что это подходящий Яндексу прогер, процентов 5.
Но по подходу автора (писать квадратичную асимптотику вместо линейной, потому что так привычнее) видно, что тут к Яндексу только один вопрос — зачем было тратить время кандидата и интервьюеров на секции после 2й-3й.
Вы меня поразили прям в мозг. Ну добавьте тогда в ваш зоопарк интервьюеров, которые выдают результат в зависимости от дня недели, и интервьюера, который убивает кандидатов с шансом 50%… В моём понимании интервьюер — это функция, которая принимает на вход знания кандидата и выдаёт 0 или 1. Если этот интервьюер выдаёт много FP или FN, значит это паршивый интервьюер и нафига он нужен. Если есть шанс ошибки, то поставьте 3-4 интервьюера рядом и пусть они исправляют друг друга. Добавьте ещё штуки 4 теста для быстрого вылета кандидатов, типа если напишут O(n^2) или если ник начинается с k, то сразу отлуп. Всё.
Судя по тому, что я видел, Яндекс не парится и берёт пулл кандидатов, пулл сотрудников, и как на той картинке с игрушечными собачками скрещивает их. А ведь эту кучу часов, которые рекрутеры тратят на кандидатов, можно было потратить, чтобы — внезапно — улучшить рекрутеров самих и весь процесс в целом.
Я как кандидат — в печали. Я хочу максимально быстрый ответ и, желательно, фидбек. Тут ни того, ни другого. Ну хоть посмеялись всем хабром.
Не очень понятно, как вместо того, чтобы собеседующие проводили по 6 секций с каждым кандидатом, пустить их время на улучшение процесса. Сажать по 6 человек на кандидата — не уменьшит времязатраты интервьюеров, но уменьшит точность за счёт меньшего числа вопросов.
Есть ли примеры крупных IT-компаний (1000+ разработчиков, не бодишоп), где быстро собеседуют и быстро могут дать положительный фидбек?
В гугле с момента подачи резюме до оффера проходит 3-6 месяцев. В Яндексе 1-2 месяца. Да, не неделя, как в небольших компаниях, но раз недостатка в кандидатах нет и акции растут, значит всё работает норм.
раз недостатка в кандидатах нет
спорное утверждение.
Ко мне рекрутеры Яндекса обращаются с завидной регулярностью. Причем уже доходило до того, что мои данные «передавали» в КА/РА, которое работает на Яндекс.
Ко многим знакомым — тоже.
Да, не спорю, туда все еще многие мечтают попасть, но есть ли прямо очереди? Чё-т не уверен.
Активность HRов, это вполне предсказуемый процесс. Яндекс хочет нанимать самых подходящих специалистов на рынке. При этом сильный кандидат может и не подозревать, что его примут в Яндекс. Поэтому Яндексу в целом выгодно множество HRов, которые ходят по рынку и холодными звонками выцепляют людей на собеседования.
И HRы эти далеко не всегда сотрудники Яндекса. В целом есть распространённая модель партнёрства, когда ты заключаешь с компанией договор о том, что она с каждого трудоустроенного от тебя кандидата платит тебе процент. А дальше ты сам себе хозяин и ищешь кандидатов где только можешь. В результате да, бывают эксцессы, а люди могут сокрушаться в комментариях, мол «мне написывал HR из яндекса, как же они задолбали», но это не признак недостатка желающих пройти собеседование.
Мне, например, когда я работал в Яндексе, в Линкедине писали такие HRы предлагая прийти на собеседование в Яндекс. Бывает, что уж
Я провёл больше сотни собеседований и почти половина кандидатов не смогли решить даже элементарной задачи типа «эффективно удалить нули из массива».
Если инплейс то можете подсказать как? Потому что так-то ничего сильно лучше arr.Where(x => x != 0).ToArray() и не придумывается.
Ну Яндекс большой и наверняка в каких-то его уголках есть культ карго. Но в целом — вряд ли. Тут ведь ещё какое-то дело — если не использовать текущую систему найма, то какую использовать? Система с «давайте пообщаемся о прошлом опыте» — полный отстой, т.к. пролезает очень много буллшиттеров (которых потом ещё хрен уволишь).
Можно тоже пример? По опыту в маленьких компаниях это отлично работает, не очень понятно что именно должно сломаться в случае большой. Или у вас в маленьких тоже не работает? Тогда тем более хотелось бы услышать ответ.
Если инплейс то можете подсказать как?
Примерно так:
function remZero(arr) {
var p = 0;
for (var i = 0; i < arr.length; ++i) {
if (arr[i] !== 0) {
arr[p++] = arr[i];
}
}
arr.length = p;
}А ну да, логично, даже странно что я про это не подумал. Мне почму-то показалось что мы можем элементы местами менять и нарушить относительный порядок. Немного не в ту сторону подумал.
В целом это и есть arr.Where(x => x != 0).ToArray() только копируем прям на месте вместо свободных нулей. Да, спасибо, тупанул чет
По прошлому опыту это ведь не просто "наврите нам покрасивее" а вопросы по этому опыту. Почему сделали так, а не иначе. А вот зачем этот компонент. И так далее.
Плюс можно гитхаб посмотреть если есть, если нет — то все же какую-нибудь задачку разминочную на 10 минут тоже можно. Это не дрючить 10 алгоритмическими задачками на 5 раундах собеседований, но какое-то видение дает. Вкупе с вопросами по арихектуре можно делать выводы.
Уже сейчас есть в интернете куча платных и бесплатных курсов, задрачивающих людей решать задачи. Т.е. человек без опыта может научится решать задачки и пройти интервью.
Если FAANG будет спрашивать массово про опыт и профиль на гитхабе, то будут курсы, которые будут учить людей складно рассказывать про "прошлый опыт" и объяснять по этому чужому профилю на гитхабе, почему сделали так, а не иначе.
В текущей ситуации имеем людей, возможно вайтишников, которые научились решать алгоритмические задачи. Значит перекладывать json они точно смогут, ибо это проще. В гипотетической ситуации будем иметь кучу вайтишников, очень слабо программирующих, но складно говорящих.
Вторая проблема: поговорить про опыт и посмотреть гитхаб — слишком субъективные оценки. Такое не годится для крупных компаний, которых пытаются засудить за дискриминацию, потому что интервьювер посмел спросить про размер байта в битах.
А еще это на порядок сложнее для интервьюверов. Сходу вот так глядя на неизвестный вам проект понять, что вот такое решение было лучшим, невероятно сложно. Это потребует невероятно много времени подготовки у интервьювера. Когда как задачки можно спрашивать одни и те же, пока они не утекут в сеть.
Вот и получается, что спрашивать задачки — единственно подходящее решение для интервью в FAANG/Яндексе. Оно скейлится, более менее объективно, просто в оценке, проверяет что-то вполне релевантное работе.
Если FAANG будет спрашивать массово про опыт и профиль на гитхабе, то будут курсы, которые будут учить людей складно рассказывать про "прошлый опыт" и объяснять по этому чужому профилю на гитхабе, почему сделали так, а не иначе.
Складно рассказать про прошлый опыт по-моему невозможно не прожив этот самый опыт. Шаг влево-вправо от "рассказывали на курсах" и провал. По крайней мере мне слабо представляется как можно составить решебник на все возможные вопросы.
Вторая проблема: поговорить про опыт и посмотреть гитхаб — слишком субъективные оценки. Такое не годится для крупных компаний, которых пытаются засудить за дискриминацию, потому что интервьювер посмел спросить про размер байта в битах.
Ну это да, но мне показалось выше сказали что и для маленьких такой способ не подходит.
А еще это на порядок сложнее для интервьюверов. Сходу вот так глядя на неизвестный вам проект понять, что вот такое решение было лучшим, невероятно сложно. Это потребует невероятно много времени подготовки у интервьювера. Когда как задачки можно спрашивать одни и те же, пока они не утекут в сеть.
Так что сложного? Все непонятные места адресуются кандидату — по его ответам будет понятно, думал он про это или нет, какие варианты отбросил и т.п. Не надо додумывать — надо спрашивать (если конечно есть у кого), наверное одна из первых вещей которые я понял когда начал работать: быстрый фидбек с короткими циклами — залог успеха.
Вот и получается, что спрашивать задачки — единственно подходящее решение для интервью в FAANG/Яндексе. Оно скейлится, более менее объективно, просто в оценке, проверяет что-то вполне релевантное работе.
Ну задачки отбирают либо студентов которые недавно их проходили либо сверхмотивированных людей которые в свободное время прорешивают литкод чисто ради фаанга. Пробовал так сделать в прошлом году — после пары десятков задач задолбался и забил.
Я не предлагаю никаких альтернатив, просто рассматриваю минусы текущего подхода. Вполне вероятно это лучшее из худшего.
лучшее из худшего.
Тоже так считаю. Да, у студентов приемущество возникает и нужно тратить время на подготовку. Ужасный метод. Но лучшего, на мой взгляд, нет.
Ужасный метод. Но лучшего, на мой взгляд, нет.
Есть. Даёте задачу и для неё штуки 3-4 решения готовых, и пусть интервьюируемый посмотрит их и скажет какое лучше и почему. Меньше затрат времени на собеседование, и плюс не будет каких-то глупых ошибок из-за спешки, стресса, неудобства написания кода в блокноте, на бумажке, или на доске.
Тут в соседнем треде мне другой товарищ доказывал, что эти алгоритмические интервью — ужасны, потому что их проходят легко "профессора" знающие наизусть О-большое всех-всех алгоритмов и умеющие доказывать заумные абстрактные утверждения, но вообще нисколько не умеющие писать код.
В отличии от текущих интервью, ваш вариант как раз подвержен такой проблеме.
Он никак не проверят, что кадидат может писать код. Он никак не проверят, что кандидат умеет решать задачи, а не выбирать из нескольких предложенных вариантов.
Нет. Вам не даны несколько вариантов. В реальной жизни у вас есть только задача. Вам надо эти варианты еще найти. Как понять, что вот этот вот ответ на стекоферфлоу — хороший? Надо ли искать дальше? Или подобно задаче о привередливой невесте, ищем 4 ответа и берем лучший, надеясь, что среди этих 4-х есть нужный?
Теперь про стандартные библиотеки: 99% всего что вы делаете — нет в библиотеках! Вы можете прикрутить стандартную структуру данных, или найти какой-то фреймворк, который надо как-то потыкать, и часть вашей задачи будет решена. Но практически все, что вы делаете — это решение одной частной ВАШЕЙ задачи. Магической функции "сделать хорошо" нет ни в одной библиотеке.
Это нормально понимать, что вам тут нужно сбалансированное дерево поиска, и взять готовую реализацию из библиотеки. Но если вы не знаете, что вам тут нужно именно дерево, то что вообще искать?
пусть интервьюируемый посмотрит их и скажет какое лучше и почему
Этим вы проверите лишь умение кандидата анализировать, а проверять надо как анализ, так и синтез. Из первого умения никак не следует второе.
Поэтому мой совет соискателям — не делайте так.
ну или алгоритмиста.
Ну нет смысла нанимать выделенного алгоритмиста. Весь абсолютно программный код по определению — алгоритмы. Большая часть — тривиальные, типа пройтись по списку и выбрать минимум или сложить 2 числа.
Без знания о том, какие бывают алгоритмы, без умения решать задачи и алгоритмического мышления часто сложно даже понять, что вот эта задача — она решается тупо (прошлись по списку и выбрали минимум), а вот та — совсем нет.
Потому что почти всегда есть простой, понятный и очень не эффективный наивный метод.
Потому что эта самая алгоритмическая задача ничем принципиально не отличается от всех других задач, которые программисты постоянно решают.
В итоге получается, что выделенный алгоритмист должен ревьювить вообще весь код в компании. С потоком кандидатов FAANG/Яндекса эффективнее, дешевле и удобнее сразу нанимать только "алгоритмистов".
с которым больше поговорить
С "поговорить" большая проблема — это очень субъективно. Мелкой компании, где условный CTO сам проводит интервью и решает: кого брать, кого нет — это работает. В крупной типа яндекса и FAANG — уже нет. Плюс, если язык хорошо подвешен, можно тупо заболтать интервьюера в процессе этого "поговорить".
А почти всегда есть не очень простой, понятный и очень эффективный наивный метод — правильно применить готовую библиотеку/фреймворк.
Плюс, если язык хорошо подвешен, можно тупо заболтать интервьюера в процессе этого «поговорить».Без знаний особо не заболтаешь, если человек подходит ответственно к интервью: можно же спросить технические детали/особенности, да и github человека можно посмотреть.
Нет, выделенный алгоритмист должен вместе с архитекторами решать как будет работать самые высоконагруженные компоненты.
А потом систему в проде уронит случайный метод. Потому что на него внезапно пришла нагрузка, а он сделан так жутко что роняет всю БД.
Внезапно — маркетинг провел рекламную компанию и пришли люди. Эти люди прочитали какую-то статью и пользуются системой не так как ожидали разработчики.
Или у пользователей по всему миру отвалиться условный ютуб на пару часов, потому что упал какой-то служебный сервис из-за возросшей внезапно нагрузки. Или несколько часов не будет показываться вся реклама от яндекса. Огромная денежная потеря.
Отвечу словами здесь https://youtu.be/NwEuRO_w8HE?t=2180 (там всего на 40 секунд вопрос и ответ). Если вас парит о-сложность до того, как вы запустили код, прогнали бенчмарки и обозначили SLA пользователям, вы занимаетесь преждевременной оптимизацией. В конце концов, насрать, что в формочке на фронте O(n^2), браузер клиента всё стерпит. Не мучайте фронта булщитом про пузырьковую сортировку, пусть об этом парятся люди, которые контрибьютят в ядро линукса или пишут низкоуровневые системные библиотеки.
А как проверить, что человек сможет исправить найденную после запуска плохую часть?
В конце концов, насрать, что в формочке на фронте O(n^2), браузер клиента всё стерпит.
А потом такие "вот сайт тормозит, пользоваться невозможно!!!". Или у людей игра грузится по 10 минут на пустом месте. При чем там наверняка такая же мысль была: Ну насрать, что там в чтении одного мелкого конфига O(n^2), клиент все стерпит. А потом n, внезапно, выросло и все стало плохо.
А потом такие "вот сайт тормозит, пользоваться невозможно!!!". Или у людей игра грузится по 10 минут на пустом месте. При чем там наверняка такая же мысль была: Ну насрать, что там в чтении одного мелкого конфига O(n^2), клиент все стерпит. А потом n, внезапно, выросло и все стало плохо.
Нет, "потом" такого не будет. Вы просто взяли и пропустили фразы про бенчмарки, SLA и так далее. Если в SLA не было оговорено условное время загрузки сайта, то что там оговорено было вообще?
Просто обычно программный код имеет столько внутренних нюансов, что замена алгоритма с O(n^2) на более оптимальный может замедлить скорость работы, если это делать в слепую.
Вы игнорируете константу, вы игнорируете наиболее полулярные N и так далее.
Что лучше, что бы у большинства пользователей корзина покупок грузилось секунду, а у кого-то 5 или что бы у всех грузилась по 3 секунды?
Только и константы там одинаковые.
Обычно сделать более быстрый (асимптотически) код ничего не стоит. Классический пример который вижу в дотнете: foos.OrderBy(x => x.Something).First().Bar. Если это на старте приложения 1 раз делается или там в какой-нибудь режкой ручке — то как бы и плевать. А когда элементов достаточно много да и код выполняется довольно часто — то как бы не очень.
При том что решение — загуглить за 5 секунд любую из библиотек-расширений LINQ (либо написать свой хелпер за 5 секунд), и заменить это на foos.MinBy(x=>x.Something).Bar — почти те же буквы и те же константы, только уже за линию.
Только и константы там одинаковые.
Зависит от контекста. Всегда люблю приводить в пример перемножение матриц)
Обычно сделать более быстрый (асимптотически) код ничего не стоит.
Зависит от контекста. В вашем примере — не стоит. В каком-то случае это ухудшение читаемости и поддерживаемости кода. В каком-то случае это написание своего более оптимального велосипеда, который потом надо поддерживать.
Я не спорю, что в каких-то случаях вы просто улучшаете точность и все работает, но это явно не 100% и, скорее всего, даже не 50% случаев.
Сколько не работал с кодом, обычно существует одно место, которое тормозит больше всего, и это место отвечает за какую-то io работу в духе "сходи забери из базы что-то с кривым запросом". Переписываешь запрос и все работает :)
Даже во всяких cpu-bound задачах довольно часто спасает кеширование или исправление конкретного места.
Буквально на днях столкнулся с "возросшей нагрузкой" — есть корпоративный портальчик, ничего супер-пупер нагруженного, состряпали, запустили, пользуемся… через пару лет начинаются жалобы — тормозит. Автор портальчика к тому моменту уже потерялся, полез смотреть сам (я не программист) — оказывается, при каждом действии, ajax шерстит историю сообщений, чтобы в случае чего новенького отрисовать "колокольчик", а сообщений накопилось уже немало, а в алгоритме почему-то был линейный перебор с "ручным" анализом "новое/прочитанное" (таблица ID прочитанных сообщений была у каждого пользователя своя, а таблицы сообщений шли сплошной простынёй)… казалось бы — сделай запрос к базе по JOIN с "объединением по NULL", чтобы отобрать только непрочитанные, но автор решил несколько иначе — выбирал все сообщения, а потом искал их ID в "личной" таблице, и если не находил — высвечивал оповещение.
Вроде рабочий алгоритм, но вот с масштабированием совсем боль.
Ну так тут же дело не в каких-то неправильных алгоритмах, а в нарушение принципов работы с БД, что все выборки и расчеты максимально должны выносится в БД.
Да, и триггеры, и хранимые процедуры могут быть полезны, Но вот крайне было бы замечательно, если бы каждый занимался своим делом. БД — хранила и выбирала данные, а все остальные — всё остальное.
Кхм, ну и да, я понимаю, что уже может быть преувеличиваю… Так можно и JOIN ересью объявить… Но возможно, об этом стоило бы подумать. :-)
Ну так это ровно то же, что вы пишите. Выборка данных + расчет производных данных на их основе (преобразование функциями, сумма, вот этот весь треш).
Если вы фильтруете или преобразовываете данные потом на бекенде, то тут что-то немного не так. Иногда это ваша вина, иногда бд.
Но, в целом, мы приходим к изначальному вопросу статьи.
Для того, чтобы выбрать Clickhouse для решения определённого набора задач, надо знать и про Clickhouse, и про то, на каких наборах задач он будет в сотни раз быстрее других СУБД…
И, да, в общем случае, я фиг знает, как вообще можно такие вопросы гарантированно решать за 2-3-4 часа одного собеседования. Но в Яндекс с 10ю собеседованиями и ставкой ниже рынка не пойду. Ну разве что совсем от голода помирать придётся…
Я на самом деле очень люблю оптимизировать. Я несколько лет работал научным сотрудником в сфере, где широко использовалась wolfram mathematica. Я очень заморачивался над вещами типа сведения интеграла к сумме по элементам массива, над вставками на C, которые работали быстрее, итд. Но я это делал уже сильно после того, как написал первый прототип программы, который работал нормально, а потом захотелось больше отзывчивого UI. Я не считаю, что рядового кодера в стрессовых условиях собеса нужно мучать на оптимальные алгоритмы. Для этого давно есть библиотеки и только в редких случаях возникнет реально проблемный боттлнек, где придётся оптимизировать код. Если такое случится — ну, ок, сядет разраб и в спокойной обстановке поищет, в чём там проблема.
Типа, сначала строим дом, потом смотрим, что получилось неплохо, но нужно сделать канализацию, затем снова поднимаем краном и прокладываем водопровод. Разматываем электрические провода вокруг дома, снимаем обои и начинаем штробить стены.
При строитенльстве домов теже проблемы, только в меньшем масштабе. Возьмите типичную квартиру и посмотрите как расположены там розетки, используются ли вские тройники и удлинители. А ведь это все можно было решить на этапе ремонта. Вот только для этого нужно точно знать где какая мебель будет стоять, какие у неё будут размеры, какие электроприборы и где будут стоять и использоваться. Точно это предугадать невозможно, поэтому и возникают все эти удлинители или абсурдно огромные группы розеток "на всякий случай".
Так же и в разработке софта. Мы зачастую не знаем сколько у нас будет пользователей конкретной фичи, не знаем какие фичи будут добавлены завтра, а какие убраны. Мы даже не знаем кто будет завтра с этим кодом работать. То что мы знаем точно — так это то что проект точно будет меняться или умрет. Но что именно будет меняться — можно лишь гадать. И правильно угадывать мы будем далеко не всегда. Поэтому намного выгоднее писать код таким, чтобы его было легко менять в будущем, пытаться предсказать что может поменяться, а что нет. А еще, чтобы его могли понять другие разработчики, желательно без необходимости вникания во всю историю проекта. Хороше же оптимизированный код зачастую сложно читать, сложно расширять. В итоге приходится балансировать между расширяемостью, читаемостью и оптимизацией. Хороший разработчик — не тот кто упарывается в одну из этих крайностей, а тот, кто умеет находить баланс в каждом конкретном случае. Когда надо — писать хорошо оптимизированный write only код, а когда надо — медленный, но легкочитаемый и/или легкомодифицируемый, а в большинсте случаев — что-то среднее.
Хороше же оптимизированный код зачастую сложно читать, сложно расширять.
Это только если упарываться микрооптимизациями. Если просто использовать нормальный алгоритм или структуру данных — то код часто даже проще и понятнее. Что легче — полный перебор через рекурсивную функцию с откатами и неочевидными отсечениями, или динамическое программирование, которое все — 2 вложенных цикла и тривиальная формула для пересчета одной ячейки массива через соседние?
Поэтому намного выгоднее писать код таким, чтобы его было легко менять в будущем,
Спасибо, вы меня поняли. Заморочиться и написать fast inverse square root всегда можно потом.
Если же Вы прораб и делаете ремонт «другим», то тут грубо говоря два варианта: 1) прораб
Все лишние розетки и удлинители после ремонта, которые видел либо от отсутствия опыта, либо от нежелания «использовать мозг по назначению»…
Рефакторинг отнимает кучу ресурсов, больше, чем было бы потрачено на изначально грамотное проектирование. В конечном итоге рефакторинг откладывается до лучших времен, баги митигируются костылями, мейнтенанс и дев луп растут.
заходишь такой в интернет-магазин… и обычный обывательский мобильник вешается.Зашёл я как-то на один технический новостной сайт с обычного пользовательского мобильника…
Впрочем, ходят слухи, что уже ведётся работа над новым движком для комментариев, и к осени он будет готов. К какой осени — источник умалчивает.
В конце концов, насрать, что в формочке на фронте O(n^2), браузер клиента всё стерпит. Не мучайте фронта булщитом про пузырьковую сортировку
Браузер стерпит. Пользователь может и не стерпеть.
И как люди без электричества сотни лет жили?
Раньше работало, плохо но работало. Сейчас если Яндекс падает такси в России перестает работать. Надо теперь с этим жить.
А конкуренты куда делись?
В прошлом году полдня Яндекс такси лежало, все конкуренты легли под нагрузкой сразу же.
https://habr.com/ru/news/t/487130
И как вам тут алгоритмы помогут? Отказоустойчивость проверяется нагрузочным тестированием. Даже идеальный алгоритм захлебнётся, если элементарно не хватит нужных ресурсов.
Никто даже не пишет его. Это слишком дорого и долго. И не нужно в общем случае.
Критический путь можно так проверять. И иногда проверяют. Но это даже близко не все методы.
А потом систему в проде уронит случайный метод. Потому что на него внезапно пришла нагрузка, а он сделан так жутко что роняет всю БД.Я ведь верно понимаю, что любой алгоритмист, при устройстве на работу, гарантирует своему работодателю некий аналог sla с несколькими девятками, и полной компенсацией в случае падения прода? Или алгоритмисты только говорить могут, а на деле роняют прод примерно так же часто, как и обычные инженеры?
А потом систему в проде уронит случайный метод. Потому что на него внезапно пришла нагрузка, а он сделан так жутко что роняет всю БД.
Если он сделан прям «так жутко», то он просто код ревью не пройдет.
Всегда есть вероятность что какой-то код написали в тестах. А кто же внимательно ревьюит тесты?
Потом этот же код скопировали в метод нужный в админке. Кто же внимательно ревьют скопированный код на который не будет нагрузки и пользователи все свои?
А потом его вызвали из любого пользовательского метода на который не должно быть нагрузки. Кто же внимательно ревьют не тот код что написан только что, а какой-то там метод? Тем более нагрузки же нет.
А потом пришла нагрузка. И все легло. И никто не виноват.
Ну нет смысла нанимать выделенного алгоритмиста. Весь абсолютно программный код по определению — алгоритмы. Большая часть — тривиальные, типа пройтись по списку и выбрать минимум или сложить 2 числа.
Под "алгоритмистами" чаще всего понимают рисерч-инженеров… давайте расскажите, как компаниям не нужен R&D и все можно порешать на уровне понимания "сейчас пройдемся по списку и сложим два числа"...
ну или алгоритмиста
Выделенный алгоритмист не нужен.
У нас был проект, где были выделенные аналитики для увеличения производительности (прям такие математики-предметники). Которые в код реально не лазили.
В итоге (у них было достаточно «веса» чтобы настоять на включении доп.оптимизаций) схема разработки превращалась в старый анекдот про филина и мышей: «я вам решение сказал, а как вы будете это делать — это уже технические (не волнующие меня) детали».
Если же вы имеете в виду, что копия в плане собеседований, то флаг им в руки. Зачем нужно проходить это все в Яндекс, когда можно то же самое все пройти в любую из FAANG?
А что не так? В Яндексе нет настолько умных людей как в FAANG? Или они не делают нормальные сервисы?
В Яндексе нет настолько умных людей как в FAANG?Вполне вероятно, что в FAANG средний уровень выше банально за счёт того, что и конкуренция, и ареал поиска кандидатов куда больше.
Или они не делают нормальные сервисы?Ну, не знаю, огромная доля сервисов Яндекса со стороны кажется банальным симптомом болезни «а во. такая штука появилась на рынке, значит, надо делать свой клон». Редкое исключение — божественный Яндекс.Маркет, но и его загаживают последнее время жутчайше.
негативных отзывов на поведение контор из избранного списка
Чего чего сделали?
Вот здесь столько спецов из яндекса рассказывают про крутые алгоритмы, и ведь никто не ответит, почему на жалобу, что в яндексе галочка «искать как в запросе» банально ничего не делала и выдача оставалась такой же, решение было принято по удалению данной галочки.
Ну, так сказать, вот они — крутые олимпиадники в действии…
Ой это действительно боль, все еще пользуюсь яндексом по инерции, но заставить его найти именно то что я хотел а не то что он выдумал, это тот еще квест. Особенно весело, учитывая что я работаю с вещами по которым 1.5 статьи и из них одна на английском. Все чаще открываю гугл или утку.
Но справедливости ради это не вина олимпиадников, это вина их начальников. У меня вообще складывается ощущение, что я последний адекватный руководитель на планете, ну что за треш то кругом а.
Ну ок, значит будем людям объяснять что на я.маркете отзывы смотреть нельзя, пусть фламп развивают.
Вполне вероятно, что в FAANG средний уровень выше банально за счёт того, что и конкуренция, и ареал поиска кандидатов куда больше.
С чего бы это? В сам FAANG конечно больше кандидатов, но вот и мест там значительно больше.
При этом для выпускников местных топовых вузов, как мне объяснял один знакомый из Долины, пойти в Гугл, это не как для москвича после МГУ / МФТИ пойти в Яндекс. Скорее как для москвича пойти в какой-нибудь банк, разгребать несвежее легаси, поскольку местные успешные разработчики стараются идти в стартапы за долей в компании.
Вполне вероятно, что в FAANG средний уровень выше банально за счёт того, что и конкуренция, и ареал поиска кандидатов куда больше.
Среднее по больнице на то и среднее, что на больших числах размеры конторы перестают влиять на средний IQ там работающих. )
ps Советую не обожествлять фаанг. Судя по рассказам, локального бардака и бюрократии там куда как больше.
С топовыми компаниями тут ошибка выжившего — не они топовые по тому что у них эффективная система найма сотрудников, а неэффективная система найма сотрудников не мешает им процветать потому что они топовые (много денег и многие хотят там работать).
пройдёт лет 10 и слоупоки-подражатели типа Яндекса тоже сменят пластинку и начнут подражать новым веяниям из Кремниевой Долины
А мне кажется, что они не слоупоки и совсем не подражатели. Просто «отличники» или около того, в большинстве своем. Ну привыкли просто так со школьной скамьи… по другому не умеют. Им бы, наоборот, поучиться у гугла с майкрософтом или у других, более адекватных к собесам российских контор. Вон ниже Emil983 о них [google/ms] рассказывает.
Я уже раза три за последние 15 лет, устраивался в подобных топик-стартеру условиях в топовые компании. Слава богу, попадались адекватные интервьюеры и будущие коллеги. Работа-то далеко не из задачек на классические алгоритмы состоит. )
А про Яндекс сколько лет не проходит одно и тоже: тупой онанизм на алгоритмы и не надо рассказывать что то «ну а как же им еще большой поток неадекватов отсеивать». У FAANG их куда больше и они постоянно улучшают процессы. В прошлом году в гугле код надо было писать в гугл доке (о да, круто, правда?), в этом уже они свой редактор сделали и плюс ввели кроме кодинг еще и код ревью собес для менеджеров.
Окей, в Гугле на первой итерации попросили сдизайнить шедулер тасков, не совсем типичная с литкода, но такие там тоже есть.
Типа надо сделать 2 метода
TaskId enque(Task task, Time time);
void cancel(TaskId taskId);
Больше вводных вроде бы не было. В целом достаточно творческая, есть над чем подумать, не супер сложная (это фон скрин был), но и не «разверните строку».
Вообще, стандартное решение этой задачи — с использованием priority_queue.
В очереди хранится пара {время, TaskId}, упорядоченная по минимуму времени. Еще нужен map TaskId->время. При enqueue создается новая задача и помещается в очередь. При cancel соответствующая запись из очереди удаляется.
Не надо даже писать очередь, можно использовать stl-овскую, например. Правда, могут спросить, а представляете ли вы как эта структура данных работает.
Другой поток просыпается при любом enqueue или по таймеру. При просыпании он смотрит, пора ли выполнять следующую задачу и выполняет ее. Если рано — ставит таймер до следующей задачи.
По-моему, при написании от кандидата не требуют знаний системных вызовов для таймеров, событий и потоков. Обертки над всем этим и так есть в любой большой компании. Достаточно сказать: ну пусть у нас есть Event, у которого есть метод Wait(timeout), который усыпляет поток, пока не выйдет таймаут или кто-то не вызовет у этого объекта метод signal. Тут интервьюер может даже подсказать, если только кандидат скажет, что надо усыплять потоки. Если кандидат знает про select — это плюс.
Потом могут быть дополнительные вопросы, а что делать, если какая-то задача выполняется дольше, чем дедлайн до следующей? (запускать следующую сразу и не засыпать). Можно ли выполнять задачи в несколько потоков? (можно. Один поток все так же спит, отсчитывает таймеры и работает с очередью, а другие спят пока не получат задание на выполнение).
Еще надо помнить про всякие крайние случаи — типа enque задачи в прошлом времени.
Колеса времени
В очереди хранится пара {время, TaskId}, упорядоченная по минимуму времени. Еще нужен map TaskId->время. При enqueue создается новая задача и помещается в очередь. При cancel соответствующая запись из очереди удаляется.
Тогда уж нужно TaskId -> Node, чтобы можно было из очереди за О(1) удалить, иначе для удаление задачи с конца нужно долго и упорно пёхать по всей очереди (если она в виде связного списка реализована).
Из priority_queue за время О(1) удалить не получится. По крайней мере, если это priority_queue на основе "пирамиды".
Хотя если брать "в среднем", то да, О(1) и выходит… Но в любом случае для нужно время, а не Node.
Впрочем, если есть Node, то его можно не удалить, а "задизаблить".
Еще можно std::set использовать в качестве очереди.
Я собеседующий в Гугл. За последние пару лет в процессе собеседования не поменялось принципиально ничего. Те же задачи, похожие на литкод. Да, хорошим тоном считается завернуть их в обёртку реального мира. Например, не строку ААААВВВ преобразовать в А4В3, а что-то, что вы военный радист и получаете донесения с передовой для дальнейшей передачи в штаб. Вам надо раз в день собранный поток сообщений как-то уменьшить в объёме, но сохранить порядок. Ещё известно, что часто подряд приходит много однотипных сообщений. Вопрос — как будете преобразовывать? Тут с помощью интервьюера дойдёте до исходного условия и дальше напишете тот же алгоритм (ну или не напишете).
P.S. я — бывший сотрудник.
Нет, они довели до абсурда худшие практики, которые в FAANG постепенно уходят из повестки собеседований.
Несколько лет назад, когда я проходил свои 4 собеседования в Яндекс, они всё же были другими. Там про архитектуру и проектирование систем спрашивали, про устройство Linux, распределённые системы и т.п. интересные вещи. А то, о чём написал автор — это квинтэссенция идиотизма. Бессмысленная трата времени и очень плохой алгоритм фильтрации и проверки кандидатов.
В начале собеседования с Гуглом, вас потребуют подписать NDA, что ни какие подробности интервью вы не можете разглашать. Какие последствия? Наверное через суд, заставят оплатить издержки, например, потратили время на 1000 кандидатов, которые уже знали заранее ответы, или оплатить 100 часов на переделку всех контрольных билетов. :-)
common = set(a).intersection(set(b)) # найдём общие элементы
for el in common:
occurs = min(a.count(el), b.count(el)) # и посчитаем, сколько они встречаются
Простите, не смог пройти мимо. Если a и b — один и тот же набор из 1000 различных чисел, то эта программа пройдет по каждому из списков по 1001 разу. Получится пара миллионов сравнений и прибавлений счётчиков. Короче получилось O(n²).
Ага, сам знаю. Но именно так я и написал бы в проде. Это легко читается, достаточно быстро на небольшом количестве элементов (а сколько их обычно будет в реале, 10-20?), легко пофиксить, если станет боттленеком. Preliminary optimization — зло, как по мне.
list((Counter([1, 2, 3, 2, 0]) & Counter([5, 1, 2, 7, 3, 2])).elements())правда не знаю какое тут О
На интервью не требуют писать стандартные структуры данных. Сойдет и использование встроенной хеш таблицы. Запрещают пользоваться стандартной библиотекой там, где есть встроенное решение всей задачи. Иначе проверять нечего.
Ну, на худой конец, можно отсортировать и слить 2 списка. Будет O(n log n) вместо O(n). Если сказать, что можно и хештаблицей, но я боюсь, что не напишу ее за интервью.
))\n — скобки закрывать надо!
Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there.
https://randomascii.wordpress.com/2021/02/16/arranging-invisible-icons-in-quadratic-time
а сколько их обычно будет в реале, 10-20?
20 уже много. Вот если 3-5. Причём нужно очень хорошо понимать, какие реальные объёмы могут встретиться на проекте. Не только самые типовые. А то потом получится как на gitlab-е, или ikea. На gitlab-е открываешь большой MR и оно едва ворочается. Или вот в ikea видимо тоже примерно так подумали — сколько человек товаров может заказать? 5? 10? Нормааально. Заказываем 14 и страница зависает на любое действие на секунды.
Не шутите с квадратами. Мы, программисты, очень часто далеки в своих оценках от реальности.
P.S. а ещё всякие катастрофические regexp-ы, убивающие поток на минуты попадись им строка чуть длиннее обычного.
Или вот в ikea видимо тоже примерно так подумали — сколько человек товаров может заказать? 5? 10? Нормааально. Заказываем 14 и страница зависает на любое действие на секунды.
Ситуации вида "ваш сайт дико тормозит" в коде вполне могут быть выражены ситуацией "наш код прекрасен и работает за O(1). Тормозит что-то? Ну, это проблема не на нашей стороне, а какой-нибудь там реакт редакс браузер виноват, но не мы (с)". Это, опять же — тоже реальный личный опыт из разгребания не вполне рабочих фронтовых проектов, созданных руками чудо-алгоритмистов.
Скажем, уже больше 10 лет назад меня попросили "оживить" проект-презенташку очень важных данных в виде таблички, где у чудо-алгоритмистов, написавших чудо-бэкэнд, вдруг возникли сложности с презентованием результатов. Я пришел, увидел код, который на примерно любое действие пользователя собирал огромнейшую строку (всю страницу вместе с большой-пребольшой таблицей в основе) и фигачил её в корневой элемент презенташки через innerHTML. Когда я немного пришел в себя и поинтересовался, как такое вообще могло появиться — мне было сказано, что тут всё реализовано через минимальную алгоритмическую сложность O(n), и это всё так и надо и правильно. А что тормозит (браузеры немного выпадали в осадок и потребление памяти дико скакало, с ожидаемыми тормозами в моменты, когда она вся выжиралась) — так это просто браузеры плохие. И вообще этот ваш веб новомодный отстой.
Я ни разу не спорю с тем, что базовые алгоритмы это только один из многих необходимых навыков :)
собирал огромнейшую строку (всю страницу вместе с большой-пребольшой таблицей в основе) и фигачил её в корневой элемент презенташки через innerHTMLТак дело именно в том, что это были не алгоритмисты, а ровно наоборот — люди, не имеющие представления об алгоритмической сложности. Уж алгоритмисты-то обязательно для начала поинтересовались бы, каково это — добавить здоровенное поддерево в dom. Сделали это как раз те, кто говорит и пишет в каждой подобной теме, как же это тупо — проверять кандидата на понимание алгоритмической сложности. Самому регулярно приходилось и приходится ликвидировать последствия подобного кода. А все потому, что люди даже не видят, не замечают, не понимают, что они на самом деле постоянно сталкиваются с оценкой сложности в повседневных задачах, вот о чем важно говорить.
Инженерное искусство состоит в умении хорошо скомпоновать готовые решения, сделать конечный продукт поддерживаемым и простым в расширении, а так же в умении видеть необходимость оптимизации, когда нужно делать что-то новое. Если готового решения не существует, пойти и разработать свое собственное. Если не хватает экспертизы — посоветоваться с кем-то.
Вы описали какие-то абстрактные требования, вопрос-то в том — КАК понять, что кандидат ими обладает? Я встречал кучу кандидатов (в тч когда побеседовал работников Яндекса в других конторах), которые молоть языком горазды — и расскажут как они сделали «конечный продукт поддерживаемым и простым в расширении» и что у них есть «умение видеть необходимость оптимизации, когда нужно делать что-то новое», но вот беда — hello world написать не могут. Как отсеять болтунов?
Вы точно понимаете, что именно делает инженер? Подсказка: он не крутит гайки. Ну, может, крутит немного, но разве что на прототипе.
> Как понять, что я инженер, а не токарь Вася с завода?
Пообщайтесь по предметной области, коснитесь углубленно каких-то тем, попросите показать, над чем он работал раньше. Конечно, это будет проблемой, если вы сами плаваете в теме. Тогда да, задачки с литкода — ваш выбор.
> молоть языком горазды
Как отсеять болтуна-физика, прикидывающегося инженером?
Ну вот я общался с кандидатами — красиво стелят, якобы делали то, сё, пятое, десятое, а hello world написать не могут. Что с такими делать? Поверить на слово что он реально это делал? Тогда почему не может hello world написать? Или включить презумпцию виновности и решить что он балабол и просто сидел на зарплате глядя как другие вот это все описанное делают, а сам JSONы два года перекладывал?
> Как отсеять болтуна-физика, прикидывающегося инженером?
Я не знаю, вы мне скажите=) Для программистов вот есть задачки с литкода — если человек потратил недельку на подготовку к собесу, он их решит. Если не потратил — то точно ли он хочет новую работу или просто так с улицы зашел? Как быть для инженеров — хз, не моя тематика.
Программист — это в первую очередь инженер (как инженер-механик). Есть программисты-ученые (это как физики), которые занимаются computer science. Написание продакшн-кода — это почти несвязанный с этим процесс. Но многие этого не понимают и продолжают нанимать физиков для проектирования трансмиссий.
Если вы не можете отличить балабола от опытного специалиста — вы плохой собеседующий. Если пытаетесь сделать это с помощью литкода — вдвойне. Потому что литкод не показывает умения проектировать архитектуру, не показывает умения грамотно структурировать проект и декомпозировать задачу. Литкод — это алгоритмическое задротство.
Вы — не гугл. Вы не можете пользоваться этой методикой. Гугл ее использует, потому что богат и может себе позволить найти задротов, нанять их, а потом спустя год работы отсеять тех, кто не имеет инженерных навыков. Вы за год работы этих самородков потеряете деньги и получите малоподдерживаемое глючное дерьмо в продакшне.
Всё же механика часть физики.
И я такой не один, нас таких достаточно много.
В абсолютных цифрах — возможно. А в потоке людей — очень и очень мало. Ну представьте себе что человек проходит какие-нибудь 3-недельные курсы на ютубе, его научили правильно отвечать на "что такое солид" и какие-нибудь киты ООП, но он реально не программист, а какой-нибудь дворник который попал на таргетированную рекламу "заработай 100500 на ~~джойказино ~~яндексе".
И вот на одного такого вас 19 вот таких фот "типа программистов".
Если в маленькой компании с вами могут нормально поговорить по душам и распознать одно от другого (это не трудно, если уделить достаточно времени) — то в компании "на потоке" кроме как собсвтенно попросить кодить это не проверить.
А вот ужастиков через третьи руки слышал, да, вот только ни разу не видел подтверждений, сколько не спрашивал
Увы, тоже пример личный. Один человек вообще себя искренне называл "Аватар тестирования" (я иногда принимаю участие в собеседовании QA, рассказываю про архитектуру и прочие вопросы по компании с точки зрения разработки).
Есть и другие истории, но их пожалуй приберегу, не все из них хочется в паблик писать, мало ли увидят и обидятся.
Если числа не очень большие по модулю — то динамическое программирование, как в задаче о рюкзаке. Будет решение за O(n*M), где M — сумма всех чисел по модулю.
Если числа — любые инты, то только перебор.
А вообще, я невнимательно прочитал задачу. Там надо не подмножество чисел взять, а отрезок из массива. Решается за линию. Идем по массиву считая частичную сумму (до начала). Поддерживаем хешмап уже известных сумм. Смотрим, есть ли там target-<текушая сумма>. Если есть — мы нашли отрезок. Потом кладем текущую сумму в мап.
Нет, просто частичные суммы. От начала до текущего элемента.
Основная идея решения: сумма на отрезке — это разность двух частичных сумм. Поэтому если для каждой частичной суммы достаточно проверить, что левее есть нужная частичная сумма.
Вот набросок кода:
pair<int, int> FindRange(const vector<int>& v, int target) {
std::unordered_map<int, int> sums;
int current_sum = 0;
for (size_t i = 0; i < v.size(); ++i) {
current_sum += v[i];
if (current_sum == target) return std::make_pair(0, i+1);
auto it = sums.find(current_sum - target);
if (it != sums.end()) {
return std::make_pair(it->second+1, i+1);
}
sums[current_sum] = i;
}
return std::make_pair(-1, -1);
}Можно избавиться от одного случая, если изначально впихнуть в map {0, -1}, но понятнее без этого, мне кажется.
Вот в псевдокоде:
Сложность O(n)
int[] nums = {1,-2,4,8,....whatever}
hashtable(int) h;
int target = 9;
for(I: nums)
if(h.contains(9-i))
{
print «решение = », 9-i, I;
}
else
map.insert(i)
итерируемся по массиву заданных чисел.
если в хештабле есть искомое-текущее значение итератора, значит решение найдено, иначе кладем текущее в таблицу и итерируемся дальше
— один из рекрутеров пользовался компилятором. Просто я что-то нестандартное написал, и без прогона через тесты сложно было понять, во всех ли случаях будет работать.
— на последнем интервью вообще вышло разногласие. Я опять попытался изобрести свой алговелосипед (но не успел), и мнение по поводу работоспособности такого алгоритма у нас с рекрутером разделились. :)
P.S. leetcode крут. Иногда хожу туда за интересными задачками
ЗЫ ну если им по ставке 200к так не жалко своего и кандидата времени, видимо нужно просить 400 с порога
Видимо чуваки, бодро решающие алгоритмические задачки, не в состоянии написать форму обратной связи.
Памятка сотрудникам техподдержки:
Это письмо составлено не потому что проблему у Автора, а потому, что проблема у Вас
Это письмо составлено потому, что Автор уважает труд разработчиков и считает что фидбек лишним не бывает.
Автор сам может справиться любой проблемой или прекратить использование продукта.
Если вас устраивает, что ваши пользователи будут сталкиваться с вышеописанной проблемой, просьба проигнорировать это письмо или в ясной форме озвучить свою позицию в ответе.
Во вторых писал я с действительно серьезными ошибками по их api/интерфейсам.
По более мелким типо отсутствия заливки фона в firefox, да, бесполезно.
Такие же наблюдения. Не понимаю где они берут специалистов с таким подходом?
Создалось мнение, что хорошие спецы попадают в большие компании будучи купленными в стартапах, а там где стартапов нет, там одни задроты-алгоритмены.
Но может это тоже работает? Нанимаешь абстрактного алгоритмена в вакууме и расширяешь необходимыми методами
Хотя, глядя на современный софт, и, даже фреймворки, разрабатываемые корпорациями, (привет гуглу и фейсбуку), которые, вообще, должны быть эталоном кода, понимаешь, что и там квалификация вайтишников на донышке.
ЗЫ опыт работы с пхп чуть больше года, уже три тикета на гитхабе aws php sdk создавал, и объяснял как им надо их баги исправлять… Мир катится в ад
А вот обратное — уже проблема. Если человек владеет инструментами, но алгоритмы сочинять не умеет, то он застрянет на вполне себе практических задачах вида «отобразить оператору клиентов, которых надо сегодня прозвонить, это клиенты, у которых есть звонки с указанной датой следующего прозвона меньше либо равной текущей дате, и нет звонков с датой следующего прозвона больше текущей даты», которые не лежат в готовом виде на SO.
Ну возьмите одного такого на 50 человек в качестве консультанта, чего ж в этом плохого? Конечно, иногда и список развернуть надо, но с чего бы такое внимание именно на этом аспекте?
Ну тут сразу два перебора получается: 1) спрашиваем три раза про одно и то же; 2) не спрашиваем больше ни о чём.
В некотором смысле каждый кулик своё болото хвалит — неудивительно, что люди, которые сильны в алгоритмах, считают, что это и есть самый важный и незаменимый навык. Но человек хорошо разбирающийся в железе или в особенностях того или иного языка/фреймворка /архитектуры тоже может доказать, что его навык самый главный. Тем более, что требования к алгоритмической задаче хорошо формализуются, и всегда можно найти если не своего, так внешнего консультанта, который это решит за лайки или за пиво.
Нужны совсем-совсем другие наыки, например, научиться использовать свое приложение. Знаете по моему сотни програмеров по миру делали рандомный лут в играх. Помню ровно одну игру с нормализацией на матожидание игрока и еще помню в диабло фикси на эту тему, все, в остальных «корейский рандом». Умные книжки на эту тему кстати есть.
Собеседование в Яндекс: театр абсурда :/