Как стать автором
Обновить

Комментарии 297

Поздравляю. Ну с точки зрения инженера почти без опыта более менее понятно. Вопрос что делать архитектору с 15 годами опыта? Ну не деревья же строить?

Тут лучше пообщаться с ребятами, кто проходил собеседование на L6, там вроде большой упор на системный дизайн и behavioral

На L5 в Фейсбуке меня про деревья спрашивали.

Там действительно бОльший упор на системный дизайн и behavioural (который на L6 в ФБ я успешно завалил без комментариев с их стороны), но кодинг весь точно такой же и без него пройти не получится.

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

А откуда бы там "джунам" взяться если даже студенты там проходят такой же отбор?

И да и нет. Для fresh grad-ов и интернов часто бывает упрощенный процесс с другими порогами.

Будете делать всё, что джуны и мидлы. Плюс своё. Тоесть всё будет. И деревья и остальное. Только еще про менеджмент и систем дизайн. Вас таких 10000 на 1 место. Можно и подурачиться.

Как раз проходил пару месяцев собеседование в Amazon в Берлин, сильно алгоритмическая задача была только в автоматическом кодинг тесте. Во всех пяти последующих интервью с живыми людьми был преимущественно акцент на system design и поведенческие вопросы. Как я понял, выбор вопросов на интервью во многом - выбор конкретных интервьюеров, поэтому практический опыт у всех может быть разный.

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

Это была не позиция архитектора, кстати, просто опытного разработчика.

15 лет - это еще куда ни шло, а что делать мне с 30 годами опыта? Хотя вопрос, конечно, риторический - таких старых, как я, в FAANGи не берут.

Неправда. По крайней мере в гугле. Те, кто решения принимают (комитет по найму) — ни вашего возраста, ни пола, ни имени не знают. Только отчеты с интервью. А от интервьювера в отчете только объективная часть — решил ли задачу, сколько времени потратил, какие идеи были. У меня один коллега 50+ был нанят недовно.

У меня один коллега 50+ был нанят недавно.

У него тоже спрашивали, как развернуть двоичное дерево?

Ну не конкретно этот вопрос, конечно, но что-то из того же класса.

Моё любимое по теме:

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

Удачи вам и спасибо за статью!

это просто процесс отбора. И никак не значит что те алгоритмы вам 100% будут нужны. Просто если порешал 450 задач — уже мотивированный и целеустремленный сотрудник а не тот кто вышел через дорогу за +500$

Я всё прекрасно понимаю и отрефлексировал это по-полной.

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

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

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

Как-то даже страшновато высказываться, но, мне кажется, есть какая-то проблема, когда "архитекторов", которые уже 15-20 лет работают "за деньги", на собеседованиях гоняют по структурам данных и алгоритмам, которые, в общем-то, наизусть помнят только вчерашние студенты. И не сказать при этом, что в условном FAANG все дураки и не понимают что делают - на их объемах данных сотрудник, запуливший в прод алгоритм с O(n^2), реально создаст проблему и, может быть, даже многомиллионные долларовые убытки. И, наверное, то, что они ставят там у себя на вход такие стерильные фильтры, имеет с их стороны смысл. Но вот сама ситуация, когда на собеседовании требуется джедайское владение теми самыми пресловутыми "структурами данных и алгоритмами", а в "реальной работе" требуется, ну "Spring, Hibernate, JPQL", и редко-редко хотя бы рекурсию применить уместный случай подвернется, мне кажется странной, скажем так.

Для того, чтобы не пулить в прод O(n^2) вроде бы существуют код ревью. А потом существует куча тестов по которым деградация перформанса будет очевидна. Более того, проблема прода в Гуглах сильно преувеличена, ведь в прод доходит процента три написанного кода, остальное в помойку. Ну и как пользователь админки gmail для компании в 50 человек, где каждое действие занимало по 30 секунд, я лично не знаю что случается потом с олимпиадниками в Гугле. Хотя, возможно, архитекторов там нет и просто 100500 микросервисов делают O(n^2) раундтрипов за данными друг к другу.

O(n^2) — вполне мемично.
Лично использовал такой алгоритм. Можно ли было использовать более быстрый? Да. Но этот программировался существенно быстрее, с меньшими проблемами, и надо было быстро увидеть результат. Алгоритм отрабатывал около 10 минут, что в сравнении с другой частью задачи — которая отрабатывала 8 часов — значение не имело.
Но да, это не обработка транзакций или чего-то подобного, а физика.

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

А не нужен им ни спринг, ни хибернейт, ни jpql. И gradle с мавеном не нужны. Там до такой степени свой мир и своя атмосфера.

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

Да все гораздо проще, как мне кажется. Если стульчик один, а желающих - 100, как будете выбирать кого усадить на него? А если 80% обладают подходящей задницей? Как в анекдоте «... ну окей, тогда показывайте сиськи»

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

О боже, программиста просят на интервью писать код чуть посложнее FizzBuzz. Какое унижение. Кому вообще могло прийти в голову просить программиста программировать? Чертовы садисты. /s

Ну справедливости ради: не сложнее fizzbuzz, а какую-нибудь задачку, для которой надо помнить какой-нибудь алгоритм Стейнхауса-Джонсота-Троттера, при этом написать закрыв глаза и стоя на коленях (зачеркнуто) высохшим маркером на вертикальном уайтборде, в стрессе и так пять раз подряд, с 9 до 15.

Был там, не уверен что хочу повторить.

а какую-нибудь задачку, для которой надо помнить какой-нибудь алгоритм Стейнхауса-Джонсота-Троттера

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


Ну вот нет у интервьюверов цели нанимать академиков по computer science. Нужны программисты, которые умеют решать задачи.


при этом написать закрыв глаза и стоя на коленях

Уже давно в гугле, и по-моему в других компаниях (но это не точно) можно писать на ноутбуке в специальном редакторе с подсветкой синтаксиса. При этом требования все такие же, как к доске: компилировать не надо, опечатки игнорируются. Даже если вы перепутаете, в каком порядке там параметры куда-то передаются — это вообще не минус. Можно даже сказать "я вот точно помню, что там какая-то функция примерно вот это делает, но вот не помню название". Интервьювер подскажет название или скажет, "ну назовите ее как хотите, только откомментируйте, что она делает". И это не разу не минус. Конечно, если кандидат сразу наворачивает хитрые и правильные конструкции и помнит все, ему ставится большой плюс в графу "кодинг" — отлично знает ЯП. Но для успешного найма такие плюсы не нужны. Они могут лишь компенсировать минусы в других интервью или пунктах.

которые умеют решать задачи.

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

Ну вот нет у интервьюверов цели нанимать академиков по computer science

есть есть, просто потому что 'вы можете' и у вас 'толпа сеньоров за забором'
это вот по факту так
===
забавно что качество софта гугла не коррелирует с требованиями при найме

а ты со своим 15 летним опытом и кучей проектов за плечами, сидишь и чувствуешь себя джуном-двоечником который пришел к крутым дядям и обкакался…

Большой дядя с 15 летним опытом стесняется кодить в присутствии других кодеров?

Я не стесняюсь, я не могу быстро думать, особенно когда над душой кто-то висит

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

Сколько я думал на эту тему - подумал вот что (я без ярлыков, если что, правильно вообще-то смотреть каждый случай индивидуально):

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

Бывают люди, которые говорят, что они думают медленно, но качественно. Я таких видел несколько, они действительно прут как танк - неспешно и неумолимо. И эта категория людей выходит не нужна faang'у, они заранее будут отсеиваться низким временем решения задачи: ты только 23 минуты входишь в задачу, а уже пора её завершать.

ты только 23 минуты входишь в задачу, а уже пора её завершать.

Этож что это за задачи такие у сеньора-программиста где надо за 15 минут решить задачу?
довольно большое количество таких случаев, которые я видел, приводили только к усугублению проблемы из-за того что человек решил 'быстро и насмотренно прямщас' и забыл что вещь которую он решает имеет далеко идущие связи в соседние подсистемы и отделы, про которые он забыл из-за того что надо 'быстробыстро'
И эта категория людей выходит не нужна faang'у,

мне чёт кажется они даже об этом не думают, ориентируясь на какието количественные показатели
Этож что это за задачи такие у сеньора-программиста где надо за 15 минут решить задачу?

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

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

которые никогда не используются в реале

я помню сильно поспорил с интервьювером в одном месте когда он показал 'правильное' решение задачи (какойто синтетической где важно было иметь случайную последовательности и должно было обрабатываться быстро) с критическим багом внесения случайности… и при этом совершенно не понимал 'ну а в чем проблема то, работает же!!! вон нажимаю.… случайные числа и быстро отрабатывает'… при этом 'случайность там такова что её предсказание займет минут 5 — хорошо подумать'… но 'то что вы предложили верно, но очень медленно работает'
у меня прямо руки опустились… это прям… позор какойто… так подходить к задачам
которые никогда не используются в реале

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


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


Задачки, даже совсем синтетические, отлично позволяют проверить, а может ли кандидат написать 10-20 строк более-менее приличного кода и объяснить алгоритм.


я помню сильно поспорил с интервьювером в одном месте когда он показал 'правильное' решение задачи (какойто синтетической где важно было иметь случайную последовательности и должно было обрабатываться быстро)

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

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

ну а я не ваше интервью в виду имею собственно то

мне давали задачи вроде в стиле 'поменять местами значения в массиве', 'упорядочить простые числа' с всякими мозголомными 'фишечками' на 'подумать'
Ну где водители «в реале» ездят по площадке с кучей конусов?

водители ездят вдоль домов где запарковано куча автомобилей, площадка с конусами — практически реальная симуляция такого случая
Задачки, даже совсем синтетические, отлично позволяют проверить, а может ли кандидат написать 10-20 строк более-менее приличного кода и объяснить алгоритм.

я могу написать код за 15 минут, посмотреть на него, запустить пару раз… потом всё стереть и написать хорошо и 'правильно",
а требования 'надо чтобы у вас компилятор был в голове и вы выдавали сразу код начистую сразу, а лучше прям на бумажке, настоящий программист может писать на доске'… это уже изврат
я, блин, на сеньорскую должность собеседуюсь… в самом то деле
==
Можете поделиться подробностями задачи и сути конфликта?

задача была как раз в стиле 'гугла/яндекса', чистая синтетика на сообразительность.
в стиле 'напишите сортировку, не используя ф-ции языка… и это тоже нельзя… и это… и set использовать нельзя… и вот так тоже нельзя'
а требования 'надо чтобы у вас компилятор был в голове и вы выдавали сразу код начистую сразу, а лучше прям на бумажке, настоящий программист может писать на доске'… это уже изврат

Нет таких требований. По крайней мере в гугле и яндексе. Есть требование рассказать интервьюверу ваше решение словами, и когда он видит, что вы придумали правильное решение — вас попросят начать кодить. Как раз, чтобы вы не писали то, что потом придется стереть. И не надо никакого компилятора в голове. Плюс интервью на бумажке, что вы можете напрочь забить даже на стандартное АПИ. Код не надо компилировать, опечатки и ошибки прощаются. Сейчас всё проводят в простых редакторах, так что и минусов от бумажки не осталось, а плюсы — остались. Например, если кандидат не помнит, какие там параметры у lower_bound и что оно там ищет — самое левое >= или самое правое <, то я или подскажу или попрошу кандидата в комментарии написать, что он там ожидает от этой функции. И никаких "баллов" за это не снимается. Я не могу говорить за всех интервьюверов во всех фирамах, но, по карйней мере в гугле — это в гайдах.


