Comments 328
Забавная штука. Мегакорпорации могут позволить себе (и позволяют) набирать лучших из лучших, а конечный результат их деятельности вызывает, так скажем, много вопросов. Может лучше отпустить чуть-чуть узду инженеров и внимательнее относиться ко всяким менеджерам, дизайнерам, директорам по развитию и прочим?

PS Ах да, /голосом Сухорукова из Брата 2/ «Вы мне еще за Panoramio ответите!»
Если всех этих людей чем-то не занимать, то они начнут расползаться. Поэтому они начинают плодить уже даже не вторичные фреймворки, нафиг никому не упавшие. Потом это же тянут в прод, чтобы оправдать усилия на их разработку, ко всему этому привлекается армия дизайнеров и фронтендеров, которые хотят красивенько, а не производительно. И получается тормозящий GMail, до кучи ломающий поведение кнопки назад в браузере и вводящий свою (ЗАЧЕМ?!), а также 3D на гуглокартах, чтобы вы каждый раз задумывались о смене своего компа, когда их открываете.
Все данные собеседований собираются воедино
За этот год можно систематизировать свои знания и заполнить обнаруженные пропуски.
Существует ли способ узнать, что именно не устроило независимый комитет, или при заполнении пропусков нужно ориентироваться только на то, что ты сам посчитал тем, что могло не устроить независимый комитет?

Отчёт о собеседовании не доступен, но HR обычно транслируют что прошло не очень хорошо.

А как же GDPR?


всё, что можно получить в соответствии с законодательством — можно получить в соответствии с законодательством.
я не знаю применим ли GDPR в данном случае, поэтому ничего сказать не смогу.
я описываю процесс как я знаю, на инженерные позиции


Либо я чего-то не понял, либо одно из двух. Собеседование на позицию инженера включает в себя подозрительно много кодинга? Я с трудом представляю себе ситуацию, когда, например, network engineer-у нужно будет быстренько нарисовать LRU-кэш.
Хм. Вообще, учитывая вещи типа ai.google/research/pubs/pub43837 — да, даже сетевику это может потребоваться.
Но да, как у них — я не знаю. Я пишу про SWE/SRE — добавил это в статью.

Кодинг есть почти везде, но в разных количествах. К примеру, если тебя нанимают на позицию менеджера, то кодинг точно будет. Даже если на позицию директора — тоже будет, но уже не очень много. По поводу не-software engineer специальностей не очень в курсе.

У сетевиков другое интервью.
Собственно, я с трудом могу сказать «другое», т.к. автор про интервью не написал почти ничего.

Я правильно понимаю что google набирает себе инженеров, и в рамках работы будет использован тот язык который лучше для данной задачи ?

Гугл набирает людей надолго, возможно даже навсегда. Поэтому залипать на какую-либо технологию и/или язык не получится. Выбор языка всегда вопрос баланса скорости разработки, стоимости поддержки и личных вкусовых предпочтений разработчика.
Выбирать команду можно под свой любимый язык, если так хочется; ну либо команде объяснить почему взять именно этот язык.
Таки что да. У меня есть бейджик за коммиты на 25+ языках, но это по сути типы файлов, которые я трогал ручками (включая ascii proto, json и т.п.). Из языков программирования лично трогал bash, bcl, c++, go, python, java, javascript. Может еще что было по мелочи, уже не помню.
В этой статье не указано, но вот другая — www.businessinsider.com/average-employee-tenure-retention-at-top-tech-companies-2018-4?international=true&r=US&IR=T с другими цифрами и с небольшим описанием как собирали:

Turnover rates are drawn from LinkedIn’s member data. We calculate turnover by taking the number of departures/movement in a given population (e.g., the retail sector, the restaurant industry, or data analysts), then dividing that number by the average headcount of that given population in 2017. We consider professionals as leaving their position if they provide an end-date for their position at a company (excluding internal job changes within the same company). A member can have multiple departures and positions within the year period.


Вроде бы логично
То есть только на основании тех, кто использует LinkedIn. Что далеко от средней популяции по больнице.

Что, думаю более чем достаточно для исследования. Кто не использует линкедин в долине?

Это требует отдельного исследования :)
Ну и тогда не «в гугле» а «в гугле в долине».

Сейчас в гугле согласно последнего отчета ~85000 человек.
Согласно это статье в долине раньше была треть человек. То есть минимум две трети (~56 тысяч) не в долине и сомнительно что охвачена линкедином.

а еще сейчас глянул — на странице www.linkedin.com/company/google указано что там работает 153 тысячи… то есть в два раза больше, чем сотрудников в компании вообще.
в общем, как-то сбор данных странных.

В любом случае не понимаю в чём спор. Вы серьезно думаете, что люди работают в 1ой компании всю жизнь?

Я говорю что цель компании — нанять человека на долгий срок.
Вы приводите разные оценки с потолка что некоторые люди меняют место работы через то-ли 2 то-ли 3 года.

Ни то ни другое друг другу не противоречит, я просто указываю, что эта цифра не имеет никакого отношения.
> эта цифра не имеет никакого отношения.
К чему?

Цель то ясна, я просто говорю, что понятное дело, что она не достижима. Но даже если 3 года это правильная цифра (хотя я думаю она меньше), то это уже более, чем хорошо для Гугл так как это сильно больше среднего по индустрии.
К цели — а цель нанимать на долгий срок :)
Я знаю, что люди устают от одной работы.

Но если все одинаково оценены и наняты гарантированно все проходящие под общие требования, внутренний трансфер становится гораздо проще.

Кстати, даже для такой вещи, сюрприз!, нужны алгоритмы ;)
См. тут. У меня перед глазами достаточно примеров перехода людей между командами.

Таким образом, если сменить команду проще, чем сменить компанию, то люди будут оставаться в компании, а значит, расходы на интервью не будут увеличены на затраты для замены этого человека.
а еще сейчас глянул — на странице www.linkedin.com/company/google указано что там работает 153 тысячи… то есть в два раза больше, чем сотрудников в компании вообще.
в общем, как-то сбор данных странных.

Это видимо с учетом тех кто работал раньше там
Пролистал первые 50 страниц результатов — все, кто указан сейчас работающим.
Подозреваю, что сюда включены еще интерны, кто меняют статус только на следующем интерншипе, и те, кто ставят «работаю в гугле» чтоб им писали рекрутёры.

(когда я прописал что теперь работаю в гугле — у меня был десяток писем разных рекрутёров из разных контор «а не хотите ли к нам?», включая тех, кто обещал оплатить затраты на ранний выход если будут)
Судя по описанию методики, интерны в гугле имеют на эту статистику такое же влияние, как младенческая смертность на среднюю продолжительность жизни — практически ноль в числителе и +1 в знаменателе. Опять же гугл это такой интерншип который воткнут в профиль все, у кого он был. В итоге пять летних интернов и Сергей Брин в сумме приносят около трех лет как средний срок работы в компании.
Это не похоже на истину. Я работаю в Google UK с февраля, за это время из тех пары десятков людей, с кем я более или менее регулярно общаюсь, не ушел никто.
То что с февраля и то что 20 человек и то что UK, возможно дает другие цифры. Выше комментарий с более вменяемым иследование, чем то что я показал ранее.
Выше написано, что среднее время работы — 3.2 года. То есть, из, скажем, 20 человек, которых я регулярно наблюдаю, за 7 месяцев должны были уволиться в среднем 3.65. А уволилось 0. То есть, не очень похоже на правду (хотя, конечно, такое совпадение не невероятно).
Вы как-то странно считаете вероятность.
Если в каждом месяце сотрудник с постоянной вероятностью либо увольняется, либо нет — то это распределение Пуассона с матожиданием 3.2 года = 38.4 мес.
При этом вероятность, что сотрудник уволится за 7 месяцев, неотличима от нуля; и только на 17 месяцах достигает 0.01%.
Ах, если бы эти «исследования» считали среднее время работы матожиданием пуассона…
Но я же работаю не в окружении людей, которых наняли одновременно со мной. Из этих людей половина работают дольше указанных трех лет. Какова вероятность, что ни один из них не уволится за семь месяцев, в вашей модели с распределением Пуассона?
Точно такая же.

«Я три года подряд кидал монетку, и каждый раз выпадал орёл. Какова вероятность, что в следующий раз выпадет решка?» — ровно такая же, как и при любом из предыдущих бросков.
Точно такая же.
Давайте я опишу, как я вас понял, а вы скажете, где я ошибаюсь.

Матожидание количества уволившихся из 20 человек за 7 месяцев неотличимо от нуля. Это же верно и для вторых 7 месяцев, и ..., и для шестых. То есть, Матожидание количества уволившихся за 42 месяца тоже неотличимо от нуля (пусть и чуть побольше). Но матожидание срока работы в компании — 38.4 месяца.
Я вижу здесь противоречие.
Если вероятность остаться после одного месяца равна p, то вероятность остаться после n месяцев — это pn, а не p·n.
1-pn — это приближение снизу для выражения (1-p)^n. Если хотите, можно честно посчитать, без всяких приближений.

Будем считать, что события «человек уволился в течение месяца» независимы и одинаково распределены для всех людей и месяцев и имеют распределение Бернулли с параметром p. Матожидание времени работы в месяцах равно 0*p + 1*p*(1-p) + 2*p*(1-p)^2 +… + k*p*(1-p)^k +… = (1-p)/p = 38.4. Отсюда p = 1/39.4 ≈ 0.025. Вероятность, что один человек не уволится за 7 месяцев, равна (1-p)^7, а вероятность, что за 7 месяцев не уволятся 20 человек, равна (1-p)^140 ≈ 0.027. То есть, вероятность того, что я наблюдал то, что я наблюдал, получается достаточно низкой. О чем я с самого начала и написал, пусть и менее строго.
PS: Так и не понял, при чем тут распределение Пуассона, оно же показывает вероятность того, что из х одинаковых событий k произойдут. Мне не интересно, сколько раз кто-то уволится за 38.4 месяцев, мне интересно, какова вероятность того, что кто-то уволится за 7.
Из языков программирования лично трогал bash, bcl, c++, go, python, java, javascript. Может еще что было по мелочи, уже не помню.
Я помню!) — asm:)
Эта статья ПИД-регулятор своими руками в закладках, в надежде, что когда-нибудь на ее основе напишу на С для stm32
В гугле я асм еще не трогал :) не было нужды. Только в дизасме копался во время разбирательства.

У меня собеседование проходило на джаве, а 80% времени приходилось писать на питоне и внутреннем языке для конфигов.

Годы идут, а воз и ныне там…

Интервью в гуглоподобных компаниях и их подражателях давно сломаны, и никто не хочет их чинить (а многие даже признать, что они сломаны). Проблем очень много и о них можно было бы статью написать, но если выделить самое основное, то компании вроде гугла, майкрософта, амазона и т.д. пытаются принять решение о найме пианиста по его способности играть на скрипке (это если повезло и борщ не заставили варить).

Хочется верить, что тот, кто изначально использовал задачи-головоломки на собеседовании действительно умел ставить по процессу решения правильный диагноз, но потом все сразу сломалось, как только собеседующие стали оценивать правильность ответа, вместо процесса размышления. Тут я поступлю нечестно и не буду ничего доказывать. Скажу лишь, что все-таки есть адекватные собеседующие, которым не все равно, кого наймут, а кого нет (обычно это в не очень популярных компаниях с точки зрения HR бренда, например, мне лично понравилось интервью в JP Morgan, хотя это вообще банк).

Те, кто в теме, мне возразят, что в гугле уже не задают задачи-головоломки, но на самом деле ничего не поменяется от того, что вы спрашиваете задачи вроде «поиска подотрезка с максимальной суммой». Если не знать решения на эту задачу, то вам явно не хватит 30 минут, чтобы ее решить. И даже показать, как вы думаете. Максимум вы всунете туда какой-то NlogN трюк, и не факт, что такой спец будет хуже «звезы», который знает решение, и не факт, что он будет лучше человека, который «почти» придумает линейное решение, но не успеет за 30 минут.

Если гуглу нужен «крутой алгоритмист», то вопросов нет, но гугл же утверждает, что они инженера нанимают. И вот тут можно вспомнить про борщ, о котором я говорил выше. Я не отрицаю сильную корреляцию между инженирингом и алгоритмами (математикой в общем случае). Человек, который знает алгоритмы и, например, еще участвует в контестах, может быть заодно еще и хорошим разработчиком софта. Но все таки разработка софта — это марафонский бег, и спринтер, даже самый лучший может не добежать до финиша в нужной кондиции.

Описанный кейс лишь одна маленькая грань большого айсберга системы найма, которая кстати заодно разгоняет скорость текучки и снижает комфорт и фан от работы. Да и качество конечного продукта давно оставляет желать лучшего.
Огромный холиварный момент. Я постараюсь описать в следующей статье ответ на вопрос «почему» именно так, зачем столько собеседований и проч.

Да, гарантий нет. Да, спортивное программирование не даёт информации о том, как будет человек работать в перспективе. Но оно, например, даёт знания алгоритмов и их реализации. А еще заставляет думать о граничных условиях.

На тему «знать» решение… Я получал прекрасный ответ на свой любимый нынче вопрос на собеседовании в первые 10 минут — кандидат смог сразу найти O(1) решение используя креативный подход к организации данных. И да, это не была домашняя заготовка — что легко выяснилось после усложнения задачи. Просто отличный сильный кандидат.

В целом, процесс собеседования модифицируется со временем и адаптируется (да, вы верно заметили — крышки люков больше никто не просит посчитать), но эти изменения не идут с бухты-барахты. Это всё «data-driven» осознанные изменения с оцененной и подтвержденной эффективностью.
Вы «защищаетесь» не с той стороны, с которой я «нападаю».

А на счет домашней заготовки, ну это еще не факт, что хорошо. Есть люди, которые хорошо проходят интервью, а есть те, кто хорошо работают, и это далеко не одни и те же люди. Зайдите на любой сайт, посвященный теме интервью, первое, что вы там увидите «I will teach you to be good at programming interviews» написанное разными словами. То есть это как минимум говорит о том, что проходить интервью и работать это две большие разницы. Это УЖЕ должно наводить на мысль о том, что система сломана.
:) да, есть профессиональные проходители интервью.
Тоже уже встречал, видно практически сразу.
Это всего лишь сокращает первую фазу до 2-5 минут.
А дальше начинается изучение как они думают вне стандартного интервью.

Я помню на хабре несколько комментов, как человек ходит регулярно на собеседования, чтоб навык не заржавел, ага
Ага, а еще это неплохой способ съездить, скажем, в Норвегию на рыбалку за чужой счет. Ищем подходящую компанию, а дальше дело техники.

И это еще одна «грань» вышеупомянутого айсберга. Способности потенциального работника ставятся выше его мотивации, хотя без должной мотивации сотрудник будет больше вреда приносить, чем пользы, вне зависимости от его навыков.
Гляньте тут: careers.google.com/how-we-hire/interview/#onsite-interviews
мотивация и его googlyness тоже оцениваются.

Но в целом, съездить так получится один раз только на одну компанию, плюс старая компания не должна обидеться на такое поведение, плюс а вдруг понравится? если человек хорош и прошел заочные собеседования, то есть шанс что он приедет-посмотрит, а там глядишь и работать придёт.

все в выигрыше, разве нет?
Ну тут тот же эффект как в инвестировании: инвестировать в компании, которые еще не прибыльные опасно, но им очень нужны инвестиции, а инвестировать в компании, которые уже вышли на прибыль сложно, потому что все хотят туда инвестировать, а инвестиции этим компаниям уже могут быть и не нужны.

