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

Комментарии 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) быть суперзвездой в чем-то, чтобы Гугл сам за вами прибежал с оффером "впишите свою зпл".

Я вот читаю все эти статьи про интервью и не могу понять, в чём проблема? Там же, по крайней мере, задачи, которые на самом деле гиперхалявные (ну, то есть, халявные настолько, что ты начинаешь думать «слишком просто, не упустил ли я чего?»), которые ИМХО любой человек, не только решавший бизнес-задачи (что бы это ни значило), но хоть немного писавший кода чуть сложнее перекладывания жсонов из одного эндпоинта в другой, может придумать и решить (иначе я не понимаю, чем он занимается в программировании).


Не теоретизирую

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


Вон, например, топикстартер сослалась на задачу на литкоде. Она же решается в уме, а решение пишется за пять минут. Серьёзно, я в 18:34 зарегался на литкоде, минуту посокрушался, что нет хаскеля, и придётся писать на плюсах, на которых я уже года два ничего серьёзного не писал, а в 18:40 отправил


решение
class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        std::vector<int> perm(indices.size());
        std::iota(perm.begin(), perm.end(), 0);
        std::sort(perm.begin(), perm.end(),
                  [&indices](int i, int j) { return indices[i] > indices[j]; });

        for (const auto i : perm) {
            const auto sourceLen = sources[i].size();
            if (s.substr(indices[i], sourceLen) == sources[i])
                s.replace(indices[i], sourceLen, targets[i]);
        }

        return s;
    }
};

которое ещё работает быстрее 100% других решений, лул:


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

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


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

В худшем случае у replace сложность O(N) от размера строки (ее придется раздвинуть).

Это ровно то, о чём я написал в последнем абзаце: для упомянутых ограничений это всё не имеет смысла, и даже такое тупое решение работает, ээ, faster than 100.00% of C++ online submissions.


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


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

Если хочется заморочиться, то вообще зачем что-то двигать? Опять сортируете индексы с конца, и результирующую строку заполняете с конца. Для каждого индекса вы знаете начало и конец в результирующей строке — копируете из исходной нужный кусок, копируете targets[i], повторяете.


Получается вполне себе линейный алгоритм.

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

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

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

Я вообще сразу старую обратно включил, новая — глючное поделие, ИМХО сделанное только ради того, чтобы что-то сделать.

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

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

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

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

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

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


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


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

ИМХО это вопрос вашего личного чувства прекрасного, и того, как ваше решение вписывается в решения других людей (если их достаточно много).


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

В гугле достаточно вспомнить, что такие вещи есть, написать с нуля RB/AVL/etc не требуют. А если где-то требуют, бегите оттуда, потому что да, вспоминать это всё очень неприятно.


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

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

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

Так это ж стандартная стратегия, работающая далеко не только на интервью: выкатить MVP самый тупой, но корректный алгоритм, и посмотреть, какова будет реакция общественности (или стейкхолдеров, или интервьювера).

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

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

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

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

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

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

Впрочем, вспомнилось тут одно собеседование в криптоблокчейн на всякой функциональщине, где всё началось с вопроса о том, хорошо ли


type Map a b = [(a, b)]

insert :: a -> b -> Map a b -> Map a b
insert k v m = (k, v) : m

find :: Eq a => a -> Map a b -> Maybe b
find = Prelude.lookup

в качестве ассоциативного контейнера (нет, не хорошо, асимптотики ужасные, дружественность к кешу тоже так себе). Мы сначала пообсуждали разные другие ассоциативные контейнеры, хорошо ложащиеся на функциональщину, пообсуждали стандартные мутабельные хешмапы и разные стили разрешения коллизий (ну там, бакет-список а-ля плюсовые хешмапы, open addressing, cuckoo hashing, вот это всё, при этом я названий не помнил, а называл идеи), пообсуждали линейные типы, которые позволяют иметь типа-мутабельные вещи в ФП со всеми ништяками, а потом, так как я упомянул про кеши, начали обсуждать, какую проблему вообще решают кеши, почему кеш не может быть размером с ОЗУ даже с бесконечным транзисторным бюджетом, и в итоге как-то дошли до обсуждения различий между фазовой и групповой скоростью света.


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

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

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

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

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

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

Да, это была совсем мелкая компания с довольно малым числом людей. В такие места собеседования наименее заскриптованные и наиболее приятные — но, как вы пишете, весьма необъективные.


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

Ну тут тоже есть что обсудить, кстати. Например, что такое «словарь», что такое денотационная семантика, и так далее (а с delete, реализованным как соответствующий filter, эта структура неотличима от обычной мапы, кроме как по производительности).

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

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