задача была как раз в стиле 'гугла/яндекса', чистая синтетика на сообразительность.
в стиле 'напишите сортировку, не используя ф-ции языка… и это тоже нельзя… и это… и set использовать нельзя… и вот так тоже нельзя'

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

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

потому что я по опыту уже, решаю задачи с точки зрения бизнеса, а не генерирую какойто синтетический код в вакууме. я вообще ниразу никогда за карьеру не писал код 'чисто по ТЗ, думать не требуется'
если я вижу что в задаче какойто бред = я уточняю, если постановщик задачи не может адекватно сформулировать зачем этот бред нужен — я эскалирую вопрос выше
кхм…
честно говоря я просто перерос рядовую должность программиста, и на меня сильно действуют уже менеджментские вопросы разработки в принятии решений.
и я на самом деле рад что из-за того что сеньорские собеседования зачастую не включают в себя подобные вопросы, за исключением некоторых странных (с моей точки зрения) компаний
потому что я по опыту уже, решаю задачи с точки зрения бизнеса, а не генерирую какойто синтетический код в вакууме. я вообще ниразу никогда за карьеру не писал код 'чисто по ТЗ, думать не требуется'

Распространю это на аналогию с экзаменом на вождение.


Вас просят параллельно припарковаться между этими конусами на экзамене, вы сбиваете конус и проезжаете еще 3 метра. Потому что в реальном вождении ни разу не сталкнетесь с "припаркуйтесь именно тут". И вообще, то место, которое вы выбрали — оно лучше — там тень. Чего машину на солнце жариться оставлять? А конусы — это же не машины с домами, они даже машину не поцарапали.

Потому что в реальном вождении ни разу не сталкнетесь с «припаркуйтесь именно тут».

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

А конусы — это же не машины с домами, они даже машину не поцарапали.

конусы запросто машину поцарапают и бампер оторвут, смотря как наехать

И простите за 2 ответа, итак длинные комменты получились.


мне давали задачи вроде в стиле 'поменять местами значения в массиве', 'упорядочить простые числа' с всякими мозголомными 'фишечками' на 'подумать'

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

Ну вам так сложно представить, что вам придется менять местами числа в массиве, упорядочить удовлетворяющие каким-то критериям числа в массиве?


Конусы — симуляция домов с припаркованными машинами. Простые числа — симуляция какого-то бизнес критерия.

Ну вам так сложно представить, что вам придется менять местами числа в массиве, упорядочить удовлетворяющие каким-то критериям числа в массиве?

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

Кто ее спрашивает?! Где?! В FAANG точно не спрашивают.

В FAANG точно не спрашивают.

вы были на всех собеседованиях со всеми интервьюверами всех компании FAANG?

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

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

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

Ну я только могу сказать что по моему опыту это совсем не так. Вы сами давно на интервью были хоть где-нибудь?

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


Автор статьи тоже никаких заумных задачек не привела в примерах. Раз уж у вас другой опыт, то дайте что ли пару ссылок на тот же leetcode на задачи, где нужен какой-то заумный алгоритм хотя бы с двумя фамилиями в названии.

заумным алгоритмом с тремя фамилиями в названии.

У автора в заметках мелькает "Дерево Фенвика". Мне лет 5 назад было страшно сложно разобраться в этом. "Смотрю в книгу — вижу фигу". Вроде слова русские, а смысла не вижу. В итоге разобрался, но осадок остался. Такое на собеседовании могут спросить? Или достаточно обычного бинарного дерева отрезков?

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


Во-вторых, дерево отрезков умеет делать все, что и дерево фенвика и даже больше. Правда, занимает в 2 раза больше памяти. Если бы действительно была задача, которую нужно решать деревом фенвика, за дерево отрезков вам бы минусов никаких не поставили.

Что насчет задачек из cracking code interview? Там есть весьма зубодробительные.

Что насчет амазонской задачки "Выберите из списка точек ближайшую к некоторой выбранно (x,y)"? Окей, она простая, а что насчет follow-up "Выберите k ближайших точек"? Судя по тому, что я читал в решениях этой задачки - нужно уметь построить rtree и дальше в нем искать. А я вот не умею в алгоритмы такого уровня - неинтересно, как-то.

Я вот слабо представляю как это без подготовки решать. А тратить месяцы жизни ради шильдика "взяли на работу в фаанг" - ну хз..

Что насчет задачек из cracking code interview?

Ну, если бы в книге все задачи были чуть сложнее fizz-buzz она бы не имела смысла. Может, когда-то давно, когда только начали такое интервью проводить и пытались нащупать нужный уровень спрашивали и зубодробительнейшие задачи. Сейчас, по крайней мере, в моем окружении — такого нет.


Что насчет амазонской задачки "Выберите из списка точек ближайшую к некоторой выбранно (x,y)"?

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

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

"Квадрат гипотенузы равен сумме квадратов катетов". Или вы о каких-то других точках?

Похоже, что в задаче список точек фиксирован и надо быстро искать ближайшую к заданной. Судя по упоминанию rtree. Если же это не так, то задача равна стандартной "найдите k максимумов в массиве". Эта задача, действительно простая при минимальных знаниях computer science. Я ее даже спрашивал несколько лет назад. Решение с кучей на k элементов было достаточно.

  • заводим массив на k элементов;

  • заполняем k первых элементов, но отдельно храним максимальный;

  • если следующий меньше максимального, то максимальный выкидываем и этот вставляем, ищем в массиве тот, который сейчас стал максимальным;

  • так проходим до конца выборки.

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

Так?

Не совсем. Нужно хранить не массив, а кучу на максимум, в которой будут k минимальных пока элементов. Если новый меньше максимума — выкидываем его и кладем новый в кучу. Можно использовать существующие std::priority_queue или std::set — не надо писать кучу.


Проблема вашего метода в том, что после выкидывания максимального элемента в мелком массиве надо найти новый максимальный. Это будет O(k) на каждое новое расстояние и суммарно даст O(nk). Когда как куча сразу найдет при изменении новый максимальный за O(log k).

Мне кажется, Set не подойдёт. Он же хранит только уникальные значения, а задача не запрещает иметь равноудалённые точки.

куча сразу найдёт при изменении новый максимальный

Само собой ничего же не происходит, КМК. Отсортированная коллекция будет при удалении/добавлении элемента пересортировываться (да, быстро, т.к. она уже отсортирована, но всё же). Лучше тогда один раз отсортировать коллекцию при достижении k элементов, а потом просто руками удалять элемент с одной стороны и добавлять с другой (должны подойти ArrayList, LinkedList, Queue).

Мне кажется, Set не подойдёт. Он же хранит только уникальные значения, а задача не запрещает иметь равноудалённые точки.

Вам же не расстояние в циферках нужно, а сами точки. Очевидно, что в set и priority_queue вы будете класть пары {расстояние, индекс точки}.


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

Нет. Это не работает. Ну вот, допустим, у вас в коллекции {1,2,4,5,6}. Максимум = 6. Пришло число 3. 3 < 6, значит 6 выкидываем. Нельзя 3 добавлять с другой стороны! Чтобы оно оставалось отсортированным — надо 3 вставляеть в центр.

А... Ну да. Протупил :))

Выберите k ближайших точек

  • для каждой точки вычислить расстояние;

  • занести в массив точки вместе с расстояниями;

  • отсортировать массив;

  • взять первые k элементов.

Профитт?

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

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

Кстати это как раз задачка из разряда, не знал, но придумал. Это почти идеальная задача, в том плане, что она действительно проверяет как человек думает.

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

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

Так они как раз отбирают стоумовых во всем, что касается, а не только в алгоритмах.

Мемас утрированный, но в целом отражает суть.

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

Да, похоже есть два пути в Гугл: 1) через internship, чтобы Гугл из вас вырастил сотрудника 2) быть суперзвездой в чем-то, чтобы Гугл сам за вами прибежал с оффером "впишите свою зпл".

НЛО прилетело и опубликовало эту надпись здесь

В худшем случае у replace сложность O(N) от размера строки (ее придется раздвинуть). И Ваш код имеет сложность O(N^2) (худший случай — замена каждого символа). Правда, по условиям задачи, меньше (замен до 100, длина до 1000).


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

НЛО прилетело и опубликовало эту надпись здесь

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

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

А ещё в новой версии хабра нет кнопки "редактировать", прекрасно.

НЛО прилетело и опубликовало эту надпись здесь

Для комментариев?

У меня ушло больше 10 минут, чтобы получить "Success" на литкоде (правда, на выбранном ЯП вообще почти не пишу, надо было гуглить). Это скорее уровень Easy, судя по моему опыту на этом же самом литкоде, так что вы или автор неудачно выбрали пример. Но я вижу, что можно очень серьёзно заморочиться над производительностью и, например, не успеть сообразить про то, как именно сделать всё в один проход, если спросят так сделать на собеседовании.

Правда, автор статьи не упоминает про то, что нужно морочиться с оптимизацией на литкоде (когда тестов под это нет). Но есть там на литкоде задачи сложнее, на которые нужно тратить много времени, задачи на смекалку, когда нужно догадаться, как решать. Действительно, навык решения таких задач на скорость нужно тренировать, и он снижается без тренировок. Плюс алгоритмические задачи. Я, к примеру, не помню какое-нибудь балансирование прямо чтоб сразу написать, нужно вспоминать принципы работы RB или AVL, а на собеседовании это плохо получается.

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

НЛО прилетело и опубликовало эту надпись здесь

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

Тут неважно, что ощущаете вы, важно, что от вас ожидает интервьювер =D Уж тем более в искусственных задачах.

НЛО прилетело и опубликовало эту надпись здесь

ну да, наверное. "Им, на их объемах, скорее всего, этого хватит"

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

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

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

Если целью является трудоустройство

у меня нет цели пойти работать в первую попавшуюся контору, славабогу рынок ИТ всётаки большой, и hr-ы несколько охренели заваливать предложениями в последнее время
Я уже натыкался один раз когда пройдя такое интервью попал в команду где я был полностью не совместим с тимлидом по принципиальным вопросам программинга… теперь мне проще отказаться заранее если контора сразу начинает хотеть странного и не может объяснить зачем ей это хотеть
НЛО прилетело и опубликовало эту надпись здесь

Души в этом куда больше

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

дружественность к кешу тоже так себе

Довольно очевидно, почему это не словарь, а однонаправленный связанный список со всеми вытекающими проблемами, даже для начинающего =D По сравнению со многим остальным, что идёт дальше. Из всех контайнеров я знаю только про finger tree и было бы интересно, что такое может позволять реализовывать что-то вроде словарей.

НЛО прилетело и опубликовало эту надпись здесь
линейные типы, которые позволяют иметь типа-мутабельные вещи в ФП со всеми ништяками

Есть ли у вас направление живительного пинка в гугл, по которому про это можно узнать подробнее? Ну, кроме wiki

НЛО прилетело и опубликовало эту надпись здесь

Спасибо, плюсануть не могу

НЛО прилетело и опубликовало эту надпись здесь

Аккуратнее со шторами - можно подпалить ярким нимбом ))))

НЛО прилетело и опубликовало эту надпись здесь

Добрый день.

Слушай, Чел (0xd34df00d), я читаю хабр на постоянной основе уже несколько лет подряд, и постоянно натыкаюсь на твои посты/комментарии.