Чаще всего компания хочет тех сотрудников, которых не может получить. Поднимает ставки, и на их место начинают ломиться те, кто на все согласен ради бесплатных обедов и пуфиков.

Вообще на вопрос о мотивации — если человек на собеседовании приходит с низкой мотивацией, а потом его удается «разогреть» это как раз лучше, чем нанять «гуглофана», потому что в голову-то не залезешь, этот гуглофан может быть кем угодно от инсайдера до интервьюкракера. А вот если человек не очень-то хочет работать в гугле, то это не просто же так. На интервью его наверняка соблазнил HR. Всегда было интересно, что бы ответил интервьюер, которому кандидат скажет: «мне че-то лень печатать, давай я тебе продиктую код, а ты сам запишешь»…
Я на NALSD собеседовании описывал всю систему из головы. Без вайтборда (я до сих пор так и не научился пользоваться ею!). Итервьюер протоколировал всё в конспект. После еще и нарисовал на доске как он меня понял, и мы обсудили моменты где у него были сомнения.

У меня пока такого не было, но я в пометки себе вношу всё что кандидат думает в слух а не записывает, чтобы не потерять.
— один раз только на одну компанию

Не соглашусь, я вот ездил в Амазон чисто потому что уже обещал приехать на собеседование, хотя оффер принял для другой компании. И снова зовут приехать.
Ну у них наверно KPI завязан на число собеседуемых, а то что компания от этого деньги теряет, никого не волнует. И так во всем. А все почему, потому что нанимают не тех, кто будет отстаивать интересы компании и быть «в доле» с компанией, а нанимают абы как абы кого лишь бы мог «очередь реализовать двумя стеками с амортизационной сложностью О(1)». Остальные специальности наверно так же нанимают… И тут вы скажете «как ты смеешь критиковать компанию, которая стоит триллиард долларов», а я возражу, что система сломана не только внутри компаний, но и снаружи. Самые умные люди в мире в среднем это все-таки ученые, но в среднем они не самые богатые. Хотя без ученых эти триллиард как цифра не существовала бы :)
Все эта сложная система собеседований мне не по душе, это как билет в закрытый клуб.

Хотя я понимаю, что система позволяет в какой-то мере уменьшить вал непригодных для девелопмента людей, каким-то образом туда по-павших.

В итоге я работаю в компании, где у меня была пара собеседований и я не писал ни строчки кода.

Компаниям из первой десятки надо хотя бы уважать людей, проработавших лет по пять в нескольких крупных компаниях — ведь понятно если человек работает несколько лет и его не слили через год — значит он реальную пользу для компании приносит и весьма вероятно не будет балластом для следующей.

А крупные компании вообще хотя бы кого-то могут слить через год? Во всех крупных компаниях, где я работал, была процедура «перевоспитания» на год-два как минимум. В первую очередь, чтобы не было исков о неправомерном увольнении.
В USA еще есть небольшая вероятность быть уволенным из большой компании, а в Европе практически не реально. В потолок можно плевать годами.
«Небольшая вероятность»? Почитайте, пожалуйста, что означает «employment at will».
А вы задуматесь над тем почему в некоторых источниках говорится о восьмидесяти тысячах сотрудников Гугла, в некоторых — о ста шестидесяти и при этом между этими данными нет противоречия.

И да — это-таки имеет самое прямое отношение к «employment at will» и не только в Гугле.
Р — релевантность.

А противоречие есть. В отличии от вас, говорить загадками либо отвечать на ваши в этом конкретном случае я не имею права.
Очень просто: восемьдесят тысяч — это сотрудники Гугла без учёта контракторов (тех, которые «employment at will»), сто шестьдесят — с учётом. Это не секрет — если бы вы вместо того, чтобы «вставать в позу» погуглили бы, то могли бы найти, скажем, вот эту статью.

При этом таки большинство SWE/SRE — это вовсе не контракторы… почему из и отбирают по несколько более сложной схеме, чем поваров или уборщиков.
Р — релевантность.
У — упорство.

Расскажите мне, пожалуйста, как постоянные работники Google в США не имеют строчки про «employment at will» в контракте.
Думаю, США не особо отличается от Канады, где увольняют просто со свистом независимо от размера компании.

В поддержку автора выше. Несколько лет назад было весьма неплохо проведённое собеседование в Гугл, которое я в итоге не прошёл. Самый последний интервьюер дал задачку на разбиение текста на слова из словаря. Я ему сразу сказал, что это можно оптимально решить с помощью построения соответствующего конечного автомата, но я не помню ни одного алгоритма для этого наизусть, и пытаться придумать и написать один за 45 минут ну никак не смогу. Вроде бы убедил ограничиться обычным Hashmap, но в самом конце он всё равно переспросил про Ахо-Корасика. И вроде бы даже не стал спорить, когда я напомнил про конечные автоматы и то, что А-К это просто хитрый вид оного.


При этом это был единственный момент, когда что-то в диалоге с собеседующим явно собеседующего не устроило. А теперь rant: ну не хочу я ботать эти ваши Ахо-Корасик и сложные алгоритмы на графах (это я о клипах, простой поиск пути ок). Сейчас в индустрии есть полно куда более полезных и, имхо, важных вещей вроде: пресловутая иерархия памяти (почему B+ лучше бинарных деревьев, и т.п.), многопоточная синхронизация и модели памяти (приходилось методом пристального взгляда искать состояние гонки в большой системе), безопасность (в любом баш скрипте в Амазоне, которые я видел это — полный ахтунг, никогда не используйте баш). Из недавнего — deep learning, как минимум принципы которого надо бы понимать, и где алгоритмы, каждый сложнее Ахо-Корасика, выпускают по 2-3 в год. Ну и, конечно, пресловутый блок-чейн (инженер FB не знал про существование и смысл SHA256, и не смог или не захотел понять решение задачи, включающее вероятность ошибки из-за коллизии в 10^-41 в течении 30 лет по тем ограничениям, которые он сам задал. И это ещё не полный список.

вы спрашиваете задачи вроде «поиска подотрезка с максимальной суммой». Если не знать решения на эту задачу, то вам явно не хватит 30 минут, чтобы ее решить
И это большая проблема очень многих компаний, которые дают алгоритмические задачи на собеседовании «чтобы как у Google». Но дело в том, что решить задачу — это вообще дело десятое, главное — показать, как ты думаешь. Если человек может выдать неоптимальное решение, а потом о нем хорошо порассуждать, это будет гораздо лучше (с точки зрения шансов попасть в Google), чем молча написать оптимальное. И в статье, кстати, об этом было написано.
Почему-то спрашивают про головоломки, но меня ни разу не спросили — есть ли у тебя программы, которые проработали несколько лет? По моему — это лучший показатель опыта и более взрослый подход.
что вы понимаете под головоломками?

у меня есть программы которыми пользовались много лет. даже без модификации.
и нет, я ими не горжусь, и даже постыжусь показывать…
Я, когда не прошел интервью в Гугле, решил собрать немножко статистики с интернета и посмотреть отзывы тех кто прошел. Конечно очень субьективно и выборка маленькая, но усредненно выглядит примерно так:
«Я после колледжа проработал несколько месяцев в одной компании, решил что меня это не устраивает и стал готовиться к интервью в Гугле. Я уволился с работы и 6 месяцев готовился по книгам и тестовым заданиям. Теперь я работаю в Гугле, счастлив и всем того же желаю.»
Обратите внимание — человек практически без опыта, зато потративший много времени и усилий именно на подготовку к интервью и именно в Гугле. Мне кажется, ихняя система отбора самонастроилась на именно таких кандидатов, как бы она там изначально не была задумана.
Вот, с вашей подачи прочитал. По моему очень типичный сценарий, только мотивация другая — автор изначально был настроен учиться, а подготовка к интервью выбрана как повод. Но обьем проделанной работы просто подавляет, вот в этом мне и кажется основная проблема — средний соискатель как правило физически не может пройти такое количество курсов и тестов за ограниченное время. Остаются самые мотивированные, но не обязательно самые лучшие. Кстати, если вы заметили, у автора тоже звучит мотив что само по себе изучение алгоримов в повседневной разработке не слишком полезно, а через пару лет без использования они забываются.
Короче, да, это примено то что я имел ввиду.
Не совсем так ) Я бы сказал, что изученные алгоритмы не используются в повседневной разработке. И забываются.
А вот изучение алгоритмов, как процесс, вполне себе помогает в повседневной разработке. Позволяет по другому взглянуть на задачи.
А то что алгоритмы забываются, это не проблема. Вспомнить то, что знаешь, гораздо проще, чем это выучить. И опять же есть знание, что в какой ситуации использовать.
Ну, там в было в контексте, не будем спорить.
Давайте я лучше скажу что я восхищен вашей работоспособностью )
Сами алгоритмы и структуры данных не занимаешься реализацией на повседневной основе. А вот решения принимаешь повседневные обоснованно и разумно, а не «так повелось». Выбирая между hashmap и treemap понимать что это не просто O(1) vs O(logN) на выборку; да и O(1) не всегда могут быть гарантированы у первого; и что порой лучше всё же vector, пусть даже надо поиск будет по нему делать.
И учишься комбинировать структуры. Тот же hashmap где все элементы слинкованы двоичным списком — для LRU кеша, например.

Ну вот я например эту разницу понимаю, но для прохождения интервью требуются более детальные знания, которые без целенаправленного обучения не получить. Тот же LRU кеш — это очень специализированная структура, которая нужна достаточно редко.
Вообще-то, все что я хотел сказать, студенты-отличники имеют по моему мнению некоторое преимущество при прохождении интервью такого типа, может это и неплохо.

Вообще-то, все что я хотел сказать, студенты-отличники имеют по моему мнению некоторое преимущество при прохождении интервью такого типа, может это и неплохо.
Как бы оценка в дипломе и должна описывать качество специалиста… что разумеется не всегда так (именно поэтому приходится проводить интервью я не брать на работу тупо на основании CGPA), но если бы корелляции не было совсем — то это обозначало бы, что вся система высшего образования вообще не имеет никакого смысла — а это, всё-таки, уже перебор…
Нет-нет, я не об этом совсем. Просто есть очень большая разница между сколько угодно хорошим студентом и специалистом скажем с десятиленим опытом. Здесь даже не лучше-хуже, просто другой подход к работе. В хорошей компании нужен баланс, иначе возникают последствия разные.

Да. При найме, кстати, на возраст не смотрят.
Я прошёл интервью без подготовки, через 8 лет после универа. Отличником не был :D


Так вот. Нанимают определённых людей, да. Нет, натренироваться на интервью можно, но шансов не так много. В конце концов, 14% ошибки все же остаются.

Ну, я вообще подозреваю что вы несколько особый случай.
А от Гугла у меня осталось именно такое ощущение — что надо именно натренироваться, безусловно в хорошем смысле слова, но все-таки. И рекрутеры этого кстати совсем не скрывают, первым делом дают список литературы для подготовки.
Насчет возраста — вопрос тонкий. Безусловно никакой дискриминации по возрасту нет, ни официально, ни неофициально. Однако существует такая модная практика — кандидат должен пообщаться с каждым членом будущей команды и быть им одобренным. Учитывая что как минимум треть состава джуниоры, может возникнуть конфликт поколений). Вот это не по слухам и не по впечатлениям, я точно знаю.

Однако существует такая модная практика — кандидат должен пообщаться с каждым членом будущей команды и быть им одобренным.
Сомневаюсь, что она практикуется в Гугле. Странно сочеталось бы с отсуствием интервьюеров в комитете…

Вот это не по слухам и не по впечатлениям, я точно знаю.
Это про Гугл или про какие-то модные стартапы?
Нет, в Гугле такого нет. Но это были и не стартапы — большие и известные компании, два раза минимум.
первым делом дают список литературы для подготовки.
Это логично. Раз большинство готовится — проще дать всем одинаковые материалы и спрашивать как с подготовленных, чем пытаться выяснить, готовился ли человек и почему.
Ну вот на сложность алгоритмов имеет смысл надрочиться перед собеседованиями, просто потому что в жизни точный ответ нужен редко, при принятии архитектурных решений.
А это происходит гораздо реже, чем просто написание кода
Это просто навык, который уходит в бэкграунд. Если попробуешь написать потом что-то кубическое, появится очень неприятное ощущение что что-то происходит не то.
А это происходит гораздо реже, чем просто написание кода
Это происходит при написании кода. Постоянно. То есть вы видите — на входе массив. И вы написали цикл, а внутри него find. В голове сразу звоночек: «так, у нас задача вроде как линейная, а я тут квардрат, вроде как устроил… что я делаю не так». Смотрим на find, обнаруживаем, что он срабатывает один раз или ни разу — успокаиваемся.

Шлемиэли встречаются куда чаще, чем нам бы того хотелось, увы — и хочется, чтобы у разрабочика был в голове звоночек, который бы срабатывал, когда он их видит…
А где полезно самому LinkedHashMap писать кроме собеседований в гугле, не подскажете?
Работа с файлами ресурсов, например.
Чтоб быстро как достать по имени, так и проитерировать в нужном порядке.
Я спрашивал про писать, а не использовать. Использую я сам весьма часто, но зачем кому-то понадобится писать свою имплементацию — вот это непонятно.
Например, если нужны дополнительные операции, типа поменять местами два определенных элемента.
Еще, насколько помню, в stdlib/stl нет эквивалента LHM.

Но в целом — важно знать что они есть, как ими можно воспользоваться, и какая у них сложность под капотом — чтобы конструировать на их базе свои решения осознанно.

При этом обычно не вызывает сложности их написать, зная наперёд какая должна быть сложность и как примерно они могут быть устроены.

А вот понадобится вам чуть нестандартный LinkedHashMap. Например, некотрые элементы нужно поментить, как неудаляемые из кэша. Простым LinkedHashMap уже не сделать. Вернее не сделать быстро.

Сделать. Можно простую обертку сделать например как тут android.googlesource.com/platform/frameworks/support.git/+/795b97d901e1793dac5c3e67d43c96a758fec388/v4/java/android/support/v4/util/LruCache.java

Два элемента в LRU местами менять смысла не имеет вообще никакого, т.к. это попахивает сортировкой связного списка. Но я согласен что это полезно знать что элементы хэш таблицы можно линковать. И еще полезнее знать что для большинства применений это либо написано либо делается существенно проще чем написание 'снуля'. Снуль вообще плохо обычно получается, особенно на интервью, особенно когда дают доску размером этак метр на метр и предлагают на нем полную имплементацию хэштаблицы впихнуть (даже не линкованной).
Объективный поиск показывает, что такой подход действительно нужен, чтобы отобрать лучших. То что вы нашли, скорее рекламные посты. Но существует другая проблема, которую хорошо иллюстрирует шутка:
Мы с коллегами часто шутили, представляя себе как Ларри и Сергей выходят в море на своих яхтах, пришвартовывают их рядом друг к другу, садятся в дорогие кресла, которые, несомненно, есть у них на яхтах, наливают себе скотч, раскуривают дорогие сигары и рассматривают фотографии гуглеров с такими маленькими ярлычками вроде “был гендиректором в мультинациональной телеком-корпорации, получил MBA в Гарварде, а сегодня работает в техподдержке Orkut“. А затем они заходятся в безудержном приступе хохота, тушат сигары в скотче и чокаются бокалами. Конечно, этого никогда не могло быть, потому что они не курят и не пьют. А впрочем, все остальное вполне правдоподобно”.
был гендиректором в мультинациональной телеком-корпорации, получил MBA в Гарварде, а сегодня работает в техподдержке Orkut
Некоторых гендиректоров лучше бы не пускать в техподдержку Orkut, а то всё развалят. Впрочем Orkut всё равно закрылся, так что возможно кто-то пролез…
У меня история была немного другая — в школьные годы чуть-чуть занимался олимпиадами, в ВУЗе забил. После выпуска пару недель по вечерам после работы чуть подготовился — устроился в Google.
Но самое важное на собеседовании — узнать как человек думает.