Смотря в каком направлении. Если вам интересен прям матан за этим всем — есть классическая книжка запись лекций Жирара Proofs and types (но её примерно с восьмой главы очень тяжело читать). Если интересны более прикладные свойства этих систем типов, можно почитать Advanced Topics in Types And Programming Languages, там первая глава как раз про substructural type systems.

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

Last Edit: October 9, 2018 12:55 AM

Что ж, джва года ждём.

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

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


Олсо, поэтому у меня дома одни жалюзи.


Скрытый текст

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

Добрый день.

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

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

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

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

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

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

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

От хедж-фонда зависит.


У меня было собеседование в один мелкий, и оно было офигенное. С одним чуваком мы написали собственный плюсовый std::any в режиме «а теперь добавим ещё и такое требование». С другим — свой парсер жсон-подобного языка на комбинаторах. С третьим — пообсуждали, как бы делали распределённую систему в HFT-условиях, но когда надо учитывать данные с других бирж, откуда свет только идёт несколько десятков миллисекунд.


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

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

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

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

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

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

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

позволяют знать себе цену без решения сотни задач с литкода

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


есть вопрос зачем это надо

Зачем что именно надо?


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


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


Ещё меня удивляет такое показное отношение «да! я не могу даже такую задачу на алгоритмы, но это всё не нужно, и вообще вот твит автора homebrew!», и я не очень понимаю ценности, стоящие за таким отношением, ну да ладно.


wataru, к слову, если человек на собеседовании выдаст за отведённые на задачу 30 минут даже такое прямолинейное решение, это ведь по гайдлайнам всё равно будет hire, пусть и не strong hire, как если бы было с разговором о способах улучшить?

Почти. За 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.

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

Не надо, это часть условия.


Тут для самого прямолинейного решения уже надо садиться и думать, но начерно я бы строил мапу String → [ContextCandidate], где ContextCandidate — это тройка из слова слева, слова справа и, потенциально, дополнительных букв в середине между двумя словами, таких, что соответствующий ключ является подстрокой их конкатенации. То есть, получается отношение между ключом и тройками слов. Его как раз удобно представить в виде орграфа, где вершины — строки, а рёбра — ContextCandidate плюс соответствующие ключи мапы. Дальше вот оно сводится к задаче коммивояжёра, что вы, возможно, имели в виду.


А вот как бы тут можно было делать вообще тупой перебор перестановок входных слов, учитывая возможность промежуточных дополнительных букв (для words = [ "foo", "oto", "oof" ] оптимальное слово "footoof", не являющееся простой конкатенацией), я не знаю.

Я бы решал как-то так: за "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". И сигнал лучше

Вот с common practice уже несколько сложнее.


Если вы приходите из модного стартапа, где весь код был обмазан gsl:: и были ежедневные митапы по чтению core guidelines по ролям, то у вас впечатление об этих практисах может быть несколько другим, чем если вы приходите из условной крупной компании с кодовой базой с 30-летней историей, собственной реализацией std:: (зато с аллокаторами везде!) и собственными базовыми библиотеками. При этом ни то, ни другое не говорит особо о вас, равно как и о совместимости ваших практисов с практисами условного гугла (которые, ввиду истории и специфики, тоже не обязаны совпадать с внешними лучшими практиками).


С другой стороны, это заодно проверяет вашу совместимость с командой — насколько вы придирчивы, какого рода комменты оставляете («What do you think about using std::to_chars here instead of std::to_string?» или «use std::to_chars»), и, собственно, что вы считаете лучшими практиками. Хорошо это или плохо — другой вопрос.

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

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

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

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


как и использовать ссылки там, где указатель никогда не nullptr.

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


References are for parameter passing, including range-for. Sometimes they’re useful as local variables, but pointers or structured bindings are usually better. Any other use of references typically leads to endless design debates.

Здравствуйте, я к вам из 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 лет я мог вообще не двигаться, спать чёрти как, и был весьма продуктивным.


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

Ну, во-первых, официальная рекомендация ВОЗ — это 150 минут лёгкой активности в неделю или 75 средней. Для этого достаточно условно ходить пешком до метро по пути на работу.
Во-вторых, я ещё не встречал ни одного эксперимента с дизайном «одни люди N минут в неделю практиковали собственную физиологию, другие — N минут в неделю решали задачки на литкоде/ботали матан/решали судоку». Почти всегда альтернативная группа занималась примерно ничем.


Дизайн экспериментов был адекватным? Или там

потратить много времени для того, чтобы иметь возможность подтянуться 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, потому, что "а смогу ли?" и деньги. Персональный челлендж.

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

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

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

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

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

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

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

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