Из чего могу сделать вывод, что ты какой-то адово скиловый разработчик. Прям Адище!

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

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

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

Зарплата? Есть кто-то, кто платит как гугл и проводит собеседования по-другому?

Хедж-фонды и трейдинг вообще платят намного больше FAANG. Но собеседования еще более утомительные, а работа, по сути, ничем не лучше, чем толкать на улице кокс в морально-этическом плане.

НЛО прилетело и опубликовало эту надпись здесь

Есть те, кто платят 80 процентов от гугла, но относятся как к людям.

Зарплата это такое дело, начиная с какого-то размера больше денег это плюс, но не определяющий фактор. Я лично трачу сейчас 1/6 своей зарплаты. Могу найти более оплачиваемую работу? Вероятно. Вопрос зачем?

но относятся как к людям.

Так в гугле отношение к работникам очень хорошее. Я не считаю требование показать, что ты можешь решать задачи, каким-то запредельным или унижающим человеческое достоинство. Предложите свой способ отбора 1 человека из 100.

Зарплата это такое дело, начиная с какого-то размера больше денег это плюс, но не определяющий фактор. Я лично трачу сейчас 1/6 своей зарплаты. Могу найти более оплачиваемую работу? Вероятно. Вопрос зачем?

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

НЛО прилетело и опубликовало эту надпись здесь

Почти. За 30-35 минут написать такое решение и хотябы после подсказок в общих чертах словами описать как его можно было бы улучшить — это был бы hire. На strong hire — написать за время интервью линейное решение.

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

Минус не ставил, но ответ очевиден. Просто избегать инженерных задач. Люди талантливо избегают сложных задач и висят на одном и том же уровне. А там где решение нужно родить — пишут первое что приходит в голову, пусть даже оно решает не ту задачу, решает её плохо. Потому что главное уметь свою проблему подать начальству так, чтобы проблема была не твоя, а, как бы, сама по себе. И это в принципе естественно для человека. Избегать сложностей и перекладывать ответственность.


Что именно в этом удивляет? Мы зачем-то наделяем программистов такими качествами как "математический склад ума", "логика", "аналитический ум". Тогда как по факту обычный программист это обычный человек. Не небритый худощавый гик с засаленным свитером, а [define a normal person].


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

быстрее 100% других решений

А это в leetcode бага такая. Он почему-то не умеет нормально измерять время работы решений на C++. На других языках такой проблемы не замечал ни разу. А на C++ - чуть менее, чем всегда.

НЛО прилетело и опубликовало эту надпись здесь

И на других языках есть такая проблема. За C# точно ручаюсь.

На других языках такой проблемы не замечал ни разу. А на C++ — чуть менее, чем всегда.

скопипастил решение на го, которое показывало 0мс, получил 4мс )

Кому-то везет, кому-то не очень. Иногда попадаются задачи сложнее, вроде этой https://leetcode.com/problems/find-the-shortest-superstring/ причем на этапе online assessment. Да-да, NP-hard даже не доходя до onsite.

И чем эта задача сложна? Там до 12 слов. Это тупо на кодинг задача. Никаких алгоритмов — тупое наивное решение (перебор всех перестановок). Хоть рекурсивно, хоть std::next_permutation. Только один момент — надо додуматься, что если слово содержится в другом целиком, то его надо выкинуть.


Можно заработать outstanding в графе алгоритмы, если сказать, что задача сводится к задаче коммивояжора, и упомянуть NP.


Причем, на hire достаточно какими-нибудь std::string::find пользоватся. Потом уже будет обсуждение, а как можно лучше всего искать вхождение строк, если бы они были длинные (тут можно блеснуть знаниями Ахо-корасика, суффиксных деревьев и других алгоритмов на строки. Естественно, писать это на интервью не надо). Или как быстро подсчитать общую часть на стыке двух строк (использование бора/trie). Но эти все рассуждения только на strong hire нужны.


Задача была бы сложнее, было бы там до 25 строк. Тут уже ожидалось бы динамическое программирование по маске уже посещенных вершин. Стандартная тоже вещь уже, но это я бы тоже хотел только на strong hire.

НЛО прилетело и опубликовало эту надпись здесь

Я бы решал как-то так: за "N^2 * M^2" (где M - средний размер строки) построить матрицу чисел совпадающих букв (сколько букв строки words[i] будет переиспользовано, если за ней поставить строку words[j]), потом в этой матрице находим максимальную перестановку (тот самый комивояжер, но можно решить перебором за N! через рекурсию), потом объединяем. Долго, уныло, но работать будет.

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


Далее, вот перебрали мы перестановку слов. Берем первое слово целиком, а потом жадно как можно глубже всовываем следующее слово в предыдущее, так что суффикс левого слова совпадает с префиксом правого слова. Вот в вашем примере можно "oto" впихнуть на 1 символ в "foo" ("foOto" — общие символы большие), "oof" на 1 символ в "oto" ("otOof"), а "oof" на 2 символа в "foo" (fOOf"). Поэтому для этой перестановки мы сначала получаем "foo", потом "footo", потом "footoof".


Доказать это все просто: рассмотрим ответ, выделим вхождения в нем всех слов в порядке увеличения начала. Очевидно, что каждый символ будет покрыт каком-то словом, иначе его можно было бы выкинуть. Никакие 2 начала совпадать не будут, мы же выкинули входящие в друг друга слова. Отсюда ответ — это какая-то последовательность исходных слов, при этом следующее слово как-то пересекается, но начинается после его начала и кончается после его конца (потому что иначе бы одно слово входило в другое, а мы такие выкинули). Далее, можно заметить, что общая длина — это сумма длин всех слов минус все длины пересечений. И главное — если зафиксировать какое-то слово, то вообще без разницы, что там было до него. Максимальное пересечение этого и следующего слова зависит только от них, ведь оно не превосходит длины левого слова. Поэтому каждый раз можно брать пересечение жадно, смотря только на 2 текущих слова.


Естественно, максимальные пересечения всех пар строк считаются один раз до перебора перестановок. В переборе мы лишь ищем максимальную сумму common_substr[perm[i-1]][perm[i]].


Вычислять максимальную глубину впихивания можно наивно за O(N^2L^2), а можно сравнивать строки с помощью хешей O(N^2L) или можно использовать префикс функцию или Z -функцию (тоже O(N^2L)). Еще можно использовать дерево из алгоритма Ахо-Корасика и тогда поиск всех пересечений будет за O(NL+N^2). Но это уже совсем высший пилотаж.

Похоже на разумное рабочее решение. Только едва ли это можно описать так:


И чем эта задача сложна? Там до 12 слов. Это тупо на кодинг задача. Никаких алгоритмов — тупое наивное решение (перебор всех перестановок)

Ваше тупое наивное решение уже "hard". Подавляющее большинство программистов никогда не сталкивалась с задачами такой сложности (и никогда не столкнётся).


Вы пишете вам потребовалось 7 минут на кодинг. Мне вот 15 потребовалось на простой перебор разной перестановки слов с рекурсией… Даже без оптимизаций. Чтобы потом понять что это нифига не сработает, т.к. есть решения где строка не состоит из поставленных рядом слов.


Попадись мне такая задача на собеседовании я бы слился, 100% :) Ну не знаю, может быть это я такой тупой. Я в состоянии её решить, но точно не за час. Особенно если надо это обсуждать голосом в слух на иностранном языке. У меня не 18 лет опыта, но 13 уже есть.

Чтобы потом понять что это нифига не сработает, т.к. есть решения где строка не состоит из поставленных рядом слов.

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

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


вот этот говнокод я родил на скорость на коленке
function shortestSuperstring(words: string[]): string {
  const excluded = new Set<string>();

  const fn = (prefix: string): string => {
    let min: string | null = null;

    for (const w of words) {
      if (excluded.has(w)) {
        continue;
      }

      const isIncluded = prefix.includes(w);
      if (!isIncluded) {
        prefix += w;
      }
      excluded.add(w);

      if (excluded.size < words.length) {
        const result = fn(prefix);
        if (!min || result.length < min.length)  {
          min = result;
        }
      } else {
        if (!min || prefix.length < min.length)  {
          min = prefix;
        }
      }

      excluded.delete(w);
      if (!isIncluded) {
        prefix = prefix.substr(0, prefix.length - w.length);
      }
    }

    return min;
  }

  return fn('');
};

const check = (src: string[], length: number) => {
  const result = shortestSuperstring(src);
  for (const w of src) if (!result.includes(w)) {
    console.log(`${w} is not found in ${result}`);
  }
  console.log(result, `${result.length} - ${length}`);
}

//check(["alex","loves","leetcode"], `alexlovesleetcode`.length);
check(["catg","ctaagt","gcta","ttca","atgcatc"], `gctaagttcatgcatc`.length);

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

Написал "тупое наивное решение в лоб". Без оптимизаций не работает. Оптимизировал на 1 порядок — всё равно :) Буду дальше думать.


Time Limit Exceeded

ещё немного говнокода
function shortestSuperstring(wordsRaw: string[]): string {
  const words = new Set(wordsRaw);
  let totalMinSize = 10 ** 5;

  const fn = (prefix: string, debugLevel: number): string => {
    if (!words.size) return prefix;
    if (totalMinSize < prefix.length) {
      return prefix;
    }

    let min: string | null = null;
    const dictionary = Array.from(words.values());

    const check = (result: string) => {
      if (!min || result.length < min.length) {
        min = result;
      }
    };

    for (const w of dictionary) {
      words.delete(w);

      if (prefix.includes(w)) {
        check(fn(prefix, debugLevel + 1));
      } else {
        check(fn(prefix + w, debugLevel + 1));

        for (
          let shift = Math.max(0, w.length - prefix.length);
          shift < w.length;
          ++shift
        ) {
          const piece = w.substr(0, w.length - shift);
          if (prefix.endsWith(piece)) {
            check(fn(prefix + w.substr(w.length - shift), debugLevel + 1));
          }
        }
      }

      words.add(w);

      if (debugLevel === 0 && min.length < totalMinSize) {
        totalMinSize = min.length;
      }
    }

    return min;
  };

  return fn("", 0);
}

Это JS? Я вообще не представляю, как вы на нем программируете, там совершенно безобидные вещи замедляют его в десятки раз. Но у вас проблема не в этом.


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


Например, если есть слова "caaaaaaaa" и "aaaaaaab" — тогда вы запустите весь перебор с оставшимеся словами при "caaaaaaaaaaaaaab", "caaaaaaaaaaaaab", "caaaaaaaaaaaab"… А если еще есть варианты "daaaaaaaaa", "aaaaaaaaad", то все варианты выше домнажаются на все варианты потом. Т.е. у вас не n*n! операций при переборе а n*n!*L^n.


Единственная оптимизация, которую вы по сути должны сделать, это внитри функции check для каждого слова запускать ровно одну check дальше. Зачем вам перебирать варианты с разным shift? нужен только один максимальный же. Раз слова в друг друга не вкладываются, следующее слово вы глубже текущего всеравно не пересечете. Значит если вы можете текущее слово поглубже запихать, нет никакого смысла этого не делать.

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

Ага. Всё так. Это следующая оптимизация. Не считать одно и тоже для одних и тех же сочетаний.


Раз слова в друг друга не вкладываются, следующее слово вы глубже текущего всеравно не пересечете.

