Всем привет!
Хотела бы поделиться своей историей прохождения собеседований в IT-гиганты и допущенными ошибками. Немного о себе: у меня диплом бакалавра по прикладной математике и 6+ опыта разработки.
Свою карьеру я начинала фронтенд разработчиком в американском аутсорсе еще на 2 курсе универа (да, бывший формошлеп будет вам сейчас вещать про алгоритмы), в Яндексе работала на fullstack, потом ушла в хороший family-created стартап. Я была по обе стороны собеседований, суммарно их около 100+ наберется, но это отдельная тема с кучей кулл стори, здесь будет больше про Google и несколько крупных компаний (не FAANG), которые мне хотелось бы осветить. Присаживайтесь поудобнее!
Если вы студент
Если вы все еще учитесь, хотите попасть в FAANG и вам кажется это нереальным, присядьте и успокойтесь. Я знаю примеры реальных людей, которые прошли на стажировку и это более, чем реально. Если бы мне кто-то сказал курсе на 2-ом, что нужно прорешать 500+ задач и попробовать податься, как postgraduate, то я бы обязательно попробовала, хотя и была очень не уверена в себе. Если вы еще не работаете и действительно этого хотите - дерзайте! Материалы и ссылки будут в конце.
Как оно там в большой компании, вроде Яндекса? И почему Google?
Единственное, чему меня действительно научил Яндекс, так это то, что ваше собеседование, как первое свидание, если вам не нравится, то дальше уже лучше не будет. Селяви и ищем другую команду и/или компанию. Ваш профессиональный рост и продвижение по карьерной лестнице очень зависит от того, оказались ли вы в нужное время в правильном месте и тоже самое касается FAANG.
Вам повезло, если у вас есть хотя бы 2 из этих 3 пунктов: адекватный менеджер, нормальный руководитель и действительно хоть какая-то доля интересных/громко-кричащих задач. Моя история это та, в которой вам не повезло и при заходе в компанию у вас нет ни одного из этих пунктов. Так или иначе спустя полгода я перевелась в другую команду и отработала год. Это был опыт, я познакомилась со многими хорошими специалистами и моя вторая команда была one love, но я уже просто устала от ненормального work-life balance в компании, не особо интересных задач, зарплаты ниже рынка и своих непонятных карьерных перспектив. После Яндекса мотивации работать не было вообще.
Я ушла в стартап, CTO которого отработал 15 лет в IBM и это человек, который меня бесконечно вдохновляет, мало кто спустя такое количество времени в IT так горит своим делом. Через полгода я немного отошла от выгорания, мы с молодым человеком решили релокейтиться так или иначе. Еще со времен университета мне всегда очень хотелось попасть в Google - это просто незакрытый гештальт.
Ну что, завелась и понеслась? Куда я проходила собеседования
Google
Amazon (реферал)
Gitlab
Stripe
Ebay (offer, под NDA, деталей особо не будет)
Компании, куда я подавалась, но меня не захотели собеседовать (непонятно по какой причине, ответ, как всегда, общий): Reddit, Github, Booking, Robinhood, Spotify, Bloomberg, Twitter, LinkedIn, Dropbox, всех и не вспомнишь уже…
Про Uber еще хочу сказать, что если вы подавались сами и вас не рассмотрели, порефералить вас на эту позицию может и не получится - будет действовать cooling period, ситуация реальная, имейте ввиду.
И отдельно про Microsoft (реферал) - тут рекрутинговый процесс нечто. Подавалась через реферала, со мной связался рекрутер и спросил, могу ли я прийти к ним на hiring coding event. Я не могла туда пойти, потому что в этот день у меня был онсайт в Google. Рекрутер на абсолютно пофигистичной ноте сказал, что сейчас у них мало слотов на собеседования, но они со мной свяжутся. Как говорится, хотите вас позовем, хотите не вас…)
Здравствуйте, котиков на работу берете? Простите, вы слишком маленький котик
Мне 25, мне никогда не казалось, что это проблема, но да - это проблема. Рекрутеры обычно не особо засчитывали мне 2 года работы в университете и считали это вялотекущим парт-таймом, хотя он таковым не был. Я работала на полную ставку, не особо ходила на пары и просто закрывала сессию на 3, но людям в Европе сложно понять, как можно получить диплом и почти не ходить на пары на матфаке. На собеседовании в Нидерланды рекрутеры настолько удивлялись моему возрасту, что переспрашивали - это 2 и 5? Возможно, именно по этой причине меня не рассмотрели в другие компании или не было матча по опыту, неизведанно. Но один из рекрутеров сказал, что до 25 они вообще не релокейтят.
Подготовка и выбор языка
Тут стоит отметить, что у меня не совсем низкий старт. Когда-то в универе я разбирала задачи на динамическое программирование, длинную арифметику, деревья и что-то сабмитила на e-olymp. Формально, я +- представляла, чего ожидать. Ребятам, у которых не было никаких алгоритмов в универе или если они пришли в разработку из другой сферы может быть сложнее на старте.
Разумеется, как изначально красильщик кнопок, я пишу на js. В С++ могу на уровне универа, написать пару несложных шаблонных функций и все. Долго думала, на чем я буду проходить собеседование еще перед началом подготовки и это был бы явно не js. В js много чего нет, например, реализации heap. Выбор пал на Python, продакшн код на Python я не пишу, но в случае чего, на вопросы, вроде зачем нужен GIL, могу ответить. Почему Python? Java - очень много букв, C++ - очень хардкорно, на Python к тому же много алгоритмических курсов, например, MIT, но это чисто мое субъективное мнение.
Roadmap задач
Я старалась решать по 2-4 задачи в будний день из разных разделов, это примерно 4 часа в день до/после работы. Например, одна на строки, другая на графы. Разделам, где я проседала больше, выделяла отдельное время - в частности, на динамическое программирование. Полностью вся суббота и часть воскресенья уходили на подготовку. Будьте к этому готовы, подготовка съест очень много вашего личного времени. На текущий момент у меня 352 задачи:
В таком режиме важен таймлайн - не можете решить задачу за 1-3 часа, смотрим подсказки, непонятно, как решать даже с подсказками, смотрим и разбираем решение. И да, купите премиум! Оно того стоит: у вас будут доступны фильтры задач по компаниям, решения, закрытые популярные задачи, тестовые подборки для собеседований. Параллельно я просматривала задачи из Cracking The Coding Interview c точки зрения подхода решения. Есть еще неплохая подборка с паттернами для решения задач Patterns for Coding Questions. Так прошло 4.5 месяца, нужно было начинать готовится к System Design.
Какие топики обязательно надо покрыть (по-моему мнению):
DP: одномерный (Coin Change, Climbing Stairs), двумерный (Unique Paths, Dungeon Game), трехмерный (Cherry Pickup, Cherry Pickup II);
Графы: DFS и BFS надо прям так, чтобы если вас разбудят среди ночи, вы их напишите. Алгоритм Дейкстры, как находить шарнирные точки, мосты, циклы. Рассмотреть задачи на BFS + Binary Search (Swim in Rinsing Water);
Матрицы: обходить змейкой, по диагонали, звездочкой и как угодно;
Задачи бинарного поиска;
RMQ: Fenwick tree, Segment tree (есть хорошее объяснение на канале у Tushar Roy);
Задачи на sliding window, prefix sums, stack, recursion (вот тут надо уметь в Master Theorem)
System Design
До этого я читала GoF (у меня даже какой-то курсач в универе по паттернам был), книгу Фаулера (подписана на его блог и слежу за статейками там). Я очень волновалась именно за системный дизайн, потому что опыта проектирования высоконагруженных систем у меня не было, но именно эта секция в Google прошла у меня лучше всего. Я знаю базовые вещи: про OSI, балансеры, LRU/LFU cache, ACID и т. д. Но нужно уметь четко выделять точки отказа в системе, как лучше шардировать данные, проектирование read heavy vs write heavy приложений и уметь донести свою мысль интервьюеру, что очень важно. В итоге, я прошла курс Grokking the System Design - хайли рекоменд, прочитала Alex Xu, System Design Interview и половину книги Designing Data-Intensive Applications (она очень интересная и стоящая, но мне не пригодилась). Есть еще более углубленный курс на educative - Grokking the Advanced System Design.
Если у вас опыт только, как фронтенд разработчика, и вы не умеете в reverse proxy и зеркалирование в nginx, начать советую с этого. Напишите маленькое приложение на бекенде, настройте балансер, потрогайте ACL (можно даже через битовые маски реализовать, чтобы и битовые операции вспомнить).
Behavioral
Моей ошибкой было то, что я особо к нему не готовилась, а стоило. Я бы предложила взять Leadership Principles Амазон и расписать в доке конкретные ситуации с примерами и быть готовым красиво выкатить ответ, когда вас спросят про пример вашего достижения, несогласия с менеджером и пару десятков часто задаваемых вопросов. Тут не буду советовать того, чего не смотрела/читала. Советую обратить внимание на док сообщества подготовки в FAANG. Есть еще неплохой список топиков на leetcode.
Mock-собеседования
Ребята из канала подготовки в FAANG в телеге проводят mock-собеседования (только на английском). Cтоит сходить, когда у вас есть хотя бы 100 задач leetcode. Вам подберут других ребят по схожему количеству задач, очень помогает научиться правильно проговаривать ход своих мыслей и объяснять ход решения другому человеку. Это не тоже самое, что тестовое интервью на leetcode. Группа очень полезна, в доке сообщества куча информации по подготовке - советую ее прочитать и начать оттуда. Рефералов можно тоже поискать в группе или на LinkedIn/Blind, но у вас должно быть прорешено определенное количество задач. И пожалуйста, если будете присоединяться в группу, прочитайте сначала закрепленные сообщения, правила и начните с доки, вы найдете там ответы на большую часть ваших вопросов, не стоит сразу писать в чат, а с чего же стоит начать и что делать.
Подготовка резюме
Очень важно подготовить резюме и уместить все ваши достижения на максимум 2 страницы, а лучше 1.5, никто не будет читать ваши 15 страниц жизни, начиная с первого приложения "Hello World!".
Резюме нужно оформить в формате достижений, а не списком технологий. Почитать можно тут, шаблон взять отсюда. Еще хорошие шаблоны тут. В телеге в этом канале можно попросить ребят поревьюить ваше резюме.
И тут сейчас будет мой факап, у нас проблемы Хьюстон! Я опечаталась в своем email при первой подаче через реферала, ситуация смешная и одновременно страшная. Вывод: всегда внимательно проверяйте контакты (раз 5) и дайте кому-то почитать перед отправкой.
Язык: Python
Оценка процесса интервью: 10 из 10
Я подавалась по формочке и меня рассмотрели. Реферала я нашла уже потом и попросилась подкрепить мой application.
Phone screen
На этапе фон скрина у меня было около 250 задач, мне повезло и попалась задача medium level очень похожая на эту. В итоге, я успела написать решение через динамику и набросать вариант префиксного дерева (Trie). Все прошло хорошо.
Onsite
Моей ошибкой было назначить все 5 этапов в 1 день, это тяжело, вы не успеваете выдохнуть, а перерывы 15-30 минут. На этапе онсайта у меня уже было 350 задач. Перед интервью я выписала топ 100 задач, по 2 строчки на каждую с общей идеей решения.
1 собеседование - System Design
Я распереживалась и сначала начала рассказывать не в том направлении, что ожидал интервьюер, но потом собралась и уже двигалась в правильную сторону. Задача была про внедрение стороннего сервиса c REST API в систему, который по эндпоинту возвращает true/false блокировать или нет ресурс для пользователя по IP. Сначала начала рисовать это в гугл доке, но это только меня тормозило, переключилась просто на текст и описывала систему сверху вниз или слева направо. В духе, client -> L3 -> L7 -> server. Интервьюер спрашивал про точки отказа, успели поговорить про них, варианты кеширования, rate limiting, middleware и много всего.
2 собеседование - Coding
Была задача - вариация c consecutive subarray. Как решать сообразила быстро, написала решение, по ходу проверки разных тест кейсов поправляла код. Фидбек был, что я долго писала реализацию и с багами, хотя очень быстро сообразила, как решать.
3 собеседование - Behavioral
Бихейв был 3 по списку. Мне казалось, что я неплохо отвечала, но ваше впечатление от интервью - это не тоже самое, что впечатление вашего интервьюера. От меня хотели услышать больше конкретных примеров ситуаций. Прошло не очень хорошо. Тут мой косяк в плане подготовки.
4 собеседование - Coding
Тут я уже знатно устала. Задача была, похожая на эту, я сходу пошла решать, при решении допустила синтаксическую ошибку и не смогла правильно сказать time complexity для копирования строки внутри цикла (тут я, честно говоря, и не сразу поняла, что хочет интервьюер от меня). Прошло не очень хорошо, хотя решение я и написала.
5 собеседование - Coding
Была задача на граф с follow up условиями, решала через BFS, немного провозилась с follow up в конце. Правильно сказала time и space complexity, этот кодинг прошел хорошо.
Summary
По фидбеку в общем рекрутер сказала, что у меня нет каких-то больших пробелов или совсем плохого кодинга. Просто есть моменты, над которыми надо поработать и можно попробовать еще раз через 6 месяцев. Насколько я поняла, cooling period зависит напрямую от результата онсайта, если вы не решите вообще какую-то задачу, то будет 12 месяцев. Впечатление от всего процесса очень положительное, интервьюеры были хорошие ребята и никто не пытается тебя завалить, нет какой-то давящей обстановки, учитывая, что ты и так нервничаешь, это очень важно. Перед онсайтом можно сходить на Champion Call - 15 минутная встреча, где можно задать интересующие вас вопросы, я на такой ходила.
А как оно там в Яндексе? Отличается от Google?
Да, если брать по моим ощущениям, то это 30% сложности от Google (тут говорю за службу, в которой я работала). Вы сами понимаете, что отбор в Google - это x20 от Яндекса, если не больше. Этапов с кодингом тоже 5 (4 онсайта и phone screen), НО если вы идете на js, то вас будут спрашивать js специфичные задачи (каррирование, замыкания, глубокую копию объекта, что-нибудь может про идемпотентность запросов). Алгоритмическая секция это easy/medium задачи, в основном массивы, списки, строки и баянистые задачи на стек, вряд ли вас вообще спросят про графы, балансировку 2 хипами, trie и уж тем более задачи RMQ. Это отличается, конечно, от того, куда вы идете и на какую позицию, но это все равно легче. Для ребят, которые идут на C++ или ML инженера с алгоритмами дела обстоят иначе.
Amazon
Язык: Python
Оценка процесса интервью: 7 из 10
Тут все прозаически эпично. Я завалила online assessment, было 2 задачи на 45 минут и 15 минут на Leadership Principles. Одна из задач была (как я уже поняла потом) на 2 heaps (похоже на решение задачи с data stream), я пыталась решить через DP, тест кейсы не проходили, я уже подумала загуглить ее, но времени оставалось мало и я не успела по кодингу, до Leadership Principles даже не дошла. Мне лично непонятно, зачем давать hard задачу на онлайн тесте, если вы ее не знаете и нет подсказки от интервьюера - то можете отвалиться по времени. Но как оказалось, можно написать текстом ход мыслей, если вы не успеваете, но я этого не знала.
Gitlab
Язык/фреймворк: js, vue
Оценка процесса интервью: 10 из 10
Рекрутер на LinkedIn написал и предложил пройти собеседование, я прошла 5 этапов, но оффер не получила. Совсем другой подход к интервью, меня не спрашивали ни одной алгоритмической задачи. Вам дают поревьюить пулл-реквест и оставить в нем комментарии, на собеседовании вы обсуждаете эти улучшения и вас попросят их заимплементить и это единственный прям технический этап. Остальные этапы были про опыт, поговорить, behavioral вопросы. Сам процесс мне очень понравился и это, правда, одно из интересных и лучших собеседований, что у меня были. Развернутый фидбек мне дали на звонке, по технической части не было каких-то замечаний, рекрутер сказал, что все прошло хорошо и я одна из 5, кто вроде как дошел до финального этапа, просто другой кандидат им понравился больше и лучше подходил. И за обратную связь просто +1000 в карму. Gitlab молодцы.
Stripe
Язык: Python на секции по бекенду, React на фронтенд. Можете выбрать любой.
Оценка процесса интервью: 5 из 10 (заявочка на победу - меня 2 раза прособеседовали по бекенд секции, такой вот форс мажор)
Подавалась по формочке и собеседовалась на fullstack. Тут все очень интересно, я до конца так и не поняла сколько у них этапов, но вроде 4. Меня реджектнули на 2 (формально на 3) - frontend секции. Секция бекенд - это алгоритмическая задача, но тут смотрят на то, как ты проверяешь свой код и какие тест-кейсы пишешь, а не на то, правильно ли ты подсчитал time complexity. У задачи есть расширенный follow up.
1 собеседование - Coding
Задача была easy/medium уровня на hashmap, но условие задачи там (без примеров) не помещалось мне в экран. На входе была hashmap соседей, у которых по ключу список по приоритетности домов других соседей, с кем бы они они хотели свапнуться. Нужно было сначала найти могут ли соседи A и B поменяться домами (приоритет обмена должен быть одинаковый), потом найти, какие связи мы ломаем/добавляем если, например, для соседа A меняем приоритет обмена домами. Сама задача несложная, но условие витиеватое было и запутанное, как мне показалось. Этот этап я прошла.
2 собеседование - Coding
Тут у меня должна была быть frontend секция, так как я подавалась на fullstack, но что-то пошло не так, это перепутали и мне снова провели собеседование по задачам. Задача была на парсинг accept-language header. Прошло неплохо, но ко мне вернулся рекрутер и сказал, что они случайно перепутали секции, лол кек.
3 собеседование - Designing UI Component
По фронтенду задача заключалась в имплементации masked input для телефона и тут в момент собеседования мне пришлось ребутать мак, потому что из-за шаринга экрана и зума у меня жралось CPU, как не в себя и я нормально не могла писать код. Делала компонент на React с кастомным хуком - useMaskedInput, который бы принимал маску/формат и значение, где по слотам для вставки digit - вставлялась бы нужная цифра. Такой же подход, как и в блоге у ребят из Тинькофф. На этом этапе меня реджектнули, развернутого фидбека не дали, что пошло не так, кроме моих проблем с компом - не знаю) Видимо что-то не понравилось интервьюеру.
Впечатления от процесса 50/50, если бы не этот форс мажор с двойной секцией, то в целом сами собеседования и процесс неплохо выстроен, но обидно, что развернутого фидбека не дали, просто общий темплейт отказа на email, а ведь потрачено на компанию было 3+ часа времени.
Ebay
Язык: js
Оценка процесса интервью: 10 из 10
К сожалению, подписывала NDA и осветить весь процесс не могу, подавалась через их careers site. Собеседовалась в 2 команды, процесс очень отличается. Впечатления по процессу собеседования в одну команду весьма положительные, очень хорошие ребята и вопросы интересные, во второй команде 50/50. Если вы готовитесь так или иначе в FAANG, то 100% можете податься.
Немного советов:
Фидбек и мнение. Во-первых, не весь фидбек конструктивен и всегда найдется человек, который думает, что он эксперт во всем и его мнение непременно самое правильное и важное и вам очень нужно это знать. Пример: у одного из моих технических лидов в команде была психологическая травма и просто чуть ли не панические атаки при слове "аутсорс". Он считал, что аутсорс, цитирую: "неправильно воспитывает людей и нормально разработке они там не научатся". Иногда чье-то мнение, это просто мнение, не имеющее ничего общего с реальностью, так что если вам скажут, что что-то тяжело/не потянете/мало лет воспринимайте это соответственно. Конструктивный фидбек - это другое, в моем случае я завалила бихейв в Google - и тут есть над чем поработать.
Готовиться придется долго и вам нужно расставить приоритеты и решить, чего вы действительно хотите, будет обидно, если вы бросите все на полпути.
Разбейте онсайт на 2 дня, если есть такая возможность. Спустя 3-4 собеседования вы устанете, лучше пусть это будет 2 дня, чем вы завалите последний этап интервью.
Решайте задачи, пробуйте писать код в гугл доке/на листике/доске. Практикуйтесь - это залог успеха. И удачи!
А что с офферами?
В этой статье хотелось осветить процесс подготовки и ошибки, а также впечатления от процесса найма в крупные компании. Некоторые компании не включила, например Facebook, потому что я все еще жду от них ответа. Я получила оффер в Ebay и компанию в составе Shell Group. Про переезд и куда я в итоге пошла will keep you posted, сейчас на этапе сбора чемоданов. Всем успехов и удачи на собеседованиях!
Ссылки и материалы
Группа по подготовке в FAANG и док сообщества
Группа по ревью резюме
Блог Ларисы Агарковой и ее хороший гайд по подготовке, можно еще интервью посмотреть
Ютуб-канал Tuchar Roy
Курс по System Design
Курс по Advanced System Design
Очень хорошая статья про подготовку в FAANG - вдохновение к написанию собственной
Комментарии (297)
glebovgin
25.07.2021 20:11+50Моё любимое по теме:
Вот и я сейчас сижу сортировки, деревья и графы раскуриваю, хотя за 18 лет реального опыта довелось решать несчётное количество бизнес-задач.
Удачи вам и спасибо за статью!
yatsenko-ihor
25.07.2021 21:01+2это просто процесс отбора. И никак не значит что те алгоритмы вам 100% будут нужны. Просто если порешал 450 задач — уже мотивированный и целеустремленный сотрудник а не тот кто вышел через дорогу за +500$
glebovgin
25.07.2021 21:17+8Я всё прекрасно понимаю и отрефлексировал это по-полной.
Только вот нюансов сильно больше: можно быть стоумовым в структурах данных и алгоритмах, но не уметь достаточно в английский или софтскиллы и снова пролететь мимо работы мечты. Хоть это и не мой случай. Тем не менее у меня лично есть вопросы к процессам хайринга в IT-среде.
euroUK
25.07.2021 21:48+12Более того, если ты по факту уровня архитектора, то для тебя важнее понимать скорее для каких задач нужны какие деревья (и нужны ли они вообще), чем уметь инвертировать бинарное дерево.
Я пишу код за деньги уже более пятнадцати лет, ни разу в жизни не понадобилось что-то там инвертировать. Может быть на лабах правда было в универе. Там мы на бумажке экзамен по программированию сдавали.
klvov
25.07.2021 22:14+10Как-то даже страшновато высказываться, но, мне кажется, есть какая-то проблема, когда "архитекторов", которые уже 15-20 лет работают "за деньги", на собеседованиях гоняют по структурам данных и алгоритмам, которые, в общем-то, наизусть помнят только вчерашние студенты. И не сказать при этом, что в условном FAANG все дураки и не понимают что делают - на их объемах данных сотрудник, запуливший в прод алгоритм с O(n^2), реально создаст проблему и, может быть, даже многомиллионные долларовые убытки. И, наверное, то, что они ставят там у себя на вход такие стерильные фильтры, имеет с их стороны смысл. Но вот сама ситуация, когда на собеседовании требуется джедайское владение теми самыми пресловутыми "структурами данных и алгоритмами", а в "реальной работе" требуется, ну "Spring, Hibernate, JPQL", и редко-редко хотя бы рекурсию применить уместный случай подвернется, мне кажется странной, скажем так.
euroUK
25.07.2021 22:21+18Для того, чтобы не пулить в прод O(n^2) вроде бы существуют код ревью. А потом существует куча тестов по которым деградация перформанса будет очевидна. Более того, проблема прода в Гуглах сильно преувеличена, ведь в прод доходит процента три написанного кода, остальное в помойку. Ну и как пользователь админки gmail для компании в 50 человек, где каждое действие занимало по 30 секунд, я лично не знаю что случается потом с олимпиадниками в Гугле. Хотя, возможно, архитекторов там нет и просто 100500 микросервисов делают O(n^2) раундтрипов за данными друг к другу.
Daddy_Cool
26.07.2021 00:18+2O(n^2) — вполне мемично.
Лично использовал такой алгоритм. Можно ли было использовать более быстрый? Да. Но этот программировался существенно быстрее, с меньшими проблемами, и надо было быстро увидеть результат. Алгоритм отрабатывал около 10 минут, что в сравнении с другой частью задачи — которая отрабатывала 8 часов — значение не имело.
Но да, это не обработка транзакций или чего-то подобного, а физика.
Gorthauer87
26.07.2021 01:10+4Так это нормальный путь - заделать квадратногнездовую реализацию и напилить тестов, а уже потом улучшать ассимптотику.
siarheiblr
26.07.2021 00:40+7А не нужен им ни спринг, ни хибернейт, ни jpql. И gradle с мавеном не нужны. Там до такой степени свой мир и своя атмосфера.
Так что если речь не о чуваках, у которых основной скилл это организовывать работу, то кроме базы и спрашивать особо нечего. Все равно потом будет нужно все необходимое изучать с нуля.
dimskiy
26.07.2021 08:41+6Да все гораздо проще, как мне кажется. Если стульчик один, а желающих - 100, как будете выбирать кого усадить на него? А если 80% обладают подходящей задницей? Как в анекдоте «... ну окей, тогда показывайте сиськи»
worldmind
26.07.2021 15:12В одном из предыдущих обсуждений темы один умный хабаровчанин заметил, что унизительный процесс найма в копрорациях становится вполне понятен, если исходит из того, что им нужны винтики, умные и лояльные, готовые делать, что скажут менеджеры не задавая дурных вопросов, про то надо ли оно.
wataru
26.07.2021 16:53+5О боже, программиста просят на интервью писать код чуть посложнее FizzBuzz. Какое унижение. Кому вообще могло прийти в голову просить программиста программировать? Чертовы садисты. /s
acklamterrace
26.07.2021 18:44+3Ну справедливости ради: не сложнее fizzbuzz, а какую-нибудь задачку, для которой надо помнить какой-нибудь алгоритм Стейнхауса-Джонсота-Троттера, при этом написать закрыв глаза и стоя на коленях (зачеркнуто) высохшим маркером на вертикальном уайтборде, в стрессе и так пять раз подряд, с 9 до 15.
Был там, не уверен что хочу повторить.wataru
26.07.2021 19:17+2а какую-нибудь задачку, для которой надо помнить какой-нибудь алгоритм Стейнхауса-Джонсота-Троттера
Нет. Из всех задач, что я видел в базе, что спрашивают коллеги и спрашивал я сам нет ни одной, которая решалась бы каким-то заумным алгоритмом с тремя фамилиями в названии. Если уж перестановки будут в задаче, то максимум что вам надо, это знать, что есть такой std::next_permutation.
Ну вот нет у интервьюверов цели нанимать академиков по computer science. Нужны программисты, которые умеют решать задачи.
при этом написать закрыв глаза и стоя на коленях
Уже давно в гугле, и по-моему в других компаниях (но это не точно) можно писать на ноутбуке в специальном редакторе с подсветкой синтаксиса. При этом требования все такие же, как к доске: компилировать не надо, опечатки игнорируются. Даже если вы перепутаете, в каком порядке там параметры куда-то передаются — это вообще не минус. Можно даже сказать "я вот точно помню, что там какая-то функция примерно вот это делает, но вот не помню название". Интервьювер подскажет название или скажет, "ну назовите ее как хотите, только откомментируйте, что она делает". И это не разу не минус. Конечно, если кандидат сразу наворачивает хитрые и правильные конструкции и помнит все, ему ставится большой плюс в графу "кодинг" — отлично знает ЯП. Но для успешного найма такие плюсы не нужны. Они могут лишь компенсировать минусы в других интервью или пунктах.
DMGarikk
26.07.2021 19:24+3которые умеют решать задачи.
в короткий промежуток времени, когда на вас смотрят четыре пары глаз и еще осуждающе хмыкают
а ты со своим 15 летним опытом и кучей проектов за плечами, сидишь и чувствуешь себя джуном-двоечником который пришел к крутым дядям и обкакался… типа великие вещи делаются, а ты убогий не умеешь обход бинарного дерева за 2 минуты написать по памяти…Ну вот нет у интервьюверов цели нанимать академиков по computer science
есть есть, просто потому что 'вы можете' и у вас 'толпа сеньоров за забором'
это вот по факту так
===
забавно что качество софта гугла не коррелирует с требованиями при найме
saboteur_kiev
26.07.2021 21:47+1а ты со своим 15 летним опытом и кучей проектов за плечами, сидишь и чувствуешь себя джуном-двоечником который пришел к крутым дядям и обкакался…
Большой дядя с 15 летним опытом стесняется кодить в присутствии других кодеров?
DMGarikk
26.07.2021 22:28+4Я не стесняюсь, я не могу быстро думать, особенно когда над душой кто-то висит
questor
08.09.2021 10:33Я часто слышу подобные фразы и мне очень любопытно понять, что это такое. С одной стороны, это очень похоже на оправдание. С другой стороны вероятно в этом что-то есть.
Сколько я думал на эту тему - подумал вот что (я без ярлыков, если что, правильно вообще-то смотреть каждый случай индивидуально):
Бывают люди, которые говорят, что не могут быстро думать, но на самом деле у них есть области, в которых они работают быстро и почти не думая -- это те области, в которых они имеют опыт работы. Неважно, что это - формочки, перекладывание джейсонов или оптимизация sql-запросов. В этой области помогает опыт, важна "насмотренность". Задачи будут решаться быстро и без проблем. Чем дальше от этой области наивысшей специализации, где мозг натёр мозоль -- тем дольше и сложнее думать. "Не могу быстро думать" = "я с этим раньше не работал, пас".
Бывают люди, которые говорят, что они думают медленно, но качественно. Я таких видел несколько, они действительно прут как танк - неспешно и неумолимо. И эта категория людей выходит не нужна faang'у, они заранее будут отсеиваться низким временем решения задачи: ты только 23 минуты входишь в задачу, а уже пора её завершать.
DMGarikk
08.09.2021 10:58ты только 23 минуты входишь в задачу, а уже пора её завершать.
Этож что это за задачи такие у сеньора-программиста где надо за 15 минут решить задачу?
довольно большое количество таких случаев, которые я видел, приводили только к усугублению проблемы из-за того что человек решил 'быстро и насмотренно прямщас' и забыл что вещь которую он решает имеет далеко идущие связи в соседние подсистемы и отделы, про которые он забыл из-за того что надо 'быстробыстро'И эта категория людей выходит не нужна faang'у,
мне чёт кажется они даже об этом не думают, ориентируясь на какието количественные показатели
wataru
08.09.2021 11:41Этож что это за задачи такие у сеньора-программиста где надо за 15 минут решить задачу?
На интервью спрашивают сильно урезанные, абстрагированные от деталей и тонкостей подзадачки. Ну, тупо, потому что абсурдно проводить четрые 5-ти часовых интервью.
DMGarikk
08.09.2021 13:12На интервью спрашивают сильно урезанные, абстрагированные от деталей и тонкостей подзадачки
которые никогда не используются в реале
я помню сильно поспорил с интервьювером в одном месте когда он показал 'правильное' решение задачи (какойто синтетической где важно было иметь случайную последовательности и должно было обрабатываться быстро) с критическим багом внесения случайности… и при этом совершенно не понимал 'ну а в чем проблема то, работает же!!! вон нажимаю.… случайные числа и быстро отрабатывает'… при этом 'случайность там такова что её предсказание займет минут 5 — хорошо подумать'… но 'то что вы предложили верно, но очень медленно работает'
у меня прямо руки опустились… это прям… позор какойто… так подходить к задачам
wataru
08.09.2021 14:42которые никогда не используются в реале
Во-перовых, не правда. Я, например, даю на интервью именно ту задачу, которую сам лично коммитил в прод. Да, обрезанную и слегка упрощенную, потому что весь контекст тупо объяснять слишком долго.
Во-вторых, вы же, наверно, не возмущаетесь, что на экзамене на водительские права вас заставляют рулить вокруг конусов на площадке. Ну где водители "в реале" ездят по площадке с кучей конусов?
Задачки, даже совсем синтетические, отлично позволяют проверить, а может ли кандидат написать 10-20 строк более-менее приличного кода и объяснить алгоритм.
я помню сильно поспорил с интервьювером в одном месте когда он показал 'правильное' решение задачи (какойто синтетической где важно было иметь случайную последовательности и должно было обрабатываться быстро)
Поделитесь, пожалуйста, подробностями задачи и сути конфликта? Может вам сильно не повезло с интервьювером, а может вы что-то недопоняли.
DMGarikk
08.09.2021 14:49Во-перовых, не правда. Я, например, даю на интерьвю именно ту задачу, которую сам лично коммитил в прод.
ну а я не ваше интервью в виду имею собственно то
мне давали задачи вроде в стиле 'поменять местами значения в массиве', 'упорядочить простые числа' с всякими мозголомными 'фишечками' на 'подумать'Ну где водители «в реале» ездят по площадке с кучей конусов?
водители ездят вдоль домов где запарковано куча автомобилей, площадка с конусами — практически реальная симуляция такого случаяЗадачки, даже совсем синтетические, отлично позволяют проверить, а может ли кандидат написать 10-20 строк более-менее приличного кода и объяснить алгоритм.
я могу написать код за 15 минут, посмотреть на него, запустить пару раз… потом всё стереть и написать хорошо и 'правильно",
а требования 'надо чтобы у вас компилятор был в голове и вы выдавали сразу код начистую сразу, а лучше прям на бумажке, настоящий программист может писать на доске'… это уже изврат
я, блин, на сеньорскую должность собеседуюсь… в самом то деле
==Можете поделиться подробностями задачи и сути конфликта?
задача была как раз в стиле 'гугла/яндекса', чистая синтетика на сообразительность.
в стиле 'напишите сортировку, не используя ф-ции языка… и это тоже нельзя… и это… и set использовать нельзя… и вот так тоже нельзя'
wataru
08.09.2021 15:14а требования 'надо чтобы у вас компилятор был в голове и вы выдавали сразу код начистую сразу, а лучше прям на бумажке, настоящий программист может писать на доске'… это уже изврат
Нет таких требований. По крайней мере в гугле и яндексе. Есть требование рассказать интервьюверу ваше решение словами, и когда он видит, что вы придумали правильное решение — вас попросят начать кодить. Как раз, чтобы вы не писали то, что потом придется стереть. И не надо никакого компилятора в голове. Плюс интервью на бумажке, что вы можете напрочь забить даже на стандартное АПИ. Код не надо компилировать, опечатки и ошибки прощаются. Сейчас всё проводят в простых редакторах, так что и минусов от бумажки не осталось, а плюсы — остались. Например, если кандидат не помнит, какие там параметры у lower_bound и что оно там ищет — самое левое >= или самое правое <, то я или подскажу или попрошу кандидата в комментарии написать, что он там ожидает от этой функции. И никаких "баллов" за это не снимается. Я не могу говорить за всех интервьюверов во всех фирамах, но, по карйней мере в гугле — это в гайдах.
задача была как раз в стиле 'гугла/яндекса', чистая синтетика на сообразительность.
в стиле 'напишите сортировку, не используя ф-ции языка… и это тоже нельзя… и это… и set использовать нельзя… и вот так тоже нельзя'И где там случайность? Пока кажется, что вы не придумали быстрое решение и стали цеплятся к чему-то совершенно не важному, оправдывая свое медленное решение.
DMGarikk
08.09.2021 16:42Пока кажется, что вы не придумали быстрое решение и стали цеплятся к чему-то совершенно не важному, оправдывая свое медленное решение.
потому что я по опыту уже, решаю задачи с точки зрения бизнеса, а не генерирую какойто синтетический код в вакууме. я вообще ниразу никогда за карьеру не писал код 'чисто по ТЗ, думать не требуется'
если я вижу что в задаче какойто бред = я уточняю, если постановщик задачи не может адекватно сформулировать зачем этот бред нужен — я эскалирую вопрос выше
кхм…
честно говоря я просто перерос рядовую должность программиста, и на меня сильно действуют уже менеджментские вопросы разработки в принятии решений.
и я на самом деле рад что из-за того что сеньорские собеседования зачастую не включают в себя подобные вопросы, за исключением некоторых странных (с моей точки зрения) компаний
wataru
08.09.2021 17:24потому что я по опыту уже, решаю задачи с точки зрения бизнеса, а не генерирую какойто синтетический код в вакууме. я вообще ниразу никогда за карьеру не писал код 'чисто по ТЗ, думать не требуется'
Распространю это на аналогию с экзаменом на вождение.
Вас просят параллельно припарковаться между этими конусами на экзамене, вы сбиваете конус и проезжаете еще 3 метра. Потому что в реальном вождении ни разу не сталкнетесь с "припаркуйтесь именно тут". И вообще, то место, которое вы выбрали — оно лучше — там тень. Чего машину на солнце жариться оставлять? А конусы — это же не машины с домами, они даже машину не поцарапали.
DMGarikk
08.09.2021 17:50-1Потому что в реальном вождении ни разу не сталкнетесь с «припаркуйтесь именно тут».
сталкиваюсь сплошь и рядом, у меня авто таких габаритов что оно очень часто помещается 'только тут и нигде больше'
вообще для автомобилей это очень частый кейс, особенно в центре Москвы кстатиА конусы — это же не машины с домами, они даже машину не поцарапали.
конусы запросто машину поцарапают и бампер оторвут, смотря как наехать
wataru
08.09.2021 15:22И простите за 2 ответа, итак длинные комменты получились.
мне давали задачи вроде в стиле 'поменять местами значения в массиве', 'упорядочить простые числа' с всякими мозголомными 'фишечками' на 'подумать'
водители ездят вдоль домов где запарковано куча автомобилей, площадка с конусами — практически реальная симуляция такого случаяНу вам так сложно представить, что вам придется менять местами числа в массиве, упорядочить удовлетворяющие каким-то критериям числа в массиве?
Конусы — симуляция домов с припаркованными машинами. Простые числа — симуляция какого-то бизнес критерия.
DMGarikk
08.09.2021 17:10-1Ну вам так сложно представить, что вам придется менять местами числа в массиве, упорядочить удовлетворяющие каким-то критериям числа в массиве?
ниразу не сталкивался с такой задачей, а работал я в разных сферах. от корпоративных сайтов до банковских процессингов.
А уж пузырьковую сортировку (рукалицо) которую спрашивают помоему у каждого второго, так вообще никто врукопашную не делает
И задачи 'надо поменять местами две переменные не используя третью переменную' — это чисто на сообразительность и умение решать всякие ребусы
wataru
08.09.2021 17:22А уж пузырьковую сортировку (рукалицо) которую спрашивают помоему у каждого второго, так вообще никто врукопашную не делает
Кто ее спрашивает?! Где?! В FAANG точно не спрашивают.
DMGarikk
08.09.2021 18:00-1В FAANG точно не спрашивают.
вы были на всех собеседованиях со всеми интервьюверами всех компании FAANG?
Я вообще прихожу к выводу что вы както необоснованно считаете свое мнение на способы и виды проведения интервью — единственно верным, хотя это не может быть верным просто потому что так не бывает.
Весь этот тред, вы доказываете что ваша точка зрения единственно истинна и верна, при этом вы аппелируете только к своим личным соображениям 'как это должно быть'.
Но у меня какието сомнения что вы сколько-либо известный рокстар в программировании чтобы ваше мнение действительно имело бОльший вес чем чье либо еще.
наш с вами опыт, я так понимаю, в корне различен, мы с разных сторон пришли в отрасль, я в свое время (вне ИТ отрасли) вообще ушел в глубокий менеджмент и бизнес, что наложило на меня серьезный отпечаток на мышление… и это мне кстати очень сильно помогает на собеседованиях…
значит ли что я плохой программист потому что для меня проблема пройти техинтерьвю на джуна-миддла? сомневаюсь, я без проблем прохожу интервью на сеньора (для меня вообще не проблема найти работу, хотя я знаю людей которые месяцами ходят по интервью и не получают офферов и запрошенных бенефитов и по многим скиллам они круче меня) хотя по вашим критериями — вы меня запросто завалите.
по этому у меня и возникает негодование, завалить человека на синтетических тех.вопросах — это ошибка организации процесса интервью, а не положительный отсев бездарностей.
acklamterrace
27.07.2021 00:31Ну я только могу сказать что по моему опыту это совсем не так. Вы сами давно на интервью были хоть где-нибудь?
wataru
27.07.2021 13:28+1Был на прошлой неделе. Повотрюсь — не спрашивал никаких заумных алгоритмов. Самая сложная часть в решении — бинпоиск.
Автор статьи тоже никаких заумных задачек не привела в примерах. Раз уж у вас другой опыт, то дайте что ли пару ссылок на тот же leetcode на задачи, где нужен какой-то заумный алгоритм хотя бы с двумя фамилиями в названии.
faiwer
28.07.2021 12:52заумным алгоритмом с тремя фамилиями в названии.
У автора в заметках мелькает "Дерево Фенвика". Мне лет 5 назад было страшно сложно разобраться в этом. "Смотрю в книгу — вижу фигу". Вроде слова русские, а смысла не вижу. В итоге разобрался, но осадок остался. Такое на собеседовании могут спросить? Или достаточно обычного бинарного дерева отрезков?
wataru
28.07.2021 13:30+1Во-первых, не требуют писать такие струтктуры данных. Обычно, самое заумное, что у вас будет — это std::set (писать его не надо, можно использовать стандартную реализацию). Если в задаче можно использовать дерево отрезков, и вы про него скажете — вам, конечно, поставят плюс, но скорее всего попросят его не писать, ибо есть более простые в реализации решения.
Во-вторых, дерево отрезков умеет делать все, что и дерево фенвика и даже больше. Правда, занимает в 2 раза больше памяти. Если бы действительно была задача, которую нужно решать деревом фенвика, за дерево отрезков вам бы минусов никаких не поставили.
PsyHaSTe
31.07.2021 00:47Что насчет задачек из cracking code interview? Там есть весьма зубодробительные.
Что насчет амазонской задачки "Выберите из списка точек ближайшую к некоторой выбранно (x,y)"? Окей, она простая, а что насчет follow-up "Выберите k ближайших точек"? Судя по тому, что я читал в решениях этой задачки - нужно уметь построить rtree и дальше в нем искать. А я вот не умею в алгоритмы такого уровня - неинтересно, как-то.
Я вот слабо представляю как это без подготовки решать. А тратить месяцы жизни ради шильдика "взяли на работу в фаанг" - ну хз..
wataru
31.07.2021 12:09Что насчет задачек из cracking code interview?
Ну, если бы в книге все задачи были чуть сложнее fizz-buzz она бы не имела смысла. Может, когда-то давно, когда только начали такое интервью проводить и пытались нащупать нужный уровень спрашивали и зубодробительнейшие задачи. Сейчас, по крайней мере, в моем окружении — такого нет.
Что насчет амазонской задачки "Выберите из списка точек ближайшую к некоторой выбранно (x,y)"?
Плохая задача на мой взгляд. Сильно нужно знание конкретных не очень популярных геометрических структур данных. Не надо такое спрашивать, если кому-то попалась — очень неповезло.
Wan-Derer
20.08.2021 09:17Сильно нужно знание конкретных не очень популярных геометрических структур данных
"Квадрат гипотенузы равен сумме квадратов катетов". Или вы о каких-то других точках?
wataru
20.08.2021 10:47Похоже, что в задаче список точек фиксирован и надо быстро искать ближайшую к заданной. Судя по упоминанию rtree. Если же это не так, то задача равна стандартной "найдите k максимумов в массиве". Эта задача, действительно простая при минимальных знаниях computer science. Я ее даже спрашивал несколько лет назад. Решение с кучей на k элементов было достаточно.
Wan-Derer
20.08.2021 11:05заводим массив на k элементов;
заполняем k первых элементов, но отдельно храним максимальный;
если следующий меньше максимального, то максимальный выкидываем и этот вставляем, ищем в массиве тот, который сейчас стал максимальным;
так проходим до конца выборки.
Можно слегка оптимизировать. Если длина одного из катетов больше максимальной длины, сразу переходим к следующему. Всё считаем в квадратах чтобы избежать операции извлечения корня.
Так?
wataru
20.08.2021 11:23Не совсем. Нужно хранить не массив, а кучу на максимум, в которой будут k минимальных пока элементов. Если новый меньше максимума — выкидываем его и кладем новый в кучу. Можно использовать существующие std::priority_queue или std::set — не надо писать кучу.
Проблема вашего метода в том, что после выкидывания максимального элемента в мелком массиве надо найти новый максимальный. Это будет O(k) на каждое новое расстояние и суммарно даст O(nk). Когда как куча сразу найдет при изменении новый максимальный за O(log k).
Wan-Derer
20.08.2021 12:46Мне кажется, Set не подойдёт. Он же хранит только уникальные значения, а задача не запрещает иметь равноудалённые точки.
куча сразу найдёт при изменении новый максимальный
Само собой ничего же не происходит, КМК. Отсортированная коллекция будет при удалении/добавлении элемента пересортировываться (да, быстро, т.к. она уже отсортирована, но всё же). Лучше тогда один раз отсортировать коллекцию при достижении k элементов, а потом просто руками удалять элемент с одной стороны и добавлять с другой (должны подойти ArrayList, LinkedList, Queue).
wataru
20.08.2021 12:58Мне кажется, Set не подойдёт. Он же хранит только уникальные значения, а задача не запрещает иметь равноудалённые точки.
Вам же не расстояние в циферках нужно, а сами точки. Очевидно, что в set и priority_queue вы будете класть пары {расстояние, индекс точки}.
Лучше тогда один раз отсортировать коллекцию при достижении k элементов, а потом просто руками удалять элемент с одной стороны и добавлять с другой
Нет. Это не работает. Ну вот, допустим, у вас в коллекции {1,2,4,5,6}. Максимум = 6. Пришло число 3. 3 < 6, значит 6 выкидываем. Нельзя 3 добавлять с другой стороны! Чтобы оно оставалось отсортированным — надо 3 вставляеть в центр.
Wan-Derer
20.08.2021 07:15Выберите k ближайших точек
для каждой точки вычислить расстояние;
занести в массив точки вместе с расстояниями;
отсортировать массив;
взять первые k элементов.
Профитт?
PsyHaSTe
20.08.2021 13:13У вас два массива точек. Нужно из второго массива выбрать k точек, ближайших к любой точке из первого (если я правильно помню задачу).
Andrey_Solomatin
25.07.2021 23:49+1Более того, если ты по факту уровня архитектора, то для тебя важнее понимать скорее для каких задач нужны какие деревья (и нужны ли они вообще), чем уметь инвертировать бинарное дерево.
Кстати это как раз задачка из разряда, не знал, но придумал. Это почти идеальная задача, в том плане, что она действительно проверяет как человек думает.
К сожалению, таких задачек очень мало, в основном уже ожидается какая-то база решений, без которой на таких собесах будет сложно. Например, если не знать, что разбор строки в число с плавающей точкой надо решать через машину состояний, то с регулярками можно уйти далеко и мимо.questor
08.09.2021 10:39Да, и это та штука, которую я называю "насмотренностью", примерно как у врачей: посмотрел мельком на пациента, один-два вопроса - и диагноз в кармане. И нет, это не рокет сайенс, не доктор Хаус, а просто обычный терапевт в городской больнице.
vics001
25.07.2021 22:23+6Процесс отбора в Google расчитанных на молодых студентов, людям с опытом уже лучше и не подаваться туда или подаваться на другие позиции. Такая позиция компании и ее можно не любить, но необходимо принять.
acklamterrace
26.07.2021 18:47Да, похоже есть два пути в Гугл: 1) через internship, чтобы Гугл из вас вырастил сотрудника 2) быть суперзвездой в чем-то, чтобы Гугл сам за вами прибежал с оффером "впишите свою зпл".
0xd34df00d
26.07.2021 03:02-1Я вот читаю все эти статьи про интервью и не могу понять, в чём проблема? Там же, по крайней мере, задачи, которые на самом деле гиперхалявные (ну, то есть, халявные настолько, что ты начинаешь думать «слишком просто, не упустил ли я чего?»), которые ИМХО любой человек, не только решавший бизнес-задачи (что бы это ни значило), но хоть немного писавший кода чуть сложнее перекладывания жсонов из одного эндпоинта в другой, может придумать и решить (иначе я не понимаю, чем он занимается в программировании).
Не теоретизируюСобеседовался в гугл — получил оффер, на трёх из пяти раундов у интервьюверов кончались вопросы до окончания времени интервью, и мы говорили о погоде.
Собеседовался в ещё две компании из упомянутых топикстартером — тоже получил офферы.
Собсна, единственный раз, когда не получил оффер — когда только начинал интервью в зарубежные компании, общался с 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не нужно, но для упомянутых ограничений это всё не требуется и нужно только для того, чтобы заполнить остаток времени.
Alex_ME
26.07.2021 04:22+2В худшем случае у
replaceсложность O(N) от размера строки (ее придется раздвинуть). И Ваш код имеет сложность O(N^2) (худший случай — замена каждого символа). Правда, по условиям задачи, меньше (замен до 100, длина до 1000).Вообще, ограничения очень маленькие и работает тривиальное решение. Я не знаю, можно ли снизить асимптотику. В голову первым делом приходит только сначала рассчитать сдвиги и двигать строку кусками с конца, чтоб не передвигать уже сдвинутое.
0xd34df00d
26.07.2021 04:34+4В худшем случае у replace сложность O(N) от размера строки (ее придется раздвинуть).
Это ровно то, о чём я написал в последнем абзаце: для упомянутых ограничений это всё не имеет смысла, и даже такое тупое решение работает, ээ, faster than 100.00% of C++ online submissions.
Когда я собеседовался в гугл и меня спросили задачу, которую можно было решать либо тупо за квадрат с их любимыми очередями, либо умно за меньшую асимптотику с kd-деревьями (там была задача, сводившаяся к жадному поиску ближайших точек, и в тупом решении вы рассчитываете все попарные расстояния и выбираете следующее наименьшее, а в умном, ну, короче, умнее), как только я заикнулся о деревьях, интервьюверша меня осекла и сказала, что не, не надо, это слишком сложно, моего ответа более чем достаточно.
Я не знаю, можно ли снизить асимптотику. В голову первым делом приходит только сначала рассчитать сдвиги и двигать строку кусками с конца, чтоб не передвигать уже сдвинутое.
Если хочется заморочиться, то вообще зачем что-то двигать? Опять сортируете индексы с конца, и результирующую строку заполняете с конца. Для каждого индекса вы знаете начало и конец в результирующей строке — копируете из исходной нужный кусок, копируете
targets[i], повторяете.Получается вполне себе линейный алгоритм.
PsyHaSTe
31.07.2021 00:51+1Когда я собеседовался в гугл и меня спросили задачу, которую можно было решать либо тупо за квадрат с их любимыми очередями, либо умно за меньшую асимптотику с kd-деревьями (там была задача, сводившаяся к жадному поиску ближайших точек, и в тупом решении вы рассчитываете все попарные расстояния и выбираете следующее наименьшее, а в умном, ну, короче, умнее), как только я заикнулся о деревьях, интервьюверша меня осекла и сказала, что не, не надо, это слишком сложно, моего ответа более чем достаточно.
Видимо остается признать, что большинство разрабочтиков тупые жсонперекладыватели (включая меня) и им это реально сложно.
PsyHaSTe
31.07.2021 00:51А ещё в новой версии хабра нет кнопки "редактировать", прекрасно.
0xd34df00d
31.07.2021 03:35+1Я вообще сразу старую обратно включил, новая — глючное поделие, ИМХО сделанное только ради того, чтобы что-то сделать.
Vilaine
26.07.2021 04:26+5У меня ушло больше 10 минут, чтобы получить "Success" на литкоде (правда, на выбранном ЯП вообще почти не пишу, надо было гуглить). Это скорее уровень Easy, судя по моему опыту на этом же самом литкоде, так что вы или автор неудачно выбрали пример. Но я вижу, что можно очень серьёзно заморочиться над производительностью и, например, не успеть сообразить про то, как именно сделать всё в один проход, если спросят так сделать на собеседовании.
Правда, автор статьи не упоминает про то, что нужно морочиться с оптимизацией на литкоде (когда тестов под это нет). Но есть там на литкоде задачи сложнее, на которые нужно тратить много времени, задачи на смекалку, когда нужно догадаться, как решать. Действительно, навык решения таких задач на скорость нужно тренировать, и он снижается без тренировок. Плюс алгоритмические задачи. Я, к примеру, не помню какое-нибудь балансирование прямо чтоб сразу написать, нужно вспоминать принципы работы RB или AVL, а на собеседовании это плохо получается.
В работе эти все навыки при этом в целом не нужны. Мне почему-то кажется, что те же разработчики после нескольких лет работы в FAANG не пройдут своё же интервью (то, о котором так много пишут).
0xd34df00d
26.07.2021 04:41+4Но я вижу, что можно очень серьёзно заморочиться над производительностью и, например, не успеть сообразить про то, как именно сделать всё в один проход.
Можно, конечно. Правда, как раз люди, 18 лет решающие бизнес-задачи, по идее должны бы даже не то что знать, а ощущать, когда заморачиваться стоит, а когда решения в лоб хватит.
А так — да, эту задачу вообще можно существенно усложнить в куче разных аспектов, не только производительностью — для начала попробуйте аккуратно сформулировать, что значит, что подстановки не перекрываются, и доказать, что ваше решение корректно. Или там, не знаю, сформулировать, когда результат инвариантен относительно перекрывающихся подстановок, или когда он всегда будет завершим для них, или… Ну вы поняли идею.
Правда, автор статьи не упоминает про то, что нужно морочиться с оптимизацией на литкоде (когда тестов под это нет).
ИМХО это вопрос вашего личного чувства прекрасного, и того, как ваше решение вписывается в решения других людей (если их достаточно много).
Я, к примеру, не помню какое-нибудь балансирование прямо чтоб сразу написать, нужно вспоминать принципы работы RB или AVL, а на собеседовании это плохо получается.
В гугле достаточно вспомнить, что такие вещи есть, написать с нуля RB/AVL/etc не требуют. А если где-то требуют, бегите оттуда, потому что да, вспоминать это всё очень неприятно.
По крайней мере, я, когда читал книжку Окасаки, свою реализацию RB-деревьев не то что написал, а формально доказал на идрисе, но уже через месяц после этого едва бы вспомнил не то что на интервью, а пусть даже за час в спокойной обстановке дома. На интервью бы сказал «ну, там есть красные узлы, есть чёрные узлы, есть инвариант, кто какого цвета детей может иметь, есть процедура балансировки, его поддерживающая, и благодаря этому всему кратчайший путь не более чем в два раза короче длиннейшего», и всё.
Vilaine
26.07.2021 04:59Правда, как раз люди, 18 лет решающие бизнес-задачи, по идее должны бы даже не то что знать, а ощущать, когда заморачиваться стоит, а когда решения в лоб хватит.
Тут неважно, что ощущаете вы, важно, что от вас ожидает интервьювер =D Уж тем более в искусственных задачах.
0xd34df00d
26.07.2021 05:09+4Так это ж стандартная стратегия, работающая далеко не только на интервью: выкатить
MVPсамый тупой, но корректный алгоритм, и посмотреть, какова будет реакция общественности (или стейкхолдеров, или интервьювера).
DMGarikk
26.07.2021 12:26+4вот уж точно, было у меня недавно одно такое интервью, я буквально затроллил интервьювера упирая на некорректность таких синтетических задач в том виде как они поставлены… вплоть до того что он начал уже блеять 'ну мы сейчас в отрыве от бизнес вопросов решаем, даватй абстрактно обсуждать'… хотя по факту в одной из задач был вариант 'надо перемешать список случайным образом'… и ответ который который интервьювер считал более верным — был категорически некорректен с точки зрения 'случайности' и в реальных бизнес задачах за такое надо отрывать не то что руки, но и ноги, уши и другие части тела… но типа 'это же быстрейший способ'… ога ога… вот кто значит пишет софт с ошибками в криптографии, олипиадники с задачами на скорость… и так было почти по всем задачам.
p.s. оффер я не получил, но туда им и дорога со своими приколами на такую тупую мозголомку
Beo
26.07.2021 17:23+3Если целью является трудоустройство, то троллинг интервьювера странная затея. Шанс, что он примет вас за великого гуру может быть ниже, чем шанс, что напишет в отзыве негатив
DMGarikk
26.07.2021 19:32+1троллинг — не в том смысле что я специально хотел посмеятся, а в том что я на работе решаю бизнес-задачи, а мне дают однозначно некорректные входные данные и хотят странного, я на это и указываю
Если целью является трудоустройство
у меня нет цели пойти работать в первую попавшуюся контору, славабогу рынок ИТ всётаки большой, и hr-ы несколько охренели заваливать предложениями в последнее время
Я уже натыкался один раз когда пройдя такое интервью попал в команду где я был полностью не совместим с тимлидом по принципиальным вопросам программинга… теперь мне проще отказаться заранее если контора сразу начинает хотеть странного и не может объяснить зачем ей это хотеть
0xd34df00d
26.07.2021 05:09+2Впрочем, вспомнилось тут одно собеседование в криптоблокчейн на всякой функциональщине, где всё началось с вопроса о том, хорошо ли
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, вот это всё, при этом я названий не помнил, а называл идеи), пообсуждали линейные типы, которые позволяют иметь типа-мутабельные вещи в ФП со всеми ништяками, а потом, так как я упомянул про кеши, начали обсуждать, какую проблему вообще решают кеши, почему кеш не может быть размером с ОЗУ даже с бесконечным транзисторным бюджетом, и в итоге как-то дошли до обсуждения различий между фазовой и групповой скоростью света.
Вот это было офигенно. Души в этом куда больше, чем в среднем фаанг-интервью. Ну и ощущаешь себя полноценным фуллстеком после этого, от типчиков и линейной логики до физики.
Vilaine
26.07.2021 05:57+1Души в этом куда больше
Да, но там, видимо, было много не совсем интервью. У меня есть опыт организации технических собеседований и по нему для большей объективности нужно поменьше души и побольше стандартизированных заданий и вопросов.
дружественность к кешу тоже так себе
Довольно очевидно, почему это не словарь, а однонаправленный связанный список со всеми вытекающими проблемами, даже для начинающего =D По сравнению со многим остальным, что идёт дальше. Из всех контайнеров я знаю только про finger tree и было бы интересно, что такое может позволять реализовывать что-то вроде словарей.
0xd34df00d
26.07.2021 09:33+1Да, но там, видимо, было много не совсем интервью. У меня есть опыт организации технических собеседований и по нему для большей объективности нужно поменьше души и побольше стандартизированных заданий и вопросов.
Да, это была совсем мелкая компания с довольно малым числом людей. В такие места собеседования наименее заскриптованные и наиболее приятные — но, как вы пишете, весьма необъективные.
Довольно очевидно, почему это не словарь, а однонаправленный связанный список со всеми вытекающими проблемами, даже для начинающего =D
Ну тут тоже есть что обсудить, кстати. Например, что такое «словарь», что такое денотационная семантика, и так далее (а с
delete, реализованным как соответствующийfilter, эта структура неотличима от обычной мапы, кроме как по производительности).
Alex_ME
26.07.2021 11:26линейные типы, которые позволяют иметь типа-мутабельные вещи в ФП со всеми ништяками
Есть ли у вас направление живительного пинка в гугл, по которому про это можно узнать подробнее? Ну, кроме wiki
0xd34df00d
26.07.2021 18:28+2Смотря в каком направлении. Если вам интересен прям матан за этим всем — есть классическая
книжказапись лекций Жирара Proofs and types (но её примерно с восьмой главы очень тяжело читать). Если интересны более прикладные свойства этих систем типов, можно почитать Advanced Topics in Types And Programming Languages, там первая глава как раз про substructural type systems.
csl
26.07.2021 07:46Оставляли Feedback для добавления Haskell: Please provide Haskell language support! - LeetCode Discuss .
dimskiy
26.07.2021 08:42+8Аккуратнее со шторами - можно подпалить ярким нимбом ))))
0xd34df00d
26.07.2021 09:36+3Да чего сразу нимб. Просто такое впечатление, что в разных вселенных живём — люди решают какие-то бизнес-задачи, а я до сих пор не понимаю, что это такое, где эти задачи обитают, и где я свернул в своей жизни не туда, что они мне не попадаются. Зато, с другой стороны, я не вижу никаких проблем в этих собеседованиях, а люди репостят известный твит создателя homebrew.
Олсо, поэтому у меня дома одни жалюзи.
Скрытый текстОлсо, выражать мнение подобным образом полезно по ряду причин, одна из которых — люди обычно так больше желают найти проблемы в том, что ты делаешь, а это продуктивнее для роста.
na9ort
26.07.2021 10:30+20Добрый день.
Слушай, Чел (0xd34df00d), я читаю хабр на постоянной основе уже несколько лет подряд, и постоянно натыкаюсь на твои посты/комментарии.
Из чего могу сделать вывод, что ты какой-то адово скиловый разработчик. Прям Адище!
Я думаю, что ты пройдёшь собес куда захочешь, и на своих условиях. Так что
иди выёбывайся в свой двордай нам, обычным смертным, пообсуждать тривиальные вопросы)wataru
26.07.2021 13:02+1Но тут не просто выпендреж в вакууме, это ответ на коммент о "18 годах опыта". Действительно, приведенные задачи имеют не такие уж и страшные решения для разработчиков с 18-ю годами опыта.
euroUK
26.07.2021 13:14+215 лет опыта как раз-таки позволяют знать себе цену без решения сотни задач с литкода. Никто не говорит, что там что-то божественно сложное, есть вопрос зачем это надо и как это свидетельствует о вашем умении быть хорошим инженером?
Dolios
26.07.2021 16:14+1Зарплата? Есть кто-то, кто платит как гугл и проводит собеседования по-другому?
cebka
26.07.2021 16:25+1Хедж-фонды и трейдинг вообще платят намного больше FAANG. Но собеседования еще более утомительные, а работа, по сути, ничем не лучше, чем толкать на улице кокс в морально-этическом плане.
0xd34df00d
26.07.2021 19:18От хедж-фонда зависит.
У меня было собеседование в один мелкий, и оно было офигенное. С одним чуваком мы написали собственный плюсовый
std::anyв режиме «а теперь добавим ещё и такое требование». С другим — свой парсер жсон-подобного языка на комбинаторах. С третьим — пообсуждали, как бы делали распределённую систему в HFT-условиях, но когда надо учитывать данные с других бирж, откуда свет только идёт несколько десятков миллисекунд.Работа тоже зависит. Столько интересных задач по оптимизации производительности и написанию хардкорного сиплюсплюса с шаблонами у меня больше не было нигде. С другой стороны, когда в одной переговорке собирается с десяток людей с PhD, и вы все дружно обсуждаете, как бы скинуть ещё пару дюжин наносекунд с латентности, становится как-то грустно. Но не назвал бы это толканием кокса в морально-этическом плане.
euroUK
26.07.2021 16:28+1Есть те, кто платят 80 процентов от гугла, но относятся как к людям.
Зарплата это такое дело, начиная с какого-то размера больше денег это плюс, но не определяющий фактор. Я лично трачу сейчас 1/6 своей зарплаты. Могу найти более оплачиваемую работу? Вероятно. Вопрос зачем?
Dolios
26.07.2021 17:20+3но относятся как к людям.
Так в гугле отношение к работникам очень хорошее. Я не считаю требование показать, что ты можешь решать задачи, каким-то запредельным или унижающим человеческое достоинство. Предложите свой способ отбора 1 человека из 100.
Зарплата это такое дело, начиная с какого-то размера больше денег это плюс, но не определяющий фактор. Я лично трачу сейчас 1/6 своей зарплаты. Могу найти более оплачиваемую работу? Вероятно. Вопрос зачем?
А для кого-то это определяющий фактор. Например, чтобы купить жилье такое, какое хочешь в том месте, в котором хочешь.
0xd34df00d
26.07.2021 19:13+3позволяют знать себе цену без решения сотни задач с литкода
Я не решил ни одной задачи на литкоде до вчерашнего дня. Да и к интервью в фаанги я как-то особо не готовился (максимум подготовки, который был в моей жизни — перед интервью в крупный околобанк под руководством знакомого с чувством стиля купил себе пиджак, которого у меня не было как класс в гардеробе, чтобы презентабельным видом вместо дырявых футболок с митол-принтом выбить зарплату побольше).
есть вопрос зачем это надо
Зачем что именно надо?
Серьёзно, в чём проблема с решением подобных задач? 10 человек моему комменту выше уже поставили минус, но ни один из них не написал, чем же в программировании надо заниматься 18 лет (или хотя бы 5 лет), чтобы не мочь решить такую задачу. Ну, то есть, достаточно было бы хотя бы раз в жизни столкнуться с задачей, которая из-за порчи индексов требовала прохода по массиву с конца.
Ну либо эти люди вообще не пишут код, в этом тоже нет ничего плохого — просто тогда надо идти не на софтваре девелопера в гугл, а на бизнес-аналитика или там, не знаю, фасилитатора.
Ещё меня удивляет такое показное отношение «да! я не могу даже такую задачу на алгоритмы, но это всё не нужно, и вообще вот твит автора homebrew!», и я не очень понимаю ценности, стоящие за таким отношением, ну да ладно.
wataru, к слову, если человек на собеседовании выдаст за отведённые на задачу 30 минут даже такое прямолинейное решение, это ведь по гайдлайнам всё равно будет hire, пусть и не strong hire, как если бы было с разговором о способах улучшить?
wataru
26.07.2021 19:22Почти. За 30-35 минут написать такое решение и хотябы после подсказок в общих чертах словами описать как его можно было бы улучшить — это был бы hire. На strong hire — написать за время интервью линейное решение.
faiwer
28.07.2021 13:45+1но ни один из них не написал, чем же в программировании надо заниматься 18 лет (или хотя бы 5 лет), чтобы не мочь решить такую задачу
Минус не ставил, но ответ очевиден. Просто избегать инженерных задач. Люди талантливо избегают сложных задач и висят на одном и том же уровне. А там где решение нужно родить — пишут первое что приходит в голову, пусть даже оно решает не ту задачу, решает её плохо. Потому что главное уметь свою проблему подать начальству так, чтобы проблема была не твоя, а, как бы, сама по себе. И это в принципе естественно для человека. Избегать сложностей и перекладывать ответственность.
Что именно в этом удивляет? Мы зачем-то наделяем программистов такими качествами как "математический склад ума", "логика", "аналитический ум". Тогда как по факту обычный программист это обычный человек. Не небритый худощавый гик с засаленным свитером, а [define a normal person].
К тому же если речь идёт об 18 годах, то велик шанс, что человек уже во многом и то что помнил забыл, сидя на бесконечных совещаниях, и почти не прикасаясь к коду.
amakhrov
26.07.2021 21:12+2быстрее 100% других решений
А это в leetcode бага такая. Он почему-то не умеет нормально измерять время работы решений на C++. На других языках такой проблемы не замечал ни разу. А на C++ - чуть менее, чем всегда.
edo1h
09.09.2021 00:47На других языках такой проблемы не замечал ни разу. А на C++ — чуть менее, чем всегда.
скопипастил решение на го, которое показывало 0мс, получил 4мс )
nlog
27.07.2021 00:44Кому-то везет, кому-то не очень. Иногда попадаются задачи сложнее, вроде этой https://leetcode.com/problems/find-the-shortest-superstring/ причем на этапе online assessment. Да-да, NP-hard даже не доходя до onsite.
wataru
27.07.2021 13:51-1И чем эта задача сложна? Там до 12 слов. Это тупо на кодинг задача. Никаких алгоритмов — тупое наивное решение (перебор всех перестановок). Хоть рекурсивно, хоть std::next_permutation. Только один момент — надо додуматься, что если слово содержится в другом целиком, то его надо выкинуть.
Можно заработать outstanding в графе алгоритмы, если сказать, что задача сводится к задаче коммивояжора, и упомянуть NP.
Причем, на hire достаточно какими-нибудь std::string::find пользоватся. Потом уже будет обсуждение, а как можно лучше всего искать вхождение строк, если бы они были длинные (тут можно блеснуть знаниями Ахо-корасика, суффиксных деревьев и других алгоритмов на строки. Естественно, писать это на интервью не надо). Или как быстро подсчитать общую часть на стыке двух строк (использование бора/trie). Но эти все рассуждения только на strong hire нужны.
Задача была бы сложнее, было бы там до 25 строк. Тут уже ожидалось бы динамическое программирование по маске уже посещенных вершин. Стандартная тоже вещь уже, но это я бы тоже хотел только на strong hire.
0xd34df00d
27.07.2021 19:07Только один момент — надо додуматься, что если слово содержится в другом целиком, то его надо выкинуть.
Не надо, это часть условия.
Тут для самого прямолинейного решения уже надо садиться и думать, но начерно я бы строил мапу
String → [ContextCandidate], гдеContextCandidate— это тройка из слова слева, слова справа и, потенциально, дополнительных букв в середине между двумя словами, таких, что соответствующий ключ является подстрокой их конкатенации. То есть, получается отношение между ключом и тройками слов. Его как раз удобно представить в виде орграфа, где вершины — строки, а рёбра —ContextCandidateплюс соответствующие ключи мапы. Дальше вот оно сводится к задаче коммивояжёра, что вы, возможно, имели в виду.А вот как бы тут можно было делать вообще тупой перебор перестановок входных слов, учитывая возможность промежуточных дополнительных букв (для
words = [ "foo", "oto", "oof" ]оптимальное слово"footoof", не являющееся простой конкатенацией), я не знаю.
Antervis
27.07.2021 20:04Я бы решал как-то так: за "N^2 * M^2" (где M - средний размер строки) построить матрицу чисел совпадающих букв (сколько букв строки words[i] будет переиспользовано, если за ней поставить строку words[j]), потом в этой матрице находим максимальную перестановку (тот самый комивояжер, но можно решить перебором за N! через рекурсию), потом объединяем. Долго, уныло, но работать будет.
wataru
27.07.2021 20:35А мне показалось очевидным. Выкинули слова, которые целиком в других словах, потому что если найти строку, которая содержит все оставшиеся, то и выкинутые она тоже содержит. Но это дальше упростит решение.
Далее, вот перебрали мы перестановку слов. Берем первое слово целиком, а потом жадно как можно глубже всовываем следующее слово в предыдущее, так что суффикс левого слова совпадает с префиксом правого слова. Вот в вашем примере можно "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). Но это уже совсем высший пилотаж.
faiwer
28.07.2021 14:50Похоже на разумное рабочее решение. Только едва ли это можно описать так:
И чем эта задача сложна? Там до 12 слов. Это тупо на кодинг задача. Никаких алгоритмов — тупое наивное решение (перебор всех перестановок)
Ваше тупое наивное решение уже "hard". Подавляющее большинство программистов никогда не сталкивалась с задачами такой сложности (и никогда не столкнётся).
Вы пишете вам потребовалось 7 минут на кодинг. Мне вот 15 потребовалось на простой перебор разной перестановки слов с рекурсией… Даже без оптимизаций. Чтобы потом понять что это нифига не сработает, т.к. есть решения где строка не состоит из поставленных рядом слов.
Попадись мне такая задача на собеседовании я бы слился, 100% :) Ну не знаю, может быть это я такой тупой. Я в состоянии её решить, но точно не за час. Особенно если надо это обсуждать голосом в слух на иностранном языке. У меня не 18 лет опыта, но 13 уже есть.
wataru
28.07.2021 15:00Чтобы потом понять что это нифига не сработает, т.к. есть решения где строка не состоит из поставленных рядом слов.
Нет же. Это правильное решение у вас было. Я же выше доказал, что можно именно так и искать — ставить слова рядом, максимально пересекая их.
faiwer
28.07.2021 15:15Да, но я их не пересекал. Я просто сделал перебор всех возможных перестановок. Можно, конечно попробовать оптимизировать это решение путём дополнительного цикла на в-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);Честно говоря в целом писать код на скорость это то ещё удовольствие. На него потом смотреть страшно. Понимаешь что можно всё так на рефакторить, что его потом родная мама не узнает. Но некогда. Надо успеть родить что-то что хотя бы функционирует :)
faiwer
28.07.2021 17:12Написал "тупое наивное решение в лоб". Без оптимизаций не работает. Оптимизировал на 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); }wataru
28.07.2021 17:42+1Это JS? Я вообще не представляю, как вы на нем программируете, там совершенно безобидные вещи замедляют его в десятки раз. Но у вас проблема не в этом.
Попробуйте, как я сделал — сначала в матрицу подсчитать для каждой пары слов, как глубоко можно одно в другое засунуть с конца. Потом в переборе не перебирать shift, а брать уже известный максимальный. У вас там проблема как в рекурсивном подсчете чисел фибонначи — слигком много веток.
Например, если есть слова "caaaaaaaa" и "aaaaaaab" — тогда вы запустите весь перебор с оставшимеся словами при "caaaaaaaaaaaaaab", "caaaaaaaaaaaaab", "caaaaaaaaaaaab"… А если еще есть варианты "daaaaaaaaa", "aaaaaaaaad", то все варианты выше домнажаются на все варианты потом. Т.е. у вас не n*n! операций при переборе а n*n!*L^n.
Единственная оптимизация, которую вы по сути должны сделать, это внитри функции check для каждого слова запускать ровно одну check дальше. Зачем вам перебирать варианты с разным shift? нужен только один максимальный же. Раз слова в друг друга не вкладываются, следующее слово вы глубже текущего всеравно не пересечете. Значит если вы можете текущее слово поглубже запихать, нет никакого смысла этого не делать.
faiwer
28.07.2021 17:59Попробуйте, как я сделал — сначала в матрицу подсчитать для каждой пары слов, как глубоко можно одно в другое засунуть с конца.
Ага. Всё так. Это следующая оптимизация. Не считать одно и тоже для одних и тех же сочетаний.
Раз слова в друг друга не вкладываются, следующее слово вы глубже текущего всеравно не пересечете.
Вот это очень неочевидная штука (для меня). Мой мозг пытается придумать такой вариант когда для слов А и Б есть такое слово С, когда длина C > длины Б, и при этом только правильная расстановка слова Б внутри слова А, даст совпадение с префиксом слова А.
Аааа. Понял. Вы правы. Получается что если Б поместилось целиком в С, то это нарушает правило задачи о невкладываемости слов. Выходит что C обязательно входит в Б не глубже, чем длина Б. А значит слово А перестаёт играть хоть какое-нибудь значение и чем короче к итерации для слова С получилась строка, тем лучше.
Теперь я всё понял. Спасибо за ликбез. Какая-то совсем не тривиальная задача, если честно. Мне кажется нельзя такое давать на интервью :)
faiwer
29.07.2021 14:56Единственная оптимизация, которую вы по сути должны сделать, это внитри функции check для каждого слова запускать ровно одну check дальше
Оказалось, что нет :) Точно не единственная. Прекалькуляция и отказ перебора вариантов разного сдвига в пользу одного или нуля заранее просчитанного позволило продвинуться с 59 теста на 73 из 83. Потом снова Time Limit Exceeded. Думал что прекалк медленно написал, но оказалось что для всех тестов вышло < 1ms. Дело именно где-то в рекурсии.
Грешил на JS и даже попробовал переписать всё на C++ (как умею, т.е. ооочень плохо), но получил примерно ту же производительность. 10 секунд на тяжёлый тест. Попробую добить задачу на выходных.
Заодно вспомнил почему я ненавижу C++ :)
wataru
28.07.2021 17:51Ладно, я был не прав. Задача не тривиальная. Средненькая. Все-таки есть простор для ошибок.
Но я, честно сказать, даже не думал, что можно вот как вы написать. Разве же не очевидно, что не надо каждый раз пробовать все сдвиги?
Это как, если бы вам надо было найти 2 элемента в массиве с минимальной суммой, но вы бы перебирали все пары элементов, вместо выбора двух минимальных элементов за один проход ну или хотя бы сортировки.
faiwer
28.07.2021 18:10Разве же не очевидно, что не надо каждый раз пробовать все сдвиги?
Неа, не очевидно. Описал выше почему. До мысли что хитрых пересечений точно нет надо ещё дойти. Не просто предположить, что может быть они невозможны, а прямо провести полноценный анализ.
Вроде как принято такие вещи решать постепенно усложняя, и тут у меня получается как-то так:
- Пишем решение в лоб: получаем проблему, программа работает быстро, но все решения с пересечением слов не работаю. Понимаем в чём соль задачи.
- Пишем более сложное решение в лоб: всё работает, но падают тесты с time limit
- Начинаем одну за одной применять оптимизации. В моём случае это попытка избежать вычисления уже заведомо проигрышных вариантов
- Затем меня понесло в микрооптимизации и я улучшил
.endsWith, но выиграл всего пару тестов - Затем в поисках "мы явно что-то делаешь лишнее, где-то считаем одно и тоже много раз" приходим к тому что пересечения слов не зависят от рекурсии и их можно сосчитать превентивно
- Затем берёмся за самое сложное — анализируем возможные corner case в поисках избегания заведомо проигрышных вариантов и приходим к той самой логике про невозможности поместить 3-е слово левее 1-го. Получаем самый главный boost
Классная разминка для ума. Но это сильно перебор для собеседования. Добавить к этому что надо рассуждать вслух (т.е. не думать о задаче, а пытаться понятным образом сформулировать это на английском), да ещё и в некомфортных условиях (в худшем случае на какой-нибудь доске с мелом на глазах у двоих интервьюверов).
wataru
28.07.2021 18:13Ну на интервью вам будут немного подсказывать и не дадут (по крайней мере в идеале) закопаться вот так. Поэтому интервьюверы перед тем как вы начнете кодить хотят чтобы вы объяснили им свое решение.
klvov
28.07.2021 22:56+1оффтоп-вопрос, если можно: для какого класса задач "из реального мира" такие суперскиллы могут понадобиться? Ну типа, если про сортировку и поиск, то это нужно, чтобы сконструировать архиватор. Если обход деревьев - то это вам понадобится, когда будете конструировать интерпретатор и компилятор. Если бинарный поиск - то это нужно, когда надо посчитать уравнения, которые не решаются аналитически. Если там обратный индекс строить - то это пригодится, когда будете делать полнотекстовый поиск. Ну и т. д. Но вот эта вот "суперстрока" - она для чего может пригодиться?
wataru
28.07.2021 23:46+1Можно ваши примеры бесконечно расширять. Например, обход деревьев нужен во всяких хитрых задачах на строки, в том же алгоритме поиска кучи шаблонов в большом тексте. Всякие деревья контролов, или тот-же dom. Бинпоиск возникает во многих задачах, если его гонять по ответу и тогда можно заставить работать жадность в задачах, где она сама по себе не работает.
Конкретно эта задача с супер-строкой может разве что в биоинформатике пригодится. Ну или для генерации злых тестов в какой-нибудь системе полнотекстного поиска. Или в сжатии данных. Вообще, задачи на строки весьма специфические.
Но навыки, которые позволяют решить эту задачу нужны еще много где. Рассуждения вида "рассмотрим ответ — о, а он оказывается всегда вот таким свойством обладает" позволяют решать огромную кучу оптимизационных задач (Например всякие планировщики, балансировщики нагрузки).
Полный перебор всех перестановок и подобные алгоритмы генерации комбинаторных объектов — базовые вещи для решения не совсем больших NP-солжных задач. Где они у вас вылезут, даже гадать сложно.
Вот такой пример из моего прошлого: раньше, когда интернет был медленный и дорогой, а жесткие диски были маленькие, было модно ходить в гости с HDD и потом записывать сериалы на CD диски. Сериалов было много и очень быстро надоело вручную раскидывать файлы по дискам, чтобы они примерно целиком заполнялись и одна логическая группа файлов (сериал, допустим) не был размазан по всем дискам. Вот в этой задаче по упаковке и перебор был и динамическое программирование и много чего еще.
klvov
29.07.2021 00:25спасибо!
я, вообще-то, согласен с вашей позицией "если не знаешь, что есть такой алгоритм, то даже не сможешь увидеть, что его можно применить вот тут". Об этом и Пол Грэм писал, в эссе про "язык Блаб". Но, теория без практики мертва, и, как в школе хотелось спрашивать учителей "а зачем эти нам синусы-косинусы понадобятся в жизни", так и тут вот позволил себе вопрос аналогичного характера )
0xd34df00d
31.07.2021 03:38+1Но навыки, которые позволяют решить эту задачу нужны еще много где. Рассуждения вида "рассмотрим ответ — о, а он оказывается всегда вот таким свойством обладает" позволяют решать огромную кучу оптимизационных задач (Например всякие планировщики, балансировщики нагрузки).
Эти рассуждения вообще везде нужны. Умение видеть инварианты и симметрии задачи помогает что с вашими примерами, что с этим моим ковырянием типчиков, что вообще с олимпиадными задачами по физике.
Vilaine
03.08.2021 06:49и к 0xd34df00d
Берем первое слово целиком, а потом жадно как можно глубже всовываем следующее слово в предыдущее, так что суффикс левого слова совпадает с префиксом правого слова. Вот в вашем примере можно «oto» впихнуть на 1 символ в «foo» («foOto» — общие символы большие), «oof» на 1 символ в «oto» («otOof»), а «oof» на 2 символа в «foo» (fOOf"). Поэтому для этой перестановки мы сначала получаем «foo», потом «footo», потом «footoof».
Только получилось добраться до этой задачи. Вот пример[ "flolo", "ololf", "ololo"]
"flololf" не сработает, должен получиться "flolololf", поэтому нельзя просто жадно запихать одно слово запихать в другое. Для генерации нужно запихнуть сначала немного и с этой парой идти перебирать всё остальные в массиве, потом попробовать сильнее и т.п. Может быть там ещё какие-то граничные случаи.
Ну хз, я такое на собеседовании легко могу не пройти, особенно вероятно не уложиться во время.
В общем, не получилось у вас пройти в Гугл или куда там) Многое зависит от собеседующего, по-видимому. Вот такое спросят, мне лично не хватило знаний об алгоритме в reservoir sampling, или смекалки на месте его вывести (если вообще).
С другой стороны, ничего страшного в отказе нет, это не экзамен.faiwer
03.08.2021 10:19"flololf" не сработает, должен получиться "flolololf", поэтому нельзя просто жадно запихать одно слово запихать в другое.
Вроде всё можно, судите сами: fl[ol{olo]lf}, где [] это 3-е слово, а {} это 2-е слово.
- 1-е слово: flolo, никуда не просунуто
- 2-е слово: ololf, максимально вдвинуто в ololo
- 3-е слово: ololo, максимально вдвинуто в flolo (дальше fl)
wataru
03.08.2021 12:07Нет, мы не впихиваем слова глубже последнего. Так, конечно можно, но будет сильно дольше — нельзя для каждой пары слов предподсчитать глубину — придется ее каждый раз заново искать по всей покачто собранной строке.
faiwer
03.08.2021 12:44Нет, мы не впихиваем слова глубже последнего
А я этого и не делаю. Всё как у вас в комментарии ниже
flolo << [olo]lo << {olo}lf. Может быть слишком путанно описал. Я хотел продемонстрировать чтоololoи само оказывается внутриflolo, и также является гнездом дляololf. Правда всё равно time limit :)
wataru
03.08.2021 12:06Вы пропустили в моем коментарии
Далее, вот перебрали мы перестановку слов.
Поэтому, когда слова перемешаются как ["flolo", "ololo", "ololf"], жадное выпихивание как-раз выдаст "flolololf".
wataru
03.08.2021 12:19Вот такое спросят, мне лично не хватило знаний об алгоритме в 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 первых чисел перемешиваемого массива.
PsyHaSTe
20.08.2021 13:19Ну тут надо просто иметь понятие о вероятности и все. Ставим мину в первую ячейку с вероятностью 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)wataru
20.08.2021 14:44В принципе, после детального разговора, немногих улучшений и хотя бы идеи решения с детерменированным временем работы, я бы это решение принял на 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(не попали в пустую клетку) как-то быстро выбирать одну из оставшихся пустых клеток.
PsyHaSTe
20.08.2021 15:35+1Я предполагал, что k << m*n, поэтому ситуацией с дубликатами можно пренебречь.
Важное улучшение, к которому я бы вас подталкивал, когда вы сможете оценить время работы — это генерировать мины или пустые места (смотря чего меньше). Тут ассимптотика тоже будет O(k). И вы должны будете это тоже доказать. Хотя все-равно остается проблема повисания при неудачном стечении обстоятельств.
Это очевидная идея в случае, если предположение о характере k неверно. Но можно было озвучить, согласен. Просто я-то думал, что он верно) Поэтому и задал вопрос
Если же k сравнимо с nm то тут уже надо думать. Например, кажется что если в случае выпадания рандома на существующий элемент идти от нашей точки вверх (модуло длина) до ближайшей дырки (а-ля хэшмап с открытой адресацией) то будет опять же равновероятно попадание в любую точку. Правда, доказывать с листочкой и бумагой не очень готов)
wataru
20.08.2021 16:13Я предполагал, что k << m*n, поэтому ситуацией с дубликатами можно пренебречь.
Но этого нигде не сказано.
Например, кажется что если в случае выпадания рандома на существующий элемент идти от нашей точки вверх (модуло длина) до ближайшей дырки (а-ля хэшмап с открытой адресацией) то будет опять же равновероятно попадание в любую точку.
Во-первых, это не так. Во-вторых, это также медленно — там ассимптотика похожая, только замучаешься ее выводить. Но хотя бы оно не повиснет при неудачном генераторе — уже плюс.
Почему оно не равномерно — вот вам пример: пусть поставленные мины в строке обозначены 1
"0111100". Вот ту вероятность взять первый ноль 1/7, второй — 5/7, третий — 1/7. В итоге в сгенерированной расстановке будет гораздо больше подряд идущих мин, чем в случайном распределении.
PsyHaSTe
20.08.2021 16:35+1Видимо, правую границу рандома нужно уменьшать на единицу после каждой генерации, и искать n-ое место для вставки, тогда в этом случае будем генерировать (0, 2) и вставим вместо одного из этих нулей. Не очень эффективно, конечно.
Куда лучше смотрится вариант зашафлить массив и взять первые k. Только как зашафлить массив не храня его целиком мне не очень понятно.
wataru
20.08.2021 16:47+1Куда лучше смотрится вариант зашафлить массив и взять первые 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; }
nlog
28.07.2021 01:40+1Видимо я потупел после ковида, но я бы не написал правильное решение за 45 минут.
wataru
28.07.2021 12:43Ну блин, неужели вот это нельзя написать за 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; }Antervis
28.07.2021 13:40"You may assume that no string in words is a substring of another string in words". Что конечно же не делает задачу сложнее. В отличие от того, что про std::next_permutation знают далеко не все, т.к. за пределами олимпиадных задач она мало где встречается. Да и в них не постоянно.
wataru
28.07.2021 14:07Ну отлично, первые 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.
questor
08.09.2021 10:46Да забудьте вы про это "быстрее 100% других решений", у литкода кривая замерялка. Там цифры скачут в весьма широком диапазоне, может повезти что вы с решением за O(N^3) окажетесь в ТОПе, а бывает что решение за линейное время отбрасывает в конец. И если бы вы прорешали не одну задачу, а сотню - вы бы увидели насколько литкод в этом плане глючен.
Апеллируйте к асимптотической сложности. Нашли решение за константное время и константную память - молодец, вот тут уже действительно выше головы не прыгнешь (задача на поиск центра star графа), нашли за квадратичное и нет идей как снизить - не молодец.
GreaterGlider
26.07.2021 14:42-1Homebrew невероятно медленный и странный пакетный менеджер (сравнивая с теми же apt, pacman и тд), так что правильно что гугл его завернул. Знай бы он как инвертировать бинарное дерево, возможно и написал бы что-то нормальное, а не это поделие.
guywithacanon
26.07.2021 14:42Так же как многие изучал и изучаю алгоритмы, решаю задачи. Но вот в этом случае как мне кажется не развернуть дерево просто говорит о том, что человек вообще не готовился. Потому как задача инвертировать это дерево совсем простая.
DMGarikk
26.07.2021 18:44+1вопрос в том не то что задача может быть сложная, а то что решить её надо в очень ограниченный промежуток времени
я например не могу так быстро думать, во первых когда быстро думаешь — ерунда получается, а во вторых у меня так мозги лучше работают. а уж когда надо еще кодом решение написать… то вообще взрыв мозга.
вот интересно, в конторах которые такие задачи дают, надо программить на скорость в условиях отключенной связи и на бумажке?
alex_blank
26.07.2021 19:43> вот интересно, в конторах которые такие задачи дают, надо программить на скорость в условиях отключенной связи и на бумажке?
Не скажу за конторы, но действительно бывают редкие случаи, когда случается пожар и нужно очень быстро разобраться в чем дело и решить проблему. Тут пригождаются навыки скоростной отладки и кодинга. Иногда бывает что и в терминале надо что-то делать, где из удобств только голый vi/vim (почти что пресловутая «бумажка»).
Конечно, никакие деревья вертеть при этом не надо обычно :)
DMGarikk
26.07.2021 22:26+2Вот это похоже на правду и действительно не нужно решать всякую синтетику по переупорядочиванмю массивов
Я периодически сталкивался с такими кейсами и думать надо в первую очередь как бы все окончательно не сломать и какие последствия будут, а не то как оптимально просуммировать простые числа в дереве без инструментов языка
И кстати таким линейные программисты обычно не занимаются
Trrrrr
26.07.2021 14:42-1ну по правде задача ж очень простая. я с начала подумал что за дичь и полез на лит код искать условие. Я не представляю как ее не решить, для этого просто надо не кодить.
KorP
25.07.2021 20:12+5Я понимаю, что в наше время без английского в ИТ просто никуда, но количество англицизмов в тексте просто зашкаливающее.
shhelen Автор
25.07.2021 23:54+1да, согласна, я просто не так часто пишу статьи, поэтому тут есть над чем поработать
etozhesano
26.07.2021 08:32+2Та вроде нормально читается. А как уже без англицизмов в 2021? Я и в жизни часто использую и ничего. Понятно что это статья всё же и т.д, но мы и не на форуме матерей
prohodil_mimo
26.07.2021 12:55-5Одно дело - терминология, а другое - разбавление обычной речи зачем-то вставленными английскими словами. Дискуссия вокруг англицизмов больше о том, что, хотя многие слова органично вошли в язык, можно было бы и обойтись без них, ведь есть местные аналоги. А здесь даже не англицизмы, а просто куски английского текста, как будто текст недоперевёлся гугл.переводчиком. В общем, i want сказать, что текст could смотреться более organic, if бы он was written на каком-то одном языке, а не на russian-английском surzhik.
cyberzx23
26.07.2021 13:59-3Было бы намного куда более плежурнее ридать текст на нативном лэнгвиче, чем на миксед. Если вы спикаете и финкаете на инглише, то и врайтайте на нём же.
Vilaine
25.07.2021 20:18+9как не потерять мотивацию за полгода подготовки в FAANG
Так как же? Инвестиция выглядит довольно рискованной. Хуже бизнеса какого-нибудь - там хоть результат по мере продвижения виден, а тут бинарная подготовка к найму в определённые компании (и почти ничего более - просто прохождение отбора), результат которой будет известен в конце. В любой момент хочется подумать "всё зря и бесполезно, лучше поделать что-то интересное/полезное".
Нужен, наверно, определённый склад характера.
terein
26.07.2021 15:03+1Присоединяюсь к вопросу. Как при основной работе сохранить мотивацию тратить 4 часа каждый день в течение полугода на подготовку к собеседованиям?
shhelen Автор
26.07.2021 15:43Не каждый день у меня получалось тратить именно по 4 часа и решать вообще, но я старалась, иногда решала меньше, во время релиза времени на это не было (на скриншоте у меня видны пустые дни, когда я ничего не сабмитила). По моим ощущениям, тяжело первый месяц-полтора, потом уже и задачи идут легче и втягиваешься в процесс. Для мотивации важна цель - желание попасть в определенную команду/компанию, переехать в Европу и поработать в большой компании, без этого никак. Конечно, вы будете уставать, иногда нужно дать себе пару дней, чтобы выдохнуть и потом продолжить. К системному дизайну мне очень нравилось готовится, я узнавала много полезного. Сами задачи интересные попадались, но в основном, просто вырабатываешь в себе привычку их решать.
questor
08.09.2021 11:10Тот, кто хотел взобраться на Фудзияму, но не достиг своей цели - окажется выше того, кто хотел забраться на кочку и смог это.
Компании FAANG в этом плане являются вершиной, вы сможете найти много достойных компаний, в которых с таким уровнем подготовки вы будете проходить собеседование намного проще. FAANG задаёт моду, которую копируют остальные - и собеседования во все большее число иностранных компании устроены по тем же общим принципам, различаясь в мелких деталях. Эта практика постепенно проникает и в крупные русские компании, почитайте например на хабре про собесы в яндекс.
Понимание этих двух простых вещей поможет сохранить мотивацию.
И разумеется, можно делать не так резко, а более плавно. Если вам не приспичило оказаться в условном гугле вот прям завтра и надо за ночь весь учебник перерешать, а вы готовы к марафонскому забегу на более длинную дистанцию, а не сгореть как спринтер после стометровки -- готовьтесь более плавно. Тут уже просто личные особенности играют роль, у кого как дофамин работает.
Vilaine
09.09.2021 23:46Компании FAANG в этом плане являются вершиной, вы сможете найти много достойных компаний, в которых с таким уровнем подготовки вы будете проходить собеседование намного проще
Звучит логично, но я вот не соглашусь.
Только что с собеседования в Amazon на L5/SDEII (как и авторша, полагаю), и, как мне показалось, если подтянуть кое-какие прозрачно тренируемые софт-скиллы, то оффер был бы гарантирован, задания довольно простые. Полгода назад технически самое сложное собеседование было в какую-то подкомпанию Oracle (помогло примерное знание устройства баз данных), они дали оффер. Далее попробую в Facebook, и, возможно, даже Google, если они не выкинут моё резюме сразу в помойку — мне нравятся вызовы.
При этом мне за долгое время не дала оффер ни одна (без преувеличения) другая мелкая малоинтересная компания, в которые не особо даже и хотелось идти (соглашаюсь на собеседования в линкедине, абы посмотреть, если предложат условия лучше нынешних). Хотя интервью прошло, как мне казалось, хорошо или идеально. Большинство после интервью отмалчиваются или прямо говорят, что не дадут мне фидбэк. (хотя 90% ещё до интервью пишут «вы нам не подходите» — после того, как сами и предлагают у них пособеседоваться)
В этом плане намного проще пройти в этот FAANG и иже с ним, ибо у них довольно скриптовые собеседования и прописанные ожидания — знаешь, что ожидать и к чему готовиться. Они сами об этом сообщают. Во многие другие компании найм — это полный чёрный ящик и кого конкретно они ищут, кем мне нужно быть я чаще всего не понимаю.
OZR
25.07.2021 20:37+24Вы крутая. Очень приятно подобное читать :)
---
Аж восприятие немного перевернулось. Столько всего пройти ... Ради FAANG ... Боюсь, это никогда не будет моим уровнем. Я искренне не понимаю, как можно год решать задачи, которые не будешь использовать. А всё что не используется, то атрофируется и забывается. Я столько всего прочитал по программированию впустую. Потому что эти знания не используются и следовательно не нужны и забываются настолько, что дойти до собеседования попросту невозможно. И это ради FAANG, корпораций, для которых люди расходный материал.
Сильно. Искренне надеюсь что у Вас всё будет хорошо. Не выгарайте ;)
Antervis
25.07.2021 21:10+4лишь бы потом не оказалось что сотни часов подготовки к прохождению собеседований не дали никакого вклада в навыки выполнения практических задач. Чего собственно вам и желаю. А то порой смотришь как люди написали трай под задачу, для которой бы хватило компаратора...
snuk182
25.07.2021 23:56+1У компании А последние два года есть опросник после кодинг-интервью, где попадался вопрос "насколько вам стало понятней по задачам на интервью, чем вы будете заниматься, если вас таки возьмут?" ИМХО, в положительном ключе на этот вопрос рука не поднимется ответить.
aigoncharov
26.07.2021 00:22+2Лично мне очень даже помог в дальнейшей работе подобный ликбез по алгоритмам и структурам данных
Antervis
26.07.2021 07:03+6в повседневной работе надо знать условные шесть-семь структур данных, причем именно с точки зрения ассимптотик/гарантий отдельных операций. Их проще запоминать если знать как эти структуры реализованы, в остальном умение расставлять черно-красный флаг и разворачивать дерево в реальном коде не пригодится. Это можно изучить часов за 10, прям досконально.
А вот перспектива потратить еще пару месяцев на изучение редких структур данных и алгоритмов, из которыхнедай бог треть пригодится за всю карьеру, кажется сомнительной. Не поймите меня неправильно, это выгодная "инвестиция" в работу мечты, просто такой подход к найму разочаровывает. Вот "поревьюить пулл реквест" кажется хорошей задачей, которая должна максимально коррелировать с опытом миддла.aigoncharov
26.07.2021 12:19Поервьюить пулл-реквест - задача с очень субъективной оценкой. Решить задачку на алгоритмы - намного менее субъективно.
Более того, в процессе интервью, сам интервьюер зачастую подсказывает и задает наводящие вопросы, и это ок. Из моего опыта, большей части интервьюеров фаанга не нужно от тебя идеальное решение сразу. Люди хотят услышать как ты думаешь и как реагируешь на новую информацию/подсказки.
JustDont
26.07.2021 13:01+1Поервьюить пулл-реквест — задача с очень субъективной оценкой.
Если у вас есть закрытый список проблем этого пулл-реквеста и вы вычеркиваете то, что отмечает интервьюируемый — всё невероятно объективно, но всё так же гораздо более приближено к реальности, чем поворот деревьев.
Antervis
26.07.2021 13:12+3Поервьюить пулл-реквест - задача с очень субъективной оценкой. Решить задачку на алгоритмы - намного менее субъективно.
по мне так "нашел 4/5 UB и 3/3 нарушений common practice" объективнее, чем "развернул дерево за 15:30 а должен был уложиться в 15:00". И сигнал лучше
0xd34df00d
26.07.2021 19:25Вот с common practice уже несколько сложнее.
Если вы приходите из модного стартапа, где весь код был обмазан
gsl::и были ежедневные митапы по чтению core guidelines по ролям, то у вас впечатление об этих практисах может быть несколько другим, чем если вы приходите из условной крупной компании с кодовой базой с 30-летней историей, собственной реализациейstd::(зато с аллокаторами везде!) и собственными базовыми библиотеками. При этом ни то, ни другое не говорит особо о вас, равно как и о совместимости ваших практисов с практисами условного гугла (которые, ввиду истории и специфики, тоже не обязаны совпадать с внешними лучшими практиками).С другой стороны, это заодно проверяет вашу совместимость с командой — насколько вы придирчивы, какого рода комменты оставляете («What do you think about using
std::to_charshere instead ofstd::to_string?» или «usestd::to_chars»), и, собственно, что вы считаете лучшими практиками. Хорошо это или плохо — другой вопрос.Antervis
26.07.2021 20:14Вообще это могли бы быть "3/3 упущенных микрооптимизации", что-то типа "давайте тут заменим сет на битсет а тут добавим забытый move", если говорить в категориях плюсов. Мой аргумент скорее был в том, что у средней алгоритмической задачи объективный сигнал "справился/не справился" и дальше у ревьюера куча гайдлайнов как увеличить разрешение этой оценки. А в задаче "найди 10 объективных изъянов" успех кандидата уже можно объективно оценить по шкале от 0 до 10, с минимальной корректировкой от ревьюера.
Да и сами common practice могут быть довольно-таки общепринятыми. Например в плюсах принято передавать владение через unique_ptr вместо сырого указателя, ровно как и использовать ссылки там, где указатель никогда не nullptr.0xd34df00d
26.07.2021 20:22Например в плюсах принято передавать владение через 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.
Antervis
26.07.2021 21:23Здравствуйте, я к вам из 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.". Контекст которых я и подразумевал.
Dolios
26.07.2021 16:20В повседневной жизни нужно уметь ходить, сидеть, лежать, держать ложку и печатать на клавиатуре. А вот перспектива потратить много времени для того, чтобы иметь возможность подтянуться 20 раз или 5км пробежать, кажется сомнительной.
Мозг - это рабочий инструмент разработчика/архитектора. Подобные тренировки ему только на пользу. Ну и, часто решение подобных задач приносит удовольствие уже по факту того, что ты смог додуматься и решить за хорошее время с приемлемой сложностью.
Antervis
26.07.2021 18:48-2Мозг - это рабочий инструмент разработчика/архитектора. Подобные тренировки ему только на пользу
Вот есть у разработчика свободное время, он может тренировать мозг изучением решения задачи комивояжера, а может посмотреть пару докладов про чистый код, особенности фреймворка, новинки языка или что-нибудь в таком духе. На дистанции второе будет полезнее и сотруднику, и работодателю... если первый пройдет ревью конечно же. Собственно проблема в том, что у претендента стимул изучать навыки, которые ни ему, ни компании после найма не понадобятся.
Dolios
26.07.2021 19:01+1На дистанции второе будет полезнее и сотруднику, и работодателю...
Почему? Умение находить оптимальное решение задачи, умение оценивать сложность алгоритмов, умение системного дизайна, софт скиллс, навыки в работе в команде, знание, как лучше поступить в той или иной ситуации не менее важны. Именно это и хотят увидеть в фаангах на интервью (алгоритмы + сисдиз + бихихейв). И эти навыки понадобятся любому разработчику. Алгособес это, сюрприз, не про заучивание алгоритмов, а про способность решать поставленную задачу приемлемым способом. К тому же, замените "вместо" на "вместе" и читайте дядю Боба тоже. Будет полезно, не спорю.
DMGarikk
26.07.2021 19:22-1а про способность решать поставленную задачу приемлемым способом
в течении короткого промежутка времени и без привычных инструментов, не забывайте главный косяк этого издевательства.
p.s. хотя то как косякнул гугл на днях с хромоосью, показывает что они реально решают задачи на ходу и сразу деплоятся без тестов… ну да, вполне используют подход на практике
alexdesyatnik
26.07.2021 23:13+1Это глубокий оффтопик, конечно, но не могу не ответить, так как познал на собственном печальном опыте истину "в здоровом теле - здоровый дух". Мозг функционирует неотрывно от остального тела, а тело у людей так устроено, что ему просто необходимы как минимум умеренные физические нагрузки на постоянной основе. Если не практиковать собственную физиологию за пределами уровня "ходить по необходимости", гарантированно получите целый спектр проблем в том числе и со снижением качества мышления (к сожалению, сейчас из головы не могу накидать ссылок, так что просто anecdotal evidence).
0xd34df00d
26.07.2021 23:29в здоровом теле — здоровый дух
С часто забываемым контекстом, что на самом деле — одно из двух?
Мозг функционирует неотрывно от остального тела, а тело у людей так устроено, что ему просто необходимы как минимум умеренные физические нагрузки на постоянной основе.
Это зависит от кучи других факторов (включая, скажем, ваш возраст). В 20 лет я мог вообще не двигаться, спать чёрти как, и был весьма продуктивным.
Если не практиковать собственную физиологию за пределами уровня "ходить по необходимости", гарантированно получите целый спектр проблем в том числе и со снижением качества мышления (к сожалению, сейчас из головы не могу накидать ссылок, так что просто anecdotal evidence).
Ну, во-первых, официальная рекомендация ВОЗ — это 150 минут лёгкой активности в неделю или 75 средней. Для этого достаточно условно ходить пешком до метро по пути на работу.
Во-вторых, я ещё не встречал ни одного эксперимента с дизайном «одни люди N минут в неделю практиковали собственную физиологию, другие — N минут в неделю решали задачки на литкоде/ботали матан/решали судоку». Почти всегда альтернативная группа занималась примерно ничем.Дизайн экспериментов был адекватным? Или там
Alendorff
28.07.2021 14:12потратить много времени для того, чтобы иметь возможность подтянуться 20 раз
о, как человек который как раз себе целью до конца лета поставил смочь подтянуться двадцать раз, не могу пройти мимо и не сказать, что многим такое спортивное достигаторство просто в кайф (и процесс и результаты). Наверное, так же обстоят дела для людей которые могут 300 задач на литкоде решить после работы и получить веер оферов из FAANG. Мне вот было бы слишком ленно, но вопрос мотивации конечно.
wataru
26.07.2021 13:12+1Их моего опыта работы в гугле: практические задачи, требующие те же навыки — возникают. Далеко не каждый день, но и динамическое программирование, и бинарный поиск писать приходилось. Json-ы перекладывать приходится гораздо чаще, конечно.
Ощущение, что эти "алгоритмы" не нужны возникает у не знающих их потому, что почти любую задачу можно сделать и в тупую "наивным" методом. Это будет на порядки медленее, часто более громоздкий и запутанный код. Но у пишушего его программиста даже не возникнет мысли, что а вот тут можно было бы и впендюрить алгоритм.
youROCK
25.07.2021 21:25+1По поводу задачек на собеседовании в Гугле: вроде как просят задачи в общий доступ не выкладывать же :). Тем, кто Вас собеседовал, придется теперь новые задачки придумывать. А так вроде всё правильно написали :).
Ну и впечатляет конечно Ваше усердие при подготовке. Я лично перед собседованием в Гугл на подготовку практически забил и меня всё равно взяли :). Наверное, если бы готовился, то может быть фидбек был бы и лучше. Впрочем, на собесах тех, кто проводит интервью учат, как определять, что человек видит какую-то задачу не в первый раз и предлагают менять условия задачи или давать другую прямо в процессе, так что в теории подготовка в виде решения похожих задач должна помогать только с тем, чтобы развивать алгоритмическое мышление. Которое, кстати, не очень часто нужно, и намного важнее в продакшн коде обработка ошибок, правильное логирование, и т.д., но это уже тема для отдельного разговора:).
shhelen Автор
25.07.2021 23:52+2мне такого по поводу задачек не говорили) Гугл сам даже ссылается на leetcode и Cracking The Coding Interview для подготовки
Infthi
26.07.2021 15:45Что, правда в переписке не ищется что-то типа
As a friendly reminder, our interview questions are confidential, so please keep things under wraps
в футере сообщения?
mspain
25.07.2021 22:19-8Очередной пруф того, что в фаангах засилие идиотов.... Ебей конечно чуть получше алиэкспресса, но тоже образец кривого убожества, которым невозможно пользоваться.
p.s. "Почему Python? Java - очень много букв, C++ - очень хардкорно" остальная аналитика на том же уровне?
etozhepivka
26.07.2021 13:59+1Тем не менее эти компании могут позволить себе отбирать специалистом с хорошим знанием Computer Science.
Порой от качества специалистов, которых приходится собеседовать, хочется плакать
blind_oracle
25.07.2021 23:02+18Вот так корячишься полгода, тебя берут в фаанг и сажают латать дыры в какои-нибудь древнючем легаси :) облом-с
Keeper7
25.07.2021 23:32-50"Нас ... , а мы крепчаем."
Судя по тексту, у автора явные склонности к мазохизму. Насколько это связано с полом автора -- оставим на домашнее задание.
Diamon33
31.07.2021 09:15+2Автор написала статью о том, как попасть в 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, потому, что "а смогу ли?" и деньги. Персональный челлендж.
В итоге, остается вопрос к Вашему изначальному сообщению - Кого е*ут-то, кто крепчает, и причем тут пол автора?
0xd34df00d
31.07.2021 10:35Есть пример того, кто попал в Amazon ради GC, и мучается, работая там (суровые дедлайны, токсичное окружение в команде), но примерно через полгода он получит свою GC и отчалит оттуда, имея в резюме Amazon.
Лучше так не писать и не говорить, это технически нарушение условий получения гринки под работу.
Diamon33
01.08.2021 07:54USCIS может счесть это "продажей GC" и потребовать доказательств о реальности работодателя и прочей бумажной волокиты.
Технически "нарушений условий" здесь нет, работодатель не может заставить Вас оставаться на работе, т.к. не смотря на спонсорство, это всё еще employment at will, а вопросами Вашего резидентства с этого момента будет заниматься USCIS.
Есть общая рекомендация проработать полгода после одобрения I-485, чтобы не привлечь лишнего внимания.
Таким образом, можно ли так делать - да. Стоит ли так делать - скорее нет, лучше немного подождать, думаю, человек продержится еще полгода, получая ~$10к в месяц.
Стоит ли делать такое уточнение, чтобы рандомный человек с хабра вдруг решил воспользоваться "случаем" из комментария другого рандомного человека, а не изучил досконально вопрос своего статуса? Не знаю, но раз Вы это подметили - уточняю.
0xd34df00d
02.08.2021 02:37Это не вся история. При EB-гринке важны ещё и ваши намерения: планируете ли вы при её оформлении (включая интервью с USCIS officer'ом) дальше работать на вашего работодателя. В частности, на интервью в USCIS вас могут спросить, планируете ли вы дальше работать, и с чистой совестью отказать, если вы даже скажете «да не, через полгода-год свалю» (и фиг вы сможете это апеллировать).
Просто я этим вопросом интересовался, так как мне в своё время довольно сильно осточертело сидеть в компании, и я любопытствовал, какие риски при уходе в какое время.
Diamon33
02.08.2021 06:09Я согласен, что при таком "тактическом отступлении" стоит продумать отход. Однако, насколько я могу судить о здешней системе, при полном соблюдении формальных условий вероятность того, что докопаются - крайне мала.
Вы можете быть в данный момент свято уверены (и говорить об этом), что по гроб будете работать в текущей компании, а через месяц, условно, приходит токсичный менеджер, закрывается непосредственно ваш проект, находится оффер, открывается стартап у друга, или еще что "внезапно происходит", и вам приходится искать\уходить на новое место. Совершенно легально.
Я никаким образом не упираю на то, что нужно действовать на грани легальности, но отмечаю, что при соблюдении всех правил можно следовать совершенно личным мотивам, здесь тыкать в тебя пальцем с возгласами "Да как ты мог?! Да таких как ты за забором.." не особо принято.
nazem
25.07.2021 23:34+4Много коментов из разряда: "Такой пути ради FAANG проходить не стоит". Я тоже был такого мнения, но поработав в русском фанге, скажу что не в фаанг уже не хочется.
Огромное спасибо за статью, удачи вам!todoman
25.07.2021 23:56+2Это в каком же «русском ФААНГе»? В какой из компаний? Вариантов всего полтора, и оба они – далеко не «работодатель мечты».
Semenych
26.07.2021 00:10+10Русский FFANG - МЯСО - Mail.ru, Яндекс, Сбер, Озон
Alexsey
26.07.2021 01:08+3И во всех 4 (ну ладно, может мейл из этого списка можно выкинуть, не доходила до меня информация о том как там работается) очень мало команд в которые реально стоит идти.
JustDont
26.07.2021 12:15+5Очень смешно.
Я, работая в одной из этих букв, и очень хорошо зная о работе в двух других буквах — легко могу сказать, что контор, которые вот просто лучше этих по подавляющему большинству параметров (исключая "огромадность") — десятки тысяч. И причем даже не все из них иностранные. Да что там, условные галеры условного EPAM и то будут выглядеть неплохо в сравнении по целому ряду причин.
germn
26.07.2021 00:14+1поработав в русском фанге, скажу что не в фаанг уже не хочется
Расскажите, почему?
0xd34df00d
26.07.2021 03:09+3У настоящего американского фаанга (конкретно, гугла) проблема в том, что там довольно тяжко пилить личный опенсорс даже в личное, нерабочее время (хотя это не для всех проблема, конечно). В РФ такое ТК не допускает, а в США работодатель вас может контрактом ограничивать достаточно произвольно.
sim31r
26.07.2021 09:51В США от штата зависит, везде по разному.
0xd34df00d
26.07.2021 09:56+4Конкретно по личным проектам (включая личный некоммерческий опенсорс) — насколько я знаю, везде может, включая достаточно про-employee-Калифорнию.
cyberzx23
26.07.2021 14:06+2В Амазоне всё ещё хуже. Там реально галеры какие-то.
https://techraptor.net/gaming/news/amazon-games-personal-game-policy0xd34df00d
26.07.2021 20:02+3Это не хуже. Это лучше, серьёзно. Давайте я вам расскажу, как было в одной компании, где я работал.
- Если хочешь вечером воскресенья что-то запилить в какой-то открытый проект, то проверь, является ли он в списке зааппрувленных (там было порядка сотни проектов суммарно, большинство из которых — те, куда люди коммитили что-то из-за работы, а не из-за личных желаний). Если да, то можешь. Если нет, см. п. 2 и далее.
- Незааппрувленные проекты нужно сначала подать в IP-отдел компании на аппрув. IP-отдел состоит из целого одного человека и одного его помощника, поэтому аппрув может занимать произвольно долго: недели и месяцы. Надо не забывать пинать людей, но так, чтобы не показалось, что тебе этот попенсорс важнее Работы. Оказывается, к слову, это довольно эффективно убивает мотивацию и желание спонтанного вечернего контрибьютинга
при свечах. - Зааппрувленный проект надо добавить на специальную страничку на вики компании. Лично для меня это проблема, так как я против смешивания работы и личной жизни, и мои личные проекты — моё личное дело, о которых я по умолчанию не хочу рассказывать всей организации.
- Аппрувить не надо проекты, «не представляющие интереса для компании». Так как компания пытается косить под гугл, IP-отдел считает, что для компании представляет интерес всё, что относится к кодингу (включая, например, книжку по написанию формально верифицированного кода на никому не нужном языке). Зато можете не аппрувить книжку о садоводстве, например, которую вы пишете в личное время.
- Аппрувить надо даже личные блоги и посты в них (если они про программирование). А то вдруг что.
- Если проект требует copyright assignment (даже если это assignment условному FSF'у у glibc до недавнего времени, например), то ты идёшь нафиг.
- Если у проекта «непонятная» лицензия для IP-отдела (типа такой, упоминаемая там Software Foundations на тот момент была, да и сейчас есть, под вполне опенсорсной лицензией), не соответствующая по шаблону привычным GPL, BSD, etc, ты идёшь нафиг.
- Если у проекта есть даже, не знаю, платная поддержка или dual licensing в таком стиле, ты идёшь нафиг. Даже если у тебя тривиальный патч на пару дюжин строк (тут мне конкретно мой манагер посмотрел на этот патч глазами и сказал «да забей на этих дураков из IP»).
- Если проект хоть немного пересекается с реальным продуктом компании (например, там, где я работал, в продукте был встроенный мессенджер, и у меня в моём проекте, который я начал в 2006-м и у которого, может, даже наберётся пара сотен пользователей, тоже есть мессенджер), ты идёшь нафиг.
Конечно, все эти «нафиг» могут немного перекрываться по договорённости с манагером типа под его ответственность, но это создаёт прикольную атмосферу нависающей угрозы — манагеры меняются, отношения с ними меняются, да и вообще.
Впрочем, так, конечно, не везде. В другой компании, где я работал, всем было пофиг, мой прямой манагер (по совместительству чиф техникал офицер) активно поощрял, что я там в блог свой строчу, и что я там опенсорслю, и даже как-то раз просил что-то, нужное для компании, допилить в сторонней библиотеке от моего имени на гитхабе, типа, чтобы про интерес компании к этой либе не узнали.
atoshin
27.07.2021 12:55Дай угадаю, WG?
0xd34df00d
27.07.2021 18:38Нет. Вернее, увы, нет — это лишнее подтверждение того, такая ерунда не только там, где я работал.
cebka
26.07.2021 16:30В US и non-compete совершенно драконовский во многих штатах. В Европе хотя бы garden leave полагается, а в штатах на мороз без зарплаты и перспектив трудоустройства к конкуренту.
0xd34df00d
26.07.2021 20:05+1Ну так не надо подписывать такие контракты.
У меня в очень драконовской по этой части области в виде всякого трейдинга было условие «полгода к конкурентам не ходить», но при этом было же «помимо severance, полгода платится зарплата, если вас увольняют without a good cause». Я прям даже пожалел, что этот пункт для меня waive'нули (вместе с зарплатой), когда увольняли по сокращению из-за кризиса в феврале того года — это трейдинг всё равно осточертел, и к конкурентам я идти и не собирался.
Semenych
26.07.2021 00:14+7Почитал, шаги вполне логичные, но у меня два вопроса в разных направлениях
Насколько оно того стоило? По деньгам и всему остальному. Прямо вот любопытно.
Описан крайне ритуализированный процесс. Интересно насколько оно там и правда помогает. Как тут справедливо писали выше такой строгий и формальный отбор с фокусом на легко формализуемые цели скорее всего приводит к изрядной токсичности среды и проблемам в решении реальных задач, когда надо не решить задачу, а понять как бы так сделать, чтобы ее решать было не надо.
aigoncharov
26.07.2021 00:20По деньгам достаточно достоверно можно тут посмотреть https://www.levels.fyi/
Clasen01
26.07.2021 05:04Это был опыт, я познакомилась со многими хорошими специалистами и моя вторая команда была one love, но я уже просто устала от ненормального work-life balance в компании, не особо интересных задач, зарплаты ниже рынка и своих непонятных карьерных перспектив.
Порадовало, im sorry)
Vilaine
26.07.2021 06:25+11примерно 4 часа в день до/после работы
Вот ещё интересно, как вы организовались поддерживать такой режим в течение нескольких месяцев и не влияло ли это на работу? 8 часов работа, 8 часов сон, остаётся 8 часов, из которых несколько часов нужно на самообслуживание (время перед засыпанием, еда, гигиена, физкультура, да и просто передышки для мозга). У меня пока получилось лишь гарантированные 2 часа в день выделять на учёбу в день. Остаётся 2 часа личного времени, открыть хабр, почитать статейки, полить растения, вот эта вся мелочь. Остальные 4 часа - транзакционные издержки жизнедеятельности, так сказать.
При этом предыдущая цель в 3 часа в день позорно провалилась, мой мозг не выдержал нагрузки и несколько месяцев после такого прокрастинировал. Что, к тому же, процентов на 20 подорвало эффективность и на оплачиваемой работе, в которой я стараюсь честно выкладываться. В общем, перехотелось после этого в FAANG. Кстати, хочется в свободное обучаться ещё и чему-то полезному или интересному, а не только надрачивать на найм, это тоже влияет на срыв планов.
В общем, какие вы тут задачи прорешивали для подготовки - это на самом деле второстепенное знание, интернет таким полнится. Уникальное знание, чему хотелось бы у вас научиться - как вам удалось долго продуктивно интеллектуально работать
примерно 4 часа в день до/после работы ... Полностью вся суббота и часть воскресенья уходили на подготовку
Вот это получится у очень редких людей и требует колоссальных мобилизационных способностей.
xtremespb
26.07.2021 08:50+5Опыт очень интересный, но стилистика изложения напомнила старый добрый хипстерский анекдот: "Один мужик сказал в коворкинге "Тот случай дал мне ценный опыт" вместо "Тот кейс дал мне ценный экспириенс" и его тут же осмеяли, облили смузи и перевели в чуханы".
balberbro
26.07.2021 09:19+3А можно уточнить вопрос, про локацию (куда именно искали релокейт) и что было с визой?
weiser
26.07.2021 10:32+1Вы - большая молодец.
Имхо, даже если работа в FAANG на практике окажется далека от работы мечты, строчка в резюме о работе в подобной компании откроет многие двери.
euroUK
26.07.2021 10:41+1Двери открываются и без этих строчек, да и сами строчки не гарантируют работадателю что разработчик реально умеет работать, потому что зазубрить алгоритмы != реальным задачам
weiser
26.07.2021 12:24Конечно и без этих, и конечно не гарантируют. Но это не отменяет того факта, что строчка о работе в одной из подобных компаний выглядит более привлекательно чем равные годы работы в ООО "Рога и копыта".
igrishaev
26.07.2021 11:31+7Искренне не понимаю, зачем тратить полгода на зубрежку алгоритмов, которые вы забудете через пару месяцев. Университет уже закончился, и ради чего насиловать себя — не ясно. Очень вероятно, что пройдя десятки интервью с вопросами про деревья и графы, вы будете просто перекладывать данные по сети. Но даже если понадобятся алгоритмы, их легко подчерпнуть из книги или банально спросить помощи у коллег.
Удивляюсь, что при всей маразматичности найма в FAANG туда стоят очереди, и поэму фирмы позволяют себе такие изнурительные процессы. Правильней было бы сказать рекрутерам — вертел я ваши деревья, если подготовка к ним занимает полгода. Подготовка к FAANG это искусственная накрутка своих скилов и в целом ритуал, которому почему-то следуют.
ilammy
26.07.2021 13:44+2Удивляюсь, что при всей маразматичности найма в FAANG туда стоят очереди
Маразматичность — маразматичностью, а $200k в год — это $200k в год (плюс очень красивая строчка в резюме). Отсюда и очередь желающих разучивать правильные трюки по полгода, оттуда и способы проредить эту очередь, чтобы если и брать специалистов по литкоду — то самых лучших и настойчивых специалистов, которых легко выдрессировать на другие трюки.
ViacheslavNk
26.07.2021 15:19Ну $200k много кто сейчас может предложить (Oracle, IBM, Intel и пр), без такой потогонки и "унижения", другое дело, что FAANG может предложить за $300k и даже больше.
wataru
26.07.2021 16:55+1Что унизительного в том, что программиста просят программировать на интервью?
euroUK
26.07.2021 17:20-2Программировать - нет. Знать 100500 алгоритмов - зашквар
wataru
26.07.2021 17:24Ну вот тут 0xd34df00d разобрал задачу из статьи. Там какие-то особые алгоритмы нужны?
TheKnight
26.07.2021 22:17+2Знать 100500 алгоритмов - зашквар
Ни фига ж себе, до чего дошло общественное мнение...
ViacheslavNk
26.07.2021 21:33Унизительного ни чего нет по большому счету (поэтому и взял в кавычки), просто если планка стоит в $200k то можно и не напрягаться пол года-год решая задачи на leetcode, topcoder, и пр, куря мануалы как пройти интервью и т.д, что бы найти интересную работу в большой корпорации.
igrishaev
27.07.2021 12:35В других фирмах вы легко найдете 150к (по крайней мере в США), при этом не будет бессонных ночей и зубрежки деревьев-графов.
greenEkatherine
26.07.2021 11:48Спасибо за упоминание канала подготовки в FAANG, очень полезная группа, я о ней к сожалению не знала, когда сама готовилась. По стилю и содержанию статьи не могу отделаться от мысли, что вы читали мою, но почему-то ее не упомянули. Тем не менее, спасибо за ваш вклад.
shhelen Автор
26.07.2021 12:03+2Я просто забыла добавить ее к ссылкам - уже исправила) Да, у вас очень хорошая статья, послужила мне вдохновением)
StriganovSergey
26.07.2021 12:01+2Вопрос скорее риторический:
Стал бы Маск тратить время свой жизни на попытку устроиться на такую работу?
И кем бы он стал в итоге, если бы устроился?
Но, я с уважением отношусь к затраченным усилиям и полученному опыту.
Желаю удачи!..
bogolt
26.07.2021 13:04+1Контрриторические вопросы:
Должен ли каждый человек ( или айтшинк ) повторить путь Маска?
Преследует ли каждый человек те же цели что Маск?
Кого будет нанимать на работу Маск если все будут Масками?
DMGarikk
26.07.2021 13:21он собой бы и остался, принцип мышления людей не зависит от работы на которой они работают
устроился бы… ну и уволился потом если бы ему не понравилось
HellWalk
26.07.2021 12:20+1Это был опыт, я познакомилась со многими хорошими специалистами и моя вторая команда была one love, но я уже просто устала от ненормального work-life balance в компании, не особо интересных задач, зарплаты ниже рынка и своих непонятных карьерных перспектив. После Яндекса мотивации работать не было вообще.
С удовольствием бы почитал статью об этом опыте
P.S.
Кстати, а прокаченный профиль на GitHub как-нибудь влияет на собеседования в тех же FAANG? Есть у кого-нибудь такой опыт?
0xd34df00d
26.07.2021 20:16Кстати, а прокаченный профиль на GitHub как-нибудь влияет на собеседования в тех же FAANG? Есть у кого-нибудь такой опыт?
Скипнули phone screening в гугл, например.
Не в гугл скипнули вообще техническое собеседование и оставили только, ээ, аналог system design и некое подобие поведенческого интервью.cebka
26.07.2021 20:46-1Странно, у меня даже не смотрели ни разу. Я уже даже хочу сделать тест на идиотов при прохождении собеседований: не смотрят в гитхаб, сразу лесом. Впрочем, пока охоты снова проходить эти собачьи свадьбы что-то нету.
questor
08.09.2021 11:39Несколько лет назад активно обсуждалось, что каждый айтишник должен иметь акк на гитхабе и все нормальные программисты плевались, что этот критерий заспамили - просто создавали пустые аккаунты, а эйчары ловились даже на это.
Я говорю про рунет если что.
И лично у меня возможно какой-то странный кейс, как будто именно мне выпадает "решка сто раз кряду", но у меня не было ни одного интервью, на котором бы программист подтвердил, что ему передали линки на мои профили гитхаб (специальный проект который можно обсудить на интервью, чтобы не обсуждать что-то под NDA) и so (ну там например есть золотая метка по моему языку программирования), даже когда обещают, что всё передадим, ага. Последний кейс был ровно вчера, я регулярно собеседуюсь. Ну что ж, иду на общих основаниях, понимаете опыт его все равно не скроешь.
В общем, за всех не скажу, но моё впечатление, что в нынешнее время на это смотрят крайне редко в русских (здесь техническое интервью до сих пор основано на вопросах по конкретным технологиям) компаниях.
(кажется, я промахнулся немного с веткой: мой ответ - на комментарий чуть выше по дереву)
CrashLogger
26.07.2021 12:35+3Хорошая статья, четко все расписано. Остается непонятным только, ради чего все это. Что такого в этом FAANG, что нужно полгода тратить все свободное время на подготовку к интервью ? При том, что можно устроиться в другие хорошие компании без всего этого геморроя и получать не сильно меньше денег.
greenEkatherine
26.07.2021 16:29ради релокейта например. не-faang тоже релоцирует, но обычно это дольше и на меньшие деньги
euroUK
26.07.2021 16:31Только ради релокейта в США. Пока вы будете полгода учить алгоритмы, я уже полгода буду работать в условной Голландии или Ирландии
greenEkatherine
26.07.2021 18:18вы умеете мгновенно релоцироваться без whiteboard-инга? в какие компании, если не секрет? хотелось бы конечно, чтобы это был практический опыт, а не теория
0xd34df00d
26.07.2021 20:27Ну мне в Indeed предлагали, например, вплоть до оффера. Там, правда, на джаве писать надо, поэтому я отказался.
Без алгоритмов предлагали на machine learning engineer'а в компанию, упомянутую топикстартером, я туда в итоге согласился. Тоже пять раундов, конечно, но один — совсем лёгкий вопрос по плюсам (типа, написать свой
auto_ptr, что для 2014-го года было ещё более-менее релевантно), три — по машинному обучению (тоже не очень сложные вещи типа «нам надо категоризовать почту, придумайте фичи»), один — с эйчаром о жизни и зарплате.greenEkatherine
26.07.2021 22:47так логично, что на ML позицию свои вопросы, но по сути - то же многоуровневое собеседование, к которому надо готовиться
euroUK
26.07.2021 21:40Практически любая небольшая компания. Я так получил как раз таки пятилетний (а больше не бывает, потом гражданство) ворк пермит. Причем я мог спокойно поменять работу на другую.
Кстати, маленькие компании зачастую веселее и больше вовлечения, я до сих пор общаюсь с людьми (проработав год) и как открою съезжу потусить.
greenEkatherine
26.07.2021 22:58Все еще не понимаю, как это опровергает мой тезис про дольше и/или меньшую зп.
Практически любая небольшая компания
Ну да, ведь практически любая небольшая компания релоцирует, общается на английском/русском, а не на местном языке, и не просит написать код на собеседовании. Осталось только узнать список таких компаний.
Причем я мог спокойно поменять работу на другую.
Кстати, маленькие компании зачастую веселее и больше вовлечения, я до сих пор общаюсь с людьми (проработав год) и как открою съезжу потусить.
А в FAANG-е, видимо, приковывают к рабочему месту и запрещают разговаривать не по работе.
Lambasruchei
26.07.2021 13:59+2Мне вот всегда не понятно было, зачем такие умные люди всегда пытаются устроиться куда-то на работу? Более того, работу в "алчных корпорациях" называют работой мечты.
Видимо, мозг человека может находиться только в одном оптимальном состоянии - если где-то слишком много, значит где-то будет слишком мало. Так вот и люди, которые и исполнительные и талантливые, и со всеми задачами справляются на отлично, но не самостоятельные. Их нужно постоянно мотивировать, либо пинать, либо хвалить, а также постоянно указывать что делать и когда делать.
П.С. поэтому и гугол (майкрсофт, яндекс и др...) с каждым годом все УЕЕ и УЕЕ, а как иначе, если там все больше и больше вот таких умных и исполнительных
CrashLogger
26.07.2021 16:35+2А какая альтернатива ? Свой бизнес ? Для этого нужны совсем другие качества и на их развитие нужно потратить время. А программист свое время уже потратил на программирование. Поэтому ему проще работать на кого-то и заниматься тем, что у него хорошо получается, отдав на аутсорс работодателю бухгалтерию, продажи, HR и прочие бизнесовые задачи.
deeptowncitizen
26.07.2021 13:59Гоняют по алгоритмам и структурам данных по той причине, что в таких компаниях инженеры сталкиваются с проблемами, которые не решаются через stackoverflow.com. Это понимание приходит в тот момент, когда видишь, что за последний год многократно приходилось использовать эти знания. В отличие от 15 предыдущих.
А вот системный дизайн очень субъективный. За 30-40 минут нужно не только нарисовать квадратики в ужасном редакторе, но и формализовать максимально нечёткие требования, придумать какую-то бизнес или UI/ux концепцию, а потом ещё и углубиться в ненужные детали. И по пути все время думать, кто же этот человек, который сразу хочет дизайн на млрд запросов. А ещё понимать абсурдность ситуации, что все происходящее практически никак не ложится на архитектурные стандарты.
DMGarikk
26.07.2021 15:28+2Гоняют по алгоритмам и структурам данных по той причине, что в таких компаниях инженеры сталкиваются с проблемами, которые не решаются через stackoverflow.com. Это понимание приходит в тот момент, когда видишь, что за последний год многократно приходилось использовать эти знания.
огромные у меня сомнения что даже 80% разработчиков сталкиваются с проблемами которые не решаются на SO и вообще простой програмистской логикойв таких компаниях
ну вот я работал в одной компании, не faang но всёже, ничего там выходящего за рамки не былоwataru
26.07.2021 16:59+2Это заблуждение. Если не знать алгоритмы, то совершенно легко даже не заметить, что они вам, оказывается, нужны. Ну просто пишется "простая програмистская логика" — наивный метод в тупую. И даже мысли, что тут что-то улучшить можно не возникает.
огромные у меня сомнения что даже 80%
Да даже если их 10%. По изложенной выше проблеме, невозможно нанимать "кодеров" и "алгоритмистов" отдельно. Потому что "кодер" даже не задумается об обращении к "алгоритмисту" и тем придется просматривать вообще весь код и постоянно что-то переписывать. Имея бюджет и количество кандидатов как в FAANG легче просто нанимать только "алгоритмистов".
iroln
27.07.2021 03:12Если не знать алгоритмы, то совершенно легко даже не заметить, что они вам, оказывается, нужны. Ну просто пишется "простая програмистская логика" — наивный метод в тупую. И даже мысли, что тут что-то улучшить можно не возникает.
Если вы вчерашний не самый прилежный студент без опыта реальной работы, может мысли и не возникнет. Если у вас есть хоть какой-то опыт в программировании вещей сложнее "табуретки", все нужные мысли возникают сами собой. Включается такая полезная штука как способность обобщать и абстрактно мыслить. Очень быстро становится ясно, что наивным способом в лоб задача не решается. А что происходит потом? Потом происходит R&D и в большинстве случаев находится подходящая библиотека, книга, статья или код/псевдокод подходящего алгоритма. И оказывается, что для решения задачи совсем не обязательно зубрить сотни классических и прикладных алгоритмов впрок, вращать и балансировать все возможные виды деревьев, компилировать и транслировать код в уме, писать парсеры на бумажке и т. п. вещи, которые так любят интервьюеры на собеседованиях.
Умные и хорошие книжки про алгоритмы и фундаментальную computer science читать, конечно, полезно и правильно. Оно даёт общее понимание, базовые знания, расширяет кругозор и вообще. Но учить ответы на каверзные вопросы на собеседованиях и делать overfitting своего мозга на определённый класс задач — это, как говорится, за деревьями леса можно не увидеть.
Да, я считаю, что "культура собеседований", образовавшаяся вокруг FAANG-компаний — это временное явление — тупиковая ветвь, ошибочный путь. Но время нас, конечно, рассудит и покажет, кто был прав, а кто заблуждался. :)
wataru
27.07.2021 13:55Очень быстро становится ясно, что наивным способом в лоб задача не решается.
Всмысле? Все решается. Просто там будет O(n^2) вместо O(n log n). Или O(2^n) вместо O(n^3).
iroln
27.07.2021 15:20+1Если программа работает приемлемое/разумное время на том количестве данных, какое у вас есть, то решается, а если нет, то не решается. Вы можете вообще использовать полный перебор и факториальную сложность, если вас это устраивает.
Такие вещи мало-мальски опытный разработчик видит и понимает. Для этого не надо хранить в собственной памяти информацию о решении сотен алгоритмических задач с какого-нибудь leetcode и уметь решать похожие за 15 минут в условиях повышенного стресса. Достаточно возможностей собственного мозга, релевантного опыта и иногда инженерного образования. Когда появится необходимость включить голову и решить задачу, он её решит. Ну или не решит, что тоже возможно, но это мало коррелирует с умением решать оторванные от жизни задачи с leetcode и проходить алгоритмические собеседования у доски. Так же как и яркое олимпиадное прошлое и победы в ICPC не гарантируют, что человек способен работать над сложными программными продуктами, писать поддерживаемый код, документировать свою работу, выбирать правильные архитектурные и инженерные решения и т. д.
wataru
27.07.2021 17:09Если программа работает приемлемое/разумное время на том количестве данных
И часто у вас там программисты замеряют время работы каждого куска и знают точно, что вот в том списке не больше 10-ти элементов всегда? А что делать, если потом выяснится, что элементов может быть 100? Что такое разумное время работы: 10мс — разумное, a 100мс?
Вот и получается, каждая отдельная часть работает приемлемое время. То, что весь проект целиком тормозит и можно почти каждую часть в 100 раз ускорить — само по себе не тригеррит "мало-мальски опытного разработчика" (в вашем понимании, конечно. В моем — у опытного разработчика итак не возникнет никаких проблем решить любую задачу с интервью в гугле. Да, может быть немного медленнее нужного на интервью совсем без подготовки из-за стресса, но не на порядки).
Так же как и яркое олимпиадное прошлое и победы в ICPC не гарантируют, что человек способен работать над сложными программными продуктами, писать поддерживаемый код, документировать свою работу, выбирать правильные архитектурные и инженерные решения и т. д.
С этим не спорю. Вот только единственный способ хотябы примерно проверить все это — это тестовый период месяцев так на 6.
Текущие интервью проверят по крайней мере умение писать поддерживаемый код (хотя бы 10-15 строчек на интервью), хорошую соображалку и знание алгоритмов.
iroln
28.07.2021 23:49И часто у вас там программисты замеряют время работы каждого куска и знают точно, что вот в том списке не больше 10-ти элементов всегда?
Преждевременной оптимизацией точно никто не занимается, но и откровенно неэффективный код стараются не писать. Это то, что лежит на поверхности. Не надо быть семь пядей во лбу, чтобы это понимать.
Практически любой программный продукт проходит этап профилирования и оптимизации по производительности. Тут тоже не боги горшки обжигают, профилированием так или иначе занимаются все разработчики, это такая же рутина как написание и отладка кода.
Текущие интервью проверят по крайней мере умение писать поддерживаемый код (хотя бы 10-15 строчек на интервью), хорошую соображалку и знание алгоритмов.
Умение писать поддерживаемый код можно проверять по разному, алгоритмические задачи на время как на олимпиаде по программированию это умение как раз не проверяют. Если у человека есть open source проекты, можно посмотреть в их код и поспрашивать по ним, можно устроить сессию парного программирования и поработать с человеком в паре над кусочком какой-то реальной задачи. Это будет эффективнее и менее стрессово чем устраивать 5 этапов изнурительных многочасовых алгоритмических собеседований. Но это сложно для самих собеседующих, им нужно лучше готовиться, разбираться в чьём-то коде, придумывать задачи для парного программирования и т. д. Проще ехать по накатанной, выспрашивать и требовать у людей академических знаний, потому что это просто. Сам прорешал сотню другую задачек с leetcode или hackerrank и гоняй всех хоть до посинения. И при этом делать вид, что это реально проверяет профессионализм, умение мыслить и быстро решать рабочие задачи.
wataru
29.07.2021 12:12Умение писать поддерживаемый код можно проверять по разному, алгоритмические задачи на время как на олимпиаде по программированию это умение как раз не проверяют. Если у человека есть open source проекты, можно посмотреть в их код и поспрашивать по ним,
А если нет opensource проектов? Потом, если такие интервью будут в FAANG, то вместо leetcode "научим решать задачки" будет куча серивсов "соберем вам аккаунт на github и научим убедительно о нем разговаривать". И интервью в итоге будет проверять только умение балаболить, а не умение писать код.
можно устроить сессию парного программирования и поработать с человеком в паре над кусочком какой-то реальной задачи. Это будет эффективнее и менее стрессово чем устраивать 5 этапов изнурительных многочасовых алгоритмических собеседований.
Работать с человеком над кусочком реальной задачи? Ну вот я даю на инетрвью ту реальную задачу, которую сам коммитил в прод. Но это такая же "олимпиадная" задача, какие вы презираете.
Потом, как вы себе это парное программирование представляете? 5 разных интервьюверов все-равно будут, потому что надо исключить предвзятость и случайности. Что, вшестиром программировать? Будет ругань "я не могу программировать, когда на меня 10 глаз смотрят и высокомерно хмурятся". Как долго такая сессия парного программирования должна происходить? Как много и что должен интервьювер программировать? И главное, чем это принципиально отличается от текущего интервью, где происходит именно что парное программирование, только задачи чуть посложнее fizz-buzz?
Ну не получится проводить 5 двухчасовых сессий "парного программирования". Будут по всяким условным хабрам еще сильнее ругать условные гуглы за их зверские интервью. Это не скейлится. В итоге будут такие же 4-5 интервью по ~45 минут. Задачки будут сильно абстрактные, потому что ну не получится за это время сделать какую-то большую реальную часть чего-то. В реальную кодовую базу, как бы хороша она не была, надо въезжать длительное время.
Потом, вот вы обвиняете интервьюверов в лени и безответственности, но приведите хотя бы один пример задачи для такого парного програмирования сами.
Проще ехать по накатанной, выспрашивать и требовать у людей академических знаний, потому что это просто
Самое академическое знание, что вам нужно на интервью — это понятие ассимптотической сложности. Не требуют на интервью писать ни красно-черные деревья, ни алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна. Знать что есть такие структуры: хеш таблицы, деревья (set/map), куча и когда их можно применять. Ну, уметь писать рекурсию + вставлять туда запоминание (вот и все "динамическое программирование"). Ну, еще уметь формализировать задачу, разбивать ее на части и логически рассуждать надо — но разве это плохие качества для программиста?
iroln
29.07.2021 13:04+1То, что вы говорите — это вроде всё правильно. То есть вы говорите правильные слова, но на деле получаются перегибы. Ну вот взять хотя бы эту статью про собеседование в Яндекс. Зачем это всё? Что это проверяет, какие навыки и знания? Как это прогнозирует, что кандидат подходит? Яндекс устраивает такой цирк для любой вообще вакансии, Python, JS, C++, ML, DevOps, да без разницы, вот тебе несколько собесов с задачками на строки и массивы — решай. Нафига это всё?
Если вам не нравится парное программирование, можно дать тестовое задание, чтобы посмотреть на реальный код. Да, я знаю, что тестовые задания многих возмущают, но это хоть как-то работает, не смотря на критику. Потому что тестовое будет ближе к предметной области реальной работы, его можно обсуждать, можно улучшать, по нему хоть что-то можно понять о профессиональных скиллах кандидата.
Парное программирование тоже можно устраивать по-разному. Необязательно все 5 собеседующих должны одновременно что-то требовать от кандидата, каждый из них может предложить задачу/код, который можно интерактивно разобрать с кандидатом. В моей практике и я сам собеседовал и меня собеседовали, в том числе с online-программированием, разборами тестового, проектированием архитектуры, просто разговорами "за жизнь" и т.п. Есть опыт как токсичных, так и не токсичных собесов. Для себя я сделал вывод, что собеседования — это не экзамены, к ним не нужно специально готовиться пол года, твоих существующих проф. знаний и уровня либо достаточно, либо недостаточно. Если компания требует от меня overfitting на олимпиадные задачи для прохождения собеса, мне с ней скорее всего не по пути. Я не буду доказывать, что достоин чести работать в этой компании.
wataru
29.07.2021 13:58+1Ну вот взять хотя бы эту статью про собеседование в Яндекс.
Там вроде есть некоторые косяки с HR. Все задачи тривиальнейшие. Чуть-чуть выше уровня fizz-buzz. Даже автор новый мем фосит: "Ну ок, хотят проверить знание каких-то базовых вещей."
Конечно, многим хотелось бы побалаболить на какие-то высокие темы, но это, во-первых, очень субъективно и, во-вторых, проверяет больше как подвешан язык. Для всяких "накидать архитектуру высоконагруженного прило..." (пожелание из статьи) уже есть отдельное system design интервью.
Яндекс устраивает такой цирк для любой вообще вакансии, Python, JS, C++, ML, DevOps,
Разработчик на питоне принципиально не может столкнуться с задачами требующими хоть минимального понимания структур данных и алгоритмов — да? А js, если вдруг это не фронтенд, а какой-нибудь NodeJS? Там данных вообще нет? Это только на C++ все встречается что ли? Не согласен, что вы эти категории выделяете как недостойные интервью с простыми задачками на программирование. Почему ML и DevOps-ов в яндексе по алгоритмам гоняют — я не знаю. Может, потому что они не только скрипты для системы сборки или нейросетки пишут — раз чел будет хоть немного программировать, пусть проходит еще и те же интерью для программистов. Может потому что компании лень плодить 100500 видов интервью. Может, если кандидат про ML ничего связного не скажет, по результатам уже этих интервью можно будет взять на обычного разработчика.
Если вам не нравится парное программирование, можно дать тестовое задание, чтобы посмотреть на реальный код. Да, я знаю, что тестовые задания многих возмущают,
Вы сами написали про "возмущают". Во-первых, это тоже не скейлится. Ну не будет кандидат решать 4 тестовых задания, каждое из которых занимает несколько часов. Во-вторых, там можно легко читерить. Задание за какого-нибудь китайца сдает его друг-программист и кратко объясняет, какие ключевые слова потом говорить. Вот и получается опять, что хорошо подвешанный язык становятся ключевыми навыками для прохождения интервью. Уже сейчас люди приходят не умея писать даже fizzbuzz — авось пронесет. Зарплата в гугле вкусная а изображать деятельность можно довольно долго. В-третьих, над этими тестовыми заданиями будут точно так же сокрушатся, что оно все слишком сложное, примеры все нереалестичные. Вот дали бы задание переложить Json — это реалистично. Только что это задание вообще проверять будет? Это даже не fizz-buzz уровень.
Необязательно все 5 собеседующих должны одновременно что-то требовать от кандидата, каждый из них может предложить задачу/код, который можно интерактивно разобрать с кандидатом.
Это и есть текущий формат инетрвью. Только вы хотите задачи потривиальнее, видимо. Разбор кода — это хорошо, но это не показывает, что кандидат умеет писать код. Это как с иностранными языками, слушать/читать на порядки легче, чем говорить самому.
iroln
29.07.2021 14:41Разработчик на питоне принципиально не может столкнуться с задачами требующими хоть минимального понимания структур данных и алгоритмов — да? ...
Конечно может, от языка это не зависит. Но от языка зависит предметная область и то, чем придется заниматься. А заниматься решением задач на строки без готовых библиотек точно не придется никому из перечисленных в 99% случаев. Верстальщика надо спрашивать об одном, инженера по devops о другом, а С++ разработчика в команду ClickHouse о третьем. Невозможно унифицировать этот процесс до одинаковых собеседований для всех подряд под одну гребёнку. Оно не будет работать. Но о чём говорить если:
Может потому что компании лень плодить 100500 видов интервью
Пока у крупных и известных компаний километровые очереди из кандидатов на входе, им не о чём переживать, можно иметь КПД найма 10% и будет приемлемо.
Недавно мой товарищ собеседовался в Яндекс на позицию ML исследователя. Его завалили задачами на деревья и строки. Только один собеседующий попросил разобрать архитектуру нейросетки.
Вот такого быть не должно, я считаю.
Я не о том говорю, что не надо давать задачи или надо давать тривиальные задачи или проводить собеседования без проверки проф. скиллов. Просто не должно быть такого перекоса как сейчас, что задачи академичны и к ним надо специально готовиться пол года, словно ты готовишься к поступлению в университет и решаешь книжку с задачами по математике. Пусть даже задачи не такие страшные как их малюют, но сама культура, которая сложилась в проф. среде, вот такие статьи как эта, в которых пишут, что к собесам надо готовиться по пол года, их же много, такие статьи появляются постоянно. Ведь это же и есть читерство по сути. Решая несколько месяцев задачи для собеса ты умнее не становишься, ты просто обучаешься решать такие задачи, мозг начинает делать это хорошо и быстро, но опыта решения проблем реального мира это не добавляет.
Задание за какого-нибудь китайца сдает его друг-программист и кратко объясняет, какие ключевые слова потом говорить
Такого ни разу не встречал. Мне кажется, достаточно легко вывести человека на чистую воду.
wataru
29.07.2021 15:00+1такие статьи как эта, в которых пишут, что к собесам надо готовиться по пол года,
Это естественный процесс. Вы какую систему интервью не введете, в итоге в гугл придется готовиться. Потому что желающих на одно место слишком много. Кто-то будет готовиться, чтобы получить приемущество, в итоге общий уровень кандидатов растет, в итоге уже без подготовки такое интервью не пройти, потому что на фоне специально тренерующихся — вы будете вяло смотреться.
Решая несколько месяцев задачи для собеса ты умнее не становишься, ты просто обучаешься решать такие задачи, мозг начинает делать это хорошо и быстро, но опыта решения проблем реального мира это не добавляет.
Чем "реальная" задача принципиально отлечается от таких вот "алгоритмических" задач? Рельные проще — да, но только и всего. Повторюсь — я на интервью справшиваю реальную задачу, которую самому пришлось решать по работе.
Такого ни разу не встречал. Мне кажется, достаточно легко вывести человека на чистую воду.
То, что попытки точно есть и будут, по-моему отрицать сложно. Во-первых ко мне на интервью приходят люди, которые fizz-buzz написать не могут. На что-то надеятся всеже. Про вывести на чистую воду — вы заблуждаетесь. Искусство bullshiting'а точно так же применимо к техническим наукам. Потом, повторяя предыдущий пункт: люди начнут готовится и очень скоро потребуется настоящее ораторское искусство, что еще дальше от реального программирования нежели умение решать "алгоритмические" задачи.
Vilaine
27.07.2021 05:56Если не знать алгоритмы, то совершенно легко даже не заметить, что они вам, оказывается, нужны
Для изучения довольно большого количества алгоритмов можно потратить всего несколько недель вечеров. На уровне "знаю что есть и примерно что такое, могу нагуглить готовые реализации" (что стоит делать и т.н. "алгоритмистам", в принципе). Многомесячные подготовки на литкоде, как у автора, для этого не нужны.
DMGarikk
27.07.2021 11:28+1Потому что «кодер» даже не задумается об обращении к «алгоритмисту» и тем придется просматривать вообще весь код и постоянно что-то переписывать.
вы меня удивляете, у вас там тимлидов нет и прочи архитекторов? линейный код пишут сеньоры-суперстары? я в такой конторе кстати тоже работал, это вообще кошмар и ужасИмея бюджет и количество кандидатов как в FAANG легче просто нанимать только «алгоритмистов».
ну вот я про это тут гдето рядом и говорю.Ну просто пишется «простая програмистская логика» — наивный метод в тупую. И даже мысли, что тут что-то улучшить можно не возникает.
ну софт гугла както так и работает, взять даже шаблоны андройд приложений из android studio, сколько блин я её помню, они никогда не работали из коробки нормально и вообще юзают depricated ф-ции, документацию для разработчиков вообще никто не поддерживает и не вычитывает, про тормоза фронта gmail тут рядом уже говорили…euroUK
27.07.2021 12:01Ну берут же алгоритмистов, а не разработчиков. Поэтому все так и работает. Потому что софт это не только бинарные деревья и операции со строками, а еще и архитектура, UI/UX, документация, поддержка.
Если отойти от мейнстрима в сторону специфических расчетных программ, то есть куча примеров, когда университеты делают и продают свои поделки. Алгоритм в принципе работает, но вот в большинстве своем пользоваться каждый день такими программами невозможно из-за отсутствия quality of life, багов и отсутствия документации.
ViacheslavNk
26.07.2021 16:01+1Во многих компаниях возникают проблемы, которые не решаются через SO, на вскидку думаю, что у Oracle, Dell, Intel, IBM, Broadcom, и пр, полно таких задач.
euroUK
26.07.2021 16:10+4Именно поэтому многочисленные поделки Гугла (типа админки гмейла) тормозят так, как будто их джун в Бангалоре левой пяткой писал.
Чтобы писать такие сложные приложения обязательно нужно наизусть помнить как балансировать деревья.
Bellerogrim
26.07.2021 16:49> как будто их джун в Бангалоре левой пяткой писал
По вашим словам можно подумать, что это ваша выдумка.
rotarepo
26.07.2021 17:17Имхо по отношению к задачкам на алгоритмы видно, кто любит поднапрячься и поломать голову, а кто пашет ровно не портя борозды. В отрасли нужны и те, и другие, но одними последними ничего прорывного не создашь.
Vilaine
27.07.2021 06:04Мне, например, нравится решать сложные вещи. Мне не нравится полировать навык чего-то подобного спортивному программированию (чего у меня опыт тоже имеется, но без особых подготовок и, следовательно, результатов), то есть быстрого решения алгоритмических задач на время. Эти задачки очень скоро становятся скучными.
Возможно, что эти компании стараются нанимать людей с крайне высоким интеллектом, кому не нужно такой подготовки для быстрого решения, но тогда эти многомесячные тренировки - это хак системы, обман. Но вроде компании сами говорят "прорешивайте".
strcpy
26.07.2021 18:14+4Всё это выглядит как тест на лояльность -- нужно решать много задачек, которые потом не будут иметь отношения к работе. Если готов угробить кучу личного времени, значит лоялен компании, будешь хорошо подчиняться. Причем это распространяется даже на data science вакансии, например моего приятеля, завалили на system design, хотя он хотел сеточки учить.
kolezz
26.07.2021 22:21А не помните, какие задачи от амазона не получилось одолеть? Случайно не про парковку и расшифровку сообщения?
shhelen Автор
26.07.2021 22:26точно не парковка, 1 - была на строки, 2-я на нахождение оптимальной стоимости сортировки массива в increasing или decreasing случае, где стоимость - это разность между элементами при перестановке (точную формулировку тут не помню, на leetcode такой задачи нет)
Razaz
27.07.2021 15:24Удачи вам в переезде и спасибо за статью. Внимательно смотрите страну, куда поедете. Желательно найти того, кто там живет. Для себя уже решил, что если и двигаться в FAA(M)NG, то только если офис разработки будет в Финляндии или на край - в Норвегии.
0xd34df00d
27.07.2021 19:08+2Интересный выбор стран для работы программистом. Почему именно они, если не секрет?
Razaz
28.07.2021 11:55+1С семьей комфортно. Медицина, садики, школы, соц обеспечение. Мы когда искали куда ехать - это были основные вопросы. Понятно, что если ехать на позицию 10k EUR + то это не так критично, но таких очень мало. И в той же Иландии 10к в месяц не помогут - жилье в Дублине просто космос.
weiser
28.07.2021 08:35в Финке разработчиков нанимает только гугл и то вроде только интернов со степенью PhD либо архитекторов.
Более-менее похожий уровень интервью для мидла здесь можно найти в Vaadin и Gitlab, там несколько алгоритмических собеседований. Крупные компании (Нокиа, Эрикссон) вроде только один собес посвящают алгоритмам, ну да они и не FAANG.
А так обычно люди за такой работой из Финляндии переезжают в ту же Ирландию.
Razaz
28.07.2021 12:01Согласен, у меня коллега так и уехал. Vaadin - Турку :P, GitLab вроде полный ремоут есть. Но вопрос соответствия тому же финскому законодательству. У меня была пара собеседований, где я задавал вопрос - 5 недель отпуска и отпускные, весь Июль как отпуск, оплата переработок, 37.5 часов рабочая неделя и тд. Кроме общих бла бла бла ответа конкретного небыло :)
wataru
28.07.2021 12:10В финке есть офис разработки гугла? 4 года назад там был только датацентр и разработчиков не было.
weiser
28.07.2021 12:31Сам удивлён :) изначально собирался написать что в Финляндии вообще нет должностей разработчиков в компании FAANG, ан нет, на https://careers.google.com/ оказывается есть и даже несколько! Правда, кажется в основном не чистые разработчики требуются, больше интеграторы.
С интернами интересная штука получается, как я понимаю могут нанять в Финке но по сути требуется переезд?
darkolorin
29.07.2021 15:47Когда-то самым популярным алгоритмом на интервью в Google было вот это чудо - https://en.wikipedia.org/wiki/Seam_carving
Я вообще узнал о нем во время интервью :)Vilaine
30.07.2021 05:43Курс по алгоритмам от Принстона и Седжвика (вроде 2 часть) даёт задание реализовать его на графах, кстати.
Vilaine
11.08.2021 23:24Amazon
Язык: Python
Оценка процесса интервью: 7 из 10
Тут все прозаически эпично. Я завалила online assessment, было 2 задачи на 45 минут
В общем, вы меня сподобили ответить рекрутеру оттуда и попробовать тоже. У меня было 2 задачи уровня very easy и somewhat easy. После каждой нужно было вписать её описание и сложность алгоритма. Таймер был на 105 минут, дескать, 90 минут на 2 задачи и 15 минут на их описание. Assessment был для SDEII, не знаю, может лёгкие задачи — это особенность этой низкой позиции.
Потом назначили 4 часа собеседований на 1 день, одно по часу. Наверно, там и будут сложные задания, но я к тому времени уже забуду про этот топик и не расскажу =)PsyHaSTe
20.08.2021 13:41+1А я напомню
Vilaine
10.09.2021 20:18+4Было интервью, 4 штуки в один день. По часу с 15-минутным перерывом. У меня было 4 недели на подготовку с момента одобрения online assessment, по 1,5-2 часа в день среднем. Упор в подготовке на 70-80% на System Design, ибо привычка накодить чего-нибудь у меня есть, даже по таймеру, и основные алгоритмы со структурами данных я знаю, а вот уверенности в таких же своих силах в системном дизайне у меня не было и в том, что там вообще могут спросить.
Первые полчаса у каждого — 2-3 вопроса по Leadership Principles (после ответа интервьюверы дозадавали уточняющие вопросы). Мне лично было сложно отвечать и это отняло больше всего моих умственных усилий, несмотря на некоторую тренировку отвечать на вопросы по этой ссылке до интервью. Каждый может попробовать по ссылке отвечать на примеры вопросов, на некоторых я просто подвисаю (и на интервью такие были).
Вторые полчаса каждого интервью — это техническое задание, 3 кодинга и одно system design.
System design назывался «спроектировать Твиттер», но обращать на слово «Твиттер» не стоит — ТЗ подаётся дозированно, очень ограниченно и нужно допытывать что конкретно нужно реализовать. Не очень хорошо получилось, потому что интервьювер как-то давил, моя модель данных стала неудачной после докидывания требований, а подумать и исправить было сложно в потоке вопросов от интервьювера. Несколько рваная секция получилась, в общем.
На Coding было 3 задания, по сложности близкие к online assessment. На каждое оставалось 30 минут, но на самом деле 20, потому что в конце было 5-10 минут для моих вопросов (они были).
— Найти наиболее квадратное поле клеток, чтобы после заполнения K там оставалось не более X свободных (обычный перебор).
— Преобразовать римские цифры в обычные (были даны примеры, так что принцип был сразу понятен).
— Get top K items, которые постоянно добавляются или увеличивают весь на единицу. Похоже на LFU.
Такие элементарные задачки сложно не решить, но тоже были шероховатости. Возможно, результат был медленнее, чем можно было бы, с парой невнимательных ошибок во время написания.
На следующий же день пришел отказ «not passing score». На мой вопрос, что не так, мне ответили, что конкретно сказать не могут, микс факторов, но в основном из-за Leadership Principles, ещё вроде уточняющих вопросов было недостаточно. Добавили, что, дескать, плохо не было, но это не «bar raiser».
Я хочу ещё отметить, что рекрутер заранее присылает материалы, темы для подготовки, как если они заинтересованы в том, что я пройду фильтры. В плане кодинга рекрутер почти исключительно упирают на алгоритмы и структуры данных, с которыми было связано 0 из 5 кодинговых задач. Даже при отказе мне прислали в советах подготовиться на следующий раз (cooldown 6 месяцев) пару ссылок, как материалы для курса алгоритмов от Принстона (год назад мною пройденный на курсере — советую всем, там сложные задания с автоматической проверкой и его часов за ~150 можно закончить). Немного иронично.PsyHaSTe
10.09.2021 22:19Ясно, спасибо. В амазон значит пока соваться не буду, учить религиозные талмуды "как жил основатель" нет никакого желания.
euroUK
Поздравляю. Ну с точки зрения инженера почти без опыта более менее понятно. Вопрос что делать архитектору с 15 годами опыта? Ну не деревья же строить?
shhelen Автор
Тут лучше пообщаться с ребятами, кто проходил собеседование на L6, там вроде большой упор на системный дизайн и behavioral
DarthVictor
На L5 в Фейсбуке меня про деревья спрашивали.
smartello
Там действительно бОльший упор на системный дизайн и behavioural (который на L6 в ФБ я успешно завалил без комментариев с их стороны), но кодинг весь точно такой же и без него пройти не получится.
mickvav
А почему бы и не построить? С 15-ю годами опыта вам восстановить все эти базовые вещи в памяти будет стоить не сотни, а максимум десятки прорешенных задач литкода. И надо понимать, что большой конторе вы можете быть нужны как ментор орды джунов, которым придется на пальцах объяснять базовые вещи. Для этого эти вещи таки знать надо...
Wan-Derer
А откуда бы там "джунам" взяться если даже студенты там проходят такой же отбор?
mickvav
И да и нет. Для fresh grad-ов и интернов часто бывает упрощенный процесс с другими порогами.
dtfkalalka
Будете делать всё, что джуны и мидлы. Плюс своё. Тоесть всё будет. И деревья и остальное. Только еще про менеджмент и систем дизайн. Вас таких 10000 на 1 место. Можно и подурачиться.
Dicebot
Как раз проходил пару месяцев собеседование в Amazon в Берлин, сильно алгоритмическая задача была только в автоматическом кодинг тесте. Во всех пяти последующих интервью с живыми людьми был преимущественно акцент на system design и поведенческие вопросы. Как я понял, выбор вопросов на интервью во многом - выбор конкретных интервьюеров, поэтому практический опыт у всех может быть разный.
К интервью специально не готовился, было как раз интересно посмотреть, можно ли пройти чисто на опыте - мечты работать в ffang никогда не было. Оказалось, что можно, но нужно как раз, чтобы немного повезло с интервьюерами - меня охотно и много спрашивали про архитектуры распределённых сервисов.
Это была не позиция архитектора, кстати, просто опытного разработчика.
FlyingDutchman2
15 лет - это еще куда ни шло, а что делать мне с 30 годами опыта? Хотя вопрос, конечно, риторический - таких старых, как я, в FAANGи не берут.
wataru
Неправда. По крайней мере в гугле. Те, кто решения принимают (комитет по найму) — ни вашего возраста, ни пола, ни имени не знают. Только отчеты с интервью. А от интервьювера в отчете только объективная часть — решил ли задачу, сколько времени потратил, какие идеи были. У меня один коллега 50+ был нанят недовно.
FlyingDutchman2
У него тоже спрашивали, как развернуть двоичное дерево?
wataru
Ну не конкретно этот вопрос, конечно, но что-то из того же класса.