Вообще, оценка предложенного API тоже может дать дополнительный сигнал об опыте и стиле мышления кандидата.

Самое важное здесь: дать одновременно и очень простое задание, чтобы кандидат мог решить и показать базовые навыки, и поднять сложность до того уровня, где кандидат не знает ответа, чтобы он мог показать как он думает.

Так всётаки, вы оцениваете ход мыслей кандидата или предложенное им решение? Что для вас важнее?
Нельзя сказать что важно что-то одно. Это отдельные оси оценки кандидата.
Человека нанимают для работы прямо здесь и сейчас — поэтому человек должен уже уметь писать код. Компания ищет людей на долгий срок — а поэтому человек должен уметь думать и учиться. А так же компания ищет людей, кто будет решать задачи, которые еще не решены (иначе зачем их делать?) в том масштабе или аспекте какой требуется. А значит, надо уметь решать те задачи, которые еще не решены. Или тем способом, которым еще не решали. Именно поэтому важно найти точку где кандидат не знает решения, и смотреть, как будет искать выход.

Сведение к знакомому алгоритму? Хорошо.
Преобразование исходных данных? Тоже хорошо.
Попытка придумать новый алгоритм на ходу? И тоже хорошо!

Да, за пол часа (которые обычно остаются на этот шаг) редко кто может придумать что-то совсем прорывное, но этого никто и не ждёт. Важно смотреть как будет идти, сможет ли предложить решение, и сможет ли реализовать предложенное хотя бы в некоем подмножестве.
А что делать людям, которые на практике не работают со сложными алгоритмами и структурами данных? Вот я 10 лет занимаюсь разработкой и мне не требовались ни графы, ни деревья, ни уникальные сортировки. Есть готовые очереди, кэши, сортировки, сессии и т.д.
Получается, что людям вроде меня Гугл не светит?
Ну вы же знаете как они работают? Очереди, кеши, сортировки, сессии? Можете представить как их реализовать? Тот факт, что вы их не пишете — не означает, что вы не можете их написать, если подумаете. Плюс, если что-то не знаете, можно же подготовиться.

Если вы не хотите знать, как это устроено и как может быть устроено, какие ограничения и какая сложность под капотом у используемого решения — да, гугл не светит. Но не потому, что вы плохой специалист, а потому, что специалист другого профиля.

Есть вероятность, что эти люди просто не увидели, что "графы, деревья и уникальные сортировки" и прочие "теоретические" вещи нужны.
Мне в своё время (лет 10-20 назад) понадобились:


  • Диофантовы уравнения и метод ветвей и границ в оптовой торговле фармацевтическими товарами
  • Реализовать хеш-таблицу и B+ tree в 1С: Бухгалтерии 7.7
  • Изучить как работает TCP в части three way handshake, модель состояний и работы с SN/ACK SN, чтобы сделать похожий сеансовый обмен между складами
  • Решить проблемы отсутствия string builder в 1С 8 (при огромном количестве конкатенаций)
  • Оптимизировать решение систем линейных уровнений в расчете себестоимости.

Это просто примеры того, что якобы "теоретические" штуки могут пригодиться в неожиданных моментах "скучных" и "простых" областей.

А вам очень повезло, что у вас за спиной не стоял менеджер и не спрашивал каждые 15 минут, когда будет готово.
Я решалку СЛУ еще в колледже вполне успешно писал, но на практике такие вещи не пригодились мне. А там, где могли бы пригодиться, никто не дал бы времени на их реализацию и отладку.
К счастью, с 1С я не работал напрямую. Но по опыту знакомых знаю, что это то еще занятие. Была у нас самописная интеграция с 1С. Приходилось на PHP парсить гиговые XML, которые генерировались часами.
за спиной не стоял менеджер и не спрашивал каждые 15 минут

По-разному было. И стоял, и кричал, и не один менеджер. Но я с такими "менеджерами" долго не работаю обычно. Оно того не стоит.


никто не дал бы времени

Дал бы. Если другого решения нет. С вашими гиговыми XML — если поток XML станет больше, чем может съесть система. Если нерешение проблемы = отзыв лицензии. Обычно получается объяснить, что время нужно. В общем, надо уметь его взять.


решалку СЛУ еще в колледже вполне успешно писал

Вопрос не в "решалке" (это и я в школе писал), она уже написана была, а в том, что матрица большая и в нескольких местах "неудобная" для Гауссо-подобных алгоритмов, плюс надо было не терять точность. В любом случае — это просто примеры.

Звучит круто!
Но получить такое на собеседовании, когда есть 45 минут и не принято отвлекаться ни на конспекты, ни на поиск — это грозит показаться неопытным человеком.
спасибо, я слышал отзывы что пользовались им, но сам не пользовался.
по сути, это пара рандомных ссылок из поиска (но про которые до меня доходили отзывы).
иногда Google проводит аналогичные кампании

можно об этом подробнее?
Слышал про несколько «interview workshop» организованных при университетах и на разных эвентах, навроде www.facebook.com/events/705306866191779
Не слежу за ними специально, поэтому как и где их ловить — не знаю.
Какой уровень английского нужен для интервью? Он важен или поняли друг друга и не суть, что не сразу? Локация в Цюрихе, если это имеет значение.

Вероятность прохождения интервью зависит от локации или везде выдерживают одинаковые стандарты?
Моего рунглиша без разговорной практики хватило. Вообще надо ~A2 + технические термины.
Важно лишь понять, переспрашивать это нормально.
Основная цель — поддерживать общий уровень одного стандарта, поэтому локация не должна иметь значения.
Мне в гугле попался китаец-интервьюер, у которого английского не было буквально совсем. Примитивная речь, кошмарный акцент, и вы спросите: а как же он проводил интервью? А вот как: зашел, пробубнил hello, положил передо мной вырезанный 2x10 кусочек бумаги, на котором было распечатана задача, и просто сидел, перерисовывал себе в блокнот каракули, которые я рисовал у себя на бумажке. В конце он попытался что-то со мной обсудить, выглядел очень жалко.
Мне один раз довелось проводить собеседование на языке, на котором я на тот момент не очень. Подозреваю, это тоже было жалкое зрелище, но зато кандидат внезапно раскрылся не только как хороший специалист, но и как человек, который умеет работать с разными людьми: умение принимать других людей, пытается ли понять, что другие люди хотят и умеет ли адаптировать свои ответы под возможности «клиента» понять. Человек прошел этот тест на ура и до сих пор приносит пользу и радость фирме и всем командам, в которых работает (дело было 5 лет назад). Ну а мне добавилось мотивации подтянуть язык :)
Но ведь все сервисы гугла уже написаны чуть более чем полностьью и на поддержке стоят ключевые люди. Зачем вам новые, чтобы ковырять и поддерживать то, что никто из своих не берёт?
Как нынче с корреляцией результатов интервью и того, насколько человек потом пользу приносит? Всё так же околонулевая ([1], [2])?:)
А вот это было бы крайне интересно почитать! Если не сложно и если реферат в публичный доступ выкладывать соберётесь — можете поделиться?
«реферат» в том смысле, что статью готовлю. ищу все крупицы данных в публичном доступе для этого. внутреннего доступа до статистики у меня нет (и не надо), но примерная картина уже расписана и так подробно.
Как нынче с корреляцией результатов интервью и того, насколько человек потом пользу приносит?

частично описано в книге «Как работает Гугл» Эрика Шмидта
86% в книге так же фигурирует)
Многие крупные компании используют Performance Review и разные виды 360*.
Вполне можно сравнить итог спустя 1-2 года с предсказанием на приёме на работу.
Performance Review — как минимум в тех не последних в мире корпорациях где я работал в лучшем случае превратились в еще одну бюрократическую процедуру по заполнении всяких бланков и проводки их через десяток этапов в HR-системе. В худшем же — перед самым Review искусственно организуются всякие завалы и всплывают «критические» проблемы — которые героически чинятся в авральном порядке. Или наоборот — за месяц до Review никто не хочет делать какие-то серьезные изменения — чтобы не вызвать негативное отношение начальства.

В гугле все не так. Там не HR, а коллеги пишут отзывы и оценки. А менеджеры потом очень долго и много обсуждают, чтобы всех по организации оценить одинаково.


Да, периодичность ревью вызывает некоторые негативные моменты — типа запусков сыроватых продуктов, чтобы пунктик себе записать, но это редкость.

Вот кстати очень правильно, что код пишете в гуглдоках. Постоянно случается ситуация, когда собеседующий предлагает открыть какую-нибудь CloudIDE и написать код, который бы проходил предварительно написанные тесты. Типа «реализуй промис, а вот пачка тестов». По-моему, это ужасная затея: в реальной практике нам нужно не писать код быстро-быстро под взглядом собеседующих в стрессовой ситуации.
Ну это уже как-то стиль олимпиад. Впрочем, возможно им нужны люди, кто могут писать в таких условиях? Или просто им так удобно. Имеют право, в конце концов.

Вообще, все люди разные — кому-то даже удобнее на доске, кто-то предпочитает писать на компе.

Для телефонных собеседований у нас есть только гуглодока, а при on-site собеседовании как кому удобнее — либо доска либо лаптоп с редактором. Но там просто редактор — из умного только отступы и подсветка синтаксиса, компилятора нет.
Думаю, это в основном от непонимания. Я помню как сильно поначалу лажал когда в Blue Brain Project искал себе замену. Первые три собеса были просто жуткими — вопросы задавал дурацкие, народ пугал. Потом понял — надо спрашивать те вещи, которые мы сами делаем на ежедневной основе.
Вот кстати очень правильно, что код пишете в гуглдоках

Не у всех так. Когда я столкнулся с написанием кода в google docs я сразу поплыл. Не смог решить 2 элементарнейшие задачи. Потому что весь мозг был занят войной с google docs. То как он реагирует на курсор, на табуляцию и прочие привычные программистам вещи съело все мои мозговые ресурсы. Не смог сосредоточиться. Было также запрещено убирать фокус из таба, чтобы что-нибудь гуглить (хотя гуглить было нечего), это тоже напрягало. В итоге из-за нервного напряжения и дискомфорта я блестяще провалил элементарнейшие задачи.


Если задачей было проверить могу ли я программировать, стоя на одной ноге в болоте, во время шквального ветра, то ребята отлично справились.

Да. Я лично надеюсь, что это изменится. В конце концов, и электронные вайтборды есть и онлайн редакторы.
В первую очередь именно для того, чтобы дать собеседуемому максимально комфортные условия.
К сожалению, пока условия всё еще бывают очень дискомфортными для некоторых людей.
Я когда собеседовался — у меня были ровно те же вопросы :)
С тех пор на очных появилась возможность использовать ноуты, и я завидую — мне было бы гораздо легче собеседоваться.
интересно. А я наоборот если меня гонят в онлайн IDE начинаю отнекиваться, что у меня она не работает и вообще это плохая идея. Написать при ком-то код, который сразу скомпилируется и заработает — я так вряд ли когда-нибудь научусь.

Гугл силен поиском, технологиями и много чем еще. А вот поиском сотрудников — явно не силен. Стелят очень много соломки просто потому что людей оттуда крайне сложно уволить (не по закону, а по внутренним полиси). Отсюда и рождаются такие кадавры, как отсутствие интервьюеров в принимающем решение комитете. Просто за гранью добра и зла.


Не ведитесь на бренд, не стройте свои процессы бездумно, просто потому что так же есть в гугле или где-то еще. Просто с их деньгами, они могут себе всю эту ерунду позволить.

Это не за гранью, а вполне разумное решение если надо обеспечить верифицируемую непредвзятость. Как предполагаете доказывать в суде непредвзятость отказа, если собеседуемый и собеседующий поговорили и на основании только одного его «нет» не взяли?
Как предполагаете доказывать в суде непредвзятость отказа

Гугл с его сонмом юристов мог бы найти миллион способов это сделать кроме такого очевидно тупого, как у вас в примере. Если бы это делала любая другая компания — ее бы уже давно слили. А тут сила бренда творит чудеса, многие смотрят и цокают языком вместо того чтобы сказать, что серьезно — они долбанулись с наймом на всю голову.


За последние годы я провел несколько сотен интервью и нанял пару десятков человек, рассуждаю именно с этих позиций. Весь описанный в статье подход — одна большая фикция, размывание ответственности и прикрывание задницы, без какой-либо внятной гарантии результата.

Вопрос: я верно понимаю, что гугл никого по-настоящему не приглашает? Слышал историю про то, как создатель Homebrew получил приглашение на собес, пришел — и не прошел по результатам собеседования. Причем завалили не на толерантности к трансгендерам, а на каких-то алгоритмах. Тогда я еще удивился — какое-такое собеседование, его же пригласили? Какое «инвертирование бинарного дерева» — чувак brew написал, неужели этого недостаточно для понимания его профпригодности? Обычно если приглашают — то просто показывают команде, что у него нет рогов и хвоста, да общаются за кофе часок. А вот у калифорнийских компаний, как я понял, не так.
А что такое «по-настоящему приглашает»? Вы вот сказали — приглашение на собеседование.
Не приглашение на работу, а на собеседование…

Имхо, частая ошибка — профпригодность != пригодность для компании.

У компании есть определённые правила, которые появились не с бухты барахты, не за один день и не на основании ЖЛП (желания левой пятки) кого бы то ни было.

Как бы ни был крут в каком-либо аспекте человек, он может не подходить по другим причинам.
UFO landed and left these words here
Я вот тут подумал — а что если вопросы будут составляться не теми, кто их задает? Собеседующий и кандидат будут видеть вопросы в первый раз в жизни и оба будут их решать. Если собеседующий сам не осилил решить — можно сделать какие-нибудь оргвыводы.
А кто будет оценивать? :) Предлагаете соображать на троих?

В целом, вопросы, используемые на собеседовании частая практика откатывать внутри на своих, для калибровки снимаемых сигналов и оценки возможных альтернативных решений.

Кстати, еще раз прочитайте статью — вопрос на максимальной сложности никто не должен мочь решить в отведённое время, если только это не его узкая специализация.
В августе собеседовался в Google (Цюрихский офис).
Прошло все довольно своебразно, сначала со мной поговорил рекрутер из Лондона, который в итоге отправил на техническое hangouts интервью с инженером из Цюриха.
Только вот отправили меня по направлению software engineer, хотя я сам системщик-эмбеддер.
Это собственно и всплыло в процессе собеседования, инженер даже немного удивился почему меня к нему отправили.
После собеседования мне прислали фидбек, что по направлению software engineer они мне не могут ничего предложить, т.к. я мол embedded/firmware engineer, так они решили. В общем то здраво :)
И добавили еще, что сейчас ищут hiring team по этому направлению и предложили созвониться что бы обсудить всё. Я согласился на созвон и после этого Google пропал, так и не дождался ответа :)
В сентябре правда прислали заполнить анкету небольшую, что бы я дал уже свой фидбек по поводу процессе собеседования и интервьюверов, я там конечно в дополнительных заметках описал возникшую ситуацию.
Так что еще и такого плана бардак небольшой присутствует.
Интересно. А когда подавались — вы подавались на software engineer или на embedded?
Я проводил собеседование на Embedded — так оно так и было помечено, как embedded…
Вероятно, провалилось в какие-то непонятные щели. Если напишете мне в ПМ, я попробую спросить куда вас потеряли.
Ну либо я попробую добавить со своей стороны — тогда я хоть буду знать что происходит, и смогу дополнительно контролировать.
Нуу, не знаю. Последний раз я вроде бы все ответил на телефонку с инжынером, раньше времени все разобрали, вопрос достаточно стандартный. Но потом HR сказал, что нет. Наверное все-таки не на техническую часть нужно обращать внимание, а именно на изучение местных карго-культов. Типа там, отступы не стабами, а пробелами.
Давно это было, не помню уже деталей, но внятного ответа я точно не получил.
ААА, начинаю припоминать. Меня человек 5 отреференсило в Гугле и один или два из них обо мне на запрос не ответило. Потом спросил, один сказал, что в отпуске был, другой, что письмо не заметил. Не знаю, но в общем, точно не по технической причине недопустили.
Например, интервьюверу мог не понравиться мой коммент, что stl это часть стандарта C++. Как описать это в отзыве обо мне? Ну, например, можно как «слабое знание С++». Вообще, о том, что «всем давно известно, что в Гугле stl нельзя использовать на интервью» можно догадаться только после прочтения специальных книжек о внутренних каких-то особенностях. Ну это чисто догадки, откуда я знаю, что там реально было. Но мне ничего не сказали кроме «Мы все еще ждем ответа от некоторых, ну и кажется, что вам нужно подтянуть алгоритмы». Это какая-то конкретная причина или ее можно кому угодно по каким угодно поводам написать?