Вот это очень неочевидная штука (для меня). Мой мозг пытается придумать такой вариант когда для слов А и Б есть такое слово С, когда длина C > длины Б, и при этом только правильная расстановка слова Б внутри слова А, даст совпадение с префиксом слова А.


Аааа. Понял. Вы правы. Получается что если Б поместилось целиком в С, то это нарушает правило задачи о невкладываемости слов. Выходит что C обязательно входит в Б не глубже, чем длина Б. А значит слово А перестаёт играть хоть какое-нибудь значение и чем короче к итерации для слова С получилась строка, тем лучше.


Теперь я всё понял. Спасибо за ликбез. Какая-то совсем не тривиальная задача, если честно. Мне кажется нельзя такое давать на интервью :)

Единственная оптимизация, которую вы по сути должны сделать, это внитри функции check для каждого слова запускать ровно одну check дальше

Оказалось, что нет :) Точно не единственная. Прекалькуляция и отказ перебора вариантов разного сдвига в пользу одного или нуля заранее просчитанного позволило продвинуться с 59 теста на 73 из 83. Потом снова Time Limit Exceeded. Думал что прекалк медленно написал, но оказалось что для всех тестов вышло < 1ms. Дело именно где-то в рекурсии.


Грешил на JS и даже попробовал переписать всё на C++ (как умею, т.е. ооочень плохо), но получил примерно ту же производительность. 10 секунд на тяжёлый тест. Попробую добить задачу на выходных.


Заодно вспомнил почему я ненавижу C++ :)

Ладно, я был не прав. Задача не тривиальная. Средненькая. Все-таки есть простор для ошибок.


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


Это как, если бы вам надо было найти 2 элемента в массиве с минимальной суммой, но вы бы перебирали все пары элементов, вместо выбора двух минимальных элементов за один проход ну или хотя бы сортировки.

Разве же не очевидно, что не надо каждый раз пробовать все сдвиги?

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


Вроде как принято такие вещи решать постепенно усложняя, и тут у меня получается как-то так:


  • Пишем решение в лоб: получаем проблему, программа работает быстро, но все решения с пересечением слов не работаю. Понимаем в чём соль задачи.
  • Пишем более сложное решение в лоб: всё работает, но падают тесты с time limit
  • Начинаем одну за одной применять оптимизации. В моём случае это попытка избежать вычисления уже заведомо проигрышных вариантов
  • Затем меня понесло в микрооптимизации и я улучшил .endsWith, но выиграл всего пару тестов
  • Затем в поисках "мы явно что-то делаешь лишнее, где-то считаем одно и тоже много раз" приходим к тому что пересечения слов не зависят от рекурсии и их можно сосчитать превентивно
  • Затем берёмся за самое сложное — анализируем возможные corner case в поисках избегания заведомо проигрышных вариантов и приходим к той самой логике про невозможности поместить 3-е слово левее 1-го. Получаем самый главный boost

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

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

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

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


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


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


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


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

спасибо!

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

НЛО прилетело и опубликовало эту надпись здесь
и к 0xd34df00d
Берем первое слово целиком, а потом жадно как можно глубже всовываем следующее слово в предыдущее, так что суффикс левого слова совпадает с префиксом правого слова. Вот в вашем примере можно «oto» впихнуть на 1 символ в «foo» («foOto» — общие символы большие), «oof» на 1 символ в «oto» («otOof»), а «oof» на 2 символа в «foo» (fOOf"). Поэтому для этой перестановки мы сначала получаем «foo», потом «footo», потом «footoof».

Только получилось добраться до этой задачи. Вот пример
[ "flolo", "ololf", "ololo"]
"flololf" не сработает, должен получиться "flolololf", поэтому нельзя просто жадно запихать одно слово запихать в другое. Для генерации нужно запихнуть сначала немного и с этой парой идти перебирать всё остальные в массиве, потом попробовать сильнее и т.п. Может быть там ещё какие-то граничные случаи.
Ну хз, я такое на собеседовании легко могу не пройти, особенно вероятно не уложиться во время.

В общем, не получилось у вас пройти в Гугл или куда там) Многое зависит от собеседующего, по-видимому. Вот такое спросят, мне лично не хватило знаний об алгоритме в reservoir sampling, или смекалки на месте его вывести (если вообще).

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

Вроде всё можно, судите сами: fl[ol{olo]lf}, где [] это 3-е слово, а {} это 2-е слово.


  • 1-е слово: flolo, никуда не просунуто
  • 2-е слово: ololf, максимально вдвинуто в ololo
  • 3-е слово: ololo, максимально вдвинуто в flolo (дальше fl)

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

Нет, мы не впихиваем слова глубже последнего

А я этого и не делаю. Всё как у вас в комментарии ниже flolo << [olo]lo << {olo}lf. Может быть слишком путанно описал. Я хотел продемонстрировать что ololo и само оказывается внутри flolo, и также является гнездом для ololf. Правда всё равно time limit :)

Вы пропустили в моем коментарии


Далее, вот перебрали мы перестановку слов.

Поэтому, когда слова перемешаются как ["flolo", "ololo", "ololf"], жадное выпихивание как-раз выдаст "flolololf".

Вот такое спросят, мне лично не хватило знаний об алгоритме в reservoir sampling, или смекалки на месте его вывести (если вообще).

Ну тут надо просто иметь понятие о вероятности и все. Ставим мину в первую ячейку с вероятностью k/(n*m) — так в условии сказано. Далее, если мы поставили мину — то остается точно такая же задача, только надо равновероятно k-1 мину поместить в n*m-1 клеток. Или, если не поставили, то надо поместить k мин.


Вот и получается, что ставим мину в i-ую клетку с вероятностью (k-j)/(n*m-i), когда до этого поставили j мин.


Я бы на такой задаче выдал подсказки: "С какой вероятностью первая клетка содержит мину?", "Сколько всего различных комбинаций расположения мин существует?", "с какой вероятностью каждая такая комбинация может выпасть?", "Сколько комбинаций, где на первом месте стоит мина, и сколько — где не стоит?".


Если после всего этого кандидат придумал решение и не накосячил в коде — я бы выдал "Hire".


Или, можно применить альтерантивное широко известное решение другой задачи — перемешивание массива. Равномерно перемешайте n*m чисел и в первые k поставьте мины. Тут вас интервьювер спросит, а надо ли вам хранить все n*m чисел, и нужно будет догадаться, что — нет — достаточно хранить k первых чисел перемешиваемого массива.

Ну тут надо просто иметь понятие о вероятности и все. Ставим мину в первую ячейку с вероятностью k/(nm) — так в условии сказано. Далее, если мы поставили мину — то остается точно такая же задача, только надо равновероятно k-1 мину поместить в nm-1 клеток. Или, если не поставили, то надо поместить k мин.

А чем не подходит решение:


let mines = HashSet::new();
while mines.len() < k {
   mines.push((rand(0, n), rand(0, m)));
}

Единственное что тут может смущать это 2 рандома, можно обойтись одним rand(0,m*n) и потом разбивать на координаты по (i/m, i%m)

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


Проблема тут, что это решение медленнее. У вас там O(k log k) операций в худшем случае k=nm. Это в среднем — и сколько угодно много, если не повезет. Как долго вы будете генерировать случайные числа, пока не попадете в последнюю пустую клетку? Если генератор случайных чисел не досаточно хорош — то ваше решение может и повиснуть навсегда.


Объяснение

Первую мину вы поставите всегда с первой попытки. Для второй потребуется в среднем 1+1/nm+1/(nm)^2+… = nm/(nm-1) попыток, для следующей — nm/(nm-2) и так далее. Можно вынести nm за скобки и развернуть сумму. Останется nm*(1/1+1/2+1/3+...+1/nm).


Получается в итоге nm*(H_{nm}) операций. H_nm (гармонический ряд) растет примерно как логарифм.


Идеальное решение за O(k) и там все операции простые. А у вас там еще и хешмап, который, хоть и за O(1) работает, но сильно медленнее одного единственного if-а.


Важное улучшение, к которому я бы вас подталкивал, когда вы сможете оценить время работы — это генерировать мины или пустые места (смотря чего меньше). Тут ассимптотика тоже будет O(k). И вы должны будете это тоже доказать. Хотя все-равно остается проблема повисания при неудачном стечении обстоятельств.


На hire вы должны сделать улучшенное решение и должно остаться немного времени получить от вас хотя бы идею O(k log k) решения, которое всегда работало бы за такое время. Тут вам придется вместо while(не попали в пустую клетку) как-то быстро выбирать одну из оставшихся пустых клеток.

Я предполагал, что k << m*n, поэтому ситуацией с дубликатами можно пренебречь.


Важное улучшение, к которому я бы вас подталкивал, когда вы сможете оценить время работы — это генерировать мины или пустые места (смотря чего меньше). Тут ассимптотика тоже будет O(k). И вы должны будете это тоже доказать. Хотя все-равно остается проблема повисания при неудачном стечении обстоятельств.

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


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

Я предполагал, что k << m*n, поэтому ситуацией с дубликатами можно пренебречь.

Но этого нигде не сказано.


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

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


Почему оно не равномерно — вот вам пример: пусть поставленные мины в строке обозначены 1
"0111100". Вот ту вероятность взять первый ноль 1/7, второй — 5/7, третий — 1/7. В итоге в сгенерированной расстановке будет гораздо больше подряд идущих мин, чем в случайном распределении.

Видимо, правую границу рандома нужно уменьшать на единицу после каждой генерации, и искать n-ое место для вставки, тогда в этом случае будем генерировать (0, 2) и вставим вместо одного из этих нулей. Не очень эффективно, конечно.


Куда лучше смотрится вариант зашафлить массив и взять первые k. Только как зашафлить массив не храня его целиком мне не очень понятно.

Куда лучше смотрится вариант зашафлить массив и взять первые k. Только как зашафлить массив не храня его целиком мне не очень понятно.

У меня там в комментарии это решение упомянуто.


Стандартный метод шафла:


for (i = 0; i < n; ++i) {
  a[i] = i;
  j = rand() % (i+1);
  swap(a[i], a[j]);
}

Можно заметить, что каждый элемент после постановки может передвигаться только куда-то правее, когда на его место встает новый элемент. Значит, если элемент выходит за первые k — его можно выкинуть из рассмотрения вообще. Ну и дальше просто хранить первые k: Перемешиваем первые k, а потом делаем как раньше для оставшихся элементов, но вместо помены просто ставим новый элемент на место старого, если он "хочет" в первые k. Потом еще можно заметить, что перестановка первых k значения не имеет.


for (i = 0; i < k; ++i)
  a[i] = i;
for (i = k; i < n; ++i) {
  j = rand() % (i+1);
  if (j < k)
    a[j] = i;
}

Видимо я потупел после ковида, но я бы не написал правильное решение за 45 минут.

Ну блин, неужели вот это нельзя написать за 30 минут? Ну, да тут кода многовато, нет времени 20 минут думать над задачей, за оставшиеся 10 не все успеют. Но мне понадобилось 7 минут написать, плюс еще 5 исправить опечатки:


int CalcIntersectionLength(const std::string& w1, const std::string& w2) {
  size_t n = std::min(w1.length(), w2.length());
  for (int i = n; i > 0; --i) {
    if (w1.substr(w1.length()-i, i) == w2.substr(0, i)) return i;
  }
  return 0;
}

