Комментарии 177
Спасибо, было интересно читать!
В задачах на кодинг всегда можно было выбирать любой язык? Среду для разработки можно было выбрать, или нужно было использовать их собственную? Если их собственную, но насколько она хороша? Ближе к блокноту, или с автокомлитом, и т.д.?
Повезло тебе, я проходил onsite интервью 2 года назад, мне фидбэк не дали, сказали что у них так не принято
Было где-то 5-6 поведенческих вопросов и тривиальная задача: найдите файл с заданным расширением и с заданным размером.
У меня такая задача была как раз на ООП, где интервьюер постоянно ее усложнял: давай добавим в поиск дату файла, несколько имен файлов, маску имени и т.д. в итоге пришли к выводу с интерфейсов которые содержит разные реализации.
Вообще интервью мне понравилось, были приятные впечатления, кроме одного интервьюера, который оказался переехавшим из Москвы, вел себя хамовато... или я не привык к таким
думаю стебутся ребята)
Если завалишь ЛП то каким бы ты не был спецом - тебя не возьмут. Говорю как работник. И, самое главное, тебе об этом не скажут.
Если классно сдать ЛП, но дать слабину в техническом плане - тебя возьмут, т.к. ты докажешь им что ты сможешь и подтянешься.
Так что не игнорируй S.T.A.R и придумывай кучу историй как ты develop-ил the best, insist-ил на высоких стандартах и obsess-ил над клиентами и далее по списку
дык по стар и делал) само собой) просто кейсы закончились, но вобщем я знаю, чтоне возьмут, как по мне ИМХО это через чур. За все этапы у меня спросили около 50 таких вопросов. то есть это 50 кейсов... У меня опыта 3 года, у них было мое СV.
Дело в том, что один кейс можно натянуть на несколько ЛП и этим нужно пользоваться. Главное чтобы один и тот же кейс не повторялся у одного и того же интервьювера. И вполне окей если один и тот же кейс с нужным уклоном использовался бы дважды у разных интервьюверов для разных ЛП с правильным разъяснением. По крайней мере я так делал и прокатило. Завал ЛП - не найм 100%. Нужно быть убедительным, когда чешешь им по ЛП. 3 года - не оправдание, в Сев. Ам. три года - это вечность.
Я все равно больше приверженец подхода "а давайте поговорим про ваш опыт" и все, без этих постанов. Там свои выводы на счет лидершипов можно сделать)
Так им редко интересен опыт. Им интересно, чтобы ты из шкуры лез и был проактивен. Я помню мне назначили первый фон колл и сказали что будет сугубо техническое. А по факту были только ЛП и немного "за жизнь". В конце интервью я спросил: как так, обещали тех а по факту было не тех. На что мне девушка ответила: если ты семь пядей во лбу тех, но не проходишь по ЛП - ты нам не нужен. А если у тебя не хватает тех знаний, но по ЛП всё отлично, то мы тебя возьмем, а тех - научим. Кстати в ту попытку я завалил ЛП и не прошел... Потому с амазоном - убираем легкомысленное отношение к ЛП и всё станет ок.
Да, дисклеймер - я бы лучшему другу не пожелал бы тут работать. Но если это способ "завести трактор" - то почему бы и нет. Главное - вовремя из амазона уйти. Не задерживайтесь здесь.
Оценить пуленепробиваемость и отказоустойчивость кандидата. Но это всего лишь моё мнение. Что они на самом деле хотят могут не знать даже они.
Практика показала, что в реальной работе лучше всего себя показывают люди, обладающие определенными личностными качествами, которые и стараются определить у кандидата спрашивая поведенческие вопросы о прошлых проектах.
Дак, можно же начать придумывать всякое)
Если честно, были кейсы, которые не совсем шли под прям "кейс" и пришлось немного приукрасить и т.д. В моем случае - это было неизбежно, потому что, если по честному, я бы из всех ответил бы может на половину, а у них не принимается "I didn't have such a situation", я пробовал.
"I didn't have such a situation" вообще вроде валидный вариант, это говорил мне их HR, и я его использовал на пару вопросов. Ну иначе это бессмысленно, как вы сами сказали, придется придумывать сказку.
Неправильно вы дядя Федор бутерброд едите (ц). В таких случаях я натягивал ситуацию на ближайший ЛП и прямо в нос спрашивал, либо утверждал: приведенная вами ситуация ближе всего подходит под ЛП №х и сразу давал зачёс по готовым шаблонам :)
Придумать от начала до конца непротиворечивый кейс не так просто, как кажется (особенно для bar raiser с сотнями собесов за плечами)
Бар рейзеры тоже люди с их недостатками. И реально бар увы давно не рейзится в найме. Мне ржачно когда на MGHD говорят, что следующий кандидат должен быть на 50% лучше чем вся существующая команда. Написано красиво, а по факту я наблюдаю непотичных бар рейзеров, которые нанимают своих, которые вообще не подходят для работы... Но колесо крутится - лавэшка мутится, а за ошибки в найме никто не несет ответственности. Очень много тупых проблем в амазоне тупо забрасывается большим количеством бабла, как бы это не фругально не звучало :)
Чисто по-приколу
Могу тоже добавить от себя, так как этим летом собеседовался в AWS Европа. Все также, в начале 2 задачки на HackerRank уровня medium/hard. Потом phone screen interview одно.
Но между ними можно посетить онлайн meeting с HR, где расскажут, что будет на вопросах по leadership principles, пришлют варианты вопросов по ним. Вообще этих вопросов, да, будет супер много, и они будут примерно отнимать 30 минуты в каждом часовом интервью. Но к ним очень легко подготовиться, я, где-то в течение 2 часов, просто выписал себе в тетрадь все ответы с примерами из жизни (они даже сами подчеркивают, что ответ должен быть с примером из вашей практики) и этого хватило, на последних интервью я просто даже "читал" по бумажке (это не запрещено).
Ну и после phone screen интервью было 4 подряд online интервью в Amazon Chime, вместо on-site. Из leetcode была только одна задача (что-то вроде пройти конем по шахматной доске из одной точки в другую за минимальное число). Следующая задача была сформулирована как написать игру, ссылку на которую мне скинули (это был sokoban, как я потом узнал). И две другие были design interview: спроектировать сервис Amazon Prime Video, и какая-то задачка на управление светофорами (я так и не понял, что там от меня требовалось, но почему-то именно ее я прошёл :)
Вообщем один из интервьюеров (задачка с игрой sokoban) сказал нет, поэтому я не прошёл. Мне сказали, чтобы пройти нужно получить да от всех. Фидбек есть, но формальный, они не ответили мне на вопрос почему нет, а только где. То есть сказали, что прошёл все leadership и решил 3 из 4 задач.
С написанием игры конечно было сложнее всего понять, что от меня требуется. В итоге пришли к тому что, я должен написать модель игры с перемещением кубиков по карте персонажем. Ну и позже, когда поиграл немного понял, что неправильно понял логику перемещения кубиков 😅
Главное в design interview подготовить среду в которой будет удобно рисовать. В идеале, наверное, стилусом на планшете.
Это интересно. Прям игру писали, сколько времени дали на это? Или просто нужно было накидать классецы, в плане что с чем будет комуницировать?
На все задачи было по 30 минут примерно, потому что в начале leadership bullshit :) я так понял, что нужно было понять какую часть логики писать, может даже определить самому, ну и дальше как успеешь. Понятно, что за 30 минут много не напишешь. Но задача была сформулирована именно в одно предложение, написать игру по ссылке. Дальше в процессе обсуждаешь.
Я помню, вроде начал с классов модели, которая хранит карту с объектами. И класса персонажа с методом move, который пересчитывает состояние карты в зависимости от действия игрока.
Точно был косяк в том что я подумал, что ящики могут толкать друг друга, но оказалось, что персонаж может двигать только один ящик за раз.
На какой уровень вы собеседовались?
В конце прошлого года собеседовался на Senior SDE (L6), также был HackerRank medium + hard, при этом hard я решил только частично. Тоже был phone screen с LP + медиум задачкой. Однако финальным этапом было 5 собеседований. 3 из них с инженерами.
Интервью с инженерами включали в себя Leadership Principles и задачку на программирование уровня медиум: простой DFS на графе, задачка на MaxHeap, задачка на проход по массиву с использованием двух указателей. На задачку оставалось 20-30 минут. Следом интервью на System Design + LP, и еще одно интервью целиком на LP.
Фидбек от моих собеседований был таким: meets the bar для программирования, bar raiser для LP, does not meet the bar для System design-а. В принципе справедливо, я меньше всего готовился к систем дизайну, и это сказалось. Не помогло и то, что последнее собеседование по систем дизайну было поздно вечером.
Оно и так и не так. Если ставят лайк и дизлайк - то один дизлайк и ты не нанят.
Но если ты одного интервьювера удовлетворил суперски - он может поставить суперлайк и тогда ты нанят.
Аналогично бар рейзер может поставить лайк и ты будешь нанят.
I can’t give you specifics but it was a mix and it was mostly on the LP’s. There were feedback on not clarifying questions and other things. You did not do so bad but just overall they felt it was not bar raising.Это, конечно, лучше, чем у некоторых компаний «у нас нет для вас фидбэка».
У меня был забавный вариант когда я шёл на позицию разработчика мобильного софта, а меня вдруг стали интервировать на ДевОпса. Я в теме что-то понимаю, но не достаточно для уровня интервью в FAANG'е. И, конечно, меня утопили и на этой почве просто тупо забанили на какие-то либо попытки в будущем.
Да, во внутренней системе найма есть такой флаг, при котором на тебя не обратят никогда больше в жизни.
Лидершип принципы офигенская штука. Реально работает. Сегодня всяких технологий и языков программирования дочерта, все меняется каждый день, и Амазон просто хочет брать людей которые сами разберутся какую технологию взять, сами все освоят и доведут проект до конца, по пути решая все проблемы какие надо, и с софтом и с хардом и с людьми и с процессами. Ну при этом хочет убедиться что у людей правильные приоритеты.
Да, я понимаю, но есть моменты,когда они хотят от тебя того, что ты дать не можешь, и твое "I didn't have such a situation" их не устраивает, они просто повторяют тот же вопрос другими предложениями, и форсят что-то отвечать, и вот тут, как по мне, процесс идет не так, как должен.
Их цель не узнать была ли такая ситуация или нет, а понять как кандидат повёл бы себя в этом случае.
Даже хорошо, что не было такой ситуации, так как под стрессом человек склонен делать больше глупостей, чем если просто общаться на эту тему и генерить банальные советы с чашечкой горячего какао в руке.
Я могу сам напридумывать кучу вопросов на эту тему и сам же предложить их изящное решение. Половина из них не сработает в реальной жизни из-за человеческого фактора и общего раздолбайства, но зато как красиво будут звучать решения!
Кстати, когда амазон хочет кого-то уволить, а они имеют стэк-рэнкинг и делают это планово - тебя, как работника, обвиняют в неследовании конкретным ЛП. Так что, да, офигенская штука в том числе чтобы увольнять... Ну и абьюзить
Хорошая фишка -- согласен. Но это можно использовать и себе на руку.
Плановые увольнения идут не личные, а просто, например, 5%. То есть, надо как в том анекдоте про голодного тигра, который гонится за тобой: "не надо бежать быстрее тигра, достаточно бежать быстрее соседа".
То есть, вся проблема сводится только к тому, что бы понять критерии увольнения и не более. И таким образом можно сделать так, что бы тебя было менее удобно увольнять, чем соседа.
Я много видел бежавших медленнее всех, но в хороших отношениях с менеджером, и они оставались. А также видел действительно продуктивных и умных инженеров, которые не играли в "коричневый носик" и оказывались за бортом. Да. когда ты по URA за бортом - то пожизненно забанен для найма в амазон и их подконтрольные компании.
Так что увольнения личные.
В "хороших отношениях" это как раз один из способов бежать быстрее других.
Бег -- это не только знания.
Личные увольнения тоже бывают, но я про обычные плановые увольнения когда начальству надо просто уволить 5% и всё.
А тут дальше вступают в силу голодные игры, когда группа рабочих сбивается в кучку, которая таргетит по их мнению белую(ых) ворону. И ты бы такой хотел бы не участвовать в "политических" играх, но твоё неучастие сделает тебя вороной. А если участвуешь - то уже ты волк и попробовал вкус крови :) Потому я считаю эти вещи очень деструктивными.
На виду у меня была команда, которая приносила результаты. Потом туда пришел новый менеджер-армянин и начал тащить своих армян, а не армян - ставить на план каждый год. Вот уже третий год подряд. И пофиг сколько тикетов или сев2 ты закрыл. Ты просто не такой, так как не свой, и пойдешь на улицу...
Кстати до армянина был неугодный менеджер, которого топы поставили на план и уже были готовы на пайвот выставить, но он вовремя получил VP-approval и перешел в другую команду...
Конечно, есть куча разных несправедливых ситуаций типа таких и даже ещё хуже. Но мы про обычные плановые увольнения сейчас.
Так URA квота и есть такова? Или вы о реоганизационных увольнениях?
Я даже не знаю что такое "URA квота" (интернет что-то про уран показывает, но это явно на другую тему).
Я про запланированные реорганизационные увольнения. Когда просто надо сократить какой-то процент людей ради сокращения бюджета и такого плана целей.
Часто же цель наоборот - развитие бизнеса и расширение отдельных направлений
Всё верно. Но есть много разных способов достижения этой цели. И многие способы не конфликтуют друг с другом никак.
Например, есть мнение, что время от времени надо увольнять некоторое количество рабочих для того, что бы было место для привлечения свежей силы. Так же это помогает показать инвесторам, что трата бюджета снижена таким образом. И так далее.
Дык в СевАмерике и так мало кто больше 2-3 лет на одном месте работает. Зачем увольнять, если достаточно пару раз прокатить с промо и pay rise и сами уйдут?
Сильно зависит от компании и кого они нанимают. В тех же гос учреждениях работают десятки лет и их никто не увольняет даже если они там ничего не делают особо. Главное, что бы уж совсем глупостями не заниматься. В тех же гос конторах часто просто нет промо и бонусов.
Есть конторы посередине между гос и быстрыми стартапами, где среднее время на одном месте можно варьироваться от 2-3 лет до десятков лет.
Более молодные обычно склонны к частому смену места работы, а более возрастные -- наоборот.
Потому что гугел снюхался с амазоном и не показывает ничего на эту тему... А вот если поискать в яндексе :)
https://yandex.ru/search/?text=amazon+unregretted+attirition+quota
Мне кажется, достаточно возможностей для внутреннего перевода, чтобы не дойти до ситуации, когда тебя хотят уволить. Часто человек просто попал не туда и это несложно исправить не увольняя.
Именно попытка внутреннего перевода ставит тебя в focus и затем PIP.
Когда ты апплаишься на внутреннем портале - твой менеджер сразу получает имел: ахтунг, раб пытается сбежать с галеры. И 3/4 менеджеров ставят его на план, а на плане ты не имеешь права менять команды без VP аппрувала
Поэтому никто там никогда и не апплаится в здравом уме, а сперва напрямую контачат с hiring manager и делают shadow loops и только потом, если все ок, ставят всех в известность.
это только в авс так? я в принципе слышал, что там плохое отношение к работникам
Фигня какая то. У нас народ туда сюда постоянно мигрирует между командами, отделами и направлениями. И простые чуваки, и топовые инженеры. Никого ни на какой пип не ставят. Амазон большой, наводите справки по конкретному направлению и менеджерам. Я год в в AWS EFS, уходить не собираюсь, тут все отлично.
Это да, как и любым инструментом - можно пользоваться по разному, и молотком можно гвозди забивать а можно пальцы отбивать. Так-то все равно все сводится к человескому фактору - и при устройстве надо пристально интервьюировать своего будущего менеджера перед принятием оффера (а не мудак ли он?), и после устройства уделять много внимания выстраиванию отношений. Это часть одинаковая в любой компании.
"Локер" -- это такие мини-сейфы для доставки посылок тем, у кого нет возможности их принять по адресу проживания. Эти локеры обычно распоположены в каких-то крупных магазинах и похожих точках, где есть доступ.
Там даже на скрине немного про это написано. Если интересно, то можно больше узнать по ключевым словам "Amazon Locker".
Постаматы
спасибо)
Конечно, не только. Ещё есть полка с замком с таким же названием. Есть устройство, которое закрывает что-либо. Наверняка, есть ещё варианты.
Но в статье было про конкретный тип от Amazon'а для доставки посылок и не более.
Очень много информации по 5 часовому интервью для разработчиков и ничего для системных инженеров. Вообще без понятия, что там будет кроме вопросов по leadership principles
У меня как раз были именно такие (хотя, я шёл на разработчика). Спрашивали про файловую систему на уровне inodes, некоторые глубокие особенности Linux'а (обычный человек за ними лезет в поисковик, так как это надо очень уж редко) и несколько команд общего назначения. С командами, хотя бы, легко, а вот остальное уже как повезёт.
Системный инженер - это кто по-английски? Чем занимается?
Возможно CTO (Chief technical officer), главный инженер по нашему.
Systems engineer.
Грубо говоря, "продвинутый администратор". Планированние/установка/настройка серверов, гипервизоров, операционных систем, сетевого оборудования (датацентровые свитчи, роутеры, лоад балансеры), систем хранения данных и т.д. и т.п. и траблшутинг. Считай с нуля спроектировать, поднять и настроить почти всю инфраструктуру. Зачастую это инженеры, работающие в интеграторах или администраторы с большим опытом. Более продвинутые больше проектированием занимаются и меньше руками работают - это системные архитекторы.
На Sysdev Engineer спрашивают такое (последний этап):
System Design (пример, как бы ты проектировал сервис конвертации текста в голос)
Linux Internal
Coding (распарсить какой-нибудь CSV на любом удобном языке; перемножить значения в массиве, все кроме текущего)
Behavioral Interview (почти на каждом собеседовании)
На первом этапе кодинг на 2 часа, задачки из разряда:
Надо в текст разбить на предложения и найти в каком предложении больше всего слов и вернуть это число
Есть выхлоп по факту
ls -l,нужно для файлов с атрибутом исполняемости, размером меньше N и созданные юзером admin, вернуть самую старую дату из файлов которые подходят под эти критерии
А оно кому-то инитересно будет?
потому что мне не дали подписать NDA, все с пруфами, скринами и прочее.
Теперь кого-то уволят из Амазона. Все общение с FAANG всегда начинается с подписания NDA.
Есть, правда, workaround. На китайских форумах, через гугл-транслейт всегда можно узнать все вопросы, со всеми ответами, со всеми обсуждениями, и это примяком из Силиконовой Долины. Совет - не пишите обратно через гугл-траслейт, вас спалят, как спалились все те индусы, что захотели поучавствовать в дискуссии.
Это история о моем опыте собеседования в Амазоне
Собеседование обычно происходит в обе стороны, т.е. не только вас, но и вы их. Надюсь, вы спросили, куда делся целиком предыдущий тим? ;-) Все резко выгорели? Ну ок, вы как раз та самая лампочка, которую вкручивают, взаместа выгоровшей.
Если без шуток, перед менеджерами в Амазоне ставят цель сделать проект лучше уволить 10% подчинённых в год. Далее, есть два варианта развития событий - если вас взять на работу, такого классного, то придётся кого-то потом уводить "из своих"; или вариант, что лучше нанять вас слабого и потом уволить через полгода "hire to fire", сохранив свой текущий коллектив.
А там, где целиком коллективы уходят выгорая, там всё просто - у всех Амазоновцев зарплата одинаковая и равна 160тыс в год, но переменная величина - это сток, который падает неравномерно, как во всех остальных хайтек компаниях, а больше на конец 4х-летнего периода. Далее технология проста, включается соковыжималка, и начинаешь работать усиленно, и но потом сдаёшься не дождавшись стоков, или досиживаешь.. но доходят не многие.
Я так думаю это верно для Америки или UK, а вот мне интересно как они проворачивают эту схему, например, в Германии? У них, вроде есть тама пара офисов.
да, по крайней мере, я правшивал у майкрософт ребят - то там все так же, зп +- одинаковая по стране, где офис, но стоками и годовыми бонусами - она очень отличается)
Хех, 100% подтверждаю, только за последний год URA target была ~6%. Это идея самого безоса (умышленно с маленькой буквы). Ну и great resignation случилась. Во всем мире скаканула инфляция и другие конторы, чтобы привлечь таланты среагировали моментально в плане подъема компенсации, а вот Beth Galetti (из S-team амазона) не среагировала и народ стал уходить пачками из потогонки на более интересные места. Вот и не брезгуют визовыми рабочими. В Ирландии у них крупный ДЦ и офис с сетевиками и разработчиками....
Кстати да, base cap 160k недавно убрали
Извините, что значит URA ?
UnRegretted Attirition. Это те, кого нам не жалко потерять.
Дело в том, что каждый менеджер в амазоне имеет метрики, и есть понятие Regretted Attirition - это когда хорошо работающий, продуктивный работник с высоким рейтингом в системе приходит завтра и говорит - я ушёл вчера. Менеджеру такой расклад - бобо, потому что не доглядел, не сделал работника счастливым, не подкинул денег, не сделал проактивный dive and save. И т.п.
Но, есть и метрика по UnRegretted Attirition, и если ты её заваливаешь - то ты хреново выполняешь свою работу и неправильно делаешь талант менеджмент. А именно не идентифицируешь плохих работников и не выставляешь их на мороз.
По каждй организации есть квота в процентах, сколько нужно выставлять на мороз, в этом году это около 6%. Потому на Talent Review and Calibration решается кто идёт на улицу и этих людей выводят на улицу давно отточенным механизмом.
А что делать когда хороший парень собрался уходить? И имел глупость сказать о намерениях перед тем, как выслать письменное увольнение? Ну некоторые менеджеры втихаря ставят их на focus план и при увольнении менеджер не получает боль за RA получает значёк за URA а работник сам того не подозревая - пожизненный бан на последующее возращение в компанию. И если раньше rehire eligibility можно было узнать звонком в ERC, то теперь они не дают подобную информацию. Потому увольнятся нужно письменно, и никому не говорить о намерениях уходить :)
Очень как-то не по человечески звучит. Такое отношение к людям должно распространяться, что бs давать негативній фидбек всем тем менеджерам, которіе такое делают.
Интересно, почему постоянно каждый год идет политика увольнения.
Так решил сам Джеф когда-то. Вот оно и идет до сих пор так.
Человеческого сложно ожидать от такой компании. У них цель сделать счастливыми инвесторов, а от этого зависит котировки акций и счастье Джефа. И пока у них неплохо получается.
В этом плане интересы работника и работодателя разные. Работник с точки зрения амазона должет быть отжат до последней капли пота и выброшен на улицу.
Подозреваю, что это от команды зависит - знакомые говорили у некоторых команд наоборот адская нехватка народу и не могут набрать согласно спущенным планам.
Leadership principles Амазона аналогичны принципам принципам и ценностям других компаний, например, аналогичный список для Яндекса. Предполагается, что если все ими пользуются, то человек способен к самостоятельной работе. Я, лично, не вижу смысла их заучивать, а скорее просто пользоваться здравым смыслом и личным опытом на собеседовании.
Насчет задачек у меня кстати обратное мнение. Заучивание решений с leetcode пусть и полезно, но слабо коррелирует с реальной работой. Придумывать хорошие и нестандартные задачи довольно сложно, отчасти поэтому и нужна NDA.
Да, но тогда как иначе (кроме как заучиваний патернов решений задач) готовится?)
Я даже книгу по нейробиологии прочитал конкретно про проблем солвинг, никто не знает как работает "еврика эфект", и кроме как попасть на что-то знакомое, или же нативного солюшна, к которому дедуктивно приходишь - вроде больше способов нету)
Рекомендую к прочтению "Думай медленно, решай быстро" Канемана. Там про эвристику многое объясняется весьма понятным языком. Да и просто для кругозора было интересно почитать.
К сожалению, если в кругу нейробиологов еще нет ответа, я очень сомневаюсь что один психолог-економист что-то годное мог бы написать по поводу "эврика эфекта" и как у нас солюшны рождаются в голове)
К тому же, я перелистывал эту книгу, лежала у знакомого, если честно - типичная поп. психология. Я приверженец академ. литературы)
Посмотрел code question 2. Пришло в голову такое решение:
- определяем за
O(n)всеcompartmentсохраняя их в отдельную коллекцию, где каждое звено это{ left: int, right: int, count: int } - создаём новый массив, где каждому звену
*задаём соответсвующийcompartmentвыше или -1, если это*по бокам - превращаем коллекцию с
comparmentsв древо отрезков по сумме - пробегаем по все интервалам, где для каждого индекса сужаем курсоры слева направо и справа налево, чтобы дойти до первого цельного отсека
- найдя цельные отсеки слева и справа, используя древо отрезков, считаем их сумму
Итого:
- на подготовку нужно:
O(n)для поиска отсеков иO(n log n) для подготовки древа отрезков - на поиск нужно
O(log N) - т.е. итоговый
O(n log n)
Но я решительно не понимаю, как такое можно успеть написать за 30 минут. оО. Я одно только древо отрезков буду отлаживать минут 20. А там за час надо обе задачи. Бррр.
Может быть есть какое-то совсем примитивное решение? Или подразумевается, что древо отрезков есть в стандартной либе?
20 минут) там ровно 20 минут, у меня все записано есть)
ну мой лид предложил другой солюшн
Мы создаем хешмапу, и проходим по каждому слову в листе.
Для кажого слова мы берем все префиксы и чекаем, есть ли этот префикс в хешмапе, если нету - продолжаем, если есть - "отрубаем его" и колаем ту же функцию рекурсивно стем, что осталось от слова. Когда доходим до конца слова - то добавляем его в хешмапу.
Мой лид придумал это за секунд 15, но я - не он, я более тупенький, поэтому не втащил)
Я про задачу с интервалами и звёздочками.
не, хэшмапа тут мимо. Это на trie задача
Это решение лида — брутфорс. Скорее всего, не прошло бы по времени. Тут надо динамическое программирование писать:
F(i) — можно ли собрать строку, начиная с i-ого символа.
База F(n) = true.
Переход — для всех следующих символов j проверяем, что подстрока с i по j-1 есть в хешмапе (или лучше — в trie, ибо мы по одному символу добавляем к проверяемой строке), и что, F(j) == true, тогда запоминаем, что после i идет j и F(i) = true.
В конце, если видим, что F(0) = true, то можно по сохраненным ссылкам пройтись и вывести все куски.
Ниже я уже привел решение.
Слушайте, а у вас русский ленгвидж атрофировался после устройства в майкрософт, или уот? Все употребляемые вами слова есть в русском языке.
Мне в голову пришло следующее решение. Не уверен, но вроде должно сработать.
Три массива для подготовки:
- массив префиксных сумм "сколько инвентаря от нуля до этого индекса"
- массив "индекс предыдущего или этого сепаратора" (можно рассматривать как массив префиксных сумм, но вместо операции + будет операция max index)
- массив "индекс следующего или этого сепаратора" (строится с конца)
Строится за линейный проход.
Рассчет за константу.
Сначала определяем индексы сепараторов. Потом result = prefixSum[end] - prefixSum[start].
С точки зрения кода - вроде просто. На думание потрачено где-то три-пять минут.
массив префиксных сумм "сколько инвентаря от нуля до этого индекса"
Вот да. В этом суть. Меня понесло в деревья отрезков, а ведь для суммы можно просто иметь массив вида a[i] = a[0] + a[1] + ... a[i]. И тогда сумма от i до j это просто a[j] - a[i]. Реализуется тривиально. Но эта мысль пришла мне уже в ночи :)
Да можно проще — проходимся по строке слева-направо и в отдельных массивах помечаем сколько до этой позиции "*" и где предыдущий "|". Потом проходимся справа-налево, и запоминаем, где следующий "|" от каждой позиции.
Получив отрезок на входе, урезаем его до ближайших "|" с концов, используя предподсчитанные позиции. А дальше берем разность из количества вещей в концах. Так как строка не меняется, никакие деревья отрезков тут не нужны. Можно использовать частичные суммы.
O(n) памяти и времени на предподготовку и O(1) на каждый запрос.
Кода тут — строк 10. Два невложенных for, пара if-ов и 2-3 счетчика. Не надо никаких стркутур данных хитрых.
Кстати, на интервью обычно, если вы знаете то же дерево отрезков, то можно его не писать. Достаточно сказать "допустим есть вот такой интерфейс и это вот такая структура данных". Интервьювер спросит про сложность всех операций и как оно там может быть реализовано, конечно, но если у вас не хватит времени его писать, это не будет проблемой.
Ага. Спасибо. Всё так. Фантазии на тему:
- Я описываю вслух своё решение с O(n log n)
- Интервьювер говорит, что хорошо, но можно быстрее и проще
- Я думаю, где можно упростить. Спрашиваю можно за O(n)?
- Он говорит6 да, можно линейно
- Я понимаю что log N у меня в древе отрезков и надо от него избавиться. Вспоминаю, что для статичных массивов можно решить проще. Описываю словами новое решение с O(n)
- Интервьювер утверждает его
- Я начинаю его писать в коде, но не успеваю по времени
Интервьювер куда-то записывает: "2-ую задачу не успел решить в коде, но озвучил правильный алгоритм, потребовалась одна подсказка". Это так работает?
Ну, я бы не стал прям оценки сложности вам говорить. Но мог бы прямо спросить, а вам точно тут нужно дерево отрезков? Нет ли более быстрой структуры данных, дающей то, что вам надо? Если бы вы не доперли, попросил бы выписать, а что именно вы со структурой делаете? Формализовать требования. Намекнул бы, что вы же ничего не меняете, а дерево отрезков позволяет любой элемент онлайн менять. Это же вам не надо.
Если не успели эту задачу закодить, то я бы поставил вам 5 за знание алгоритмов и 2 за эффективность. В целом, я бы не рекомендовал нанимать такого кандидата вот прям сейчас. Надо бы, конечно, успеть эту задачу закодировать. Но я бы в своем отчете обязательно сказал, что если это единственное интервью, то стоит дать человеку еще шанс. Может, тупил и волновался. Если из пяти интервью у вас одно такое, то, я думаю, шансы быть нанятым у вас бы были не плохие.
Тогда есть ещё 1 вопрос. Я заметил, что если не объяснять решение интервьюверу (о чём чуть ли не капсом пишут во всех статьях про интервью), а просто тупо молчать и делать задачу, как если бы интервьювера вообще не существовало, то, внезапно, оказывается мозг начинается сосредотачиваться на самой задаче, а не на том, как бы сформулировать ему на английском, что тут индекс сюда\индекс туда. В таком случае можно даже успеть что-то решить, хаха. Такое рассматривается как дерзость? :)
- I think I almost have grasped the task, but I need some time to debug it in my head. If you don't mind I'll do it and later will explain how it's supposed to work.
Что-нибудь такое.
Пример из жизни. Буквально вчера меня попросили написать палиндром (хаха, как он ещё всем не надоел). Ну я написал. А оно не работает. Трём программистам (два интервьювера) понадобилось минут 5 на то чтобы заметить, что вместо arr[len - i - 1] написано arr[len - 1]. А что, 1 похожа на i. В глаза не бросается. Но т.к. считается что все должны постоянно что-то тараторить (включая интервьюверов, им ведь тоже интересно поучаствовать), и даже дебажить вслух, то даже коллективный разум сильно падает :) Чем больше галдежа и мнений, тем ниже коллективный интеллект.
Можно и без массивов с ближайшими "|". Нужны только префиксные суммы, и "сдвинутые префиксные суммы", из которых будем брать значение для стартовых символов.
Для примера из задания:
строка "| * * | * | *",
sums = [0, 0, 0, 2, 2, 3, 3], shiftSums = [0, 2, 2, 2, 3, 3, 3]
result = max(0, sums[end] - shiftSums[start])
Амазон top-down компания с неограниченной силой в руках менеджера. Ты ему лицом не понравился, или не улыбнулся когда требуется и через пару месяцев сдаешь бэдж
Да камон, на рынке сейчас такая нехватка народу, что не известно кто больше на этом потеряет.
Так я ж не менеджер. Я так просто наблюдаю со стороны.
И им говорят - хватить энфорсить URA, но Beth не реагирует...
Дык это же бизнес, ничего личного. Первые пару раз когда увольняют еще напрягаешься, а потом попускает.
Вот-вот. Вне ФААНГов в США с этим зачастую хуже, нанимать не умеют, наберут балласта, потом массово увольняют без разбора, потом страдают и никого нанять не могут. А так-то и в ФБ можно влететь на ПИП если с менеджером общий язык не нашел, и Гугл сокращает если проект закончился а ты себе быстро новый не нашел итп.
Я как-то работал полтора года в подразделении компании и у нас за это время ни одного проекта не было. Мы делали спринты, что-то писали, но ничего, за что платят конторе деньги. В один момент халява кончилась и всех уволили одним днем. Я на них сперва обиделся, но они оставили медстраховку на месяц и выплатили денег больше чем должны. Тч спустя годы должен признать, что повели себя вполне по-человечески.
После этого я понял, что это игра, в которую можно играть вдвоем и что не нужно сидеть на жопе ровно и если подворачивается хорошая возможность, то точно так же нужно уходить одним днем и ни о чем не жалеть.
Ну гугл дает достаточно времени чтобы найти. И дает тебе приоритет, если ты выбрал что-то внутри. А амазон просто пипнет и 3 мес severance и ты на улице
Возможно и не улыбнулся, но реджекта не пришло. Аппрува впрочем тоже. Из чистого любопытства наблюдаю сколько в их системе можно висеть в статусе "Under consideration" после окончания третьего этапа. Текущий рекорд с сентября 2020 по сейчас.
Можно поинтересоваться, какие такие интересные вопросы, возможно будет еще возможность посмотреть на то, как шпарят методичку)
Отлично расписали, очень интересно читать!
Проходить многоуровневые фильтры компании это нервы и подготовка. А потом кажется не задействуешь и половины информации. После приходит осознание, что неплохо прокачался
То интервью я не записал на видео, но записал пару вопросов, если кому интересно:
Как удалить файл на линуксе
Если вы удалили файл, но видите, что память не освобождена - что делать?
Вы начали понимать, что у вас на машине нет интернета - что будете делать?
Как в линуксе достать файл с наибольшим весом?
Как передать аут из одной команды в другую в Линуксе
У вас на сервере закончилась память на диске, как будете траблшутить?
В одном регионе задержка запросов увеличилась, в других - все окей, как будем фиксить и трабл шутить?
Как линукс-инженер, я смог без гугла ответить только на 1-й, 3-й (частично), 5-й и 6-й (тоже частично). 2,4 - есть маразм спрашивать ключи комманд "на память". Достаточно спросить - как будешь гуглить ту или иную команду. 7-й - специфический, поле для мыслей обширное - часа на 2 обсуждений
Задача была в следующем, мы должны спроектировать нотификейшн систем, который отправлял бы нотификейшены, когда его об этом будут просить сторонние сервисы.
Тут вообще нагорожено неподетски в ответе у автора. Мыслю так - каждый сервис имеет свои логи. В логах сидят ключевые слова. Таким образом - делаем в cron ежеминутную задачу - отслеживать конкретный лог-файл на предмет ключевого слова/фразы/цифры и т.д. При появлении таковых - нотификейшн на мыло/телегу/смс. Кому интересен код крона - пишите.
2 - это ошибка перевода, похоже. Если удалили файл [на блочном устройстве], а [оперативная] память не освобождена, то я буду недоумевать. Должна была, что-ли?
Это про дисковую. Файл удалили, а свободного места не прибавилось. Что делать? Искать процесс, в котором был открыт этот файл. Дальше "линукс-инженеры" знают, что делать :)
Это раньше называть дисковое пространство памятью было грубой ошибкой, а теперь я такие штуки даже в технической документации встречаю.
вроде бы tail -f сейчас под капотом inotify использует, поэтому подписатся на логи проще, запустив нижеприведенный код после ребута (systemd service или тот же крон)
tail -f logfile | grep "keyword" | xargs send_notification.sh
Но мне кажется все таки, что изначальная задача немного о другом.
Таким образом - делаем в cron ежеминутную задачу - отслеживать конкретный лог-файл на предмет ключевого слова/фразы/цифры и т.д.
Мне кажется, это одно из худших проявлений Hyrum's law. Мне было бы неприятно, если после релиза с изменением логов стали стучаться в личку и требовать вернуть их назад, а то не считается статистика за день. Настолько "разумную жизнь" на основе логов надо убирать как можно быстрее.
Задача была в следующем, мы должны спроектировать нотификейшн систем, который отправлял бы нотификейшены, когда его об этом будут просить сторонние сервисы.
Можно более подробно про условия задачи? Также не очень понятны требования:
- Notification Service is ext
- Do not loose data
Похоже, что хотят внешний event-driven notifications service и намекают, что at most once delivery не пойдет (как и просто фейлить обработку событий без ретрая)
там в процессе накидывал реквы.
"notification service is ext" - Вобщем, имейл сендер, phone notification sender - это не наше, может упасть, нужны ретраи. То, что будет нас колать - тоже не наше, я в принципе отделил пунктирной линией на солюшне своем (только лоадбалансер должен быть выше).
"Do not loose data" - Мы не должны потерять запрос на посыфл нотификейшна
Стало интересно решить задачу про составные слова, за один проход.
Получилось так
static void Main(string[] args)
{
var words = new HashSet<string> { "rock", "super", "rockstar", "super", "star", "way", "highway", "superhighway", "high", "a", "waya" };
var list_of_parts = new List<string>();
var word = new StringBuilder();
string candidate;
int count_parts;
foreach (var w in words)
{
word.Clear();
count_parts = 0;
list_of_parts.Clear();
for (var index = 0; index < w.Length; index++)
{
word.Append(w[index]);
if (words.TryGetValue(word.ToString(), out candidate))
{
if (string.Compare(w, candidate) != 0)
{
count_parts++;
word.Clear();
list_of_parts.Add(candidate);
}
else break;
}
}
if (count_parts > 1)
{
Console.WriteLine($"{w} = {string.Join(" + ", list_of_parts)}");
}
}
}Вывод:
rockstar = rock + star
highway = high + way
superhighway = super + high + way
waya = way + aА на тесте {"a", "b", "abc", "d", "abcd"} сработает? А если перетасовать? Просто если ваше решение сначала жадно откусит кусок "a" от "abcd", то уже никак не соберет его, потому что надо откусывать именно "abcd".
Тут, похоже, надо динамическое программирование писать. Надо считать, можно ли префикс текущей строки 0..i собрать как набор слов. А дальше, если текущий префикс можно собрать, то проверять, если ли слово i+1..j и помечать, что можно собрать префикс с 0 по j. В итоге O(n l^2). получается, где l — длина максимальной строки.
Если
Забыл добавить проверку что сумма длин составляющих слова будет равна длине слова. А жадный алгоритм действительно не подходит. Придется задуматься.
Вот все решение:
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
class Trie {
public:
Trie() : nodes(1) {};
void Add(std::string s) {
int v = 0;
for (auto c: s) {
auto it = nodes[v].next.find(c);
if (it == nodes[v].next.end()) {
nodes[v].next[c] = nodes.size();
v = nodes.size();
nodes.push_back(Node());
} else {
v = it->second;
}
}
nodes[v].final = true;
}
int Next(int v, char c) {
auto it = nodes[v].next.find(c);
if (it == nodes[v].next.end()) return -1;
return it->second;
}
bool IsFinal(int v) {
return nodes[v].final;
}
private:
struct Node {
bool final = false;
std::unordered_map<char, int> next;
};
std::vector<Node> nodes;
};
int main()
{
std::vector<std::string> words = { "rock", "super", "rockstar", "super", "star", "way", "highway", "superhighway", "high", "a", "waya" };
Trie trie;
for (const auto w : words) {
trie.Add(w);
}
for (const auto w : words) {
std::vector<bool> repr(w.size()+1, false);
std::vector<int> prev(w.size()+1);
repr[w.size()] = true;
for (int i = w.size()-1; i >= 0; --i) {
int v = 0;
for (int j = i; j < w.size(); ++j) {
v = trie.Next(v, w[j]);
if (v == -1) break;
if (trie.IsFinal(v) && repr[j+1] && (i > 0 || j+1 < w.size())) {
repr[i] = true;
prev[i] = j+1;
}
}
}
if (repr[0]) {
std::cout << w << " = ";
bool is_first = true;
int i = 0;
while (i < w.size()) {
int next = prev[i];
if (!is_first) std::cout << " + ";
else is_first = false;
for (int t = i; t < next; ++t) {
std::cout << w[t];
}
i = next;
}
std::cout << std::endl;
}
}
return 0;
}Заняло у меня 20 минут с отладкой и перервами помешать и наложить пельмени. Сначала упустил +1 в нужном месте. Потом понял, что у меня строчки-состовляющие в обратном порядке выводятся, развернул цикл.
Если я не ошибаюсь ваше решение всегда будет иметь квадратичную сложность от общего количества символов. И trie в случая поиска с конца строки не нужен: так-же проходя с конца строки можно искать совпадения в хеш сете - экономится время на написание trie. С траями можно осуществлять поиск проходом с начала строки - чтобы преодолеть выше упомянутую проблему жадного алгоритма необходимо убрать "жадность" и просматривать все ветки - т.е. если нода в середине слова имеет индекс просматриваем уже два бранча. На определенных данных типа "a", "aa", "aaa" это тоже будет медленно работать, но на обычном тексте должно быть хорошее отсечение плохих вариантов.
Если я не ошибаюсь ваше решение всегда будет иметь квадратичную сложность от общего количества символов.
От длины слов, O(N L^2), где N — количество слов, L — максимальная длина.
И trie в случая поиска с конца строки не нужен
Нужен. Обратите внимание: у меня поиск идет слева-на-право. Хоть начало и сдвигается задом-наперед, результаты поиска предыдущей итерации переиспользуются. Использование хеш-сета сделает мое решение O(N L^3), ведь хешсет будет пробегаться по строке считая хеш. Если только не считать хеш самостоятельно и, опять же, переиспользовать предыдущие итерации. Но такой хеш еще надо в std::unordered_set как-то засунуть. Своя функция подсчета какого-нибудь полиномиального хеша по коду и по времени написания займет сравнимо с trie. И на практике может работать хуже, ибо хороший хеш — это сложно.
На определенных данных типа "a", "aa", "aaa" это тоже будет медленно работать, но на обычном тексте должно быть хорошее отсечение плохих вариантов.
Во-первых, не просто медленно, а экспоненциально медленно. Это большой минус. Если вдруг у пользователя окажется файл с кучей букв "a", или этот код какая-то часть системы и злыдень может прислать такие слова, то экспоненциальная сложность приведет к DoS. Да достаточно просто иметь кучу сильно-составных слов.
Во-вторых, мое решение можно соптимизировать, чтобы оно на хороших текстах работало не за квадрат — для этого надо поменять смысл ДП: вместо проверки, что можно собрать суффикс слова, надо считать, а можно ли собрать префикс. Тогда внешний цикл разворачивается и можно не запускать внутренний, если текущий индекс не собрать. Правда тогда восстановление ответа (последний цикл while) выдаст составные слова в обратном порядке.
Я сначала так и написал, но было лень слова из ответа куда-то складывать и разворачивать, я просто развернул цикл и чуть-чуть подрпавил индексы при работе с ДП.
Если вдруг у пользователя окажется файл с кучей букв "a"
На leetcode в аналогичной задачке так и было. Предпоследний тест это множество a, aa, aaa, aaa… Потребовалось делать алгоритм жадным и добавить проверку на уже посещённые звенья.
В целом спасибо за наводку. Я так и не понял что у вас в коде происходит (слишком много всяких мне незнакомых c++ наименований). Но увидел, что нужен Trie. Научился их строить, и смог пройти эту (и ещё 2 аналогичных) задачу, по принципу:
- строим trie по всем словам
- пробегаем по каждому слову и запускаем рекурсию
- пробегаем слева на право по trie, но посимвольно, сохраняя ссылку на вложенный trie
- на развилках (где можно попробовать поискать слово длиннее или начать строить следующее слово) — ДП
- остальное зависит от задачи — там есть где нужно собрать все варианты, есть где нужно проверить можно ли вообще составить это слово, и т.д..
Я понимаю что поиск в трае идет слева-направо.
Но просмотр слова справа налево действительно будет лучше. Не учел что скорее всего идти от j-го символа до конца строки не придется. Хотя можно конечно подобрать проблемные ввод типа rockstar, r1, ar1, tar1, ...
Вы правда выводите только одну найденную комбинацию, а по условию задачи и примеру входа вроде как подразумевается что нужны все возможные.
для "rock", "star", "rockstar", "rockstars", "stars", "rocks", "tar", "ro", "ck", "st", "ar":
rock: ro+ck
star: st+ar
rockstar: ro+ck+st+ar
rockstar: ro+ck+star
rockstar: rock+st+ar
rockstar: rock+star
rockstar: rocks+tar
rockstars: ro+ck+stars
rockstars: rock+stars
Я понял эту задачу, как найти все слова, которые представимы. И задача на литкоде тоже просит перебирать все варианты.
Да, если нужны все варианты, которых экспоненциально много может быть, то тут будет рекурсивный перебор.
Но я думаю, что задача все-таки — вывести каждое слово по одному разу. Задачи на полный перебор давать не очень любят, потому что там единственное решение и есть наивный полный перебор.
Вторая: эту я тогда не решил, не успел, брутфорс падал по таймауту, нужно было дайнемик программинг использовать.
Тут не динамическое программирование, а префиксная сумма + бинарный поиск по ней
Про работу в амазон последнее время слышно только плохое.
Видимо, в зависимости от локации(а может ещё чего), процесс интервью немного меняется.
Я проходил собеседование в прошлом (2021) году с февраля по май на SDE 3 а.к.а сеньёр-помидор в Берлин, и у меня не было отдельных поведенческих интервью, все этапы были 50/50, пару-тройку поведенческих вопросов + кодинг челендж/систем дизайн. И интервью на последнем этапе было "всего" 4.
Получил отлуп я в таком же стиле:
"Your answers to our Leadership Principle questions were great, but unfortunately the technical competencies weren’t quite where we need them to be."
В чём конкретно была загвоздка я так и не понял, потому что все кодин челенджи я решил(я был хорошо подготовлен), и по реакции на мои систем дизайн ответы, мне казалось, что тоже норм наговорил.
Пути Амазона неисповедимы.
Моя бывшая жена менеджерствует на Амазон-проекте. Говорит, последние соки выжимают из людей... Я предпочитаю работать с Европой (не британцами только)... В условиях тайм-прессинга мой мозг клинит, задачи на время решать не умею... Вообще не верю в собеседования с точки зрения уровня и подходящести человека: верю только в испытательный срок.
Мой опыт собеседования в Amazon