То есть, грубо говоря, у меня сложилось впечатление, что когда я стал писать решение отличное от того, что было у интервьювера перед глазами, он сразу же решил, что оно неправильное и что я ничего не знаю. А так как у меня есть много знакомых, все-таки прошедших это интервью, я в курсе, что для этого нужно долгое зазубривание стандартных всех решений стандартных задач и ровно этого от тебя ожидает интервьювер. Я просто слишком ленивый для этого.
Хм. А с каких пор stl стало частью стандарта? Но если понимать как «в стандартной поставке современного c++ компилятора» — то это правда :D

А кто сказал что нельзя? Можно. Используйте на здоровье. Но если вы строите очередь на std::vector — будьте добры ответить о полученной сложности алгоритма с учетом вставки и удаления из головы vector'а.

А если говорите «допустим, у нас есть библиотека для хранения графов, и мы можем использовать функцию, которая даст кратчайший путь для произвольных вершин» — это тоже нормально для решения. Но да, попросить реализовать эту функцию тоже могут попросить. Ну или как минимум описать её сложность.
Если она O(1) — тогда особенно интересно, сколько она по памяти.
Stl является частью стандарта С++ по-моему с 98ого года. Соб-но, поэтому С++98 так важен.
Вот документ стандарта 2005ого года, в который stl уже включен www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf

Задача у меня была в духе «написать itoa» и естественно, например, предложить использование std::string в качестве выходного значения. Точнее по-моему что-то про массив нулей и единичек и ес-но, я предположил, что хранится он в векторе, а не просто в указателе. Но в известной книжечке приведено решение на указателях, вот и спрашивают тоже с указателями. А иначе как еще можно понять, что решение правильное?

То есть, простыми словами: хороший программист С++ должен знать, что stl — часть стандарта С++98 (да и вообще неплохо бы отличия стандартов друг от друга), а хороший программист, проходящий интервью в Гугл, еще и должен знать, что они не считают, будто stl включен в С++.
Отлично! Не знаю про какую известную книжечку вы говорите, но вот стайлгайд:
google.github.io/styleguide/cppguide.html#C++11
говорит вообще использовать всё что можно из C++11.

Вы говорите stl ключен в C++98, отсюда вывод, что stl использовать можно.

Я подозреваю, что у вас было огромное недопонимание друг друга, а ответ рекрутера не помог понять что же именно пошло не так.

Может просто попробуете еще раз? Будет другие собеседующие и другие вопросы. Если вы считаете, что проблема была в собеседнике — на этом вопрос будет закрыт.
Да сейчас уже лень, у меня работа хорошая и дом и прочее. Просто мой пойнт в том, что интервьювер ожидает от тебя быстрые стандартные ответы на стандартные вопросы и ничего другого. Не надо обманывать людей, будто там реально будет какое-то вдумчивое обсуждение. Все эти вопросы есть в книжечке cracking code interview, которую нужно просто выучить наизусть. Только там вы выясните, что, например, нужно прикидываться, будто stl не является частью С++, чтобы не ставить интервьювера в неудобное положение и многое другое.
Не надо обманывать людей, будто там реально будет какое-то вдумчивое обсуждение.
У меня есть ощущение, что вы провалились как раз на «вдумчивом обсуждении». Потому что для людей, которые на интервью активно используют STL у меня есть стандартный вопрос на 3 минуты: что написано про сложность оператора std::map:iterator::operator++ в стандарте.

И, заметьте, ответ «фиг его знает, я стандарт наизусть не помню» — меня более чем устроит. Вопрос будет лишь слегка переформулирован: «что должно быть написано про сложность оператора std::map:iterator::operator++ в стандарте при условии, что его писали разумные люди — и почему.»

И есть у меня ощущение, что вот на каком-то подобном вопросе вы и «поплыли» и «перешли в оборону» по типа «да нафиг мне это знать и кого это вообще волнует». После чего, как было уже указано — вас попросят на выход… не потому, что вы плохой специалист, а потому, что специалист другого профиля.

Причём, заметьте — это не издевательство. Для этого профиля даже есть название: Application Engineer. Вот ему разрешено произносить сакральные фразы «у нас есть XXX (в данном случае STL) и потому про YYY (не знаю уж чего там было… сортировки, аллокацию памяти или чего ещё) знать не нужно».
Я прекрасно понимаю, что любая хорошая компания пытается произвести приятное впечатление на собеседуемого, даже если ему отказывает. Пытается сделать ему наиболее прозрачную и понятную оценку, обьяснить, что она не основана на каком-нить там расизме и дать повод подумать, над чем поработать, чтобы прийти через год. Мой оригинальный коммент был вызван тем, что конкретно у Гугла это в моем случае не получилось вообще никак. При этом я в курсе как можно было бы избежать этих проблем — надо было просто заучить стандартные ответы на стандартные (а мне задали совершенно стандартные вопросы из cracking code interview) и я бы прошел совершенно прекрасно. Поэтому мой совет начинающим и не только программистам — не следуйте моим путем, просто тупо заучите, что от вас требуется и оттарабаньте на собесе, как это делают все остальные прошедшие.
Вы даёте вредные советы. Заучите, и попробуйте пройти. Я писал в статье о самом важном, что делаю на собеседовании — пропускаю заученную часть. Не беспокойтесь, я поставлю задачу так, что заученное не поможет.
А дальше вопрос. Если вы выучили и поняли — то прекрасно, вы прошли. Но это не потому, что зазубрили книжку, а потому, что ее поняли.
А если зазубрили — без понимания — то в этот момент поплывете.
Может быть вы собеседуете и так. Ну, знамечательно. А вот другие, судя по всему, по другому.
Скажем так. Как я писал в статье — на телефонном некоторые задают несколько мелких вопросов. Но даже там важно решение, это черновой осмотр. Даже если вы заучите и пройдёте такое телефонное, на очном будут уже только вопросы на пределе. Где произойдёт точно тот же завал.

Хм. Удивительно, что вы не знаете, что это часть стандарта. Собственно из-за такого к интервью гугл и есть вопросы. Кажется, что интервью веры просто заучивают одно правильное решение и если ты даёшь отличный от этого ответ — ты в пролёте.

Я не являюсь специалистом по C++, и у меня нет readability для него — если я пишу любой код на C++, в обязательном порядке его будет review делать кто-либо, кто знает и меня поправит.
Вы не должны знать все языки досконально, это не суть — для поддержания общего стиля и правильности есть правила review, есть люди, кто могут проверять код на соответствие правилам.
И я писал выше — интервьюеры проверяют как кандидат думает.
Во-1х единственно правильного ответа не существует, во-2х если ты даёшь отличный ответ это хорошо, но не значит, что на этом интервью закончилось.
Оно заканчивается по времени, вопросы резиновые.

Именно поэтому нельзя заучить одно правильное решение.
Вот и у меня сложилось впечатление, что интервьювер не ориентируется в С++ и вместо того, чтобы просто признать, что он не понимает, что я ему пишу, он сверился с листочком с решением, не увидел совпадений и подумал, что ему мозги дурят. Опять же, чисто мое впечатление.
Например, я не беру единственный оператор в составной {}, но бывают джуниоры, которые даже не понимают, что это вообще, и, опять же, это противоречит google code style, однако никак не противоречит здравому смыслу.
Давайте уже перейдём к конкретному примеру вместо воспоминаний о впечатлениях?
Напишите itoa — те самые пять злосчастных строчек.
Для начала я бы уточнил язык. Это Си или C++? И если это С++ не лучше ли конвертить не в ANSI string, а в std::string, у которой уже есть c_str()? Ну и таких вопросов у меня еще много. Хотя, конечно, ничего удивительно нет в том, что они вызывают раздражжение у собеседующего, который просто хочет сравнить 5 написанных строк с тем, что у него в памяти. Но, разве, это какие-то плохие вопросы?
Почему? Прекрасные вопросы. Более того, я вообще надеялся, что хоть кто-нибудь в комментариях захочет реально рассмотреть какой либо вопрос! Полноценно, вдумчиво (но честно, не бегая в гугл или книжку)

Отвечу по порядку: язык выбираете вы сами. Сказали си? Пишите на си. Сказали с++? Пишите на нем.
Вот только зачем вам функция преобразования анси строки в стд строку и стринг в инт, если вопрос был itoa?

Итак, отлично, уточню вопрос: напишите функцию, с тем интерфейсом, который вы считаете оптимальным, которая преобразует число в строку. Язык возьмите какой хотите на выбор из c, c++, python, go, Java, c#. Не используя библиотечные функции преобразований и форматирования строк.
Хорошо, но строка в С++ это std::string. Допустим, мы хотим преобразовать в string, но не используя ф-ий преобразования string. Тогда разумно использовать std::vector для хранения промежуточного результата, не так ли?
Тогда разумно использовать std::vector для хранения промежуточного результата, не так ли?
Нет — потому что это приведёт к лишней аллокации памяти в куче, что расточительно для itoa. Но если вам так хочется… выбор за вами.
А этот вопрос я не совсем понимаю к чему ведёте. Для меня это уже ваше рассуждение в слух, я продолжаю ждать, когда вы будете писать саму функцию.
Если задано с интонацией вопроса требующего подтверждения просто скожу, хорошо, продолжайте.

Обратите внимание еще раз на формулировку задания, ваш вопрос ничему не противоречит, продолжайте.
Но, разве, это какие-то плохие вопросы?
А давайте я тоже — вопросом на вопрос: плохие или хорошие… для чего? Для того, чтобы «почувствовать себя умным и красивым»? Хорошие вопросы. Для того, чтобы устроиться на работу? Плохие, несомненно.

Потому что вместо того, чтобы решить задачу — они нафиг не нужны. И они, как вас чётко и недвусмысленно сказали будут отброшены при написании отчёта — потому что это всё к делу отношения мало имеет.

То есть вы, задавая ваши вопросы, просто сокращаете время, которое вам останется на содержательную часть с 30 минут до 20 или 10. Или и вообще до нуля. С соответствующими последствиями для результатов собеседования.

Хотя в редких случаях они могут дать и позитивный эффект: если вы их задаёте, давая себе отчёт в том, что вы сами у себя крадёте время, и в конце-концов выполните «обязательную программу» и у вас ещё останется время на то, чтобы обсудить разные интересные вещи, связанные с вашими вопросами — ну тут может быть и прибыль для вас получиться… но редко.

А ответы… «Если бы собеседование проводил я»…

Это Си или C++?
Выберите что хотите.
И если это С++ не лучше ли конвертить не в ANSI string, а в std::string, у которой уже есть c_str()?
Если вам больше нравится std::string — почему нет… «замечание про себя: человек сам себе копает яму, нужно будет не забыть спросить про сложность std::string::push_back и std::vector::push_back».
Ну и таких вопросов у меня еще много.
И чем больше вы их задаёте — тем меньше у вас шансов пройти нормально собеседование.

При этом никакой «нелюбви к STL» тут нету: есть банальная неприязнь к любителям «покрасоваться, вместо того, чтобы решить задачу, которую нужно решать». Я таких персонажей не люблю страшно… могу даже представить, что в реальной работе вы ведёте себя иначе… но на всякий случай — буду предполагать худшее.

Тут не нужно какой-то особого «Гуглового подхода». Как и про любую банальность в IT про это написал Спольски:
Главное и единственное требование, предъявляемое к кандидату на работу в нашей компании: он должен
знать свое дело и уметь его делать.

А все ваши вопросы кладут такие маленькие-маленькие крохотные минусики на чашечку «не уметь его делать»…
Ну так и я про то же. Да, в реальной работе я всегда задаю подобные вопросы — зачем нам конкретно это надо, почему мы делаем именно так и чем вызваны любые нестандартные решения. Не нужно раздражжать интервьювера. Вместо этого нужно просто оттарабанить стандартное всем известное решение и еще несколько таких, получить свой оффер, сидеть в офисе у батареи и радоваться жизни, радостно поковыривая в носу.
Да, в реальной работе я всегда задаю подобные вопросы — зачем нам конкретно это надо, почему мы делаем именно так и чем вызваны любые нестандартные решения.
Кому вы это задаёте, я извиняюсь? Себе — ну так похвально: так и на интервью сделайте. И расскажите — почему вы сделали так, а не иначе. Интересно будет послушать.

А если не себе — то кому? Это ваша работа и часть ваших должностных обязанностей. А чьих ещё?

Вместо этого нужно просто оттарабанить стандартное всем известное решение и еще несколько таких, получить свой оффер
Да не получите вы оффер, «оттарабанив всем известное решение», успокойтесь уже. Получите как раз вопросы — на которые вы должны будете ответить.

сидеть в офисе у батареи и радоваться жизни, радостно поковыривая в носу
«Поковыривать в носу» не получится — нужно будет как раз регулярно отвечать на те вопросы, которые вы хотите «свалить» на кого-то. Ну, кроме прочих обязанностей.
Первый раз в жизни встречаю человека, который на полном серьезе мне доказывает, что моя обязанность — работать, не задавая вопросов. Работаете в индустрии вывоза больших черных мешков или отмывания странных больших пятен?
Первый раз в жизни встречаю человека, который на полном серьезе мне доказывает, что моя обязанность — работать, не задавая вопросов.
Нет — ваша обязанность — работать, не задавая дурацких вопросов не по делу. А вопросы, относящиеся к вашей компетенции — задавая себе и отвечая на них самостоятельно.

Работаете в индустрии вывоза больших черных мешков или отмывания странных больших пятен?
Не угадали. Работаю в компании, очень похожей на ту, где работает автор статьи. И у нас таки есть много людей, которым можно задавать разные вопросы. Дизайнеры, переводчики, юристы, уборщики и даже грузчики. А также маркетологи и бухгалтера.

Вот только есть проблема: я оччень сомневаюсь, что бухгалтер или грузчик сможет дать вам ответ на вопрос — стоит вам использовать ANSI string или std::string.

Если же вы считаете, что должен быть какой-то загадочный архитектор или тим лид, который вам даст ответ на эти вопросы, а вы потом только клац-клац-клац закодируете, как робот — то вынужден разочаровать: у нас таких нет. Как и, подозреваю, у автора статьи.
ну, что такое «дурацкий» вопрос это очень субъективно.
но то, что надо уметь отделять вопросы релевантные от нерелевантных — это факт. вопросы «где это будет использоваться» — хорошие, позволяют создать API.
вопрос «должен ли я использовать std::vector» — осмысленен в форме «не запрещено ли по условиям задачи».
вопрос «должен ли я использовать std::vector» — осмысленен в форме «не запрещено ли по условиям задачи».
Вопрос как «должен ли я использовать std::vector» осмысленен как что-то, что вы проговорите про себя и отвергните.