std::string GetShortestCoverString(std::vector<std::string> words) {
  std::vector<std::string> unique_words;
  for (size_t i = 0; i < words.size(); ++i) {
    bool is_contained = false;
    for (size_t j = 0; j < words.size(); ++j) {
      if (i != j && words[j].find(words[i]) != std::string::npos) {
        is_contained = true;
        break;
      }
    }
    if (!is_contained) {
        unique_words.push_back(words[i]);
    }
  }

  std::vector<std::vector<int>> intersections(unique_words.size());
  for (size_t i = 0; i < unique_words.size(); ++i) {
    for (const auto& other: unique_words) {
      intersections[i].push_back(CalcIntersectionLength(unique_words[i], other));
    }
  }

  std::vector<int> perm(unique_words.size());
  std::iota(perm.begin(), perm.end(), 0);
  int best = 0;
  std::vector<int> best_perm;

  do {
    int cur = unique_words[perm[0]].length();
    for (size_t i = 1; i < unique_words.size(); ++i) {
      cur += unique_words[perm[i]].length() - intersections[perm[i-1]][perm[i]];
    }
    if (best == 0 || best > cur) {
      best = cur;
      best_perm = perm;
    }
  } while (std::next_permutation(perm.begin(), perm.end()));
  std::string ans = unique_words[best_perm[0]];
  for (size_t i = 1; i < unique_words.size(); ++i) {
    ans += unique_words[best_perm[i]].substr(intersections[best_perm[i-1]][best_perm[i]]);
  }
  return ans;
}

"You may assume that no string in words is a substring of another string in words". Что конечно же не делает задачу сложнее. В отличие от того, что про std::next_permutation знают далеко не все, т.к. за пределами олимпиадных задач она мало где встречается. Да и в них не постоянно.

Ну отлично, первые 14 строк можно выкинуть.


Без next_permutation задача решается так же просто через рекурсию:


void BruteForce(vector<bool> &taken, const vector<vector<int> &intersections, vector<int> &perm, vector<int> &best_perm, int &best, const vector<string> &unique_words) {
  if (perm.size() == taken.size()) {
    int cur = words[perm[0]].length();
    for (size_t i = 1; i < unique_words.size(); ++i) {
      cur += unique_words[perm[i]].length() - intersections[perm[i-1]][perm[i]];
    }
    if (best == 0 || best > cur) {
      best = cur;
      best_perm = perm;
    }
  }
  for (size_t i = 0; i < taken.size(); ++i) {
    if (!taken[i]) {
      taken[i] = true;
      perm.push_back(i);
      BruteForce(taken, intersections, perm, best_perm, best, unique_words);
      perm.pop_back();
      taken[i] = false;
    }
  }
}

Если не лениться и написать класс, то будет меньше всяких параметров. Но люди на интервью не хотят обычно писать классы, обходятся функциями. И это нормально. Я понимаю, что у нас не весь день, а лишь 45 минут. Я этот вопрос на интервью бы поднял, но переписывать не заставлял бы и минусов за это не ставил в coding.

Да забудьте вы про это "быстрее 100% других решений", у литкода кривая замерялка. Там цифры скачут в весьма широком диапазоне, может повезти что вы с решением за O(N^3) окажетесь в ТОПе, а бывает что решение за линейное время отбрасывает в конец. И если бы вы прорешали не одну задачу, а сотню - вы бы увидели насколько литкод в этом плане глючен.

Апеллируйте к асимптотической сложности. Нашли решение за константное время и константную память - молодец, вот тут уже действительно выше головы не прыгнешь (задача на поиск центра star графа), нашли за квадратичное и нет идей как снизить - не молодец.

Homebrew невероятно медленный и странный пакетный менеджер (сравнивая с теми же apt, pacman и тд), так что правильно что гугл его завернул. Знай бы он как инвертировать бинарное дерево, возможно и написал бы что-то нормальное, а не это поделие.

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

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

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

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


Не скажу за конторы, но действительно бывают редкие случаи, когда случается пожар и нужно очень быстро разобраться в чем дело и решить проблему. Тут пригождаются навыки скоростной отладки и кодинга. Иногда бывает что и в терминале надо что-то делать, где из удобств только голый vi/vim (почти что пресловутая «бумажка»).


Конечно, никакие деревья вертеть при этом не надо обычно :)

Вот это похоже на правду и действительно не нужно решать всякую синтетику по переупорядочиванмю массивов

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

И кстати таким линейные программисты обычно не занимаются

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

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

да, согласна, я просто не так часто пишу статьи, поэтому тут есть над чем поработать

Та вроде нормально читается. А как уже без англицизмов в 2021? Я и в жизни часто использую и ничего. Понятно что это статья всё же и т.д, но мы и не на форуме матерей

Одно дело - терминология, а другое - разбавление обычной речи зачем-то вставленными английскими словами. Дискуссия вокруг англицизмов больше о том, что, хотя многие слова органично вошли в язык, можно было бы и обойтись без них, ведь есть местные аналоги. А здесь даже не англицизмы, а просто куски английского текста, как будто текст недоперевёлся гугл.переводчиком. В общем, i want сказать, что текст could смотреться более organic, if бы он was written на каком-то одном языке, а не на russian-английском surzhik.

Было бы намного куда более плежурнее ридать текст на нативном лэнгвиче, чем на миксед. Если вы спикаете и финкаете на инглише, то и врайтайте на нём же.

Пожалуйста, консидеринг это

как не потерять мотивацию за полгода подготовки в FAANG

Так как же? Инвестиция выглядит довольно рискованной. Хуже бизнеса какого-нибудь - там хоть результат по мере продвижения виден, а тут бинарная подготовка к найму в определённые компании (и почти ничего более - просто прохождение отбора), результат которой будет известен в конце. В любой момент хочется подумать "всё зря и бесполезно, лучше поделать что-то интересное/полезное".

Нужен, наверно, определённый склад характера.

Присоединяюсь к вопросу. Как при основной работе сохранить мотивацию тратить 4 часа каждый день в течение полугода на подготовку к собеседованиям?

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

Переезд

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

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

Понимание этих двух простых вещей поможет сохранить мотивацию.

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

Компании FAANG в этом плане являются вершиной, вы сможете найти много достойных компаний, в которых с таким уровнем подготовки вы будете проходить собеседование намного проще
Звучит логично, но я вот не соглашусь.
Только что с собеседования в Amazon на L5/SDEII (как и авторша, полагаю), и, как мне показалось, если подтянуть кое-какие прозрачно тренируемые софт-скиллы, то оффер был бы гарантирован, задания довольно простые. Полгода назад технически самое сложное собеседование было в какую-то подкомпанию Oracle (помогло примерное знание устройства баз данных), они дали оффер. Далее попробую в Facebook, и, возможно, даже Google, если они не выкинут моё резюме сразу в помойку — мне нравятся вызовы.
При этом мне за долгое время не дала оффер ни одна (без преувеличения) другая мелкая малоинтересная компания, в которые не особо даже и хотелось идти (соглашаюсь на собеседования в линкедине, абы посмотреть, если предложат условия лучше нынешних). Хотя интервью прошло, как мне казалось, хорошо или идеально. Большинство после интервью отмалчиваются или прямо говорят, что не дадут мне фидбэк. (хотя 90% ещё до интервью пишут «вы нам не подходите» — после того, как сами и предлагают у них пособеседоваться)
В этом плане намного проще пройти в этот FAANG и иже с ним, ибо у них довольно скриптовые собеседования и прописанные ожидания — знаешь, что ожидать и к чему готовиться. Они сами об этом сообщают. Во многие другие компании найм — это полный чёрный ящик и кого конкретно они ищут, кем мне нужно быть я чаще всего не понимаю.

Вы крутая. Очень приятно подобное читать :)

---

Аж восприятие немного перевернулось. Столько всего пройти ... Ради FAANG ... Боюсь, это никогда не будет моим уровнем. Я искренне не понимаю, как можно год решать задачи, которые не будешь использовать. А всё что не используется, то атрофируется и забывается. Я столько всего прочитал по программированию впустую. Потому что эти знания не используются и следовательно не нужны и забываются настолько, что дойти до собеседования попросту невозможно. И это ради FAANG, корпораций, для которых люди расходный материал.

Сильно. Искренне надеюсь что у Вас всё будет хорошо. Не выгарайте ;)

Спасибо)

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

У компании А последние два года есть опросник после кодинг-интервью, где попадался вопрос "насколько вам стало понятней по задачам на интервью, чем вы будете заниматься, если вас таки возьмут?" ИМХО, в положительном ключе на этот вопрос рука не поднимется ответить.

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

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

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

Поервьюить пулл-реквест - задача с очень субъективной оценкой. Решить задачку на алгоритмы - намного менее субъективно.

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

Поервьюить пулл-реквест — задача с очень субъективной оценкой.

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

Поервьюить пулл-реквест - задача с очень субъективной оценкой. Решить задачку на алгоритмы - намного менее субъективно.

по мне так "нашел 4/5 UB и 3/3 нарушений common practice" объективнее, чем "развернул дерево за 15:30 а должен был уложиться в 15:00". И сигнал лучше

НЛО прилетело и опубликовало эту надпись здесь

Вообще это могли бы быть "3/3 упущенных микрооптимизации", что-то типа "давайте тут заменим сет на битсет а тут добавим забытый move", если говорить в категориях плюсов. Мой аргумент скорее был в том, что у средней алгоритмической задачи объективный сигнал "справился/не справился" и дальше у ревьюера куча гайдлайнов как увеличить разрешение этой оценки. А в задаче "найди 10 объективных изъянов" успех кандидата уже можно объективно оценить по шкале от 0 до 10, с минимальной корректировкой от ревьюера.

Да и сами common practice могут быть довольно-таки общепринятыми. Например в плюсах принято передавать владение через unique_ptr вместо сырого указателя, ровно как и использовать ссылки там, где указатель никогда не nullptr.

НЛО прилетело и опубликовало эту надпись здесь

Здравствуйте, я к вам из HFT и у меня уник_птры тормозят.

решаемо в принципе, хотя вряд ли у вас там clang. Плюс, проходя собес в контору обычно есть примерное представление HFT там или нет.

А потом приходит к вам чувак, читавший Саттера, и с порога заявляет:

"When passing/returning an object by reference, this isn’t a problem because we know we’re always passing by pointer under the covers and when we use the name we’re always referring to the existing object by alias. That’s clear, and references are well designed for use as function parameter/return types.". Контекст которых я и подразумевал.

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

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

Мозг - это рабочий инструмент разработчика/архитектора. Подобные тренировки ему только на пользу

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

На дистанции второе будет полезнее и сотруднику, и работодателю...

Почему? Умение находить оптимальное решение задачи, умение оценивать сложность алгоритмов, умение системного дизайна, софт скиллс, навыки в работе в команде, знание, как лучше поступить в той или иной ситуации не менее важны. Именно это и хотят увидеть в фаангах на интервью (алгоритмы + сисдиз + бихихейв). И эти навыки понадобятся любому разработчику. Алгособес это, сюрприз, не про заучивание алгоритмов, а про способность решать поставленную задачу приемлемым способом. К тому же, замените "вместо" на "вместе" и читайте дядю Боба тоже. Будет полезно, не спорю.

а про способность решать поставленную задачу приемлемым способом

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

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

