Добрый вечер, дамы и господа. Я знаю, что статьи про собеседования в крупные IT-компании видели почти все, и у некоторых это уже вызывает непреодолимый приступ тошноты, но когда ты убиваешь порядочный кусок жизни на получение определенного навыка, тебе кажется, что смысл твоей жизни - поделиться этим опытом с другими. У написания этой статьи есть и вторая причина - я видел много разных статей про Frontend и Backend разработку, но никто никогда не писал про то, как проходят собеседования в IT гиганты для специалистов в области DataScience и Machine learning инженеров.
Всех, кто еще не уснул от скуки, прошу пожаловать под кат.
Снятся ли программистам электроовцы
На данный момент я Machine Learning Engineer в Российском подразделении Intel. До Intel я работал в небольшом стартапе.
Я не заканчивал какие-то топовые Российские ВУЗы, у меня степень магистра простого местного университета (чтобы избежать холиваров я не буду его называть).
Когда говорят про подготовку в FAANG, то обычно людям в голову приходят одна мысль: а ради чего все это? Единственная вещь, которая заставляла меня вставать в 9 утра в офис зимой - это сладкие мысли про релокейт.
Процесс релокации у FAANG довольно хорошо отлажен, так что я выбрал именно эти компании, как основной путь к достижению своей цели.
Это статья в том виде, в котором я ее представляю, не про мотивацию, так что просто напишу тут, что найти в себе силы на решение N задач - это пол дела. А вот сохранить вообще веру в человечество после N отказов - это настоящий вызов.
Наверное где-то тут у читателя появился вопрос: почему бы не релоцироваться через Intel. Скажу сразу, что, в моем случае, это было невозможно ибо нос грейд не дорос. Но это тема для отдельной статьи.
Ну что, пришло время поливать грязью конструктивно критиковать те компании, куда меня не взяли.
Но перед этим…
Я не боюсь человека, который изучает 10 000 различных ударов
Здесь стоит сказать, что каждая компания играет по своим правилам, но, в целом, вам стоит ожидать примерно таких этапов: тестовое задание (aka online assessment), phone screen и сам onsite.
Тестовое задание
Тестовое задание в случае ML инженеров может быть самым разным. Booking, например, дает небольшой тест на 30 минут, в котором всего 12 вопросов про то, как работают разные алгоритмы и в каком случае какой алгоритм машинного обучения использовать. Mckinsey, Ebay и Amazon дают задачи. Советую перед решением тестового задания сначала поискать какую-то информацию, которая подскажет, чего ожидать. Можно заглянуть в leetcode discussion или же на glassdoor.
Phone Screen
Phone Screen обычно включает в себя задачу и разговор за ваш опыт. В LinkedIn например умудряются за час спросить и задачу, и алгоритм какой-то, и способы решения реальной бизнес задачи. Кстати, скажу заранее, что хорошо решенная задача не гарантирует прохождение на следующий этап.
Большинство задач, которые дают крупные компании, можно найти на leetcode.com. Если этого вам показалось мало, то можно прочитать сверху cracking the coding interview и competitive programming. Однако, в случае с ML инженерами ситуация может быть чуть сложнее и для оптимального решения задачи от вас могут ожидать некоторой подкованности в области математики. Экзамен по матану никто вам проводить не будет, конечно, но умение найти минимум функции аналитически или упростить функцию - вполне реальные кейсы, с которыми я сталкивался. Об этом расскажу ниже.
Обычно именно задачи пугают людей больше всего. Дело в том, что большинству инженеров хитроумные алгоритмы для решения повседневных задач не нужны. Но, тем не менее, как-то отбирать хороших специалистов нужно, поэтому там выше решили, что логичнее тестировать на знание computer science. Я к этому нейтрально отношусь, с одной стороны, меня правда бесят все эти вопросы в духе: а есть ли метод X в библиотеке Y. С другой стороны, я не вижу смысла в том, чтобы ментально насиловать человека 4 собеседованиями на знание алгоритмов. Но спасибо, что хоть про люки не спрашивают.
Я решил чуть больше 450 задач на leetcode (93 easy, 300 medium, 57 hard). И за все собеседования ни разу не было такого, что я не смог решить задачу. Но у меня есть чувство, что я слегка переподготовился. Я считаю, что хватит около 200 задач уровня easy и medium. Исключением может быть собеседование в Google.
Онсайт
Онсайт подразумевает в себе 3-4 алгоритмические задачи, System Design и Behavioral.
Про задачи я писал выше, они не отличаются на онсайте.
System Design
Если задачи для всех покемонов примерно одинаковые и могут отличаться только сложностью, то вот System Design может быть самый разный. Если вы проходите собеседование как ML специалист, то ожидать вам следует примерно всего, что взбредет в мозг вашего интервьюера: доказательство теоремы, задизайнить рекомендации Youtube или Rate Limiter - список весьма большой и никого особо не волнует, что вы о значении некоторых слов узнали прямо сейчас на интервью.
В гайде для подготовки к онсайту от Amazon написано, что вы можете акцентировать внимание на том, в чем вы хорошо разбираетесь. Так что я следовал такому плану: курс grokking Machine learning interview, ML system design, Cracking the system design на educative. Еще я прочитал Alex xu system design на всякий случай. Если вы идете на уровень выше, то можно еще пройти курс advanced system design. Я часто видел такую ошибку, что люди игнорировали этот этап и полагали, что их опыта им хватит. Скажу так, это может не стать причиной отказа, но серьезно может занизить ваш будущий доход. Да и, в любом случае, это довольно интересно и полезно.
Еще очень полезным может быть сообщество FAANG interview. Ребята регулярно проводят моковые собеседования по алгоритмам и system design. А еще там можно найти реферала. Есть еще FAANG Data Science. Там активность чуть меньше, но ребята тоже делятся опытом собеседований и выкладывают полезную информацию.
Behavioral
Этот этап включает в себя поведенческие вопросы. Не буду особо углубляться в детали. Скажу только, что не стоит пренебрегать этим этапом. После того как более 100 часов были потрачены на подготовку, будет обидно провалить собеседование, потому что кто-то посчитал вас не очень заинтересованным.
Советую пройтись по Amazon leadership principles и вспомнить ситуацию на каждый случай. Постарайтесь сделать так, чтобы в вашей истории фигурировали числа: ускорили что-то в N раз, чихнули и это принесло N тысяч долларов, опечатались и сэкономили компании N миллионов - говорите про все.
Итак, пришло время того, зачем вы тут!
Интервью в TikTok. Ой, в ByteDance
Подавался по формочке и как-то пропустил, что страна назначения была Сингапур. Туда я не особо собирался, но подумал, что это будет хорошим опытом. Буквально через недели 3 написал рекрутер и без всяких церемоний отправил на собеседование. Что за команда, что за продукт, какие у меня будут обязанности - это все я должен был узнать уже на поле боя.
Этапы
Никакого звонка с рекрутером не было. В письме были оговорены только самые важные моменты: этапов будет 3, у вас будет кодинг, так что уважительная просьба использовать ноут. Все.
1 этап
Первый этап собеседования мне понравился. Интервьюер был вежливый, подробно все описал и явно был очень заинтересован моим опытом. Разве что парень не очень хорошо говорил по-английски и постоянно просил меня говорить медленнее. Ну допустим, что это камень в мой огород.
Мы так увлеклись разговором про мои прошлые проекты, что я совсем забыл про задачу. Задачу, кстати вот она, я решил довольно быстро.
После этого меня попросили рассказать про линейные модели (log reg, linear regression) и на этом разошлись. Приглашение на второй этап пришло на следующий день.
2 этап
Второй этап был намного сложнее. Сам интервьюер говорил по-английски еще хуже, чем прошлый.
Мы быстро перешли к задаче и вот тут началось. Скажу честно, похожую задачу я не видел ни разу ни в книжках, ни на leetcode, ни даже в самом страшном кошмаре. Если коротко, то суть была в следующем: дан массив чисел, нужно было найти такой индекс, который бы разбивал массив на 2 подмассива так, чтобы некоторая целевая функция для этих кусочков была одинаковая. Пришлось потратить примерно 5 минут на то, чтобы понять, что я вообще только что прочитал. Я попросил привести пример и мой товарищ написал массив и сказал, чтобы этот самый индекс я посчитал сам. А, понял, вопросов больше не осталось. Сам трюк в задаче был в том, чтобы упростить эту целевую функцию. Но, если честно, я не совсем понял, в чем принципиальная разница, ведь задача все равно решалась за линию.
В конце мы пошли опять говорить за линейные модели, про то, как в распределенном режиме тренировать нейронные сети и какие регуляризаторы использовать (эта тема их волновала больше всего). Этого, видимо, им показалось мало и в конце мне дали еще одну задачу - рассчитать градиент сигмоиды. Суммарно все интервью заняло 2 часа вместо обещанного часа.
Общие впечатления
Мне нравится TikTok своей интересной системой рекомендаций. И было бы здорово поработать над чем-то таким, но я получил отказ на следующий день.
Интервью в Apple
На протяжении всего процесса меня не покидала мысль, что я собeседуюсь не в Apple, а в какие-то “Рога и копыта”. Даже пару раз проверял письма интервьюера, чтобы убедиться в том, что все это правда. Но обо всем по порядку.
Этапы
Подавался я стандартно - через формочку. Должен сказать, что у Apple довольно удобный механизм подачи резюме. Заполняешь один раз и потом просто жмешь кнопку Apply. Звучит, как что-то само собой разумеющееся, но после 50 компаний, куда я подавал резюме, я понял, насколько это большая редкость. Хотите немного пострадать - попробуйте отправить свое резюме в Lego.
Ответили мне довольно быстро - примерно через месяц. Как и в случае с ByteDance, никакого звонка с рекрутером не было, он просто скинул всю информацию по почте и отправил на собеседование. Самое удивительное, что мне даже не написали, какие будут этапы и сколько их всего.
1 этап
Интервьюер сказал, что не подготовил каких-то вопросов для меня и мы просто поговорили за опыт. Сначала казалось, что где-то тут подвох и вот он сейчас выпрыгнет на меня с каким-то каверзным вопросом. Но нет. Через пару часов мне пришел ответ, что я прошел на следующий этап.
2 этап
На втором этапе я общался с Hiring Manager. Его интересовали особенности питона и с++, multithreading, multiprocessing, куча, стек. Еще меня попросили рассказать про любой алгоритм машинного обучения. Через пару часов пришел ответ, что меня позвали на кодинг.
3 этап
Собеседующий был довольно неприятный тип. Все время крутил кубик Рубика или другие вещи со своего стола и всем своим видом показывал, какой он умный. Сама задача была довольно простая: найти все уникальные элементы в тензоре.
После того как я предложил решение меня попросили рассказать про то, можем ли мы как-то его ускорить. Учитывая, сколько до этого меня мучили вопросами про многопоточность, я предложил именно этот способ. Но интервьюер ожидал ответ намного проще - мы можем использовать numpy. Я примерно помнил, какой метод мог мне тут помочь, но немного натупил с reshape. В итоге пришел отказ, в котором интервьюер написал, что был крайне недоволен, что я не предложил использовать numpy сразу и что я написал класс, а не функцию для решения задачи.
Общие впечатления
Очень невнятный процесс для компании уровня FAANG.
Для меня было довольно странно, что для решения задачи нужно использовать стороннюю библиотеку. Позже на reddit я прочитал, что, если вас просят реализовать какую-то функциональность, которая уже реализована в какой-то библиотеке, можете про это сказать.
По поводу класса: в Google и Facebook рекомендуют писать именно классы, чтобы проще было работать с follow up к задачам. Задачи на leetcode тоже выполнены как классы. Впрочем, я уверен, что если бы там была функция, спросили бы, а почему не класс?
Интервью в NVIDIA
Подавался стандартно, по формочке. Мне ответили в течении 2-х недель. Видимо, строчка Intel все-таки сыграла какую-то роль.
Этапы
Как обычно, никакого звонка. Вся информация в письме. Всего собеседование включает в себя 2 этапа.
1 этап
Вообще я долго думал, стоит ли включать это собеседование в список. Однако тут есть некоторые моменты, которые я все-таки хотел бы осветить.
Была задача. Кто бы мог подумать. Max points on a line. С этой проблемой я сталкивался до этого и честно сказал про это. Весь мой ход мысли был озвучен, интервьюер согласился с моим подходом и я пошел писать код.
Из-за того, что я озвучил, что уже решал задачу, интервьюер чувствовал себя крайне некомфортно и ему мерещилось, что код я просто вспоминаю. По крайней мере мне так показалось.
На следующий день пришел отказ. На мою просьбу все-таки написать, что пошло не так, мне прислали список книг. Книжки - это хорошо, будет что почитать.
Общие впечатления
Когда-то на хабре уже писали про то, что не обязательно говорить интервьюеру, что вы уже решали задачу, потому что всегда можно придумать follow up, который заставит кандидата пошевелить мозгами.
Я хорошо понимал, что именно в этой задаче будет отлично видно, что я видел ее раньше. Да и новых задач я не боялся, поэтому решил быть максимально честным. Не знаю, был бы у меня другой фидбек, если бы я промолчал.
Интервью в LinkedIn
LinkedIn нашел меня, как ни странно, через LinkedIn.
Этапы
Мне позвонила рекрутер и предложила пройти собеседование в Ирландский офис LinkedIn. Это был первый раз, когда мне дали полное представление о команде, кто чем занимается, какие могут быть задачи, чего ожидать на phone screen и какие зарплатные вилки есть. Казалось бы что-то, что должно быть само собой разумеющееся, но это одна из немногих компаний, которая сразу проговорила все детали
1 этап
Мне попалась задача применить функцию ax^2 + bx + c к некоторому массиву. Массив, a, b и c даны. Ограничение было таким, что a > 0. Суть простая: найти минимум функции и потом двумя указателями сформировать результат. Я написал решение довольно быстро, но и сам интервьюер отметил, что задача довольно простая, особенно для магистра. Понял, рано радоваться.
Дальше меня попросили рассказать про любой ML алгоритм и дали бизнес задачу: предсказать цену на отель / апартаменты. Тут я рассказал про то, какие могут быть признаки, как их обрабатывать, какую модель выбрать, какие метрики использовать. Вроде все прошло хорошо, но через пару часов я получил отказ. Оказалось, что первые 2 этапа прошли отлично, но на последнем интервьюер хотел услышать больше деталей. Только потом прочитав курс про ML System Design я понял, что можно было добавить. Вот сейчас было обидно.
Общие впечатления
Вообще, судя по Glassdoor, у LinkedIn очень непростые собеседования. Вас могут попросить доказать теорему или написать функцию, превращающее одно распределение в другое. Все это требует довольно серьезной математической базы, так что, возможно, правильно, что меня не пропустили дальше.
Другие компании, куда меня не взяли
Google (реферал) - Написали, что получили мой реферал и обещали вернуться с ответом, но пропали.
Facebook (реферал) - ничего не написали, но прислали survey.
Amazon (реферал) - прошел все этапы, после чего получил отказ. Оказалось, что позиция, куда я собеседовался, больше про backend, поэтому мой опыт посчитали нерелевантным.
Mckinsey - успешно прошел все этапы, но на данный момент, я не тот специалист, который им нужен. (Может быть тот, которого они заслуживают?)
Snap - после Phone Screen рекрутер написал, что у меня слишком сильный бэкграунд и они постараются расти дальше, чтобы там было для меня место. Жду, на вас вся надежда.
Booking - прошел Phone screen, после чего HR пропала. Она стабильно отвечает на письма, но до сих пор не прислала ссылку на onsite.
Affirm - написали по ошибке. Когда узнали, что я из России, свернули лавочку.
Microsoft (реферал) - кандидатов из России рефералить нельзя. Им нужно отправлять специальное письмо в Москву. Письмо отправил, но никто не ответил. Наверное, там полный завал.
И еще около 50 компаний, которые прислали стандартный ответ: "Здравствуйте, мы очень внимательно вас изучили и вы нам не нравитесь. До свидания, присылайте свое резюме еще."
По ком звонит колокол
Однажды Эрнест Хемингуэй поспорил, что напишет самый короткий рассказ, способный растрогать любого. Он выиграл спор, написав: "We were impressed with your skills and experience, however, the team has decided not to move forward with your candidacy for this role."
В заключении, хочется сказать, что, во-первых, оставляйте хотя бы 2-3 строчки фидбека людям, которым решили отказать. Когда человек потратил на собеседование 2-6 часов, то очень обидно получать шаблонный ответ в духе: "мы вам перезвоним."
Во-вторых, постарайтесь хотя бы сделать вид, что вам не безразлична судьба кандидата. Собеседование - это стресс. Кандидату, кроме правильных ответов на вопросы, ещё нужно показать себя так, чтобы вы хотели с ним работать. Порой это трудно сделать, когда собеседующий сидит с хмурым лицом и на все вопросы отвечает одним словом.
В-третьих, собеседование в большие компании - это лотерея. Вы можете быть хоть трижды лучшим специалистом и все равно получить отказ. Таких историй полно. Главное, не теряйте надежду.
Если кому-то интересна моя судьба, то свой оффер я все-таки получил.
Спасибо за внимание.
Еще полезные ссылки:
Комментарии (44)
lair
22.09.2021 20:02-7Он выиграл спор, написав: "We were impressed with your skills and experience, however, the team has decided not to move forward with your candidacy for this role."
Это шутка такая?..
ivanovdev
22.09.2021 21:05+7горькая правда, которая трогает за душу
lair
22.09.2021 21:07-8Ммм, каким образом это правда, если я не могу найти никакого подтверждения, что Хемингуэй это писал?
AntonEryomin
22.09.2021 21:12+4Это была шутка :) Понятное дело, о какой конкретно фразе Хемингуэя идёт речь (про детские ботиночки).
n0rbert
24.09.2021 05:04Самое интересное в этой ситуации, что и рассказ про ботиночки Хемингуэй не сочинял.
AntonEryomin
22.09.2021 20:57+5А куда в итоге получили оффер, если конечно не секрет?
По поводу собеседования на MLщика, на мой взгляд это одни из самых сложных собесов, просто потому что есть слишком большое число вещей, по которым можно спросить, начиная от разработческого собеседования, вплоть до университетской математики и всё это довольно релевантные друг другу вопросы...
masai
22.09.2021 21:22+2Мне попалась задача применить функцию ax^2 + bx + c к некоторому массиву. Массив, a, b и c даны. Ограничение было таким, что a > 0. Суть простая: найти минимум функции и потом двумя указателями сформировать результат.
Непонятно. Зачем для применения функции к массиву искать минимум? И зачем тут два указателя?
etozhepivka Автор
22.09.2021 21:28Я пропустил важную часть условия, спасибо, что указали на это. Результат должен был быть отсортированным. Оригинал задачи: https://leetcode.com/problems/sort-transformed-array/
masai
22.09.2021 22:12+1Спасибо! Чтоб посмотреть условие по ссылке нужно логиниться, похоже, поэтому скопирую условие сюда для других:
Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax*x + bx + c to each element x in the array. The returned array must be in sorted order. Expected time complexity: O(n)
masai
22.09.2021 21:58+1После того как я предложил решение меня попросили рассказать про то, можем ли мы как-то его ускорить. Учитывая, сколько до этого меня мучили вопросами про многопоточность, я предложил именно этот способ. Но интервьюер ожидал ответ намного проще - мы можем использовать numpy. Я примерно помнил, какой метод мог мне тут помочь, но немного натупил с reshape. В итоге пришел отказ, в котором интервьюер написал, что был крайне недоволен, что я не предложил использовать numpy сразу и что я написал класс, а не функцию для решения задачи.
Если речь про Python, то обрабатывать массив питоновскими циклами — это плохая идея. Они очень медленные.
Многотопоточность скорости не добавит из-за GIL. А если использовать многопроцессность, то будут большие накладные расходы на IPC, да внутри всё равно же те же питоновские циклы.
Так что вариантов немного:
Написать бинарное расширение. Это, очевидно, не для интервью.
Использовать Numba. Проще, но тоже есть нюансы.
Использовать Numpy, который очень сильно оптимизирован. Это вариант для решения лучший.
Я думаю, что основная претензия была всё же к многопоточности, а не к классу.
Насчёт класса тоже понятна претензия. От кандидата часто ждут, что он будет писать код, как в продакшн. А там на такую простую задачу смысла заводить класс нет. Python — это же не Java. То, что в LeetCode везде классы, — это не аргумент. Там они просто для упрощения запуска сделаны и смотрятся инородно.
etozhepivka Автор
22.09.2021 22:10Да, речь шла про python.
Я вот как раз и подумал, какой хороший вопрос, чтобы рассказать про GIL. Конкретно я предложил написать код на плюсах и завернуть его в python модуль. Ну и тут как бы само собой напрашивается numpy, но для меня тогда вариант с использованием дополнительной библиотеки как-то вообще в голове не укладывалсяmasai
22.09.2021 23:21С точки зрения интервьюера это, видимо, был признак того, что кандидат плохо знаком с Numpy. Всё же в реальном коде для такой задачи скорее всего никто расширение на плюсах писать не будет.
Да и для собеседования это уже перебор писать на плюсах расширение (пусть даже и с помощью pybind11, что намного проще). Если не делаешь это каждый день, то попробуй ещё вспомни, как там GIL отпускается и как массив Numpy через buffer protocol туда-сюда гонять (ещё и выделять память под него). И это ещё надо распараллелить поиск уникальных элементов (не то, чтоб это было сложно, но время-то не резиновое).
masai
22.09.2021 22:01Насчёт Snap интересно. Так и написали, что overqualified?
etozhepivka Автор
22.09.2021 22:11+1Написали, что видят много силы в моем бэкграунде, если переводить на русский. Но я думаю, что они всем это пишут, когда отказывают
G1lgamesh
22.09.2021 23:19+2Воронка в 60+ отказов и игноров, конечно, поражает. Особенно с учетом того, что алгозадачи в подавляющем большинстве решались. Так понимаю, конторы с визой заморачиваться не хотят, а у остальных и так очередь на собеседование.
Все-таки в РФ с поиском работы сильно проще, даже с учетом всех нюансов.
masai
22.09.2021 23:23+1FAANG перевозит без вопросов, у них как раз нет проблемы оформить визу. Просто у них есть принцип, что лучше отказать хорошему кандидату, чем случайно взять плохого. Вот и доля отказов очень большая. Если есть сомнения — отказывают.
0xd34df00d
23.09.2021 06:05+1Из-за того, что я озвучил, что уже решал задачу, интервьюер чувствовал себя крайне некомфортно и ему мерещилось, что код я просто вспоминаю.
А что там интервьювер ожидает? Это же относительно простая задача (с примерно полутора тонкими моментами), идея решения с околоквадратичной сложностью (и я не уверен, что можно асимптотически лучше) придумывается быстро, само рабочее решение ваяется в литкоде минут за 15 на очень неприятных для этого плюсах, или ещё быстрее, минут за 10 у доски, где можно замести под ковёр детали вроде реализации кусочка рациональных чисел.
Нам нужно посчитать максимальное количество точек на прямой. Прямая задаётся двумя числами — k и b в уравнении y = kx + b. Кроме того, заметим (и это первый тонкий момент), что в этой задаче все координаты целочисленные, поэтому их отношения, которые вылезут в k и b, будут замыканием множества целых чисел над операциями умножения и деления, то есть, рациональными числами (так что думать о погрешностях флоатов не нужно), пополненными ещё одним элементом для случая двух точек на одной вертикальной прямой и «бесконечным» k (и это второй тонкий момент, но этот случай можно просто рассматривать отдельно, и вместо пары (k, b) оперировать положением на оси x, а все остальные рассуждения остаются теми же). Сами точки указывать не надо, поэтому по факту нам нужно посчитать максимум функции (k: ℚ, b: ℚ) → ℕ, отображающей k и b в число точек, лежащих на соответствующей прямой. В этой задаче естественно представить эту функцию таблично — ну, то есть, какой-нибудь там мапой из пары рациональных чисел в число точек. Как это посчитать? Напрямую неприятно, но легко заметить, что можно просто попарно рассматривать все точки, для них считать по легко выводимым формулам k и b, и инкрементировать соответствующее значение в мапе. Правда, тогда мы посчитаем не количество точек, а количество пар точек на каждой прямой, но, к счастью, максимум одного равен максимуму другого, поэтому мы можем найти максимальный элемент
maxв такой модифицированной мапе, и для этого элемента выполняется, что искомое число точекnс ним связано какn * (n - 1) / 2 = max. Дальше я минуты три выводил формулу решения квадратных уравнений (и мне лень было идти за ручкой, пришлось писать в комментах), потому что напрочь забыл, как это делается, наверное, перед интервьювером было бы стыдно, ну да ладно. В качестве задачи со звёздочкой можно подумать о физическом смысле отрицательного корня. В итоге пишется что-тотакое#include <map> struct Ratio { int n; int d; auto operator<(const Ratio& o) const { return (static_cast<float>(n) / d) < (static_cast<float>(o.n) / o.d); } }; template<typename T> int val_max(const T& cont) { if (cont.empty()) return 0; return std::max_element(cont.begin(), cont.end(), [](const auto& l, const auto& r) { return l.second < r.second; })->second; } class Solution { public: int maxPoints(vector<vector<int>>& points) { // k -> b -> count std::map<std::pair<Ratio, Ratio>, int> counts; // k ~ inf -> x -> count std::map<int, int> verticals; for (int i = 0; i < points.size(); ++i) { const auto xi = points[i][0]; const auto yi = points[i][1]; for (int j = i + 1; j < points.size(); ++j) { const auto xj = points[j][0]; const auto yj = points[j][1]; if (xj == xi) { ++verticals[xi]; } else { // y = kx + b // => // b = y - kx // in particular for jth point // b = yj - (yj - yi) * xj / (xj - xi) = // = yj * (xj - xi) / (xj - xi) - (yj - yi) * xj / (xj - xi) = // = (yj * (xj - xi) - (yj - yi) * xj) / (xj - xi) const Ratio k { yj - yi, xj - xi }; const Ratio b { yj * (xj - xi) - (yj - yi) * xj, xj - xi }; ++counts[{ k, b }]; } } } const auto max = std::max(val_max(counts), val_max(verticals)); // ax^2 + bx + c = 0 // x^2 + b/a x + c/a = 0 // x^2 + b/a x + (b^2 / 4a^2) + c/a - b^2/4a^2 = 0 // (x + b/2a)^2 + c/a - b^2/4a^2 = 0 // (x + b/2a)^2 = b^2/4a^2 - c/a // x + b/2a = +-sqrt(b^2/4a^2 - c/a) // x = -b/2a +-sqrt(b^2 - 4ac) / 2a // we probably only need positive root so assuming -4ac > 0: // x = (-b + sqrt(b^2 - 4ac)) / 2a // thus // n*(n - 1) / 2 = max // n*(n - 1) = 2 * max // n^2 - n - 2 * max = 0 // // 8max is > 0 given the assumptions so there's unique root // n = (1 + sqrt(1 + 8max)) / 2 return std::round((1 + sqrt(1 + 8 * max)) / 2); } };Учитывая
Runtime: 12 ms, faster than 76.40% of C++ online submissions for Max Points on a Line.
нормалёк.
Олсо, технически это
Oθ(n^2 log m), где n — число точек, m — число уникальных прямых, и убрать логарифм можно было бы хешмапой вместо мапы, но единственный адекватный хеш на рациональных числах, который я придумал, связан с gcd двух чисел, что куда тяжелее обычного деления и сравнения, и что-то мне не кажется это хорошей идеей для любых адекватных размеров входных данных — в худшем случае, когда все точки на разных прямых, будет m ~ n^2 прямых, что даст θ(n^2 log (n^2)) = θ(n^2 log n) (ну или на самом деле мне просто лень все эти кастомные хешеры писать руками,operator<проще).Задачу вижу первый раз, решение придумал только что, литкод вечерами и сотнями задач не прорешиваю.
iboltaev
23.09.2021 11:14+1раз вы сравниваете рационалки через каст к float-у, то и всю задачу можно было во float-ах решать, результат бы, я думаю, не изменился.
0xd34df00d
23.09.2021 16:43+1Нет, потому что для сравнения по порядку вам нужно меньше точности, чем для того, чтобы разные представления одного рационального числа попали в один бакет.
По крайней мере, доказать обратное у меня сходу не получилось.
iboltaev
23.09.2021 17:05А в каком случае в std::map-е 2 разных Ratio будут считаться эквивалентными? Когда
!(l < r) && !(r < l)что для float-ов означает, что они одинаковые. Так что вроде без разницы.
0xd34df00d
23.09.2021 20:11+1Если вы считаете всё в целых и переводите во флоаты только в момент засовывания в мапу, то да, конечно, это эквивалентно. Иначе у вас начинает накапливаться погрешность и до этого (например, там, где вы умножаете k на x), поэтому всю задачу на флоатах делать всё равно не стоит.
Но, конечно, наиболее правильным решением будет перебороть лень и сделать ещё полсотни нажатий на клавиатуре, чтобы написать все нужные проверки на знаки во всех нужных местах, как я упомянул в комментарии чуть ниже.
iboltaev
23.09.2021 20:37так у вас k на x и не умножается нигде
0xd34df00d
23.09.2021 21:19+1Как это не умножается? Умножается вон там справа, когда рассчитывается b.
AnthonyMikh
23.09.2021 13:18+1А зачем касты к float на операциях сравнения? На координаты ограничения от -10^4 до 10^4, тут можно обойтись одними умножениями в целых числах.
А ещё у вас, кажется, оператора разыменования в
val_maxне хватает, ибоstd::max_elementвозвращает итератор, а не сам элемент.0xd34df00d
23.09.2021 16:46+2А зачем касты к float на операциях сравнения? На координаты ограничения от -10^4 до 10^4, тут можно обойтись одними умножениями в целых числах.
А я об этом думал, но для умножения думать надо и учитывать знаки делителей (a1/b1? a2/b2 не эквивалентно a1 b2? a2 b1). Поэтому надо брать результат сравнения a1 b2 и a2 b1 и инвертировать его, если sgn(b1) sgn(b2) = -1, но это все уже неприятно, и особенно неприятно, что в C++ сигнума-то нет.
Ну либо можно, конечно, недонормализовывать рациональные числа при создании, меняя знак числителя и знаменателя, если знаменатель отрицательный, но это все снова неприятно, в рамках ограничений этой задачи конкретно оператор сравнения можно просто сделать на флоатах.
А ещё у вас, кажется, оператора разыменования в val_max не хватает, ибо std::max_element возвращает итератор, а не сам элемент.
Он там спрятался за стрелочкой в выражении
->second.
masai
23.09.2021 15:10Хэш от рационального числа a / b часто считают так:
hash(a / b) = hash(a * inv(b))где
inv— это обратный элемент по модулю. Если в качестве модуля берём простое число, там достаточно быстро считается и асимптотика зависит только от самого модуля, а это константа. Да, тяжелее умножения, но зато мы асимптотику улучшаем переходом на хэш-таблицу. Впрочем, для ограничений задачи на практике в этом большого смысла и нет, константа под асимптотикой съест всё преимущество, наверное.
Про float уже сказали, что можно заменить на умножения. Или наоборот. Несмотря на то, что я числам с плавающей точкой не доверяю, при ограничениях задачи, наверное, всё можно было бы на них сделать и работало бы.
Если вдруг хочется полностью от float избавиться, то можно и корень выкинуть. Можно счётчик сделать хитрее. Надо будет хранить пару: (число точек на прямой, число встреченных пар). Изначально там (1, 0). Каждый раз когда добавляем пару, увеличиваем второе число на 1. Если оно стало равно первому, то увеличиваем уже его, а счётчик пар сбрасываем в 0. На асимптотику не влияет, просто на каждой итерации добавляется проверка и иногда ещё одно сложение и присваиванием.0xd34df00d
23.09.2021 16:55+1Хэш от рационального числа a / b часто считают так:
Проблема в том, что у нас тут a и b не сокращены, и хэш 1/1 будет другим, чем 2/2, например, а это неприятно.
masai
24.09.2021 13:37Нет, для 1/1 и 2/2 хэши будут одинаковыми.
inv(b) — это такое (уникальное) число, a inv(b) = 1 (mod m).
Из малой теоремы Ферма следует, что inv(b) = b^(phi(m) - 1) (mod m). То есть, переходим от инверсии к обычной степени, а там можно раскрыть скобки и перегруппировать множители. И получаем, что inv(k b) = inv(k) inv(b) (mod m).
Соответственно, для несокращённой дроби ka / kb получаем k a inv(k b) = (k inv(k)) (a inv(b)) = a inv(b) (mod m), а это то же, что и для дроби a / b.
То есть, можно не сокращать.
Кстати, в Python легко обратный элемент считать, там это функция pow умеет:
pow(b, -1, m) # inv(b)Так что можно убедиться:
>>> a, b, m = 15, 33, 17389 >>> inv = lambda x: pow(x, -1, m) >>> (a * inv(b)) % m 12647 >>> k = 30 >>> (k * a * inv(k * b)) % m 12647Но и на C++ это легко реализуется через быстрое возведение в степень.
Правда, надо сделать замечание, что числа должны быть взаимно простыми с m. Но можно взять простое m, большее, чем верхняя граница из условия задачи, тогда и GCD считать не нужно.
masai
24.09.2021 13:51На самом деле можно даже брать m, не большее, чем граница, а большее, чем корень из границы. Этого достаточно, чтоб m не был множителем чисел из указанного диапазона. Если в задаче до 10^4 числа, то можно взять какое-то простое, большее 100. Это произвольные числа, так что можно вообще выбрать то, которое удобнее.
Если взять m=131, то возводить надо в степень 129 = 2^7 + 1. Тогда получается такой код:
>>> def inv(a): ... r = a ... for _ in range(7): ... r = (r * r) % 131 ... return (r * a) % 131 ... >>> inv(1234) 81 >>> pow(1234, -1, 131) 81masai
24.09.2021 14:36А, не. Про корень я наврал, конечно. :) Так как само число m уже имеет множитель m.
Ну, тогда можно взять m = 2 ^ 15 + 3 = 32771 (это простое число) и в алгоритме выше заменить 7 итераций на 15 и 131 на 32771.
0xd34df00d
24.09.2021 16:44+2Соответственно, для несокращённой дроби ka / kb получаем k a inv(k b) = (k inv(k)) (a inv(b)) = a inv(b) (mod m), а это то же, что и для дроби a / b.
Только ведь k inv(k) равно единице только по модулю m. Поэтому, да,
hash(a / b) = hash((a * inv(b)) `mod` m)будет работать, но у вас этого модуля не было (с другой стороны, и я мог бы догадаться).masai
24.09.2021 17:29+1А, ну да. Я подразумевал, но забыл написать. :)
0xd34df00d
24.09.2021 18:09+2Энивей, спасибо за продуктивную дискуссию, я и забыл, что находить обратные в кольцах вычетов по простому числу можно эффективно.
Вот, флексить решениями полезно, узнаёшь что-то новое!
LevOrdabesov
24.09.2021 18:34Подумалось: прикинув количество ресурсов (особенно терпения, целеустремлённости, общего уровня подготовки), которые требуются только для того, чтобы попасть внутрь «супер-компаний», можно предположить, что скоро кандидатам будет проще находить себе «креативного директора» («формального лидера», «генератора идей» и т.п.) и самим открывать компанию с любыми плюшками, какие хочется.
anonymous
etozhepivka Автор
Каждая компания по своему понимает обязанности дата саентиста. Кого-то попросят оптимизировать ML модели и обучать нейронные сети, а кого-то могут попросить excel файл переписать на python