Почему отвергните? Ну очень просто. Какие есть плюсы у использования std::vector? Ну разве что «это модно, стильно, молодёжно». Всё же остальное попадает в графу недостатки: вы используете память «в куче», вы вызываете с десяток реаллокаций, вы усложнаяете машинный код самой функции… и при этом даже не экономите память: на стеке вам будет нужен массив размером в 32 байта, а std::vector занимает 24 байта плюс ещё минимум 8 байт будет менеджером памяти задействовано… ну и нафига козе баян?

Я ещё могу как-то «понять и простить» джуна без опыта, который просто тупо лепит std::vector так как про std::array он не знает, а «сырых массивов» боится… но человек с опытом должен такие вещи замечать.
Это преждевременное суждение. Пока не было даже решения с std::vector, так что мы не знаем, почему этот вопрос был задан.
А еще мне не нравится, когда джуниор, собеседующий меня со своими двумя годами опыта, считает, что он лучше меня разбирается в разработке ПО, раз работает в Гугле, чем я со своими 15ю. Потом, вам лет через 10 с опытом придет, что людям очень редко надо на самом деле именно то, что они просят.
Потом, вам лет через 10 с опытом придет, что людям очень редко надо на самом деле именно то, что они просят.
На самом деле для этого 10 лет не требуется. Но непонятно сколько лет требуется для того, чтобы понять что ровно тот факт, что «людям очень редко надо на самом деле именно то, что они просят» обозначает, что попытки выяснить разнообразные хитрые детали реализации у того, кто вас о чём-то просит — бессмысленны, разве нет?

Джоел тут, кстати, недооценивает свой собственный совет, когда говорит: хороший дизайнер интерьера постоянно приносит эскизы клиенту и вещи, из которых он может выбрать — но он никогда не обсуждает с клиентом расположение умывальника… умывальник находится рядом с канализационной трубой и не важно, чего хочет клиент.… нет смысла тратить время на обсуждения, где должен находится умывальник — он должен быть рядом с трубой, даже не начинайте разговор об этом; пусть клиенты изливают свои дизайнерские потуги делая какие-то безвредные вещи вроде изменения своего мнения 200 раз о том, нужно ли использовать для столешницы итальянский гранит или мексиканскую плитку, или норвежскую древесину

Джоел говорит что так нужно общаться с «клиентом или нетехнический менеджером»… но на самом деле с вашими коллегами — подход должен быть тот же. Просто немного по другой причине. Если «клиент или нетехнический менеджер» не может понять ваших рассуждений, то ваши коллеги просто не будут хотеть этого делать. Если они «влезут в задачу», которую делегировали вам, настолько, что будут разбираться там в каждой запятой — то на это уйдёт стольков времени и сил, что им проще будет всё самим сделать… зачем такой человек в команде нужен?
Джоел то, Джоел это. Я помню тоже удовольствием зачитывался им, когда еще не существовало скайпа и ютуба. Каждый джуниор с новой книжкой для себя столько великих идей открывает. До clean code, я так понимаю, еще не добрались?
Идеи Джоела как раз банальны. Никаких хитрых истин у него в блоге нет. Но он хорошо пишет, а прописные истины от того, что прошло 5-10-15 лет ложью не становятся.
Ну почему же. Я сам попросил думать вслух, что и слушаю. Нормальные вопросы. Правда, если человек ждёт подтверждения на каждый шаг реализации — это настораживает, потому что его автономность может вызвыать сомнения, но мы еще не закончили, а преждевременные выводы — зло.

Я никогда не делаю выводов заранее, пишу протокол подробно и целиком, а оценку делаю чуть позднее, читая протокол а не полагаясь на мои воспоминания и ощущения. Это снижает предвзятость.
Я думаю, если бы попал на собеседование к вам, мы бы прекрасно поговорили. Но мой пойнт в том, что куда более вероятно попадание к khim, которые, конечно же, считают, что вопросы важно и нужно задавать, но только те, которые ожидает интервьювер и на которые заранее знает ответы. И что сам формат собеседования по времени реально не предусматривает достаточно времени для вдумчивого обсуждения задачи. Ничего сильно плохого в этом нет. В том же универе на экзамене вы тоже знакомитесь с лекциями, а потом часто от вас требуется прямо на ходу выдавать ответ. Просто надо заранее обсуждать формат собеседования, что, мол, спрашивать будем вот по этим вот лекциям.
Кстати, многие американские представители Гугла и прочих компаний в открытую говорят — не выучите материал этих книжке — интервью не пройдете.
khim, которые, конечно же, считают, что вопросы важно и нужно задавать, но только те, которые ожидает интервьювер и на которые заранее знает ответы.
Бред какой. С чего вы решили, что мне не нравятся вопросы, ответ на которых я не знаю? Наоборот — если кандидату удаётся указать мне на что-то в тех вопросах, которые я задаю, чего не знаю (такое редко, но случается, я не Бог, всеведением не обладаю) — то это большой плюс. И почти все кандидаты, кому это удалось были приняты в итоге.

Чего я не люблю (и не люблю достаточно сильно) — так это нарушения правила, которое мне очень лаконично описала ещё моя мать в детстве: «не задавай вопрос, на который можешь ответить сам». Потому что это лишняя трата времени.

Что интересно, datacompboy показал, что он, в принципе, считает так же:: а этот вопрос я не совсем понимаю к чему ведёте. Для меня это уже ваше рассуждение в слух, я продолжаю ждать, когда вы будете писать саму функцию… это ведь то же самое, что сказал я, только в «политкорректной форме».

Мы отличаемся, скорее вот в этом месте: я никогда не делаю выводов заранее, пишу протокол подробно и целиком, а оценку делаю чуть позднее, читая протокол а не полагаясь на мои воспоминания и ощущения.

Если честно, то меня это удивляет. Во всех компаниях, где я работал принцип был одинаков: меня просили ответить на вопрос «хотите ли вы увидеть кандидата в вашей команде?» — вот именно так и никак иначе.

О том же пишет и Джоел:
Вместо «Нанимать, но не в мою группу» напишите, не задумываясь, «не нанимать», и все будет в порядке. Даже если вы столкнулись с прекрасным специалистом в одной конкретной области, но для вас не подходящим — это значит «не нанимать». [...] Никогда не говорите «может быть» или «не уверен». Не уверены — не нанимайте. Это проще, чем кажется. Не уверены? Скажите нет. И ещё, если вы занимаете выжидательную позицию, это тоже значит «не нанимать». Никогда не говорите: «Хорошо, я думаю, мы его возьмем, хотя есть некоторые сомнения насчет...». Это тоже «не берем».
Если кандидат лично мне не понравился, но остальные от него в восторге — его ведь возьмут всё равно, но если вопрос стоит как «хочу ли вот конкретно я работать бок-о-бок вот конкретно с этим кандидатом»… то эмоции, которые у меня вызывает общение с ним — чуть ли не важнее объективных знаний и умений.

Просто надо заранее обсуждать формат собеседования, что, мол, спрашивать будем вот по этим вот лекциям.
Кто вам такое сказал? Единственное ограничение — интервью длится 45 минут или час, реже 2-4 часа (в разных компаниях по разному, но везде, где я собеседовал был лимит) и, соответственно, времени на обсуждение «погоды на Марсе» у нас нет — ну так и в реальной разработке «лишнее» время редко когда бывает.

И что сам формат собеседования по времени реально не предусматривает достаточно времени для вдумчивого обсуждения задачи.
Вы хотите сказать, что вам не хватит 45 минут времени (более короткие интервью мне не встречались), чтобы «вдумчиво обсудить» itoa? А сколько времени вам потребуется на «вдумчивое обсуждение» реальных задач? Год? Или два?
Боюсь что поговорили бы прекрасно, но вот примера кодирования я так и не увидел, хотя задача уже была сформулирована и даже ответы на нерелевантные вопросы даны.
Так что результат был бы «нет».

И, прошу заметить, stl тут не при чем.
Да я вообще-то спал. Или вы думаете я должен был всю ночь бдеть и отвечать на вопросы?
Нет, что вы. Я тоже спал. Просто вы отвечали на другие вопросы, вот и всё.
Еще 18 или 19 лет назад я на олимпиаде по программированию занял 1ое место по городу. Я прекрасно в курсе кода, который принято писать для «C++ имплементации itoa». Но он мерзкий. Он из 90ых. С тех пор С++ изменился, а этот мерзкий пример — нет. Просить написать этот код в 2018ом году, это как просить журналиста написать тестовую статью на старославянском, при том, что писать он будет на современном русском.
Я разве просил вас написать «код, который принято писать»? Нет.
Но вы не хотите писать даже тот код, который считаете красивым и опрятным на современном C++.

Проще говоря, если вы пришли на собеседование на кодинг, где заранее было оговорено что надо будет написать десяток строк (а об этом написано — «Be prepared to write around 20-30 lines of code in your strongest language.») с желанием просто поговорить — я понимаю, почему собеседование закончилось неудачей.
Да нет, я прекрасно понимаю, что требуется написать код в духе
www.geeksforgeeks.org/implement-itoa(и я могу его воспроизвести по памяти, так как писал его еще мелом на доске, когда Ельцин был президентом). И я знаю, что это именно то, что ожидается. Просто этот код мерзкий. Ни один здравый программист, размышляя с нуля не будет писать такой код. Просто есть такая древняя традиция, лет 30 которой уже, задавать вопрос по itoa (который некорректный сам по себе) и отвечать таким говнокодом, делая вид, что это С++
Нет, ожидается, что вы что-нибудь напишете, а не будете разводить демагогию про олимпиады ельцина в детском саду.
Если бы мне была очень нужна работа, я бы написал код, приведенный по ссылке сверху. Можете его покритиковать, будет интересно. Очень удивлюсь, если он неидеален по стандартам Гугла.
Но просить написать такой код это примерно как, нанимая электрика, дать ему два провода и сказать — «сделайте нам скрутку», ожидая, что сейчас от зачистит провода зубами, скрутит руками и сверху изоленточкой. Нормальный электрик вас просто пошлет с такими заданиями. Вежлиый начнет спрашивать, из каких металлов провода, на какой ток расчитаны, какой толщиной, почему нельзя их спаять, можно ли использовать термоусадочные материалы и прочее.
Интервьювер наверняка скажет, что электрик совсем ничего сделать не может, то, что даже ребенок умеет. Но понимаете, и электрик скорее всего вежливо просто обойдет такую контору стороной, если у него есть выбор работать там, где провода пальцами не скручивают.

Если вы вместо этого "говнокода" напишете рабочую версию с std::string::push_back и std::reverse, вам это зачтется за правильный ответ, если, разумеется, сможете объяснить сколько это будет работать и почему.

Если вкратце то:
— постановка задачи «написать itoa на С++» некорректна
— постановка задачи «написать int to std::string на C++» корректна
— постановка задачи «написать int to std::string на C++ без использования ф-ий std::string» некорректна

У вас постановка задачи — написать itoa. На вашем любимом языке. Например, в проекте нужно записать число в нестандартной кодировке (вместо 0 — a, вместо 1 — b, и т.д.)


на C++ без использования ф-ий std::string

Где вы это требование взяли? Я вам написал выше — используйте любые методы std::string и стандартные алгоримы. Все, кроме, собственно to_string.

Все, кроме, собственно to_string.
А чем to_string не угодил? Он же только с основанием 10 работает. Не очень понятно куда его засунуть и зачем, но если удастся его как-то поиспользовать… будет интересно посмотреть…
Попытка сократить время до получения кода.
Ведь требования поддержки radix не было…
«a» в itoa означает ANSI string — null terminated 1 bytes per char. Это Сишный формат строк. У С++ свой формат строк. Постановка задачи некорректная. Корректная — написать string to_string(int)

Касаемо «ожидания готового кода», мне его скопипастить, чтоли, из приведенной выше ссылки? Я написал, что именно это подразумевается под правильным ответом на вопрос «напишите itoa».

Касательно требования «нельзя использовать ф-ии string» — его мне высказал автор статьи

Реально я более, чем уверен, что std::to_string реализуется достаточно муторно, но можно это сделать на коленке примерно так:

string to_string(int x)
{
	if (x < 0)
		return string('-') + to_string(-x);

	const int BASE = 10;
	string s;
	for(; x > 0; x/=BASE)
		s += digit_of(x%BASE);

	return reverse(s);
}
Я вижу две:
1. Для нуля будет пустая строка.
2. Для MIN_INT вы вызовете UB и, скорее всего, в реальной реализации переполните стек.
С исправленными этими ошибками я бы зачел результат, не обратив внимание на string(char) и неправильное использование reverse — это не то, о чем здесь стоит рассуждать, вопрос на алгоритмику а не синтаксис.

Затем стоит спросить, каким образом вы могли бы убедиться, что в функции нет ошибок; и какая получилась сложность функции по скорости и памяти.

После чего перешел бы к основному вопросу собеседования.
Я был сразу прерван фразой «stl использовать нельзя». Вообще, я бы не советовал использовать С++ на собеседовании, а то столько разных ньюансов вокруг этого появляется. Питон будет лучшим вариантом.

Гугл известен тем, что платит наибольшие деньги и я буду очень рад, если многие, читающие этот форум, смогут туда устроиться, тем более, что это заграницей. И я надеюсь наш разговор будет полезен всем тем, кто еще не проходил собеседования, для того, чтобы примерно оценить ожидания собеседующего и примерное настроение при разговоре.
«a» в itoa означает ANSI string
Нет. A обозначает «ASCII» — можете открыть man page из первой версии UNIX и убедиться.

Это Сишный формат строк. У С++ свой формат строк. Постановка задачи некорректная. Корректная — написать string to_string(int)
Извините, но это бред. По вашей логике atoi в Python тоже с сишными строками работает? Или в Go? Как насчёт rustа? Весь мир шагает не в ногу, один вы, такой красивый — в ногу?

Я написал, что именно это подразумевается под правильным ответом на вопрос «напишите itoa».
Нет никакого «правильного» ответа. Есть код. Который вы должны написать. И который можно обсуждать. Вы этого не сделали — так что и обсуждать нечего.

Если вашей целью прихода на собеседование не было желание устроиться на работу, а было желание потроллить интервьюеров — вы этой цели достигли прекрасно. Понятно, что на работу вас, после этого, не возьмут, но это же и не было вашей целью — так что единственная проблема заключается в том, что вы потратили изрядное количество времени других людей. Не очень понятно — зачем вам это нужно, но у разных людей — разные хобби…
Извините, но это бред. По вашей логике atoi в Python тоже с сишными строками работает? Или в Go? Как насчёт rustа? Весь мир шагает не в ногу, один вы, такой красивый — в ногу?

То есть во всех этих языках реально конвертится в null-terminated строку или все-таки в нативный формат? Спрашиватель сей задачи ожидает ответ для null-terminated Сишной строки или нет?

Нет никакого «правильного» ответа. Есть код. Который вы должны написать.

Обычно люди с таким менталитетом идут в армию. Там им удобно и понятно. Им сказано подметать плац ломом, значит, надо подметать плац ломом.
То есть во всех этих языках реально конвертится в null-terminated строку или все-таки в нативный формат?
Я уже, кажется, говорил, что я думаю по поводу вопросов, на которые вы сами можете ответить (если не можете — то тем хуже для вас, извините).