Это глубокий оффтопик, конечно, но не могу не ответить, так как познал на собственном печальном опыте истину "в здоровом теле - здоровый дух". Мозг функционирует неотрывно от остального тела, а тело у людей так устроено, что ему просто необходимы как минимум умеренные физические нагрузки на постоянной основе. Если не практиковать собственную физиологию за пределами уровня "ходить по необходимости", гарантированно получите целый спектр проблем в том числе и со снижением качества мышления (к сожалению, сейчас из головы не могу накидать ссылок, так что просто anecdotal evidence).

НЛО прилетело и опубликовало эту надпись здесь

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

о, как человек который как раз себе целью до конца лета поставил смочь подтянуться двадцать раз, не могу пройти мимо и не сказать, что многим такое спортивное достигаторство просто в кайф (и процесс и результаты). Наверное, так же обстоят дела для людей которые могут 300 задач на литкоде решить после работы и получить веер оферов из FAANG. Мне вот было бы слишком ленно, но вопрос мотивации конечно.

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


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

По поводу задачек на собеседовании в Гугле: вроде как просят задачи в общий доступ не выкладывать же :). Тем, кто Вас собеседовал, придется теперь новые задачки придумывать. А так вроде всё правильно написали :).

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

мне такого по поводу задачек не говорили) Гугл сам даже ссылается на leetcode и Cracking The Coding Interview для подготовки

Что, правда в переписке не ищется что-то типа

As a friendly reminder, our interview questions are confidential, so please keep things under wraps

в футере сообщения?

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

p.s. "Почему Python? Java - очень много букв, C++ - очень хардкорно" остальная аналитика на том же уровне?

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

Вот так корячишься полгода, тебя берут в фаанг и сажают латать дыры в какои-нибудь древнючем легаси :) облом-с

"Нас ... , а мы крепчаем."

Судя по тексту, у автора явные склонности к мазохизму. Насколько это связано с полом автора -- оставим на домашнее задание.

Это отвратительно читать. Мне монитор твоей завистью, сексизмом и ущемлённым самолюбием заляпало.

Ну конечно, всё, что делают (с вами) в FAANG -- хорошо по определению. Расслабьтесь и получайте удовольствие.

Автор написала статью о том, как попасть в FAANG.

Люди обычно хотят попасть туда, чтобы:

  • Оказаться в компании с мировым именем

  • Заработать денег (на FIRE, например)

  • Получить GC (мб day 1 application)

  • Работать в сильных, мотивированных командах (в большинстве случаев)

  • Получить строчку в резюме, которая поможет "зачетке работать на тебя"

Что из вышеперечисленного Вам непосредственно так неприятно, что процесс подготовки к такой вакансии Вы назвали "мазохизм"? Это обычные правила игры, когда на одну вакансию порядка 300+ кандидатов ради уже указанных причин, и таким образом компании отсеивают большинство людей, которые "просто заучили ответы на вопросы интервью". Большей части FAANG нужны инженеры с хорошим знанием Computer Science, чтобы быстро вникнуть в любой язык или фреймворк, и не заморачиваться с тем, что "я пишу на Java\C#\C++\JS\Python\<whatever> и остальное не предлагать".

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

Касательно непосредственно опыта:

У меня есть пример человека, который после переезда в США через 2 месяца нашел работу в ZipRecruiter на 190к тотал (135s+15b+40e), он решил ~100 задач на leetcode и почитал примериы интервью. Также получил оффер из Rakuten на 170к тотал. Это не FAANG пока, но LinkedIn, Amazon, Facebook отклонили его кандидатуру непосредственно из-за его типа EAD - CPT, однако результаты собеседования сохраняются в течение года, если он получит OPT EAD или GC - они примут его. Он не готовился так яростно ни к чему, что перечислено в статье, может быть просто повезло, но факт есть факт.

Есть пример человека (лично не знаю), кто решил 1000 задач на литкоде и не попал никуда, и всё еще пытается.

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

Сам я считаю себя отвратительным программистом, и работаю пока в Калифорнии во вполне обычной компании за 100к в год (без бонусов, акций, и прочих надбавок), что считается крайне мало для хоть сколько-нибудь серьезного инженера, к тому же мне уже 35. И тем не менее у меня есть намерение попасть в FAANG, потому, что "а смогу ли?" и деньги. Персональный челлендж.

В итоге, остается вопрос к Вашему изначальному сообщению - Кого е*ут-то, кто крепчает, и причем тут пол автора?

НЛО прилетело и опубликовало эту надпись здесь

USCIS может счесть это "продажей GC" и потребовать доказательств о реальности работодателя и прочей бумажной волокиты.

Технически "нарушений условий" здесь нет, работодатель не может заставить Вас оставаться на работе, т.к. не смотря на спонсорство, это всё еще employment at will, а вопросами Вашего резидентства с этого момента будет заниматься USCIS.

Есть общая рекомендация проработать полгода после одобрения I-485, чтобы не привлечь лишнего внимания.

Таким образом, можно ли так делать - да. Стоит ли так делать - скорее нет, лучше немного подождать, думаю, человек продержится еще полгода, получая ~$10к в месяц.

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

НЛО прилетело и опубликовало эту надпись здесь

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

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

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

Много коментов из разряда: "Такой пути ради FAANG проходить не стоит". Я тоже был такого мнения, но поработав в русском фанге, скажу что не в фаанг уже не хочется.

Огромное спасибо за статью, удачи вам!

Это в каком же «русском ФААНГе»? В какой из компаний? Вариантов всего полтора, и оба они – далеко не «работодатель мечты».

Спасибо, вопрос в комментарии был не об этом очевидном.

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

Очень смешно.
Я, работая в одной из этих букв, и очень хорошо зная о работе в двух других буквах — легко могу сказать, что контор, которые вот просто лучше этих по подавляющему большинству параметров (исключая "огромадность") — десятки тысяч. И причем даже не все из них иностранные. Да что там, условные галеры условного EPAM и то будут выглядеть неплохо в сравнении по целому ряду причин.

поработав в русском фанге, скажу что не в фаанг уже не хочется

Расскажите, почему?

НЛО прилетело и опубликовало эту надпись здесь

В США от штата зависит, везде по разному.

НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь

Дай угадаю, WG?

НЛО прилетело и опубликовало эту надпись здесь

В US и non-compete совершенно драконовский во многих штатах. В Европе хотя бы garden leave полагается, а в штатах на мороз без зарплаты и перспектив трудоустройства к конкуренту.

НЛО прилетело и опубликовало эту надпись здесь

Почитал, шаги вполне логичные, но у меня два вопроса в разных направлениях

  1. Насколько оно того стоило? По деньгам и всему остальному. Прямо вот любопытно.

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

По деньгам достаточно достоверно можно тут посмотреть https://www.levels.fyi/

Это был опыт, я познакомилась со многими хорошими специалистами и моя вторая команда была one love, но я уже просто устала от ненормального work-life balance в компании, не особо интересных задач, зарплаты ниже рынка и своих непонятных карьерных перспектив.

Порадовало, im sorry)

примерно 4 часа в день до/после работы

Вот ещё интересно, как вы организовались поддерживать такой режим в течение нескольких месяцев и не влияло ли это на работу? 8 часов работа, 8 часов сон, остаётся 8 часов, из которых несколько часов нужно на самообслуживание (время перед засыпанием, еда, гигиена, физкультура, да и просто передышки для мозга). У меня пока получилось лишь гарантированные 2 часа в день выделять на учёбу в день. Остаётся 2 часа личного времени, открыть хабр, почитать статейки, полить растения, вот эта вся мелочь. Остальные 4 часа - транзакционные издержки жизнедеятельности, так сказать.

При этом предыдущая цель в 3 часа в день позорно провалилась, мой мозг не выдержал нагрузки и несколько месяцев после такого прокрастинировал. Что, к тому же, процентов на 20 подорвало эффективность и на оплачиваемой работе, в которой я стараюсь честно выкладываться. В общем, перехотелось после этого в FAANG. Кстати, хочется в свободное обучаться ещё и чему-то полезному или интересному, а не только надрачивать на найм, это тоже влияет на срыв планов.

В общем, какие вы тут задачи прорешивали для подготовки - это на самом деле второстепенное знание, интернет таким полнится. Уникальное знание, чему хотелось бы у вас научиться - как вам удалось долго продуктивно интеллектуально работать

примерно 4 часа в день до/после работы ... Полностью вся суббота и часть воскресенья уходили на подготовку

Вот это получится у очень редких людей и требует колоссальных мобилизационных способностей.

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

А можно уточнить вопрос, про локацию (куда именно искали релокейт) и что было с визой?

Вы - большая молодец.

Имхо, даже если работа в FAANG на практике окажется далека от работы мечты, строчка в резюме о работе в подобной компании откроет многие двери.

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

  Конечно и без этих, и конечно не гарантируют. Но это не отменяет того факта, что строчка о работе в одной из подобных компаний выглядит более привлекательно чем равные годы работы в ООО "Рога и копыта".

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

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

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

Ну $200k много кто сейчас может предложить (Oracle, IBM, Intel и пр), без такой потогонки и "унижения", другое дело, что FAANG может предложить за $300k и даже больше.

Что унизительного в том, что программиста просят программировать на интервью?

Программировать - нет. Знать 100500 алгоритмов - зашквар

Ну вот тут 0xd34df00d разобрал задачу из статьи. Там какие-то особые алгоритмы нужны?

Эта задача уровня easy, там спрашивают не такие задачи.

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

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

Знать 100500 алгоритмов - зашквар

Ни фига ж себе, до чего дошло общественное мнение...

Унизительного ни чего нет по большому счету (поэтому и взял в кавычки), просто если планка стоит в $200k то можно и не напрягаться пол года-год решая задачи на leetcode, topcoder, и пр, куря мануалы как пройти интервью и т.д, что бы найти интересную работу в большой корпорации.

В других фирмах вы легко найдете 150к (по крайней мере в США), при этом не будет бессонных ночей и зубрежки деревьев-графов.

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

Я просто забыла добавить ее к ссылкам - уже исправила) Да, у вас очень хорошая статья, послужила мне вдохновением)

Вопрос скорее риторический:
Стал бы Маск тратить время свой жизни на попытку устроиться на такую работу?
И кем бы он стал в итоге, если бы устроился?

Но, я с уважением отношусь к затраченным усилиям и полученному опыту.
Желаю удачи!..
Контрриторические вопросы:
Должен ли каждый человек ( или айтшинк ) повторить путь Маска?
Преследует ли каждый человек те же цели что Маск?
Кого будет нанимать на работу Маск если все будут Масками?
он собой бы и остался, принцип мышления людей не зависит от работы на которой они работают
устроился бы… ну и уволился потом если бы ему не понравилось

Это был опыт, я познакомилась со многими хорошими специалистами и моя вторая команда была one love, но я уже просто устала от ненормального work-life balance в компании, не особо интересных задач, зарплаты ниже рынка и своих непонятных карьерных перспектив. После Яндекса мотивации работать не было вообще.

С удовольствием бы почитал статью об этом опыте

P.S.

Кстати, а прокаченный профиль на GitHub как-нибудь влияет на собеседования в тех же FAANG? Есть у кого-нибудь такой опыт?

Так была же статья на хабре про яндекс, где все достаточно хорошо расписали
НЛО прилетело и опубликовало эту надпись здесь

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

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

Я говорю про рунет если что.

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

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

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

Хорошая статья, четко все расписано. Остается непонятным только, ради чего все это. Что такого в этом FAANG, что нужно полгода тратить все свободное время на подготовку к интервью ? При том, что можно устроиться в другие хорошие компании без всего этого геморроя и получать не сильно меньше денег.