Это не вся история. При EB-гринке важны ещё и ваши намерения: планируете ли вы при её оформлении (включая интервью с USCIS officer'ом) дальше работать на вашего работодателя. В частности, на интервью в USCIS вас могут спросить, планируете ли вы дальше работать, и с чистой совестью отказать, если вы даже скажете «да не, через полгода-год свалю» (и фиг вы сможете это апеллировать).


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

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

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

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

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

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

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

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

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

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

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

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

У настоящего американского фаанга (конкретно, гугла) проблема в том, что там довольно тяжко пилить личный опенсорс даже в личное, нерабочее время (хотя это не для всех проблема, конечно). В РФ такое ТК не допускает, а в США работодатель вас может контрактом ограничивать достаточно произвольно.

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

Конкретно по личным проектам (включая личный некоммерческий опенсорс) — насколько я знаю, везде может, включая достаточно про-employee-Калифорнию.

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


  1. Если хочешь вечером воскресенья что-то запилить в какой-то открытый проект, то проверь, является ли он в списке зааппрувленных (там было порядка сотни проектов суммарно, большинство из которых — те, куда люди коммитили что-то из-за работы, а не из-за личных желаний). Если да, то можешь. Если нет, см. п. 2 и далее.
  2. Незааппрувленные проекты нужно сначала подать в IP-отдел компании на аппрув. IP-отдел состоит из целого одного человека и одного его помощника, поэтому аппрув может занимать произвольно долго: недели и месяцы. Надо не забывать пинать людей, но так, чтобы не показалось, что тебе этот попенсорс важнее Работы. Оказывается, к слову, это довольно эффективно убивает мотивацию и желание спонтанного вечернего контрибьютинга при свечах.
  3. Зааппрувленный проект надо добавить на специальную страничку на вики компании. Лично для меня это проблема, так как я против смешивания работы и личной жизни, и мои личные проекты — моё личное дело, о которых я по умолчанию не хочу рассказывать всей организации.
  4. Аппрувить не надо проекты, «не представляющие интереса для компании». Так как компания пытается косить под гугл, IP-отдел считает, что для компании представляет интерес всё, что относится к кодингу (включая, например, книжку по написанию формально верифицированного кода на никому не нужном языке). Зато можете не аппрувить книжку о садоводстве, например, которую вы пишете в личное время.
  5. Аппрувить надо даже личные блоги и посты в них (если они про программирование). А то вдруг что.
  6. Если проект требует copyright assignment (даже если это assignment условному FSF'у у glibc до недавнего времени, например), то ты идёшь нафиг.
  7. Если у проекта «непонятная» лицензия для IP-отдела (типа такой, упоминаемая там Software Foundations на тот момент была, да и сейчас есть, под вполне опенсорсной лицензией), не соответствующая по шаблону привычным GPL, BSD, etc, ты идёшь нафиг.
  8. Если у проекта есть даже, не знаю, платная поддержка или dual licensing в таком стиле, ты идёшь нафиг. Даже если у тебя тривиальный патч на пару дюжин строк (тут мне конкретно мой манагер посмотрел на этот патч глазами и сказал «да забей на этих дураков из IP»).
  9. Если проект хоть немного пересекается с реальным продуктом компании (например, там, где я работал, в продукте был встроенный мессенджер, и у меня в моём проекте, который я начал в 2006-м и у которого, может, даже наберётся пара сотен пользователей, тоже есть мессенджер), ты идёшь нафиг.

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


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

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

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

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

Ну так не надо подписывать такие контракты.


У меня в очень драконовской по этой части области в виде всякого трейдинга было условие «полгода к конкурентам не ходить», но при этом было же «помимо severance, полгода платится зарплата, если вас увольняют without a good cause». Я прям даже пожалел, что этот пункт для меня waive'нули (вместе с зарплатой), когда увольняли по сокращению из-за кризиса в феврале того года — это трейдинг всё равно осточертел, и к конкурентам я идти и не собирался.

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

  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? Есть у кого-нибудь такой опыт?

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

Именно от этого автора не было. А каждая история уникальна, я бы послушал.

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

Скипнули phone screening в гугл, например.
Не в гугл скипнули вообще техническое собеседование и оставили только, ээ, аналог system design и некое подобие поведенческого интервью.

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

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

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

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

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

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

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

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

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

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

Ну мне в Indeed предлагали, например, вплоть до оффера. Там, правда, на джаве писать надо, поэтому я отказался.


Без алгоритмов предлагали на machine learning engineer'а в компанию, упомянутую топикстартером, я туда в итоге согласился. Тоже пять раундов, конечно, но один — совсем лёгкий вопрос по плюсам (типа, написать свой auto_ptr, что для 2014-го года было ещё более-менее релевантно), три — по машинному обучению (тоже не очень сложные вещи типа «нам надо категоризовать почту, придумайте фичи»), один — с эйчаром о жизни и зарплате.

так логично, что на 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-ти элементов всегда?