Спрашиватель сей задачи ожидает ответ для null-terminated Сишной строки или нет?
Спрашиватель сей задачи примет ответ, работающий с null-terminated Сишной строкой — но отсюда вовсе не следюет, что никакой другой ответ принят не будет.
Приходит такой человек собеседоваться. Вы ему «подметите плац» и показываете набор инструментов. Он хватает лом, быстро подметает, вы одобрительно киваете. Молодец, далеко пойдет.
что за бред — прекрасный и оптимальный, разумно написанный код для этой задачи
а вот из-за подобного «эстетства», мы и имеем современный, выражаясь вашим языком, говнософт, тормозящий и непомерно жрущий память на элементарных операциях. зато, небось, в исходниках всё красиво, по последней моде

другой вопрос, только, почему как отметили почти в самом первом комменте, сервисы у гугла выходят точно такими же дико тормозящими и безмерно потребляющими память, при том что на интервью задают вопросы и обращают внимание на такие правильные вещи
нужно будет не забыть спросить про сложность std::string::push_back

Мне вот любопытства ради в каком STL и в каком компиляторе на практике есть реализация со сложностью за линию? В вашей практике такое сочетание было?
Чисто любопытства ради.
Сложность «за линию» — это в смысле, O(n)?
Это в любом, когда realloc требует перемещения в памяти же.
Там всё гораздо хуже: у строки нет capacity, так что очень многие реализации делают реаллокацию на каждый push_back, что может привести к тому, что алгоритм, сносно работающий на std::vector, будет тормозить на std::string.

Однако к нашему примеру это не относится, так как тут у нас не более 32 символов и мы, скорее всего, «лишних» движений делать не будем. При этом если мы не будем использовать совсем уж маленькие radixы, то мы за предел в 22 символа не вылетим и нас «спасёт» SSO… но спасёт не до конца: ровно из-за той самой SSO мы будем много лишних операций в std::string::push_back иметь.

Потому — лучше, всё-таки, std::array или «сырой» массив…
у строки нет capacity

Лолчто? N4713 24.3.2.4
size_type capacity() const noexcept;
9 Returns: The size of the allocated storage in the string.

есть еще и reserve(), но вообще я хотел бы это услышать от кандидата, а не у помощи со стороны :D
Посыпаю голову пеплом. Действительно в C++11 строки ведут себя как std::vector (что фактически лишает их смысла, ну да ладно).

И, действительно, aeyrwbz std::string::capacity была даже в C++98/C++03, но так как она всё равно не гарантировала ничего, то использовать str::string было бессмысленно.

А вот в C++11 std::string это стало иметь смысл. И, возможно, даже имеет смысл использовать std::string напрямую внутри itoa если мы потом всё равно хотим возвращать std::string. Спасибо за дельное замечание!

P.S. Смысла использовать std::vector «внутри» для реализации по прежнему нет даже в C++11
Как это не гарантировала?
Она, несомненно, гарантировала, что одна цифирька больше другой. Но поскольку были разрешены разного рода строки со счётчиками и чуть ли не GC, то никаких гарантий на то, что если ты сделаешь reserve(), а потом начнёшь строку менять, то у тебя аллокаций не будет и будет какая-то временяемая сложность — не было.

Впрочем, я не специалист по стандарту плюсов, просто помню что оно есть уже давно
Оно есть начиная с GCC5. До этого — очень долго были COW-строки с совсем другими характеристиками, чем требуется в C++11.
Да, но realloc зависит от реализации malloc, как минимум стандартный и tcmalloc выделяют чанками всё равно, так что realloc будет O(1) (пусть и дорогой (1)) некоторое время. Учитывая, что предел — 32 символа, реальный перенос больше 4 раз я бы не ожидал. Но! Это уже дебри реализации, на которые полагаться отдельный моветон. Кааак рванёт на очередном апдейте, или смене malloc'а…
Вообще, о том, что «всем давно известно, что в Гугле stl нельзя использовать на интервью» можно догадаться

Что? Первый раз слышу. Сам на интервью использовал несколько раз. Более того, я еще и порядок аргументов напутал, интервьюверов это не волнует вообще.


интервьюверу мог не понравиться мой коммент,

Интервьювер может написать об этом в своем отчете, но все-равно, на это будет смотреть комитет. Так что это не просто мнение одного чувака, которому что-то не понравилось. С ним, как минимум, еще несколько человек согласилось.

Повезло с stl
Комитет рассматривает телефонки тоже? Я думал только онсайт. У них судя по всему такой поток телефонок, что вообще отбирают скорее по тембру голоса или еще чему-то загадочному.

Вообще, я всегда влет проходил телефонки во всякие Фейсбуки-Амазоны. Когда не прошел с Гугл, думал — ну, не понравился челу, бывает. Когда второй раз не прошел, опять же, решив все, понял, что Гугл куда более загадочный зверек, чем пытается казаться.

Да, вы правы, телефонки комитет не рассматривает. Но кто-то там тоже посмотрит отчет и если надо, второе интервью назначит.

Спасибо за статью.

Смотрел недавно видео интерьвю на youtube, тоже парень из гугла, и тоже рассказал как проводит собеседования. Многое совпало :)

В целом с подходом понятно, и нормально.
У меня на каждом интервью настойчиво интересовались, кого я в компании знаю лично.
Не подскажете с какой целью?
Интересно. Меня спрашивали только один раз, рекрутер изначально, и я в итоге работаю в команде с тем единственным человеком кого знал :)

Возможно, чтобы исключить этих людей из круга тех, кто должен вас собеседовать — это будет неэтично и предвзято.
Человек, которого вы знаете лично не должен проводить интервью (и если это случится может плохо кончится для обоих), зато у него могут попросить написать отзыв «в общую папку».

Но чтобы этим интересовались на каждом интервью… странно это. Не ожидал от Гугла.
Опять нет-нет), я имел ввиду не при каждом разговоре, а при каждом новом приглашении на интервью, они мне почти каждый год звонят.
Интересно, что надо сделать, чтобы они почти каждый год звонили?
Думаю, зависит от рекрутера и что он думает на тему есть или нет шансы.
Либо по результату прошлой беседы, осталось у них впечатление что кандидат заинтересован, подтянется за этот год.
У этих людей просят написать на вас отзыв. А еще их убирают из пула интервьюверов. А если вы знаете кого-нибудь в офисе, где происходит онсайт, то вы сможете с этим человеком пообедать.
Можно сформулировать как “представьте, что наш сервис для обработки запроса проверяет существование внешнего объекта. Как можно ускорить обработку?” — ожидая очень очевидное предложение “давайте просто кешировать результат”.

Не понял, что именно предлагается кэшировать, результат проверки существования внешнего объекта? Но если его кэшировать, то как можно быть уверенным, что с момента прошлой проверки внешний объект все еще доступен? Если такая проверка есть, вероятнее всего доступность объекта критична и следует минимизировать время между проверкой и использованием. Кому может прийти в голову кешировать результат проверки?

Прекрасный вопрос! На котором можно обсудить ttl, что именно кешировать — положительные или отрицательные ответы.


И чтобы продолжить беседу, запостулируем, что отрицательный ответ получается быстро, но его не надо кешировать, а положительный долго, но его можно запомнить, так как объекты не удаляются.

Чувствуется опыт проведения собеседований. Во многих компаниях интервьюеры на быструю адаптацию вопросов не способны.

А что не так с самым простым ответом про кеш?
Язык Java.
Используем стандартный потокобезопасный ConcurrentHashMap. Получаем достаточно быстрое добавление. Добавление будет на порядок быстрее чем получение информации о статусе объекта. Поиск информации об объекте и получение будет просто быстрее некуда. TTL обрабатываем неторопясь отдельным потоком или потоками. Тоже самым стандартным способом hashMap.foreach(...). Возможны небольшие нарушения TTL, но такое обычно не критично. Если критично подгоняем TTL. Так чтобы время обработки всей коллекции + наш поправленный TTL были равны требуемому TTL.
Прекрасно, неплохое начальное решение!
Самое время задать вопрос, который я уже упоминал в статье: а как быть, если мы хотим контролировать максимум памяти, потребляемую этим кешем?
До TTL еще далеко, у нас уже 1000 ответов в кеше, и нужно сохранить. Просто добавить — их станет 1001.
Допущения без которых никуда:
Требования по памяти приблизительные. Контролировать хотим, но небольшие отклонения не критичны.
Объем кеша такой что проход очистки по ttl по всем элементам занимает небольшое, по сравнению и с ttl и со временем когда кеш переполнится, время.

Тут надо уточнять насколько равномерно используются элементы кеша.
Предположим что очень неравномерно. К одному элементу единицы обращений за время жизни, ко второму тысячи. Соответственно мы хотим хранить активно используемые элементы до ttl, остальные можно выкидывать по памяти.
Добавляем в объект хранимый в кеше счетчик обращений. В функцию чистящую по ttl добавляем проверку на максимальный объем и при подходе к нему или превышении чистим самые неиспользуемые объекты. Так чтобы осталось процентов 80 (или сколько хотим) от максимально возможного. Поиск самых неиспользуемых и удаление тривиальны. По ресурсам или память для хранения и удаление при том же проходе. Или вообще без затрат: При первом проходе только ищем граничный по обращениям и при следующем цикле проверки ttl заодно удаляем все что ниже него. Память будет немного плавать, но сильного превышения не будет.

При равномерном обращении все аналогично только критерий удаления по памяти это время оставшееся до ttl. Других критериев у нас нет. При проходе очистки ищем граничный и при следующем удаляем все что ниже него.
Итого, какова итоговая сложность добавления, получения и очистки у вашего решения получилась?

Что вы сделаете, если верхнее требование по памяти критичное?
Добавление и получение O(1) коллизий у нас нет или почти нет.
Удаление и по ttl и по памяти требующее полного прохода O(n). Зато не влияет на основные процессы и работает независимо.
Отслеживание памяти при втором проходе ничего.

Тогда при равномерном использовании и удалении самого старого берем LinkedHashMap и просто удаляем первый элемент. Раньше добавлен, значит у него минимальный остаток ttl. Сложность o(1).

При неравномерном использовании и удалении самого малоиспользуемого все плохо. Нам надо в момент любого добавления знать какой элемент должен пойти на удаление. Заводим рядом TreeMap с объектами вида (id, количество обращений) и и компаратором по количеству обращений. Обновляем его одновременно с обновлением основного hashmap. Сложность вставки сильно возрастает o(logn). Сложность удаления o(1).

При массовых вставках и редких ситуациях переполнения по памяти можно сделать совсем просто: При достижении лимита сортируем исходный hashmap и удаляем самый малоиспользуемый. Долго при переполнении, зато вставку не замедляем и гарантируем не переполнение памяти. В сценарии редкого переполнения должно работать неплохо.
Вы практически получили идеальный вариант с O(1) по удалению и вставке включая случай переполнения, сделаете этот шаг?
Про переполнение в сложных случаях я ниже написал.
O(1) это для обычной вставки или удаления первого элемента LinkedHashMap

Зачем получать? Я честно нагуглил. Помню я это примерно так:
1. Это очень быстро вообще не паримся.
2. Это быстро. Если надо чтобы очень быстро было проверить это место.
3. Это медленно. Будет тормозить.
4. Это нереально медленно. Переписать при первой возможности.

Для собеседования в Гугле естественно не подойдет, но для повседневности достаточно.
Вариант «по переполнению сортировать и удалять» можно засчитать как амортизированную сложность, но только если вставок больше, чем происходящих переполнений.

Итого, как же выглядит итоговое решение, которое даст O(1) на вставку и O(1) на получение, гарантировано без переполнения и при этом с семантикой удаления того, которым не пользовались дольше всего вперед?

Я схитрил и прочитал про LRU cache. Я в восторге. Предельно просто и эффективно.


Итого:


  • у нас есть hashMap, который хранит сами кешированные данные и данные TTL
  • у нас есть queue в виде двустороннего связного списка
  • при запросе по ID мы проверяем его наличие в hashMap, т.е. O(1)
  • при удачном запросе (hit) мы помимо того, что возвращаем элемент из hashMap, ещё и вырываем его из списка помещая его в голову (размыкаем цепь и помещаем в начало), таким образом поднимая его "популярность"
  • при записи в кеш мы проверяем не привышен ли capacity кеша, если нет, то пишем данные в кеш, а ссылку на эти данные ставим в голову
  • если же capacity превышен, то в принципе всё тоже самое, кроме того, что 1 элемент из хвоста очереди (+ из hashMap) мы убираем
  • итого запись O(1)
  • память O(n), если capacity достигнут

Но тут ни слова про TTL. Нууу… Мне кажется, что можно вообще не заморачиваться с ним. Просто хранить его вместе с данными в hashMap. А при HIT-е просто проверять. Если данные устарели, то стираем его из очереди и хешмапы, и ведём себя будто его и не было вовсе. Суть не меняется. Из недостатков: мы храним устаревшие значения дольше, чем в идеальном случае, но по факту нам плевать, т.к. если запись непопулярна, то она сама по себе улетит в трубу при работе с кешем. Если же запись популярна, то кеш обновится во время очередного HIT-а. Логично?


Никаких потоков и прочего не трогал, т.к. в моём уютном JS обычно таких педалей нет :)

Именно такую реализацию я предложил на собеседовании в одну фирму с известным поисковым движком и даже начал писать код. Дальше меня начали спрашивать как быстро посчитать хэш от массива (кэшировать планировалось блобы), как обеспечить O(1) в хэшмапе, как точно считать всю память, что использует наш LRU кэш, т.к. работает это на оборудовании с ограниченной памятью. Потом, правда, мне сказали, что в C# GC работает на подсчёте ссылок, а поколения — бред, который я только что выдумал.
как я и писал в статье — как только вы нашли решение, пока есть время — задача будет усложняться и усложняться.
А вот я пошел честно и гуглить оптимальный алгоритм не стал. И без подсказки datacompboy до лучшего решения не догадался.

Да, я понял. LRU очень простой, но простой он тогда, когда ты уже прочитал о нём, а когда ты о нём ранее не знал, догадаться наверное весьма не просто :) Всё таки должен быть определённый навык жонглирования структурами данных, которые в олимпиадках и прививают.

Отлично, если вы загуглили (загугли! от загугли слышу!) — то вопрос естественным образом вырастает до примерно того, что ниже писал T-D-K.
Например — а как быть, если ограничение по памяти в количестве байт, а не числе объектов? А если объекты могут быть СИЛЬНО разных размеров? пара мег / сотня байт, например?
А если мы всё равно хотим сохранить примерно О(1)?
Ну хотя бы амортизированно?
Ну хотя бы гарантировать отсутствие OOM?

И тааак даалее.
а как быть, если ограничение по памяти в количестве байт, а не числе объектов?

А структура, которую мы планируем хранить — фиксированного размера? Если фиксированного, то вроде всё просто. Можно даже заранее посчитать кол-во элементов, которые мы можем хранить.


А если объекты могут быть СИЛЬНО разных размеров? пара мег / сотня байт, например?

Вот тут сложнее стало. В JS нельзя написать что-то типа getSize(object) и получить его размер. Но наверное мы говорим о каких-то языках, где можно. Буду исходить из того, что такая возможность есть.


Первое что приходит в голову — при добавлении\записи значения — удалять с хвоста элементы до тех пор, пока новый не влезет. Но тут никаким O(1) и не пахнет. Условно если записать в кеш элемент размером почти с кеш, то придётся выпилить все элементы, что там уже были.


Судя по вашим словам — можно это сделать за O(1). Но я не представляю как. Ведь даже если нам не надо искать — на каком элементе можно остановиться, нам ведь всё равно надо их из hashMap-ы удалять. Поочерёдно. А ведь там ещё небось какие-нибудь деструкторы могут быть (честно говоря ничего не понимаю в этом), и просто разом затереть память нельзя. Честно говоря я не знаю, как это сделать за O(1). Ну можно питание сервера отключить.