ради релокейта например. не-faang тоже релоцирует, но обычно это дольше и на меньшие деньги

Только ради релокейта в США. Пока вы будете полгода учить алгоритмы, я уже полгода буду работать в условной Голландии или Ирландии

вы умеете мгновенно релоцироваться без whiteboard-инга? в какие компании, если не секрет? хотелось бы конечно, чтобы это был практический опыт, а не теория

НЛО прилетело и опубликовало эту надпись здесь

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

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

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

Все еще не понимаю, как это опровергает мой тезис про дольше и/или меньшую зп.

Практически любая небольшая компания

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

Причем я мог спокойно поменять работу на другую.

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

А в FAANG-е, видимо, приковывают к рабочему месту и запрещают разговаривать не по работе.

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

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

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

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

Гоняют по алгоритмам и структурам данных по той причине, что в таких компаниях инженеры сталкиваются с проблемами, которые не решаются через stackoverflow.com. Это понимание приходит в тот момент, когда видишь, что за последний год многократно приходилось использовать эти знания. В отличие от 15 предыдущих.

А вот системный дизайн очень субъективный. За 30-40 минут нужно не только нарисовать квадратики в ужасном редакторе, но и формализовать максимально нечёткие требования, придумать какую-то бизнес или UI/ux концепцию, а потом ещё и углубиться в ненужные детали. И по пути все время думать, кто же этот человек, который сразу хочет дизайн на млрд запросов. А ещё понимать абсурдность ситуации, что все происходящее практически никак не ложится на архитектурные стандарты.

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

огромные у меня сомнения что даже 80% разработчиков сталкиваются с проблемами которые не решаются на SO и вообще простой програмистской логикой

в таких компаниях

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

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


огромные у меня сомнения что даже 80%

Да даже если их 10%. По изложенной выше проблеме, невозможно нанимать "кодеров" и "алгоритмистов" отдельно. Потому что "кодер" даже не задумается об обращении к "алгоритмисту" и тем придется просматривать вообще весь код и постоянно что-то переписывать. Имея бюджет и количество кандидатов как в FAANG легче просто нанимать только "алгоритмистов".

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

Если вы вчерашний не самый прилежный студент без опыта реальной работы, может мысли и не возникнет. Если у вас есть хоть какой-то опыт в программировании вещей сложнее "табуретки", все нужные мысли возникают сами собой. Включается такая полезная штука как способность обобщать и абстрактно мыслить. Очень быстро становится ясно, что наивным способом в лоб задача не решается. А что происходит потом? Потом происходит R&D и в большинстве случаев находится подходящая библиотека, книга, статья или код/псевдокод подходящего алгоритма. И оказывается, что для решения задачи совсем не обязательно зубрить сотни классических и прикладных алгоритмов впрок, вращать и балансировать все возможные виды деревьев, компилировать и транслировать код в уме, писать парсеры на бумажке и т. п. вещи, которые так любят интервьюеры на собеседованиях.


Умные и хорошие книжки про алгоритмы и фундаментальную computer science читать, конечно, полезно и правильно. Оно даёт общее понимание, базовые знания, расширяет кругозор и вообще. Но учить ответы на каверзные вопросы на собеседованиях и делать overfitting своего мозга на определённый класс задач — это, как говорится, за деревьями леса можно не увидеть.


Да, я считаю, что "культура собеседований", образовавшаяся вокруг FAANG-компаний — это временное явление — тупиковая ветвь, ошибочный путь. Но время нас, конечно, рассудит и покажет, кто был прав, а кто заблуждался. :)

Очень быстро становится ясно, что наивным способом в лоб задача не решается.

Всмысле? Все решается. Просто там будет O(n^2) вместо O(n log n). Или O(2^n) вместо O(n^3).

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


Такие вещи мало-мальски опытный разработчик видит и понимает. Для этого не надо хранить в собственной памяти информацию о решении сотен алгоритмических задач с какого-нибудь leetcode и уметь решать похожие за 15 минут в условиях повышенного стресса. Достаточно возможностей собственного мозга, релевантного опыта и иногда инженерного образования. Когда появится необходимость включить голову и решить задачу, он её решит. Ну или не решит, что тоже возможно, но это мало коррелирует с умением решать оторванные от жизни задачи с leetcode и проходить алгоритмические собеседования у доски. Так же как и яркое олимпиадное прошлое и победы в ICPC не гарантируют, что человек способен работать над сложными программными продуктами, писать поддерживаемый код, документировать свою работу, выбирать правильные архитектурные и инженерные решения и т. д.

Если программа работает приемлемое/разумное время на том количестве данных

И часто у вас там программисты замеряют время работы каждого куска и знают точно, что вот в том списке не больше 10-ти элементов всегда? А что делать, если потом выяснится, что элементов может быть 100? Что такое разумное время работы: 10мс — разумное, a 100мс?


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


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

С этим не спорю. Вот только единственный способ хотябы примерно проверить все это — это тестовый период месяцев так на 6.


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

И часто у вас там программисты замеряют время работы каждого куска и знают точно, что вот в том списке не больше 10-ти элементов всегда?

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


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


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

Умение писать поддерживаемый код можно проверять по разному, алгоритмические задачи на время как на олимпиаде по программированию это умение как раз не проверяют. Если у человека есть open source проекты, можно посмотреть в их код и поспрашивать по ним, можно устроить сессию парного программирования и поработать с человеком в паре над кусочком какой-то реальной задачи. Это будет эффективнее и менее стрессово чем устраивать 5 этапов изнурительных многочасовых алгоритмических собеседований. Но это сложно для самих собеседующих, им нужно лучше готовиться, разбираться в чьём-то коде, придумывать задачи для парного программирования и т. д. Проще ехать по накатанной, выспрашивать и требовать у людей академических знаний, потому что это просто. Сам прорешал сотню другую задачек с leetcode или hackerrank и гоняй всех хоть до посинения. И при этом делать вид, что это реально проверяет профессионализм, умение мыслить и быстро решать рабочие задачи.

Умение писать поддерживаемый код можно проверять по разному, алгоритмические задачи на время как на олимпиаде по программированию это умение как раз не проверяют. Если у человека есть open source проекты, можно посмотреть в их код и поспрашивать по ним,

А если нет opensource проектов? Потом, если такие интервью будут в FAANG, то вместо leetcode "научим решать задачки" будет куча серивсов "соберем вам аккаунт на github и научим убедительно о нем разговаривать". И интервью в итоге будет проверять только умение балаболить, а не умение писать код.


можно устроить сессию парного программирования и поработать с человеком в паре над кусочком какой-то реальной задачи. Это будет эффективнее и менее стрессово чем устраивать 5 этапов изнурительных многочасовых алгоритмических собеседований.

Работать с человеком над кусочком реальной задачи? Ну вот я даю на инетрвью ту реальную задачу, которую сам коммитил в прод. Но это такая же "олимпиадная" задача, какие вы презираете.


Потом, как вы себе это парное программирование представляете? 5 разных интервьюверов все-равно будут, потому что надо исключить предвзятость и случайности. Что, вшестиром программировать? Будет ругань "я не могу программировать, когда на меня 10 глаз смотрят и высокомерно хмурятся". Как долго такая сессия парного программирования должна происходить? Как много и что должен интервьювер программировать? И главное, чем это принципиально отличается от текущего интервью, где происходит именно что парное программирование, только задачи чуть посложнее fizz-buzz?


Ну не получится проводить 5 двухчасовых сессий "парного программирования". Будут по всяким условным хабрам еще сильнее ругать условные гуглы за их зверские интервью. Это не скейлится. В итоге будут такие же 4-5 интервью по ~45 минут. Задачки будут сильно абстрактные, потому что ну не получится за это время сделать какую-то большую реальную часть чего-то. В реальную кодовую базу, как бы хороша она не была, надо въезжать длительное время.


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


Проще ехать по накатанной, выспрашивать и требовать у людей академических знаний, потому что это просто

Самое академическое знание, что вам нужно на интервью — это понятие ассимптотической сложности. Не требуют на интервью писать ни красно-черные деревья, ни алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна. Знать что есть такие структуры: хеш таблицы, деревья (set/map), куча и когда их можно применять. Ну, уметь писать рекурсию + вставлять туда запоминание (вот и все "динамическое программирование"). Ну, еще уметь формализировать задачу, разбивать ее на части и логически рассуждать надо — но разве это плохие качества для программиста?

То, что вы говорите — это вроде всё правильно. То есть вы говорите правильные слова, но на деле получаются перегибы. Ну вот взять хотя бы эту статью про собеседование в Яндекс. Зачем это всё? Что это проверяет, какие навыки и знания? Как это прогнозирует, что кандидат подходит? Яндекс устраивает такой цирк для любой вообще вакансии, Python, JS, C++, ML, DevOps, да без разницы, вот тебе несколько собесов с задачками на строки и массивы — решай. Нафига это всё?


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


Парное программирование тоже можно устраивать по-разному. Необязательно все 5 собеседующих должны одновременно что-то требовать от кандидата, каждый из них может предложить задачу/код, который можно интерактивно разобрать с кандидатом. В моей практике и я сам собеседовал и меня собеседовали, в том числе с online-программированием, разборами тестового, проектированием архитектуры, просто разговорами "за жизнь" и т.п. Есть опыт как токсичных, так и не токсичных собесов. Для себя я сделал вывод, что собеседования — это не экзамены, к ним не нужно специально готовиться пол года, твоих существующих проф. знаний и уровня либо достаточно, либо недостаточно. Если компания требует от меня overfitting на олимпиадные задачи для прохождения собеса, мне с ней скорее всего не по пути. Я не буду доказывать, что достоин чести работать в этой компании.

Ну вот взять хотя бы эту статью про собеседование в Яндекс.

Там вроде есть некоторые косяки с HR. Все задачи тривиальнейшие. Чуть-чуть выше уровня fizz-buzz. Даже автор новый мем фосит: "Ну ок, хотят проверить знание каких-то базовых вещей."


Конечно, многим хотелось бы побалаболить на какие-то высокие темы, но это, во-первых, очень субъективно и, во-вторых, проверяет больше как подвешан язык. Для всяких "накидать архитектуру высоконагруженного прило..." (пожелание из статьи) уже есть отдельное system design интервью.


Яндекс устраивает такой цирк для любой вообще вакансии, Python, JS, C++, ML, DevOps,

Разработчик на питоне принципиально не может столкнуться с задачами требующими хоть минимального понимания структур данных и алгоритмов — да? А js, если вдруг это не фронтенд, а какой-нибудь NodeJS? Там данных вообще нет? Это только на C++ все встречается что ли? Не согласен, что вы эти категории выделяете как недостойные интервью с простыми задачками на программирование. Почему ML и DevOps-ов в яндексе по алгоритмам гоняют — я не знаю. Может, потому что они не только скрипты для системы сборки или нейросетки пишут — раз чел будет хоть немного программировать, пусть проходит еще и те же интерью для программистов. Может потому что компании лень плодить 100500 видов интервью. Может, если кандидат про ML ничего связного не скажет, по результатам уже этих интервью можно будет взять на обычного разработчика.


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