Ну хотя бы гарантировать отсутствие OOM?

Имеется ввиду недопустить превышение лимита размера кеша? Просто ООМ можно получить, скажем, на загрузке этого самого элемента при MISS-е по сети… Мало ли, может там нам гигабайт подсунули. Тут уже нужно поточно по чанкам грузить данные от источника данных и прерывать если с памятью беда. Но я думаю вопрос не об этом. В таком случае нам достаточно удалять из кеша элементы до того, как в этот кеш новые писать.


Всё, не сдал? )

> Всё, не сдал? )
см. Методы Кристобаля Хунты.
:) кто сказал, что решение существует?
А вот метод поиска решения отличный.

Когда мы начинаем считать размер, O(1) вообще возникает вопрос, можно ли получить. Надо еще учесть, от чего считается O. Если нам становится важен размер объектов (кстати, даже в JS косвенно его можно оценить — например, по длине хранимых строк), то мы в общем-то добавляем не за O(1), а за O(size).

И тут возникает хороший вопрос… А ответ мы вообще, копируем или отдаём по ссылке? Объект в кеше мутабельный или нет? Если мутабельный, то мы должны его копировать, и тогда получается что у нас в принципе и get операция уже O(size). Ну и очистка туда же идёт.

Для гарантии отсутствия OOM как минимум нам понадобится запас по месту как минимум на один самый максимальный объект [мы же вообще еще не обсуждали многопоточность доступа, да? :)], ну и опять же — можно еще обсудить а где и сколько раз данные по сети пришедшие будут скопированы, посмотреть знает ли кандидат разницу по памяти между «вычитали N мегабайт из сети» и «обработали N мегабайт из сети».

Например — потоковая обработка позволяет ограничить футпринт на обработку по сути одним буфером, но если мы начинаем кешировать… А если у нас по пути пара контейнеров… А если где-то они мутабельные… А если… :)

Это всё не вопрос на «сдал/не сдал»! Это не экзамен, тут важно думать, а не помнить.

Хаха, у меня примерно те же мысли крутились в голове. Но я постеснялся их выражать вслух :) Ещё примут за сумасшедшего. Мол мы тебе дали конкретную задачу, а тебя куда-то понесло…


Так то да, когда мы рассматриваем объекты сильно разного размера, то bigO надо рассматривать уже совсем по-другому. В точку ;) Касаясь ООМ возникает много вопросов к тому, как мы эти данные вообще получаем… Даже элементарно, если мы их чанками грузим по сети… то выдаёт ли нам сервис их размер заранее, или нет. В общем тут много чего всплывает.


В общем от меня бы требовалось уже просто высказывать свои соображения по этому поводу?


кстати, даже в JS косвенно его можно оценить — например, по длине хранимых строк

Ну это полная дичь, если честно :D

Конечно! Равно как и предыдущее решение — предполагается, что оно получено размышлениями, и процесс размышления шел вслух.
Нет, я не стал рекрутером.

Я уже писал, и ещё раз скажу: вполне себе обычный собес. Как обычно, многое зависит от умения конкретного человека проводить собеседования, но не все могут, увы :-}


datacompboy а как вас готовят к проведению интервью? Понятно, что какое-то время вы ходите на второй позиции, а дальше? Есть ли возможонсть отказаться от проведения интервью в принципе, или это обязательно?

Что такое «ходите на второй позиции»?

Перед тем как можно начать интервью — надо пройти тренинг, разумеется. Он не обязательный. Не хочешь — не собеседуешь. Даже если походил и надоело — выставь в настройках доступности для интервью 0 и все.
Что такое «ходите на второй позиции»?

Первый человек собеседует, второй молчит, может быть что-то отмечает у себя.
По крайней мере, у меня на интервью второй парень сделал ровно два действия:


  • поздоровался
  • подтвердил, что основной интервьювер пишет не в тот документ

Не хочешь — не собеседуешь.

А какова мотивация собеседовать людей в другие команды?

А! Понял. Полная цепочка: Тренинг => несколько Shadow интервью, где ты либо только слушаешь, либо ведёшь интервью а второй, более опытный, только слушает => Собеседуешь самостоятельно.

Фаза Shadow важна для калибровки навыков — тогда вы оба пишете отчет по одному и тому же интервью никак не договариваясь, независимо, а потом уже обсуждаете чтоб понять оба ли одинаково поняли и оценили произошедшее.

Я, разумеется, уже автономен и если надо тот самый «более опытный».

А какова мотивация собеседовать людей в другие команды?


А мы собеседуем не в команды, а в компанию. Так что вполне можете встретиться и в одной команде через год-другой :)
2 раз пытался, оба раза фейл. Интервью ничем не отличается от других «больший» компаний. Задания тоже стандартные и все на литкоде и тд. Очень любят давать вопросы на динамическое программирование (из-за чего я и зафейлился кстате). Печеньки кстати в гугле давно не айс, там рядом офис ЛинкедИн — кто похитрее туда ходит питаться :)
В котором из гуглоофисов не айс? :)) «У компании Google более 70 офисов в 50 странах.»

Вы были на телефонном или на очном собеседовании? Они все были на динамическое?
Вы что-либо изучали за год между попытками?
Собеседовался в МВ. Был и там и там оба раза, нет не все на динамическое, но не решил именно их + общался с другими сотрудниками и они сами говорили что дают исключительно ДП. Перерыв был больше года, что-то учил, но не прям готовился.
Ну, кто-то любит такие задачи :) Но это их право и любовь. Только на очных собеседованиях вопросов много, и мы договариваемся чтобы они были разные.

Моя любимая сводится на графы (но есть и альтернативные решения, всегда люблю, когда их находят), но я держу на готове еще вопрос на динамику (использую, если никто другой на динамику не подготовил) и есть на комбинация структур данных, если и графы и динамику уже взяли.
Если честно, мне жаль потерянного времени — никаких сверхъестественных вещей я не увидел, а весь этот цирк с задачами только злит.
А какие сверхестественные вещи вы ожидали?
У нас работа совершенно не сверхестественная, вопросы соответствующие.

Если задача на 20 минут вас злит — то нам просто не по пути. В конце концов, собеседоавние — это диалог. Не только компания оценивает кандидата, но и кандидат оценивает компанию. Поэтому это нормально, что кому-то этот процесс не нравится, и он делает для себя пометку «тут не работать». Вы только что сэкономили себе пол-года год жизни! Вы же могли иначе начать тут работать, и это было бы не то, что нравится.
> Если задача на 20 минут вас злит
Я думаю, речь идет не про одну задачу, а про весь процесс интерьюирования. Перезвоны с HR, телефонное интерьвю (все исключительно в рабочие часы), поездка в офис, весь день там — нормально так потраченного времени набирается.

> кандидат оценивает компанию
Да, в теории. На практике, все люди у меня на собеседовании были из других команд, ничего путного сказать не могут (либо NDA, либо не знают), единственное — офис посмотреть.
На практике, все люди у меня на собеседовании были из других команд
Гугл начал набирать людей в команду? У меня было ощущение, что он всегда нибирал в Гугл, а не в конкретную команду… а команда и проект — это уже потом… отсюда, кстати, многие объяснимые особенности интревью-процесса.
С одной стороны — да, с другой… Одно дело когда собеседуются студенты без опыта — им часто все равно. А если у вас уже есть N лет опыта и с текущего места не гонят, то уже начинаешь присматриваться и выбирать. Вот тут и возникает проблема, что «кандидат оценивает компанию» особо и не работает.

Объявления о работе всегда про конкретную позицию и команду. Какое мне дело, грубо говоря, как все устроено в YouTube, если позиция в Android.

Единственное, что я узнал о компании — это везде open space. Можно ли по этому оценивать компанию — не знаю.
Есть lunch interview, на который можно, наверное, попросить дать пообщаться человека из конкретного подразделения.

Динамическое программирование — это не просто академическая игрушка и головоломка-пароль, чтобы пройти в гугл. Я на практике как раз в гугле применял. Пару раз вместо полного 2^N перебора можно было сделать что-то квадратичное или кубическое.


Поэтому стоит его ожидать на интервью и дальше и подучить его.

Поэтому стоит его ожидать на интервью и дальше и подучить его.

Мне кажется слово "подучить" тут не очень подходит. Это не какой-нибудь React освоить. Это, ИМХО, на пару лет по выходным...

Ну нет. Идете на тот-же leetcode, и прорешиваете задачки с подсказками. Пару вечеров в неделю, да выходные — за пару недель можно натаскаться. Там же основная идея одна и та же. Осталось только натаскаться угадывать, что взять параметрами.

Я так уже делал. Решил порядка 180 задач. Многие из них у меня отнимали по многу часов. Чем глубже я углублялся, тем сложнее становилось. Тем больше я понимал какой объём работ впереди. И судя по всему на собеседовании в google меня попросят решить не задачу в стиле:


  • проверьте правильно ли расставлены 3 вида скобок в строк
  • верните true если число N можно получить путём произвольного сложения чисел 6, 9, 20

А что-то сильно более лихое. Ну т.е. что-нибудь, что я может и решу, но не за 20 минут под наздором. Или я не прав и сгущаю краски? )

Ну вот вам пример запрещенной теперь к интервью задачи (потому что утекла) — меня именно ее пару лет назад и спрашивали:


У гугла куча офисов в разных странах. В разных странах разное количество праздников. Можно раз в месяц перелетать в другой офис (в конце месяца). Как и куда лететь, чтобы максимизировать количество выходных? Дано сколько выходных в каком офисе в каждом из 12 месяцев. Еще дан список возможных перелетов офис->офис. Верните список из 12 офисов.


Из уточнений — не обязательно перелетать, можно сидеть в офисе несколько месяцев подряд; нельзя делать несколько перелетов подряд, т.е. лететь только без пересадок. Перелеты однонаправленные (если дано A->B, то не обязательно можно лететь B->A); Вам дан начальный офис, заканчивать год можно где угодно.


Ненамного сложнее того, что вы упомянули, но ничего сверхъестественного. Решение — буквально 10 строк. Да, тут еще как-бы и граф есть но ДП на графах — тоже стандартная вещь.

Звучит вполне подъёмно.


  • рекурсия, каждый следующий шаг которой, это след. месяц
  • перебираем из каждого офиса все те офисы, куда можно из него прилететь, без иключения
  • на каждом шаге рекурсии по итогу вычислений запоминаем лучший локальный результат (аля: с 5-го месяца из офиса 17 до конца года можно набрать 12 выходных согласно такому то маршруту) в кеше
  • соответственно на каждой итерации предварительно проверяем результат в кеше
  • в финале пробегаем по первому уровню кеша и берём максимальный результат

Такой ответ устроил бы собеседующего? Это обязательно воплощать в коде или можно "на словах"? Просто придумал как решать я быстро, но боюсь написать рабочее решение за 30 минут я не успею.

Примерно такой ответ и был и устроил собеседуюшего. Я правда, развернул рекурсию и делал двумя циклами в матрице.


Только надо не забыть, что можно в офисе остаться при переборе следующего и в финале не перебираем первый уровень — нам же дан стартовый офис.


Конечно, надо в коде. Но это 10-20 строк всего. Чего тут за 30 минут можно не написать? Код не надо компилировать, если там будут опечатки — это не минус для оценки. Если забудете что-то (напрмер, остаться в офисе) — интервьювер даст подсказки, типа "а вы нечего не забыли? А если такой тест?".

Такой ответ Вы бы засчитали?
        //int[i, j] holidays - сколько выходных в офисе i в j месяц
        //bool[i, j] fligths - есть ли перелёт из офиса i в j
        //startOffice - начальный офис
        static int[] Solve(int[,] holidays, bool[,] flights, int startOffice) {
            int[,] h = new int[12, 12]; //h[i,j] - как много выходных можно получить, если сейчас i-й месяц и мы находимся в офисе j,
                                        //отрицательным значением пометим если мы этот офис не можем достичь к месяцу i
                                        //можно обойтись и двумя массивами, т.к. на текущем месяце нам нужны данные только из предыдущего.
                                        //но сначала я бы написал именно такой алгоритм.
            int[,] p = new int[12, 12]; //p[i,j] - из какого офиса мы переехали в j в i-м месяце;
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 12; j++) {
                    h[i, j] = -1;
                }
            }
            h[0, startOffice] = holidays[startOffice, 0];
            //i - индекс месяца
            //j - индекс офиса отправления
            //k - индекс офиса прилёта
            for(int i = 1; i < 12; i++) {
                for(int j = 0; j < 12; j++) {
                    if(h[i - 1, j] < 0)
                        continue;
                    for(int k = 0; k < 12; k++) {
                        if (!flights[j, k] && j != k)
                            continue;
                        if (h[i, k] < h[i - 1, j] + holidays[k, i]) {
                            h[i, k] = h[i - 1, j] + holidays[k, i];
                            p[i, k] = j;
                        }
                    }
                }
            }
            //находим где больше выходных в конце года
            int bestOfficeAtTheEnd = 0;
            for (int i = 1; i < 12; i++) {
                if (h[11, i] > h[11, bestOfficeAtTheEnd]) {
                    bestOfficeAtTheEnd = i;
                }
            }
            //восстанавливаем ответ
            int[] result = new int[12];
            result[11] = bestOfficeAtTheEnd;
            for (int i = 10; i >= 0; i--) {
                result[i] = p[i + 1, result[i + 1]];
            }
            return result;
        }

Один мелкий недочет — в интервью бы исправилось сразу при написании — кто вам сказал, что офисов 12? Их N. Но это у вас просто 12 в нескольких местах на N поменять надо.


Решение отличное. Вы даже учли случай, когда из начального офиса нельзя никуда улететь вообще.


Если осталось время на интервью, я бы попросил вместо коментариев сделать имена переменным осмысленные, но это не критично. Еще обязательно спросил бы про сложность вашего решения. Может быть обсудил бы еще, почему вы считате, что можно -1 использовать для недостижимых позиций (очвидно — мы счиатем, что не может быть отрицательного количества выходных, поэтому -1 мы в достижимых позициях не получим никогда. Но хотелось бы это услышать на интервью).

Спасибо большое за оценку.
Сделать количество офисов переменным — это логичный шаг, но я ориентировался на то, что сказано, что их 12. Ввести переменную — не проблема. Не был бы я уставшим, скорее всего начал бы своё решение с ввода константы const int officesCount = 12. А не просто использовал число. Считаю, что это мой косяк.
Время на интервью точно бы осталось, т.к. на это решение я потратил 10 — 15 минут. Идею придумал сразу.
Про осмысленные имена переменным — вопрос интересный. В разных фирмах ко мне были разные требования к именам переменных и оформлению комментариев. Такой код я в мастер не отправил конечно же, но на собеседовании на листике так бы и написал.
Сложность. Если число офисов N, то сложность O(N^2).
Про -1 я бы рассказал на этапе написания ещё.
У меня есть опыт прохождения многоуровневых собеседований в крупные международные компании, потому примерно представляю что и когда бы говорил. Но волновался бы жутко! :)
Летом попробую к вам в фирму отправить заявку. Может что-нибудь получится.
Где было сказано, что их 12, имелось в виду, что ответ — это список из 12 офисов (по одному на месяц)
Спасибо большое за замечание! Больше не буду ничего писать уставшим в пятницу.
К счастью, очные собеседования не проводятся в пятницу вечером. Да и нормальный интервьювер обратил бы ваше внимание на этот момент и не зачел как ошибку.
PS: Писать что-нибудь уставшим в пятницу вечером полезно, увеличивает выносливость. Когда я занимался олимпиадным программированием, у нас были специальные 2-часовые туры из небольшого количества сложных задач вечером, после учебного дня, для симуляции условий конца контеста.
Это «у страха глаза велики» :)