Вы сами написали про "возмущают". Во-первых, это тоже не скейлится. Ну не будет кандидат решать 4 тестовых задания, каждое из которых занимает несколько часов. Во-вторых, там можно легко читерить. Задание за какого-нибудь китайца сдает его друг-программист и кратко объясняет, какие ключевые слова потом говорить. Вот и получается опять, что хорошо подвешанный язык становятся ключевыми навыками для прохождения интервью. Уже сейчас люди приходят не умея писать даже fizzbuzz — авось пронесет. Зарплата в гугле вкусная а изображать деятельность можно довольно долго. В-третьих, над этими тестовыми заданиями будут точно так же сокрушатся, что оно все слишком сложное, примеры все нереалестичные. Вот дали бы задание переложить Json — это реалистично. Только что это задание вообще проверять будет? Это даже не fizz-buzz уровень.


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

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

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

Конечно может, от языка это не зависит. Но от языка зависит предметная область и то, чем придется заниматься. А заниматься решением задач на строки без готовых библиотек точно не придется никому из перечисленных в 99% случаев. Верстальщика надо спрашивать об одном, инженера по devops о другом, а С++ разработчика в команду ClickHouse о третьем. Невозможно унифицировать этот процесс до одинаковых собеседований для всех подряд под одну гребёнку. Оно не будет работать. Но о чём говорить если:


Может потому что компании лень плодить 100500 видов интервью

Пока у крупных и известных компаний километровые очереди из кандидатов на входе, им не о чём переживать, можно иметь КПД найма 10% и будет приемлемо.


Недавно мой товарищ собеседовался в Яндекс на позицию ML исследователя. Его завалили задачами на деревья и строки. Только один собеседующий попросил разобрать архитектуру нейросетки.


Вот такого быть не должно, я считаю.


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


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

Такого ни разу не встречал. Мне кажется, достаточно легко вывести человека на чистую воду.

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

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


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

Чем "реальная" задача принципиально отлечается от таких вот "алгоритмических" задач? Рельные проще — да, но только и всего. Повторюсь — я на интервью справшиваю реальную задачу, которую самому пришлось решать по работе.


Такого ни разу не встречал. Мне кажется, достаточно легко вывести человека на чистую воду.

То, что попытки точно есть и будут, по-моему отрицать сложно. Во-первых ко мне на интервью приходят люди, которые fizz-buzz написать не могут. На что-то надеятся всеже. Про вывести на чистую воду — вы заблуждаетесь. Искусство bullshiting'а точно так же применимо к техническим наукам. Потом, повторяя предыдущий пункт: люди начнут готовится и очень скоро потребуется настоящее ораторское искусство, что еще дальше от реального программирования нежели умение решать "алгоритмические" задачи.

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

Для изучения довольно большого количества алгоритмов можно потратить всего несколько недель вечеров. На уровне "знаю что есть и примерно что такое, могу нагуглить готовые реализации" (что стоит делать и т.н. "алгоритмистам", в принципе). Многомесячные подготовки на литкоде, как у автора, для этого не нужны.

Потому что «кодер» даже не задумается об обращении к «алгоритмисту» и тем придется просматривать вообще весь код и постоянно что-то переписывать.

вы меня удивляете, у вас там тимлидов нет и прочи архитекторов? линейный код пишут сеньоры-суперстары? я в такой конторе кстати тоже работал, это вообще кошмар и ужас

Имея бюджет и количество кандидатов как в FAANG легче просто нанимать только «алгоритмистов».

ну вот я про это тут гдето рядом и говорю.

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

ну софт гугла както так и работает, взять даже шаблоны андройд приложений из android studio, сколько блин я её помню, они никогда не работали из коробки нормально и вообще юзают depricated ф-ции, документацию для разработчиков вообще никто не поддерживает и не вычитывает, про тормоза фронта gmail тут рядом уже говорили…

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

Если отойти от мейнстрима в сторону специфических расчетных программ, то есть куча примеров, когда университеты делают и продают свои поделки. Алгоритм в принципе работает, но вот в большинстве своем пользоваться каждый день такими программами невозможно из-за отсутствия quality of life, багов и отсутствия документации.

Во многих компаниях возникают проблемы, которые не решаются через SO, на вскидку думаю, что у Oracle, Dell, Intel, IBM, Broadcom, и пр, полно таких задач.

Именно поэтому многочисленные поделки Гугла (типа админки гмейла) тормозят так, как будто их джун в Бангалоре левой пяткой писал.

Чтобы писать такие сложные приложения обязательно нужно наизусть помнить как балансировать деревья.

> как будто их джун в Бангалоре левой пяткой писал

По вашим словам можно подумать, что это ваша выдумка.

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

Я думаю на весь FAANG хватит пальцев обеих рук чтобы перечислить все "прорывные" вещи, которые они сделали за последние лет 10-15. И то еще надо будет смотреть какую часть из перечисленного они просто купили.

99% купили или скопипастили.

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

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

Всё это выглядит как тест на лояльность -- нужно решать много задачек, которые потом не будут иметь отношения к работе. Если готов угробить кучу личного времени, значит лоялен компании, будешь хорошо подчиняться. Причем это распространяется даже на data science вакансии, например моего приятеля, завалили на system design, хотя он хотел сеточки учить.

А не помните, какие задачи от амазона не получилось одолеть? Случайно не про парковку и расшифровку сообщения?

точно не парковка, 1 - была на строки, 2-я на нахождение оптимальной стоимости сортировки массива в increasing или decreasing случае, где стоимость - это разность между элементами при перестановке (точную формулировку тут не помню, на leetcode такой задачи нет)

Познавательно.

Удачи вам в переезде и спасибо за статью. Внимательно смотрите страну, куда поедете. Желательно найти того, кто там живет. Для себя уже решил, что если и двигаться в FAA(M)NG, то только если офис разработки будет в Финляндии или на край - в Норвегии.

НЛО прилетело и опубликовало эту надпись здесь

С семьей комфортно. Медицина, садики, школы, соц обеспечение. Мы когда искали куда ехать - это были основные вопросы. Понятно, что если ехать на позицию 10k EUR + то это не так критично, но таких очень мало. И в той же Иландии 10к в месяц не помогут - жилье в Дублине просто космос.

в Финке разработчиков нанимает только гугл и то вроде только интернов со степенью PhD либо архитекторов.

Более-менее похожий уровень интервью для мидла здесь можно найти в Vaadin и Gitlab, там несколько алгоритмических собеседований. Крупные компании (Нокиа, Эрикссон) вроде только один собес посвящают алгоритмам, ну да они и не FAANG.

А так обычно люди за такой работой из Финляндии переезжают в ту же Ирландию.

Согласен, у меня коллега так и уехал. Vaadin - Турку :P, GitLab вроде полный ремоут есть. Но вопрос соответствия тому же финскому законодательству. У меня была пара собеседований, где я задавал вопрос - 5 недель отпуска и отпускные, весь Июль как отпуск, оплата переработок, 37.5 часов рабочая неделя и тд. Кроме общих бла бла бла ответа конкретного небыло :)

В финке есть офис разработки гугла? 4 года назад там был только датацентр и разработчиков не было.

Сам удивлён :) изначально собирался написать что в Финляндии вообще нет должностей разработчиков в компании FAANG, ан нет, на https://careers.google.com/ оказывается есть и даже несколько! Правда, кажется в основном не чистые разработчики требуются, больше интеграторы.

С интернами интересная штука получается, как я понимаю могут нанять в Финке но по сути требуется переезд?

Здравствуйте, @shhelen, Вы пишете, что у вас диплом бакалавра, а если не секрет, какого вуза?

Крымский федеральный университет имени В.И. Вернадского

Когда-то самым популярным алгоритмом на интервью в Google было вот это чудо - https://en.wikipedia.org/wiki/Seam_carving
Я вообще узнал о нем во время интервью :)

Курс по алгоритмам от Принстона и Седжвика (вроде 2 часть) даёт задание реализовать его на графах, кстати.

Amazon
Язык: Python
Оценка процесса интервью: 7 из 10
Тут все прозаически эпично. Я завалила online assessment, было 2 задачи на 45 минут

В общем, вы меня сподобили ответить рекрутеру оттуда и попробовать тоже. У меня было 2 задачи уровня very easy и somewhat easy. После каждой нужно было вписать её описание и сложность алгоритма. Таймер был на 105 минут, дескать, 90 минут на 2 задачи и 15 минут на их описание. Assessment был для SDEII, не знаю, может лёгкие задачи — это особенность этой низкой позиции.
Потом назначили 4 часа собеседований на 1 день, одно по часу. Наверно, там и будут сложные задания, но я к тому времени уже забуду про этот топик и не расскажу =)

А я напомню

Всё равно я и Алексей ждём!

Комментарием ниже полный отчёт.
Было интервью, 4 штуки в один день. По часу с 15-минутным перерывом. У меня было 4 недели на подготовку с момента одобрения online assessment, по 1,5-2 часа в день среднем. Упор в подготовке на 70-80% на System Design, ибо привычка накодить чего-нибудь у меня есть, даже по таймеру, и основные алгоритмы со структурами данных я знаю, а вот уверенности в таких же своих силах в системном дизайне у меня не было и в том, что там вообще могут спросить.

Первые полчаса у каждого — 2-3 вопроса по Leadership Principles (после ответа интервьюверы дозадавали уточняющие вопросы). Мне лично было сложно отвечать и это отняло больше всего моих умственных усилий, несмотря на некоторую тренировку отвечать на вопросы по этой ссылке до интервью. Каждый может попробовать по ссылке отвечать на примеры вопросов, на некоторых я просто подвисаю (и на интервью такие были).

Вторые полчаса каждого интервью — это техническое задание, 3 кодинга и одно system design.
System design назывался «спроектировать Твиттер», но обращать на слово «Твиттер» не стоит — ТЗ подаётся дозированно, очень ограниченно и нужно допытывать что конкретно нужно реализовать. Не очень хорошо получилось, потому что интервьювер как-то давил, моя модель данных стала неудачной после докидывания требований, а подумать и исправить было сложно в потоке вопросов от интервьювера. Несколько рваная секция получилась, в общем.
На Coding было 3 задания, по сложности близкие к online assessment. На каждое оставалось 30 минут, но на самом деле 20, потому что в конце было 5-10 минут для моих вопросов (они были).
— Найти наиболее квадратное поле клеток, чтобы после заполнения K там оставалось не более X свободных (обычный перебор).
— Преобразовать римские цифры в обычные (были даны примеры, так что принцип был сразу понятен).
— Get top K items, которые постоянно добавляются или увеличивают весь на единицу. Похоже на LFU.
Такие элементарные задачки сложно не решить, но тоже были шероховатости. Возможно, результат был медленнее, чем можно было бы, с парой невнимательных ошибок во время написания.

На следующий же день пришел отказ «not passing score». На мой вопрос, что не так, мне ответили, что конкретно сказать не могут, микс факторов, но в основном из-за Leadership Principles, ещё вроде уточняющих вопросов было недостаточно. Добавили, что, дескать, плохо не было, но это не «bar raiser».

Я хочу ещё отметить, что рекрутер заранее присылает материалы, темы для подготовки, как если они заинтересованы в том, что я пройду фильтры. В плане кодинга рекрутер почти исключительно упирают на алгоритмы и структуры данных, с которыми было связано 0 из 5 кодинговых задач. Даже при отказе мне прислали в советах подготовиться на следующий раз (cooldown 6 месяцев) пару ссылок, как материалы для курса алгоритмов от Принстона (год назад мною пройденный на курсере — советую всем, там сложные задания с автоматической проверкой и его часов за ~150 можно закончить). Немного иронично.

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

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

Публикации

Истории