В статье приведен пример вопроса — «напишите LRU кеш».

Вариант вопроса на динамику (тоже больше спрашивать уже не должны) — организуйте структуру данных, которая позволит записать число по заданным координатам, и запросить сумму квадрата между двумя произвольно заданными точками.

Обратите внимание на пост — вопрос был задан прямо вот так. Я обычно задаю в менее явной форме, чтобы дать 2-3 минуты кандидату подумать и уточнить задачу, чтобы понять как он думает о проблемах возникающих; но если сведение к этому не было предложено в эти 2-3 минуты — ничего страшного, просто скажу что «это можно сделать, например, используя структуру данных» и далее по тексту. Кстати, еще раз: это НЕ плохой сигнал. Ничего плохого не произошло :)

Пример вопроса в форме задачи, который должен сводиться к вышесказанной — «Представьте, что вы запускаете систему слежения за бюджетом в компании. Каждый сотрудник вносит свои затраты по множеству подкатегорий используя супер-навороченный сканнер чека. Они, разумеется, сканируют и старые чеки. Финансовые же аналитики заинтересованы в анализе различных срезов — по отделам и категориям. То есть им надо то периодически посмотреть суммарные затраты на мышки в IT, то затраты на коврики у геймеров. Представьте что это всё вмещается в память, как вы организуете данные для удобства формирования таких отчетов?»

Спасибо за задачу. Вопрос про квадраты интересный. Открыл Excel для "рисования". Стал думать. Пришёл к следующим выводам:


  • сумму любого прямоугольника можно рассматривать как сумму от дальней точки до 0, минус две боковых прямоугольника, плюс один угловой.
  • можно в этой структуре хранить не только величину самой ячейки, но и сумму от 0 точки
  • при UPDATE операции O(N^2) мы увеличиваем значения всех ячеек правее и ниже
  • при QUERY просто считаем ту сумму и разность 4 прямоугольников до 0. Итого O(1)

Я прошёл? :) По вашей ссылке в коде явно не то, что я бы сделал. Там какие-то сплошные вычисления сумм...

Прекрасное стартовое решение! Вы отлично оптимизировали QUERY, а можете представить решение, если вставки происхоlят _гораздо_ чаще?

А можете подумать, как найти решение сбалансированное по стоимости запросов и обновлений?

Подумал. Придумал одно странное решение, которое долго кодить. В общем:


  • берём M=sqrt(N)
  • создаём новый массив M*M
  • в этот массив мы пишем всё тоже, что и в алгоритме выше, но теперь каждая ячейка такого массива содержит в себе сумму элементов которые она обобщает
  • в оригинальном N*N массиве храним всё также как и согласно оригинальному алгоритму, но берём 0-ую угловую точку не по 0:0 координате, а по координате их обобщённого квадрата.
  • в итоге UPDATE у нас сводит к тому чтобы поправить значения внутри под-квадрата и поправить итоговые суммы у внешних квадратов что правее и левее, не трогая их содержимое
  • QUERY сводится к двум операциям по складыванию и вычитанию прямоугольников

Мне кажется я придумал какую-то дичь. Но она определённо должна работать сильно быстрее чем первый вариант на UPDATE. Плюс формально можно её сделать много уровневой, а не двух-уровневой. Правда кодить это будет всё потом больно.


P.S. погуглил, кажется я тут "родил" двумерную sqrt-декомпозицию...

Ага, прекрасный подход к улучшению решения!

Хотелось бы еще посмотреть на примерную прикидку полученной сложности — но она легко получается после написания его, можете прикинуть по времени, сколько бы оно заняло?

Я думаю, что


  • для UPDATE это было бы M * M внутри "под-квадрата", и M * M снаружи. Т.е. (sqrt(N) * sqrt(N)) + (sqrt(N) * sqrt(N)). Т.е. N + N. Т.е. O(N).
  • для QUERY надо сделать 4 операции для внешних M-квадратов, и 4 операции для внутренних квадратов. O(1)?
  • в реализации с двумерным древом отрезков UPDATE был бы быстрее, а вот QUERY медленнее (не O(1)). С асимптотикой затрудняюсь ответить, т.к. очень плохо помню как оно там работает. Надо будет освежить в памяти.

Правильно посчитал?


P.S. если бы интервьювер попросил меня по быстрому на коленке это закодить, я бы наверное задымился. Мне нужно гораздо больше времени, чем 30 минут для этого.

Ну кодить я бы попросил еще первый, просто квадратный вариант.
Из него переделать проще, плюс можно решение декомпозироовать в него, что, кстати, я видел не часто в качестве решения.

Остался только один вопрос: а почему вы говорите о квадрате?
И есть ли разница, если одно из измерений сильно больше другого?

Разницы вроде нет, алгоритм тот же. Может быть если одна размерность сильно больше другой, то есть более оптимальные решения. Не думал об этом.


О квадрате я говорю только потому что по вашей ссылке написано:


Given a 2D space of maximum size NxN which supports two operations...

Собственно задачу я понял, посмотрев на ^, а не на:


организуйте структуру данных, которая позволит записать число по заданным координатам, и запросить сумму квадрата между двумя произвольно заданными точками

Ваша формулировка вызвала у меня много вопросов :) Координатам чего? Что такое сумма квадрата? Нипаняяятна. На собеседовании я бы стал сразу уточнять, что именно вы имеете ввиду, пытаясь угадать. Но тут просто перешёл по ссылке и посмотрел формулировку у китайца.

Понял, вы совершенно правы :)
Для подведения итога осталось только накидать реализацию, чтобы получить оценку времени сколько у вас на это уйдёт — и, боюсь, результат не понравится.
(В смысле, это окажется меньше, чем вы думали).
обсуждение задачи

Я правильно понимаю, что тут достаточно линейного решения для update и count, и не требуется (log n)^2 решение на двумерных деревьях отрезков/фенвика?

Деревья отрезков. Точно. Я совсем забыл про них. Даже решал с ними задачки. И древо Фенвика курил (очень долго пытался понять причём тут битовые маски… но таки вкурил). В итоге забыл про них. А говорят что алгоритмы не забываются.

Вообще, 2D деревья отрезков — это немножко дичь. Там нельзя наивно пилить прямоугольник на 4 части-угла. Это будет иногда работать за линию. Надо делать дерево отрезков по одной координате и там каждая вершина будет деревом отрезков по второй координате. Если специально не тренировать это — не закодишь.


Поэтому я считаю, что это решение на 5+. Если кандидат сам сразу придумал и уверен в себе — честь и хвала такому кандидату. Иначе, ни в коем случаее не надо подталкивать кандидата к этому решению и если времени на кодинг осталось мало, то попросить написать что-нибудь попроще.

Совершенно верно. Достаточно, если человек может написать квадратичное решение, и найти одно его улучшение. Если знает решение еще лучше — рассказать его, закодить в это время это уже или высший пилотаж или домашняя заготовка.
И в реальной работе так же. Важно, чтобы кандидат не получал линейные алгоритмов там, где они-таки должны быть линейные (и да, вопросы про сложность std::map::iterator::operator++ и std::string::push_back — они как раз сюда) и чтобы он вовремя смог заметить, что, скорее всего, его решение не оптимально и, почти наверняка, какая-нибудь хитрая структура с хитрыми алгоритмами сделает решение лучше, чем просто лобовое.

Во втором случае можно либо устроить «мозговой штурм», либо «забить» решив, что размерность задачи недостаточно велика для того, чтобы заморачиваться со сложными структурами данных (хотя вот это решение имеет привычку со временем возвращаться и «больно кусаться»). Но главное — заметить, что мы используем больше ресурсов чем могли бы.
во всяких веб-фреймворках DP как раз вагон и маленькая тележка.
например та же мемизация стейта — это же классическая тема динамического программирования!

теперь осталось только изучить табличные прекалькуляции
christopherstoll.org/2012/01/javascript-dynamic-programming-example.html

после чего останется еще один шаг — редукция таблиц до только необходимой истории, и всё — вы знаете ДП.

последний штрих — решить 3-5 задач на них чтоб закрепить знания и понять как распознать что задача сводится к ДП.

зачем вам пара лет?
За 10 лет работы совокупно в 4 разных организациях пока ни разу не приходилось проходить интервью. Надеюсь, так и будет дальше.
За 10 лет 3 компании, сотня интервью (с обоих сторон баррикады).
Надеюсь, так и будет дальше.
10 лет в одной фирме, но каждые два года новая позиция и десятки внутренних интервью. Надеюсь, переходы станут проще…
Я не люблю тот формат собеседований, который предлагает Гугл, однако, работая в крупной компании, я решил пройти тренинг для собеседующих. Мне было очень интересно посмотреть изнутри на процесс, который должен по всей логике научить людей отделять «мух от котлет» имея в распоряжении лишь сорокаминутную попытку решить пару сомнительных задачек. Собственно, то, что я увидел в процессе тренинга меня ничуть не удивило.

Выглядело это примерно так. Сначало нужно посетить несколько лекций, где «наш-самый-лучший-собеседователь-80-уровня» разберёт пару типичных задач с комментариями вроде «если так решает, то это плохой сигнал, а если так, то норм». Естественно, даже имея здоровый интерес к процессу обобщить такой подход на остальные 999 задач едва ли получится. Уже на этом этапе каждый сам для себя решает, какие именно сигналы он будет относить к позитивный и негативным (однажды, в Гугле мне собеседующий высказал «фи» за то, что я переменную объявил парой строчек выше, чем можно было. Я не шучу!). Но об интересе, здоровом или не очень, говорить не приходится — большинство кандидатов в собеседующие пишут рабочий код или уставились в телефон. И вот тут вы думаете, что дальше будет что-то интересное… а его нет =) После этих пресловутых «лекций» идут один или два так называемых «shadow interview», где кандидат в собеседующие просто находится в одной комнате с другим собеседующим и собеседуемым и тихо смотрим на процесс. После собеседования можно обсудить кандидата и задать вопросы основному собеседующему. И далее — обратный процесс, «reverse shadow», когда кандидат собеседует, а «бывалый» молча за ним наблюдает. И если только кандидает не умудрился показать полнейшую неадекватность, то после пары shadow его добавляют в пул собеседователей, чтобы он мог присоединиться к десятитысячной армии «унижателей задачами про сортировку гномиков».

И да, я забыл рассказать самое интересное. Результат собеседования это галочка/крестик/boolean — «брать» или «не брать» («hire»/«no hire»). Всем фиолетово на эти вот «важно не само решение, а процесс его поиска». И собеседующие никогда не собираются вместе, чтобы обсудить кандидата. Хорошо, если они успеют написать свой отзыв в течение недели, потому что многие могут тянуть этот момент очень долго, получая редкие попинывания от рекрутера. Вместе собираются уже другие люди на hiring committee, но ведь не надо быть гением, чтобы понять, насколько информация искажается, пройдя столько этапов?
И да, я забыл рассказать самое интересное. Результат собеседования это галочка/крестик/boolean — «брать» или «не брать» («hire»/«no hire»).

В гугле не так. Во первых, градаций больше, есть еще leaning hire/no-hire. Во вторых, результат — это не просто оценка, а детальный отчет. Этоти отчеты от всех 4-5 интервьюверов смотрит отдельный комитет. Они читают все и могут вообще проигнорировать отчет какого-то интервьювера, если там нет объективных сигналов.


С телефонными ближе к тому, что вы сказали, но там тоже детальный отчет читает рекрутер. Если есть основания пологать, что вы просто не понравились интервьюверу — вам назначат второе собеседование.

Звучит как кто-то попробовал «сделать как google» без знания а как это именно, а карго-культ.
Да ладно — несколько знакомых их Гугла подтвердили, что там всё один в один.
однажды, в Гугле мне собеседующий высказал «фи» за то, что я переменную объявил парой строчек выше, чем можно было. Я не шучу!
Не понимаю ни почему вас это удивило, но почему вы решили, что кто-то решил, что вы шутите. Это ж просто правило хорошего тона! А в Гугле оно и вовсе формализовано.

Впрочем если вы писали на листе бумажки (не в Google Docs), то тут я бы скорее интервьюеру замечание сделал: писать на листе бумажке и без того трудно, а нарушение этого правила процесс чуть-чуть облегчает.
Может быть потому что это порядок переменных в коде, который написан маркером на доске, это так себе «сигнал»?
Если это маркер на доске (или на бумажке) — то это придирки интервьюера, однозначно.
Google ищет инженеров постоянно.

Как-то раз подавал заявку в одну специфическую команду, с рекомендацией. Через три месяца (!) рекрутер написал, что у меня крутые навыки, но не подходящие для той команды. Без скринингов, без каких-либо разговоров. «Мы с вами свяжемся». Вариантов пособеседоваться на другую вакансию не предлагал :)
Возможно, в специфические и есть ограничения. Но гляньте на careers.google.com — есть поиск по офису и тексту, может есть интересующая альтернатива?
Я мастодонт — я учился по «Алгоритмы+Структуры данных = программы» Вирта; а так же выкурил трёхтомник Кнута в детстве (хотя не, буду честным — не выкурил, а проглядел как художественное чтиво: задачи не прорешивал, мне лень было, когда попадалось что-то сильно нудное пропускал).
Вирт дал понимание важности и базу, Кнут дал понимание важности сложности и навык её оценки, а так же вздох «как всё сложно».
Подскажите, если есть высшее образование, но не техническое, и живу в снг, есть ли смысл готовиться к собеседованию? Слышал что без технического диплома, очень сложно получить формальное разрешение на работу. Есть двухлетние курсы переподготовки в нескольких вузах с дипломом гос образца. Стоит ли поступать, дадут ли с ним разрешение на работу или лучше прокачиваться в навыках собеседования
Насколько понимаю, надо смотреть на требования страны в которой офис.
Зачастую требования или/или: либо профильный диплом из признанного вуза, либо N лет работы по профессии.
Всё равно можно готовиться, когда вы пройдёте — рекрутёры соединят с фирмой, которая поможет определить требования и ограничения (куда можно и какие бумаги нужны).
Конечно, если вы поищете и подготовитесь сами будет проще и понятнее, но тем не менее.

Например смотрю сюда: www.germany-visa.org/work-employment-visa
Если уже есть оффер, то в требованиях я не вижу документов подтверждающих знания и умения (вероятно, предполагается что фирма уже проверила это).

Однако я не юрист и не специалист по миграционным правилам стран, так что гарантий дать не могу.
В UK для получения визы Tier 2 (general) нужно набрать 70 баллов. При этом 20 дается, если зарплата больше, чем некоторый минимум (у всех разработчиков зарплата больше, минимум очень низкий), еще 30 — если работодатель выполнил некоторую бюрократию по доказательству того, что ему нужен работник из-за рубежа, а на внутреннем рынке таких привлечь не получается, еще 30 — если профессия входит в список профессий, где есть недостаток работников (вроде программисты входят, но не любые), еще 30 дает UK recognised degree, но я не уверен, что степени в российских вузах ими являются. Упоминаний, что степень должна соответствовать работе, не встречал.
PS: Я не юрист, могу ошибаться.
А почему народ так рвется идти работать в гугл, майкрософт и прочие гиганты? ЗП там обычно средние или даже ниже средних по рынку. Бюрократия, ощущения «шестеренкой» в тяжеленной махине… Бррр…
В чем бонусы? Если честно, то я не понимаю этого.
ЗП там обычно средние

Разве? Скажем, вот Гамбург Google — 98-104k euro. А вот там же 40-50-60-70k, но другие компании. Выше очень немного предложений (Facebook например).