Comments 112
Недавно собеседовал на С++. Все кандидаты написали в резюме senior (у некоторых было даже tech-lead). Задача — «Дана матрица. Нужно повернуть числа в ней по часовой\против часовой стрелке. Предложите структуру(ы) для ее хранения, передачи и решения задачи».
Ни с одним не дошли до стадии «компилируется и хоть как-то выполняет задачу»…
Сейчас почитал статью — наверно надо было предлагать решить ее на питоне.
Ни с одним не дошли до стадии «компилируется и хоть как-то выполняет задачу»…
Сейчас почитал статью — наверно надо было предлагать решить ее на питоне.
Самое тупое чтобы не думать: создается матрица-копия и в нее пишется, потом оригинал уничтожается. Более сложное и правильное использовать простую перестановку 2х чисел (проще через третье в памяти) и циклы, но тут надо быть внимательным чтобы ничего не потерять. Вроде ответ очевиден, или что хочется услышать? Применение какой-либо готовой функции из общедоступных библиотек? Если что мопед не мой, я не программист уже четвертый год: )
на самом деле, я смотрел в глаза, и при ответе типа: " создается матрица-копия и в нее пишется ...", уже ставил плюсик.
Если там была еще и хорошая мысль — то второй плюс, и так за каждое улучшение. Как у автора оригинальной заметки: «это фрактальная дисциплина».
Если там была еще и хорошая мысль — то второй плюс, и так за каждое улучшение. Как у автора оригинальной заметки: «это фрактальная дисциплина».
Вот честно, когда дают задание что-то написать конкретное, особенно абстрактное, и чтобы компилировалось и работало и эффективно, то возникает желание взять и уе… с мыслями вроде «что я тут делаю» и «может они так себе задачи нахаляву решают». Алгоритмически обсудить, нарисовать простейшую блок-съему и т.п. всегда пожалуйста, но писать, компилить и дебажить код — увольте. Это скучно и займет много времени без всякого производительного результата. Например я уверен что смогу запрограммировать свои идеи, а вот программировать их в коде просто так не горю желанием. Нанимайте меня и тогда буду кодить. Но то может я такой хреновый программист, а хорошему и закодить за 5 минут нетрудно на любом предложенном языке.
Вы отказываетесь писать работающий код на собеседовании на должность программиста? Не домашнее задание на неделю работы, а именно на собеседовании в офисе.
Вот мне даже интересно как такие люди вообще работу находят?
Вот мне даже интересно как такие люди вообще работу находят?
Не знаю, ни разу не приходилось. Один лишь раз Тандер выдал домашнее задание, но мне было лень его делать. Все остальные разы было достаточно предъявления опыта работы, теоретической беседы и тестов. Написание кода если и было то лишь буквально 3-4 строчки и то для иллюстрации сказанного, без компиляции на компьютере. Как нахожу работу сам не понимаю.
P.S. не ну я ж сразу сказал я плохой программист, на 100% им никогда не был, и код взрослый не писал, так что-нибудь в продакшен оператора связи наживую запулить и все, не операционную систему ж для ракеты созидаю.
P.S. не ну я ж сразу сказал я плохой программист, на 100% им никогда не был, и код взрослый не писал, так что-нибудь в продакшен оператора связи наживую запулить и все, не операционную систему ж для ракеты созидаю.
Я себе так нашел. Только словесное техническое интервью с директором и просто знакомство с тимлидами.
После гуглей, блумбергов, амазонов с 8 интервью за день, просто душой отдыхал.
После гуглей, блумбергов, амазонов с 8 интервью за день, просто душой отдыхал.
Вы отказываетесь писать работающий код на собеседовании
Это подмена понятий.
Во-первых, писать работающий код без инструментария, к которому я привык за годы работы не хочу. IDE, хоткеи – без них я чувствую себя некомфортно. Вполне реально забыть как в той же джаве инициализируются двумерные массивы, если их не используешь.
Во-вторых, в реальности код всегда пишется в каком-либо контексте и чтобы в этот контекст войти часто нужны недели. Писать абстрактный код без контекста (нет, алгоритм это не контекст, а условие) – уровень университетской лабораторной работы, это не проверяет ничего.
Я не понимаю этого нехотения писать код. Писать код это то что мы хорошо умеем делать. Это то за что нам платят деньги. Просто логично на собеседовании показать свое лучшее умение.
Забытый кусок синтаксиса это ну настолько мелкая проблема. Всегда можно честно сказать я забыл как именно это пишется. Поэтому считаем массив заранее инициализированным. Тонкости синтаксиса гуглятся за минуту. Все в курсе.
Есть множество людей которые не способны писать код. Вообще. При этом у них будет красивое резюме (мы же не хотим проводить расследование о правдивости резюме для каждого кандидата?), они будут очень красиво говорить общие слова и даже смогут ответить на типовые теоретические вопросы. На работе они будут копипастить со SO без понимания как и почему. Как таких отсеять? Отсеивание на испытательном сроке это очень печально, его надо всеми силами избегать.
Проверяем умение писать код. Простой. Абстрактный. Это точно проще чем любой продакшен код. И это как минимум гарантирует что человек лабы в университете делал сам. Таких меньшинство.
Забытый кусок синтаксиса это ну настолько мелкая проблема. Всегда можно честно сказать я забыл как именно это пишется. Поэтому считаем массив заранее инициализированным. Тонкости синтаксиса гуглятся за минуту. Все в курсе.
Есть множество людей которые не способны писать код. Вообще. При этом у них будет красивое резюме (мы же не хотим проводить расследование о правдивости резюме для каждого кандидата?), они будут очень красиво говорить общие слова и даже смогут ответить на типовые теоретические вопросы. На работе они будут копипастить со SO без понимания как и почему. Как таких отсеять? Отсеивание на испытательном сроке это очень печально, его надо всеми силами избегать.
Проверяем умение писать код. Простой. Абстрактный. Это точно проще чем любой продакшен код. И это как минимум гарантирует что человек лабы в университете делал сам. Таких меньшинство.
Ага, писать код мы любим и умеем, а вот писать код стоя в гамаке обутыми в лыжи — не очень. Лично я — отказываюсь писать код в лыжах, хотя очень люблю писать код и посвящаю этому все свое свободное и рабочее время.
Элементарно: поговорите с человеком. Не задавайте тупых «типовых теоритеческих вопросов», спросите что человеку интересно, узнайте о его философии, подходах к работе, симпатиях и антипатиях. Попробуйте поспорить, обязательно на позитиве, на какую-то тему. Попросите показать код, которым человек гордится, попробуйте выяснить почему. Я вас уверяю, все будет ясно, если вы сами обладаете хоть каким-то боевым опытом.
Как таких отсеять?
Элементарно: поговорите с человеком. Не задавайте тупых «типовых теоритеческих вопросов», спросите что человеку интересно, узнайте о его философии, подходах к работе, симпатиях и антипатиях. Попробуйте поспорить, обязательно на позитиве, на какую-то тему. Попросите показать код, которым человек гордится, попробуйте выяснить почему. Я вас уверяю, все будет ясно, если вы сами обладаете хоть каким-то боевым опытом.
Умение писать код в условиях стресса и цейтнота — тоже нужный на практике навык («сервер ни с того ни с сего лёг, теряем сотни денег каждую минуту!»)
Интересно: сколько лично вы собеседовали соискателей?
По-моему, навык «очаровать собеседника при беседе» никак не коррелирует с «писать код быстро и хорошо»
Элементарно: поговорите с человеком.
Интересно: сколько лично вы собеседовали соискателей?
По-моему, навык «очаровать собеседника при беседе» никак не коррелирует с «писать код быстро и хорошо»
Умение писать код в условиях стресса и цейтнота — тоже нужный на практике навык
Ну да, как же без «ее величества» — стрессоустойчивости. Вас, когда «лег сервер» заставляют писать абстрактный код на бумажке? Отбирают все доки, мануалы, анализаторы? Заставляют одновременно решать, подходит ли мне этот работодатель? Заставляют вспоминать теоретические моменты, напрямую к ситуации никак не относящиеся? Думаю что нет.
Интересно: сколько лично вы собеседовали соискателей?
Не помню точно, но не один десяток. Достаточно, чтобы иметь обоснованное мнение по данному вопросу.
По-моему, навык «очаровать собеседника при беседе» никак не коррелирует с «писать код быстро и хорошо»
Ага, попробуйте «очаровать» технического специалиста, рассуждая на технические темы, о которых имеете слабое представление. Беседа ведь предполагается вовсе не о погоде. И никто вам не даст абсолютно никакой гарантии, что человек, решивший «быстро и хорошо» задачку на бумажке, будет работать «быстро и хорошо». Все эти задачки — это просто способ переложить личную ответственность за принятое решение о найме на формальный критерий, слабо коррелирующий с реальными боевыми условиями.
Просто логично на собеседовании показать свое лучшее умение.
Лучшее умение программиста — читать код. Чем меньше кода в итоге написано, тем лучше. Меньше кода — меньше багов.
А что может показать написание кода за полчаса на интервью? То, что человек смог заучить десяток ключевых слов языка и имеет приблизительное понимание того, что такое код программы?
Код может написать и хреновый программист. Описать, формализовать и обсудить решение – только хороший. Беседа на общие и даже отдаленные темы показывает свою куда бОльшую эффективность в долгосрочной перспективе, чем решенное тестовое.
Код может написать и хреновый программист. Описать, формализовать и обсудить решение – только хороший. Беседа на общие и даже отдаленные темы показывает свою куда бОльшую эффективность в долгосрочной перспективе, чем решенное тестовое.
То что человек может писать код. Странно правда?
Я лично собеседовал человека у которого в резюме было слово SQL, а в вакансии было слово Оракл. У него судя по резюме был опыт, он довольно красиво рассказывал про нормальные формы и прочую теорию.
Только вот с задачей написать простенький селект с джойном и групбаем из пары табличек на бумажке он не справился. От слова вообще. Такое ощущение, что он синтаксис sql впервые увидел. О чем после такого может идти речь?
Я сильно подозреваю что на вакансии Java, С итп такие же кадры приходят. Резюме вроде хорошее работал, сделал итд. Теорию зазубрить несложно. На собеседованиях очень типовые вещи по теории спрашивают. А вот написать десяток строк кода человек не может.
Отмазки мол я не могу без IDE написать десять строк кода это глупости. Базовый синтаксис у любого человека пишущего код за деньги в подкорке сидит. Каждый день же используешь. В практических задачах использовать что-то кроме базового синтаксиса никогда не надо. О сложных вещах можно и просто поговорить.
Спрашивать сложные вещи по теории хуже чем заставлять писать код. Они как раз каждый день не используются и великолепно забываются.
Я лично собеседовал человека у которого в резюме было слово SQL, а в вакансии было слово Оракл. У него судя по резюме был опыт, он довольно красиво рассказывал про нормальные формы и прочую теорию.
Только вот с задачей написать простенький селект с джойном и групбаем из пары табличек на бумажке он не справился. От слова вообще. Такое ощущение, что он синтаксис sql впервые увидел. О чем после такого может идти речь?
Я сильно подозреваю что на вакансии Java, С итп такие же кадры приходят. Резюме вроде хорошее работал, сделал итд. Теорию зазубрить несложно. На собеседованиях очень типовые вещи по теории спрашивают. А вот написать десяток строк кода человек не может.
Отмазки мол я не могу без IDE написать десять строк кода это глупости. Базовый синтаксис у любого человека пишущего код за деньги в подкорке сидит. Каждый день же используешь. В практических задачах использовать что-то кроме базового синтаксиса никогда не надо. О сложных вещах можно и просто поговорить.
Спрашивать сложные вещи по теории хуже чем заставлять писать код. Они как раз каждый день не используются и великолепно забываются.
Если вы ходите на работу только для того, чтобы писать код, я вам сочувствую. Я своих подопечных никогда не просил на собеседовании тратить время на написание кода. В конце концов есть испытанный срок, с человеком можно и расстаться.
А можно не терять время на испытательный. Если на собеседование по SQL человек не может сделать create table с 3 полями(выбрав их тип под задачу и объяснить почему выбрал этот), а потом написать селект с 1 join и парой условий (а таких много, если не предлагать зарплату в два рынка), то тратить бумагу на договор не стоит. Так же, когда человек заявляет опыт в чём-то типа ++ в 5-10-15 лет, но не может сделать простой класс (на любом удобном ему языке), путается между наследованием и методом, то опять не вижу смысла продолжать. Если какой-то рокстар отсеется на этом этапе, то и пусть (обычно задачи сильно прозаичнее, чем он бы хотел).
Квадратную матрицу можно сначала транспонировать (против ч.с. — относительно главной диагонали, по — относительно побочной), затем обменять местами строки (первую с последней, вторую с предпоследней и т.д.). Достаточно swap'а элементов.
Да и неквадратную тоже можно, при транспонировании её форма как раз "повернётся".
Хотя я вместо этого думал сделать обертку, которая отображает индексы типа x, y => y, width — x и потом либо сделать просто обертку над старой матрицей, которая притворяется "новой", либо с таким отображением индексов скопировать всё в новую матрицу. (Копировать можно поблочно, чтобы кеш работал)
Но вариант с траспонированием и переворотом строчек более красивым кажется, в том же питоне numpy такое быстро сделает, в отличие от ручного перекладывания элементов.
Будет что-то типа А.T[::-1, :]
Если уж пользоваться numpy, так там вообще просто есть rot90, который делает именно то, что нужно.
Более того, в numpy (во многих операциях, в документации заметно по «returns — view of m») используется именно идея с оберткой и отображением индексов, что позволяет не проводить фактически никаких операций с массивом на самом деле, но зато ухудшает работу кэша.
Итого, нам, на самом то деле, недостаточно данных: если из массива далее будут интенсивно последовательно читать данные, то лучше перенести на самом деле, иначе — можно воспользоваться отображением.
Более того, в numpy (во многих операциях, в документации заметно по «returns — view of m») используется именно идея с оберткой и отображением индексов, что позволяет не проводить фактически никаких операций с массивом на самом деле, но зато ухудшает работу кэша.
Итого, нам, на самом то деле, недостаточно данных: если из массива далее будут интенсивно последовательно читать данные, то лучше перенести на самом деле, иначе — можно воспользоваться отображением.
а можно сначала свапнуть, а потом транспонировать — и тогда не нужно побочной диагонали.
Если не ошибаюсь подобную встречал на LeetCode. Или Cracking Code Interview. Вообще имхо доводить на бумажке или доске до состояния компилируется ИМХО все же не правильно, я, например, могу от волнения тупо забыть методы из stl, какие в них параметры передаются, порядок, что выдают на гору. Мне кажется во всех подобных задачах при решении у доски важен именно диалог, который дает понять как у человека с алгоритмизацией и мышлением. А вот если уже комп дают, то можно уже смотреть с точки зрения компилирования, но там и ide помогает.В таких случаях я, например, начинал писать с юнит тестов (TDD), а потом итеративно писал алгоритм и придумывал дополнительные кейсы после того, как основная часть уже готова, но часто просили просто обсудить граничные условия, а не их реализацию и мы переходили к следующей.
P.S. Вакансия С++, просить написать на Python — будет странно смотреться))) Яб сильно задумался на месте собеседуемых, что от меня будут требовать в будущем.
P.S. Вакансия С++, просить написать на Python — будет странно смотреться))) Яб сильно задумался на месте собеседуемых, что от меня будут требовать в будущем.
Есть замечательные онлайн-компиляторы с возможностью совместного редактирования (и для С и для С++17 и проч и проч). Там можно накалякать простой код и запустить.
А про питон — вот я сейчас сам для себя дома пишу всякую всячину на питоне (на который перешел с перла), и размышляю, что не так важен язык, как умение сесть и действительно задуматься над задачей (а не фигачить код).
Вот когда алгоритм уже линейный-логарифмический, а скорости все равно нехватает — тогда наверно можно и переписать на чем-то быстром, но до такого пока не доходило…
А про питон — вот я сейчас сам для себя дома пишу всякую всячину на питоне (на который перешел с перла), и размышляю, что не так важен язык, как умение сесть и действительно задуматься над задачей (а не фигачить код).
Вот когда алгоритм уже линейный-логарифмический, а скорости все равно нехватает — тогда наверно можно и переписать на чем-то быстром, но до такого пока не доходило…
А почему senior должен решать такие задачки лучше джуна со свеженькими знаниями из университета по «верчению» разных матриц, деревьев и прочих laba2.cpp?
Вы бы еще попросили поделить столбиком на бумажке два числа – я бы не смог, а вот третьеклассники умеют. Только какое это все имеет отношение к компетенции программиста?
Вы бы еще попросили поделить столбиком на бумажке два числа – я бы не смог, а вот третьеклассники умеют. Только какое это все имеет отношение к компетенции программиста?
Тут важно не решение задачи, а то, как кандидат рассуждает, и то, как глубоко он видит контекст. Собственно, об этом в статье говориться.
Разумеется, задача хоть немного должна быть привязана к тематике его будущей работы. Если предлагается потом писать высокооптимизированный код для обработки изображений, то задача с поворотом матрицы вполне годится как повод для начала разговора.
Это как задачка «Расскажите, что происходит, когда вы вводите адрес в браузере и нажимаете Enter». Тоже можно до бесконечности углубляться.
Ну и есть другой аспект. Иногда люди претендующие на высокие должности просто не дотягивают до них. Таких можно отсеять подобными задачками.
Такими «задачками» можно лишь отсеять людей, которые на такие должности как раз дотягивают. Если вы будете и на работе давать tech lead'ам задачки на выкручивание матриц по кругу – нужна ли ему такая работа? А если не будете давать на работе, то зачем тратить его и ваше время на возню с университетскими i,j,k?
Конечно, вышесказанное не относится к обработке изображений или какому-нибудь ML. Но, учитывая, что подавляющая часть вакансий это перегонка SQL в JSON и обратно, то задача типа «сделайте BFS обход дерева» смотрится неуместно.
Конечно, вышесказанное не относится к обработке изображений или какому-нибудь ML. Но, учитывая, что подавляющая часть вакансий это перегонка SQL в JSON и обратно, то задача типа «сделайте BFS обход дерева» смотрится неуместно.
Конечно, вышесказанное не относится к обработке изображений или какому-нибудь ML.
Ну вот об этом и речь. Нет универсальной задачи на собеседования для всех случаев. И если берут программиста программировать фронтэнд, то понятно, что повороты матриц будут смотреться оторванно от реальности.
Чтобы перегонять SQL в json и в университет ходить не надо было.
Ого, аж три минуса! Надеюсь, это из-за опечатки с -ться.
Я смотрю, аргументы такие:
- такие задачки задевают достоинство высококвалифицированного кандидата,
- зачем тратить время на написание кода, нужно побеседовать,
- любой программист больше времени пишет документацию, тесты, общается с заказчиком.
Это всё хорошо в теории. Но посмотрите на первый пост в этой ветке. Вот экспериментальный факт — люди, претендующие на должность senior, не справляются с элементарной задачей.
Я ещё раз повторю, важно знать, какие именно задачи будет решать человек. Ответьте для себя на вопрос, вы бы взяли такого кандидата, чтобы он, скажем, решал задачи обработки изображений на микроконтроллерах? Понятно, что веб-разработчику такую задачу давать бессмысленно.
Если же кандидат быстро решил задачу, то можно побеседовать с ним дальше — как оптимизировать код с точки зрения какого-то из критериев.
Например, как избежать копирования всех данных в матрице? А как оптимизировать последовательный обход? А как оптимизировать поворот, если матрица хранится на диске в каком-то хитром формате и в память не влезает? А что если нужно поворачивать квадратные участки большой матрицы? Тут масса поводов поговорить на не такие уж и простые темы.
Можно, конечно сразу вести разговор не требуя что-то запрограммировать. Но дьявол кроется в деталях. Я видел людей, которые абстрактно, на словах знают, как решать задачи (часто встречающиеся реальные, не оторванные от жизни). Например: «Тут нужно применить такую-то структуру и такой-то алгоритм». Но как эту структуру реализовать или какую библиотеку использовать, они уже не знают. Почему бы не взять человека, который знает и не будет тратить время на гугление, а не того, который не знает? Или если senior, то уметь программировать не нужно?
Если не нужно, то да, ОК, можно задачи на программирование и не давать, а просто поговорить.
По поводу последнего аргумента о том, что программист большую часть времени тратит вовсе не на задачки. Не забывайте, что программисты разные. Да, не все каждый день пишут ПО для лунных миссий, обработку изображений, числодробилки. Но есть люди, которые этим действительно занимаются каждый день.
Собственно, весь мой пост — это выражение удивления, что люди сходу говорят, что так собеседовать нельзя, такие задачи не подходят, но никто не спросил, а на какие задачи кандидата собеседуют, и все почему-то неявно считают, что собеседование было одно и состояло только из одной простой задачи.
А почему senior должен решать такие задачки лучше джуна со свеженькими знаниями из университета по «верчению» разных матриц, деревьев и прочих laba2.cpp?
а что это за senior что не может решить задачки джуна?
а что это за senior что не может решить задачки джуна?А что это за врач, который не может решить задачи медсестры?
А что это за врач, который не может решить задачи медсестры?
ну как минимум сравнение не уместное, так как джун, это будущий сениор, когда медсестра это будущая старшая медсестра (а не врач).
Тогда переформулируем в:
- что это за старшая медсестра, которая не может решить задачи медсестры
- что это за хирург, который не может решить задач ассистента хирурга
Да и вообще, задачу, которую тут обсуждают, ничего общего со «свежими» знаниями из университета не имеет.
Есть 2d массив, нужно свапануть элементы. И все.
Вас никто не спрашивает написать AVL или Red-Black Tree.
Спрашивают азы, базу.
> «Дана матрица. Нужно повернуть числа в ней по часовой\против часовой стрелке. Предложите структуру(ы) для ее хранения, передачи и решения задачи».
Многое зависит от контекста задачи.
Навскидку, что приходит в голову:
1) Если матрица всегда маленькая и скорость некритична, то просто создаём новую и заполняем как надо. Или делаем перестановки прямо на месте.
2) Если матрица очень большая и копировать данные не хочется — храним данные построчно и делаем 4 индексатора для каждого из углов поворота.
Пусть данные хранятся в массиве A. Храним поля: номер последней строки — r, число столбцов — c, номер последнего элемента – N = (r + 1) * c - 1. Пусть запрашивается элемент (i, j). (Имена полей, разумеется, в реальном коде надо сделать человекочитаемыми.)
0° – A[c * i + j],
90° – A[c * (r - j) + i],
180° – A[N - (c * i + j)],
270° – A[N - (c * (r - j) + i)].
При каждом повороте записываем адрес нужного индексатора, который и будем вызывать при запросе элемента.
3) Если часто выполняется последовательный проход, в прошлом варианте могут быть проблемы с непопаданием в кэш, если обходим по строкам повёрнутую на 90° матрицу. Тут тоже есть разные варианты решения. Можно хранить два варианта матрицы — по строкам и столбцам. Или можно в фоновом потоке выполнять поворот, пока нет обращений к матрице.
4) Матрица может быть разреженной и т. д. Короче, тут можно до бесконечности усложнять.
По поводу передачи матрицы — отдельный разговор.
Прошу прощения, вопрос дилетанта.
«Повернуть» — это элемент a[0][0] в a[0][n-1] перевести?
«Повернуть» — это элемент a[0][0] в a[0][n-1] перевести?
давайте я «на пальцах» —
дано: есть матрица 3х3:
1 2 3
4 5 6
7 8 9
надо: чтобы в stdout она была выведена
1) по часовой стрелке:
7 4 1
8 5 2
9 6 3
2) против часовой стрелки:
3 6 9
2 5 8
1 4 7
индексы, размеры матрицы и её прямоугольность, способ хранения, алгоритм и тд и пр — все на ваше усмотрение.
Всё является предметом обсуждения, потому что мне лично было все интересно, даже с какого места начиналась работа мысли — написать на бумажке формулу, или нарисовать на бумажке диаграмму, или написать сначала пустую обертку в коде (а потом думать над алгоритмом), или ничего не писать а задавать уточняющие вопросы.
Мой самый любимый момент на собеседованиях — это момент «ага!», когда голова у человека включается и он задумывается над проблемой. (ну или нет — и тогда извините)
дано: есть матрица 3х3:
1 2 3
4 5 6
7 8 9
надо: чтобы в stdout она была выведена
1) по часовой стрелке:
7 4 1
8 5 2
9 6 3
2) против часовой стрелки:
3 6 9
2 5 8
1 4 7
индексы, размеры матрицы и её прямоугольность, способ хранения, алгоритм и тд и пр — все на ваше усмотрение.
Всё является предметом обсуждения, потому что мне лично было все интересно, даже с какого места начиналась работа мысли — написать на бумажке формулу, или нарисовать на бумажке диаграмму, или написать сначала пустую обертку в коде (а потом думать над алгоритмом), или ничего не писать а задавать уточняющие вопросы.
Мой самый любимый момент на собеседованиях — это момент «ага!», когда голова у человека включается и он задумывается над проблемой. (ну или нет — и тогда извините)
Задача как мне кажется довольно простая, при этом очень муторная. В ней много корнер кейсов которые надо дополнительно обрабатывать (например не специфицирована операция «поворота по часовой стрелке» матрицы 1xN или Nx1 которая обязательно появится для неквадратной матрицы). Никакой специфичной структуры данных для такой задачи не могу придумать, кажется достаточно определить функцию трансформации координат что-то вроде
Но на пути к рабочему решению лежит бесчисленное множество граблей, минус единиц, и прочих
Мне кажется что это не очень хорошая задача для собеседования, потому что по ней не очень много можно понять о кандидате. Как уже говорили выше, её может решить студент первокурсник, а может накосячить опытный разработчик.
transformXY(sizeX, sizeY, x, y) -> {x, y} (псевдокод) а затем обойти матрицу «по слоям» от краев к центру, свапая элементы. Так мы получим О(1) по памяти и О(NxM) по времени что кажется является теоретическим пределом (нельзя потратить памяти меньше константной, нельзя провернуть матрицу не потрогав каждый её элемент).Но на пути к рабочему решению лежит бесчисленное множество граблей, минус единиц, и прочих
<\<= требующих сильной концентрации и внимательности.Мне кажется что это не очень хорошая задача для собеседования, потому что по ней не очень много можно понять о кандидате. Как уже говорили выше, её может решить студент первокурсник, а может накосячить опытный разработчик.
В Google мне конечно не попасть, но, при чтении статьи, меня не покидала мысль, что я бы стал всё это делать на SQL, а при необходимости отладки, тестов, и демонстрации результатов — использовал бы BigQuery.
Я наверно что-то не понял, но зачем так сложно? Нечто вроде баскет сорта великолепно сработает.
Заводим лист с номерами корзин и мапу с самими корзинами.
HashMap<String, Integer> baskets;
List basketNumbers;
Первую пару кладем в нулевую.
Далее для каждой пары: Если любое слово из пары найдено в любой корзине, второе добавляем в туже. Если ничего не найдено заводим новую с новым номером. Если найдены в разных, то ставим им одинаковый номер.
Далее тривиально ищем номера корзин для всех отличающихся слов в строках для поиска.
Сложность O(m+n)
m количество пар
n количество слов в минимальной строке для поиска
Вот интересно, а есть ли инженерные позиции в гугл-фэйсбук-***, где не нужны такие знания?
Условный сетап — я умею в деревья, но никогда в жизни не делал дп, красно-чёрное дерево было два раза на лабе. 40% рабочего времени — это формочки, 20% — что-то задеплоить (вебпак-докер-ci/cd) и ещё 40 — разное от интервью до талент менеджерства. Есть шансы, или пора открывать книжки с алгоритмами?)
*Просто каждый пост с собесами про гугл имеет слова, похожие на `обратная функция Аккермана` — там просто люди есть?)
Условный сетап — я умею в деревья, но никогда в жизни не делал дп, красно-чёрное дерево было два раза на лабе. 40% рабочего времени — это формочки, 20% — что-то задеплоить (вебпак-докер-ci/cd) и ещё 40 — разное от интервью до талент менеджерства. Есть шансы, или пора открывать книжки с алгоритмами?)
*Просто каждый пост с собесами про гугл имеет слова, похожие на `обратная функция Аккермана` — там просто люди есть?)
В Apple и Tesla точно есть обычные люди и есть позиции куда не спрашивают алгоритмов сложнее стеков и очередей. Во всяком случае в embedded разработке это так.
я точно не помню чтоб про офА писал :))
деревья — но не списки, не рекурсия, не матрицы? вот такая узкая специализация?
или просто другие ветки не прокачаны, но общие сведения есть?
в последнем случае тот же leetcode на 3-4 недели по 2 часа вечером = всё вспомнено и готов к собесу…
деревья — но не списки, не рекурсия, не матрицы? вот такая узкая специализация?
или просто другие ветки не прокачаны, но общие сведения есть?
в последнем случае тот же leetcode на 3-4 недели по 2 часа вечером = всё вспомнено и готов к собесу…
В вашей статье нет, в самом деле :) И да, общие сведения, разумеется.
Просто судите сами, я сделал запрос на хабре про собеседования в гугл — второй, пятый, шестой результаты — везде алгоритмы.
Мой вопрос скорее даже не про интервью, а про как там работать. Можно за два месяца накачаться в алгоритмах, пройти интервью, даже проскочив на шару с какой-то задачей, которую решал до этого — а дальше-то что? Какой скилл реально нужен для работы?
Просто судите сами, я сделал запрос на хабре про собеседования в гугл — второй, пятый, шестой результаты — везде алгоритмы.
Мой вопрос скорее даже не про интервью, а про как там работать. Можно за два месяца накачаться в алгоритмах, пройти интервью, даже проскочив на шару с какой-то задачей, которую решал до этого — а дальше-то что? Какой скилл реально нужен для работы?
а дальше-то что? Какой скилл реально нужен для работы?Реализовывать алгоритмы каждый день не нужно (как минимум в той части Гугла, где я). Знать, что они есть, чтобы аргументированно выбирать структуры данных и раз в сто лет все-таки что-то реализовывать — нужно.
Если интересно, как часто используются сложные алгоритмы, можно попробовать посмотреть исходный код каких-нибудь опенсорсных продуктов — например, Андроида. По-моему, особо не отличается от того, что бывает в других продуктовых компаниях.
Насколько я понимаю, особенность Гугла в том, что «просто людей» им нанимать нет смысла — и так на каждое место у них претендует 100500 «ракетных учёных», и они могут себе позволить выбирать среди них. Так что и формочками и деплоем у них тоже занимаются «ракетные учёные».
и так на каждое место у них претендует 100500 «ракетных учёных»
Даже если это — их подсознательное желание, оно не соответствует действительности.
Рынок говорит нам о том, что соотношение спрос/предложение на инженера с опытом 10+ лет улетает в комос по экспоненте. И имеется тенденция увеличение стартовой скорости ;-)
Вот Facebook даёт з/п в 1.5 раза больше в кэше, Microsoft лоббирует возможность завозить разрабов из стран третьего мира пачками, кто-то открывает офисы разработки не в it-долинах, и отвоёвывет локальные рынки труда. Все пытаются доставить своих космонавтов на орбиту по-разному.
Касательно же самого Google… по моим личным наблюдениям, у них явно прослеживаются циклы закручивания и откручивания гаек при найме.
Но компании с некоторой задержкой понимают, что нельзя нанимать интернов пачками на работу, иначе они через 3-4 года сгорят и всем отрядом уедут на острова пить ром. (нет, ну круто же в 25 лет быть миллионером?), и что если не нанять толкового человека, который a little bit below the line, то потеря времени просто чудовищная, и значительно лучше дообучить сотрудника в контексте компании, потому что так или иначе, но синдром самозванца начинает жрать всех, кому за ..
Короче, посомтрите замечательный доклад Growing the Site Reliability Team at LinkedIn: Hiring is Hard
PS. Почему-то большинство людей думает, что в %big_company_name% всё сложно-сложно и ничерта не понятно. Но это же не так, потому что сложные системы сложно деббажить и разрабатывать, а на сотнях и тысячах банок — это вообще ад и погибель, поэтому системы состоят из более мелких и максимально тупых подсистем. Об этом говорят на каждой конфе.
Я про конкуренцию Гугла не с Фейсбуком и Амазоном, а с «сайтостроительными артелями» из дюжины-двух человек. «Простые люди», занимающиеся формочками и деплоем, нужны и там и там, но техногигантам нет смысла их нанимать, потому что могут на их место нанять «непростых».
Я вам ровно об этом и писал: не может нанять, потому что нельзя из /dev/urandom сгенерировать инженера.
Кроме того, любой техногигант — это в первую очередь множество legacy, которое надо поддерживать. Об это разбилась ни одна сотня, а может и тысячи инженеров, которые приходили двигать индустрию вперёд, но бизнес говорил им делать другое :-P
Вот интересно, а есть ли инженерные позиции в гугл-фэйсбук-***, где не нужны такие знания?Disclaimer: личный опыт нерепрезентативен
Когда я собеседовался в Google, никакие особо алгоритмы были не нужны (бинарный поиск (использование, не реализация) и стек, кажется, понадобились, но это же все знают, ведь так?), но была нужна ДП. Ее особенность в том, что нет некоторого «алгоритма», который нужно знать, а до всего можно додуматься самостоятельно, с нуля. И очень многие известные алгоритмы (например, большая часть того, что обычно называют «графы»), на самом деле, несложно придумывается с нуля, если умеешь в ДП.
никогда в жизни не делал дпИзвините, не верю. Простое ДП (уровня «посчитать числа фибоначчи») встречается вообще везде, и обычно все его делают интуитивно, не считая за ДП.
Еще одна задачка, угадай что я думаю. Итого дано две пары синонимов. ('rate', 'ratings'),
('approval', 'popularity') И первое что я должен спросить у собеседующего:«Есть ли у слова еще синонимы? » Вопрос такой с подвохом: Типа у Маши и Кати 6 яблок они поделили поровну, сколько у них яблок? А вот нет, они в процессе дележки три потеряли и и два Витя отнял!
Второй про транзитивность, это тоже умно с учетом, что у нас два слова и нет третьего, я должен спросить, а не транзитивны ли они? ДА какая мне разница, если всего два слова?
О порядке слов я тоже почему-то должен спросить, хотя по моему это очевидно что рейтинг популярности и популярность рейтинга — это немного разные вещи.
В итоге все сводится к тому, что решая задачу про дележку яблок между Катей и Таней, я должен спросить, а точно ли это яблоки, мож еще груши были и равны ли груши яблокам, был ли Витя и с кем он дружит, и не имеет ли яблоки способности спонтанно делиться на две груши или нет.
('approval', 'popularity') И первое что я должен спросить у собеседующего:«Есть ли у слова еще синонимы? » Вопрос такой с подвохом: Типа у Маши и Кати 6 яблок они поделили поровну, сколько у них яблок? А вот нет, они в процессе дележки три потеряли и и два Витя отнял!
Второй про транзитивность, это тоже умно с учетом, что у нас два слова и нет третьего, я должен спросить, а не транзитивны ли они? ДА какая мне разница, если всего два слова?
О порядке слов я тоже почему-то должен спросить, хотя по моему это очевидно что рейтинг популярности и популярность рейтинга — это немного разные вещи.
В итоге все сводится к тому, что решая задачу про дележку яблок между Катей и Таней, я должен спросить, а точно ли это яблоки, мож еще груши были и равны ли груши яблокам, был ли Витя и с кем он дружит, и не имеет ли яблоки способности спонтанно делиться на две груши или нет.
Да, почему-то в реальной жизни приходится задачу доопределять и вообще понять о чем идёт речь. Требовать точного ТЗ и 100% определения можно только кодерам на галере. Даже в универе ответ чаще всего будет «а вы подумайте.»
У меня вот обратная проблема, я наоборот слишком усложняю решения задач там, где можно оператору написать в инструкции «вот в этом случае не нажимать». Все зависит от размера компании и бюджета.
Например, вместо пандусов и лифтов в пешеходных переходах можно инвалидам за счет города выделить бесплатное такси за счет муниципалитета. Возможно это в разы дешевле, хотя инженерно пандусы и лифты выглядят куда круче. (Я кстати не утверждаю, что так будет правильно, я не урбанист и не архитектор, я лишь привел другой вариант, который может оказаться в определенных условиях лучше, и я думаю, что именно это делает меня инженером, а не знание алгоритмов и стеков технологий)
Мастер не тот, кто все знает, а тот — кто знает то, чего он не знает. Имхо если на собеседовании спрашивать «что бы вы хотели изучить, и что даже трогать не станете по крайней мере сейчас», то можно куда полнее картину о кандидате построить.
Например, вместо пандусов и лифтов в пешеходных переходах можно инвалидам за счет города выделить бесплатное такси за счет муниципалитета. Возможно это в разы дешевле, хотя инженерно пандусы и лифты выглядят куда круче. (Я кстати не утверждаю, что так будет правильно, я не урбанист и не архитектор, я лишь привел другой вариант, который может оказаться в определенных условиях лучше, и я думаю, что именно это делает меня инженером, а не знание алгоритмов и стеков технологий)
Мастер не тот, кто все знает, а тот — кто знает то, чего он не знает. Имхо если на собеседовании спрашивать «что бы вы хотели изучить, и что даже трогать не станете по крайней мере сейчас», то можно куда полнее картину о кандидате построить.
Не спорю. Если б данный товарищ, сказал вот вопросик к нему можно задать кучу дополнительных вопросиков и потрындеть с кандидатом за жизнь в процессе чего выяснится его уровень знаний, то да.
Но автор сказал, что вот есть список «правильных» вопросов для хорошего кандидата, которые он обязан задать. Правильные они только в его мозгу. Банально:
if len(q1) != len(q2):
output.append(False)
C чего бы это? «рейтинг популярности Обамы» и «рейтинг популярности Барака Обама» и «популярность Обамы» не могут быть синонимами? Автор ни слова не сказал, про это оно как будто так и должно написал этот код. То есть у него, например, по умолчанию, количество слов является мерилом синонимичности фраз, а у меня по умолчанию например транзитивность синонимов, и будем справедливым, я логичней в этом вопросе.
По этому я и говорю задача на «угадай мыслю», что собеседующий считает важным, а что не очень, притом, что он может быть неправ.
Но автор сказал, что вот есть список «правильных» вопросов для хорошего кандидата, которые он обязан задать. Правильные они только в его мозгу. Банально:
if len(q1) != len(q2):
output.append(False)
C чего бы это? «рейтинг популярности Обамы» и «рейтинг популярности Барака Обама» и «популярность Обамы» не могут быть синонимами? Автор ни слова не сказал, про это оно как будто так и должно написал этот код. То есть у него, например, по умолчанию, количество слов является мерилом синонимичности фраз, а у меня по умолчанию например транзитивность синонимов, и будем справедливым, я логичней в этом вопросе.
По этому я и говорю задача на «угадай мыслю», что собеседующий считает важным, а что не очень, притом, что он может быть неправ.
В реальной жизни, задачи — это "угадай мыслю", что заказчик считает важным, а что не очень, притом, что он может быть неправ. По-моему уточнение требований, и понятие видения задачи постановщиком на собеседовании — это очень приближенный к реальности скилл.
В реальной жизни, задачи — это «угадай мыслю», что заказчик считает важным, а что не очень, притом, что он может быть неправ. По-моему уточнение требований, и понятие видения задачи постановщиком на собеседовании — это очень приближенный к реальности скилл.
Казалось бы, да, всё верно.
Однако, на собеседовании нас собеседуют обычно разработчики, лиды, старшие разработчики и прочие, казалось бы, разумные личности.
Поэтому, если за заказчиком нужно изначально додумывать, дорасспрашивать, доставать с целью вынуть нужную информацию — то при общении с разработчиками и получении от них задач мы невольно считаем их полными и точными, если не сказано обратного. Ведь, не будете же вы давать своему коллеге таск из разряда «есть такая фигня, почини», верно?) Вы изложите детально все ньюансы и проблемы. Скорее всего даже с вариантами решения.
И на собеседовании невольно может сработать та же аналогия и человек может даже не подумать спросить вопрос, который он задал бы в другое время, просто из-за того, что считает человека, сидящего перед ним, разумным человеком.
А вы задаёте правильные вопросы. Это и требуется на собеседовании — думать.
И да, продовить черту когда еще надо докапываться, а когда уже пора лабать код.
Список правильных вопросов он всегда есть в подсознании, но оцениваются те вопросы, которые задают кандидаты. И таки да — многие очень креативны, и я лично когда встречаю вопрос которые задают 1 из 20 всегда очень радуюсь. Это всегда хороший знак, особенно если потом закрепляется впечатление более-менее корректным кодом.
И да, продовить черту когда еще надо докапываться, а когда уже пора лабать код.
Список правильных вопросов он всегда есть в подсознании, но оцениваются те вопросы, которые задают кандидаты. И таки да — многие очень креативны, и я лично когда встречаю вопрос которые задают 1 из 20 всегда очень радуюсь. Это всегда хороший знак, особенно если потом закрепляется впечатление более-менее корректным кодом.
Автор ни слова не сказал, про это оно как будто так и должно написал этот кодАвтор сказал:
Могут ли синонимы охватывать несколько слов, как «США» является синонимом для фраз «Соединённые Штаты Америки» или «Соединённые Штаты»?А далее
Если кандидаты задают вопросы, я всегда начинаю с самого простого случая
а дальше сразу долгий гундеж на тему неэффективности контэйнс в пайтоне, хотя сразу пишет что его можно использовать при паре десятков значений в списке, но синонимов как раз обычно пару десятков и есть. Но тебе это поставят в минус, потому что этот парень, случайно глянул в реализацию контейнс в питоне и решил, что не подходит.
Я не очень эмпатичен, и намучался с этим типом людей, которые считают себя самыми умными и возьмут только тех, кто мышлением похож на них, и не дай бог тебе мыслить по другому или оказаться умней его. В худшем случае тебя обзовут идиотом, в лучшем просто потом пришлют письмо, что вы не подходите. И слава богу. про телепатию в списке моих достоинств ничего не написано)))
Я не очень эмпатичен, и намучался с этим типом людей, которые считают себя самыми умными и возьмут только тех, кто мышлением похож на них, и не дай бог тебе мыслить по другому или оказаться умней его. В худшем случае тебя обзовут идиотом, в лучшем просто потом пришлют письмо, что вы не подходите. И слава богу. про телепатию в списке моих достоинств ничего не написано)))
Сколько синонимов стоило бы спросить. Вы правда считаете, что поисковики оперируют словарями в десятки синонимов?
Собственно, в крупные компании принимать по мнению только одного человека никогда не будут. Собеседований несколько, и личное мнение никого из них особой роли не играет.
Собственно, в крупные компании принимать по мнению только одного человека никогда не будут. Собеседований несколько, и личное мнение никого из них особой роли не играет.
У меня яндекс есть)) К слову «рейтинг», если исключить однокоренные «медиарейтинг», «тв-рейтинг» и забавное «писькомерка» осталось всего 7 синонимов. Если взять первый синоним «оценка», и посмотреть его 57 синонимов, то на втором месте можно увидеть слова «цена» и «суд» и вопрос о транзитивности отмирает мгновенно. Но этот человек, посвятил ему полстатьи, и если ты скажешь ему вежливо, причем здесь транзитивность-то?, ты будешь весьма поверхностным и недалеким типом, который не мыслит глубоко фрактально, также как мыслит этот гений современности.
Я еще раз скажу, есть вопросы на которые нет правильного ответа, это вопросы на порассуждать, например «главное достижение/факап Путина», или «Где правильное ударение в слове „Маркетинг“», но этот чувак, считает что он знает правильный ответ и будет гнобить всех, кто так не считает. Поэтому он профнепригоден, как собеседователь.
Я еще раз скажу, есть вопросы на которые нет правильного ответа, это вопросы на порассуждать, например «главное достижение/факап Путина», или «Где правильное ударение в слове „Маркетинг“», но этот чувак, считает что он знает правильный ответ и будет гнобить всех, кто так не считает. Поэтому он профнепригоден, как собеседователь.
Хорошо, вы посмотрели несколько синонимов. Так всё же — сколько их всего? Какой размер словаря?
А на тему правильного ответа — ответ он всегда правильный в заданных условиях и только. Пока вы пытаетесь спорить не с тем вопросом, который был задан, причем с человеком, которого здесь нет, отвечая за него то, что вы думаете…
А на тему правильного ответа — ответ он всегда правильный в заданных условиях и только. Пока вы пытаетесь спорить не с тем вопросом, который был задан, причем с человеком, которого здесь нет, отвечая за него то, что вы думаете…
ИМХО, возможно с этой транзитивностью и связаны особенности текущего поиска быстро и как не спрашивай, но если тебе нужно "не то что отдают по этим словам большинству", найти почти невероятно.
p.s. у меня для этой задачи есть другая мысль, искать точно по словам но при этом вести статистику того, сколько людей кликнули на один и тот-же результат.
Обратите внимание, что мы перешли от трёх ключей и шести записей к четырём ключам и двенадцати записям. Слово с 50 синонимами потребует 50 ключей и почти 2500 записей. Необходимое пространство для представления одного слова квадратично растёт с увеличением набора синонимов, что довольно расточительно.
Есть и другие решения, но не буду слишком углубляться, чтобы не раздувать статью. Наиболее интересное из них — использование структуры данных синонимов для построения ориентированного графа, а затем поиск в ширину для нахождения пути между двумя словами. Это прекрасное решение, но поиск становится линейным по размеру набора синонимов для слова. Поскольку мы выполняем этот поиск для каждого запроса несколько раз, такой подход не оптимален.
Неужели за все то время, что он собеседовал этой задачкой, никто на этом этапе так и не сказал, что можно обойтись все тем-же словарем и для 50 синонимов иметь 49 ключей с одинаковым значением — первый синоним?
типа, есть словарь
fast — quick
rapid — quick
для добавления fast — speedy достаточно добавить в словарь еще один ключ:
speedy — quick
упд:
Непересекающиеся множества решают совсем иную проблему: вместо определения конкретного элемента они позволяют определить, принадлежат ли два элемента одному набору. Более того, структура делает это за с ослепительно быстрое время O(a(n)), где a(n) — обратная функция Аккермана.
Но ведь в моем варианте можно сделать то-же самое за два запроса к словарю со сложостью O(1), или я дурак и где-то ошибаюсь?
Ой, действительно я дурак, что не дочитал до конца, а побежал комментировать, там в итоге к тому-же самому и пришли.
Не совсем к тому же. У вас запрос O(1), у них запрос O(a(1)). С другой стороны, у них одна пара синонимов обрабатывается за те же О(1), а у вас как бы не О(n) будет. Так что такую структуру, как у вас — придется долго строить.
Хм, действительно, реализации все-таки разные, там приходят к ссылкам на один общий синоним во время поиска синонимов, из-за чего повышается сложность этого шага, а я предлагаю сразу писать в словарь ссылки на общий синоним.
Почему? Если посмотреть предложенную реализацию класса DisjointSet, там в итоге используется все тот-же словарь но самая долгая операция это поиск корня get_root(), которая, кроме всего прочего, приводит одинаковые синонимы к одному значению (и поэтому имеет цикл), и этот метот вызывается дважды как во время добавления пары синонимов, так и во время поиска синонимов.
Я думаю, что гораздо более эффективно сразу на этапе добавления слов в словарь писать в него нужные значения: увеличивается скорость добавления пар синонимов, скорость поиска синонимов, кроме того ключами в словаре у нас будут не все возможные слова, а на одно слово, коренной синоним, меньше для каждой группы синонимов. То есть, если синонимов только два, то будет одна запись, когда один синоним это ключ, а второй синоним это значение; если синонимов три, то будет две записи, первый синоним ключ, второй значение, плюс еще одна запись где ключ третий синоним, а значение — второй; и тд.
Этого можно достичь добавив дополнительный HashSet (уж не знаю какой его аналог в Питоне), в котором будут храниться синонимы — значения словаря.
Будет что-то вроде этого (прошу прощения за любые ошибки, ибо я не питоновец и написал просто по-аналогии с кодом из статьи):
Операция чтения словаря/hashSet — O(1), добавления значения — либо O(1), либо O(n) если вдруг нам понадобилось увеличить емкость.
В моем случае для каждой пары синонимов добавляется либо одна запись в parents, либо две записи: одна в parents и одна в root_values. В реализации из статьи записи будут добавляться в один единственный словарь, из-за чего n того словаря будет больше, а значит и емкость словаря придется увеличивать чаще, и сложность O(n) этой операции будет расти быстрее. Это не говоря уже о возможности нарваться на цикл при каждом добавлении синонима.
Для проверки синонимов мне в худшем случае надо прочитать два раза из словаря, в реализации из статьи в худшем случае можно нарваться на цикл и свертку.
С другой стороны, у них одна пара синонимов обрабатывается за те же О(1), а у вас как бы не О(n) будет. Так что такую структуру, как у вас — придется долго строить.
Почему? Если посмотреть предложенную реализацию класса DisjointSet, там в итоге используется все тот-же словарь но самая долгая операция это поиск корня get_root(), которая, кроме всего прочего, приводит одинаковые синонимы к одному значению (и поэтому имеет цикл), и этот метот вызывается дважды как во время добавления пары синонимов, так и во время поиска синонимов.
Я думаю, что гораздо более эффективно сразу на этапе добавления слов в словарь писать в него нужные значения: увеличивается скорость добавления пар синонимов, скорость поиска синонимов, кроме того ключами в словаре у нас будут не все возможные слова, а на одно слово, коренной синоним, меньше для каждой группы синонимов. То есть, если синонимов только два, то будет одна запись, когда один синоним это ключ, а второй синоним это значение; если синонимов три, то будет две записи, первый синоним ключ, второй значение, плюс еще одна запись где ключ третий синоним, а значение — второй; и тд.
Этого можно достичь добавив дополнительный HashSet (уж не знаю какой его аналог в Питоне), в котором будут храниться синонимы — значения словаря.
Будет что-то вроде этого (прошу прощения за любые ошибки, ибо я не питоновец и написал просто по-аналогии с кодом из статьи):
class DisjointSet(object):
def __init__(self):
self.parents = {}
self.root_values = {} # не знаю питона, здесь нужен тип HashSet, или аналоги, впрочем, для демонстрации словарь тоже подойдет
def add_synonyms(self, w1, w2):
if self.are_synonymous(w1, w2):
return
# Если одно из слов уже есть в root_values, значит второе - его синоним и просто добавляем его в словарь
if w1 in self.root_values:
self.parents[w2] = w1
return
if w2 in self.root_values:
self.parents[w1] = w2
return
# Если одно из слов есть в словаре, значит добавляем второе в словарь со значением значения первого слова.
if w1 in self.parents:
self.parents[w2] = self.parents[w1]
return
if w2 in self.parents:
self.parents[w1] = self.parents[w2]
return
# Новая пара синонимов
self.parents[w1] = w2
self.root_values.add(w2) # я не знаю, есть ли hash set в питоне, если нет, ну пусть будет словарь и тогда вместо self.root_values.add(w2), self.root_values[w2]=0
def are_synonymous(self, w1, w2):
if w1 = w2:
return True
root_w1 = w1
if w1 in self.parents:
root_w1 = self.parents[w1]
if root_w1 == w2:
return True
root_w2 = w2
if w2 in self.parents:
root_w2 = self.parents[w2]
if root_w2 == w1:
return True
return root_w1 == root_w2
Операция чтения словаря/hashSet — O(1), добавления значения — либо O(1), либо O(n) если вдруг нам понадобилось увеличить емкость.
В моем случае для каждой пары синонимов добавляется либо одна запись в parents, либо две записи: одна в parents и одна в root_values. В реализации из статьи записи будут добавляться в один единственный словарь, из-за чего n того словаря будет больше, а значит и емкость словаря придется увеличивать чаще, и сложность O(n) этой операции будет расти быстрее. Это не говоря уже о возможности нарваться на цикл при каждом добавлении синонима.
Для проверки синонимов мне в худшем случае надо прочитать два раза из словаря, в реализации из статьи в худшем случае можно нарваться на цикл и свертку.
В питоне я тоже не особо, так что не беспокойтесь.
Во-первых, ваша реализация работает некорректно. Проверим на парах (1, 2), (3, 4), (2,4). После добавления всех трёх у вас parents = {{1, 2}, {3, 4}, {4, 2}}, и root_values = {2, 4}. are_synonymous(1, 3) выдаёт false, хотя должен true. Сами догадаетесь, что не так?
Во-вторых, в настоящем DisjointSet, примерно как в статье, время одной операции действительно может быть большим — как из-за увеличения словаря (хотя его обычно заполняют сразу, parent[w] = w]), так и из-за длинного цикла (не больше O(logn)). Но при этом в среднем запрос выполняется за константу — точно так же, как хотя иногда добавление в массив выполняется за О(n), в среднем оно выполняется за O(1).
Во-первых, ваша реализация работает некорректно. Проверим на парах (1, 2), (3, 4), (2,4). После добавления всех трёх у вас parents = {{1, 2}, {3, 4}, {4, 2}}, и root_values = {2, 4}. are_synonymous(1, 3) выдаёт false, хотя должен true. Сами догадаетесь, что не так?
Во-вторых, в настоящем DisjointSet, примерно как в статье, время одной операции действительно может быть большим — как из-за увеличения словаря (хотя его обычно заполняют сразу, parent[w] = w]), так и из-за длинного цикла (не больше O(logn)). Но при этом в среднем запрос выполняется за константу — точно так же, как хотя иногда добавление в массив выполняется за О(n), в среднем оно выполняется за O(1).
Да, действительно, такой случай я не учел, спасибо!
Чтобы его покрыть, в моей реализации необходимо делать root_values словарем, где в качестве значения держать список синонимов и в случае когда пришла пара у которой оба слова уже есть в root_values — приводить ветки к одному значению. Такая реализация уже будет проигрывать по памяти реализации из статьи и вероятно проигрывать по скорости добавления синонимов. Скорость are_synonymous все равно будет быстрее, из-за не слишком удачной реализации в статье get_root, хотя если get_root переделать, то скорость извлечения будет одинаковой.
Чтобы его покрыть, в моей реализации необходимо делать root_values словарем, где в качестве значения держать список синонимов и в случае когда пришла пара у которой оба слова уже есть в root_values — приводить ветки к одному значению. Такая реализация уже будет проигрывать по памяти реализации из статьи и вероятно проигрывать по скорости добавления синонимов. Скорость are_synonymous все равно будет быстрее, из-за не слишком удачной реализации в статье get_root, хотя если get_root переделать, то скорость извлечения будет одинаковой.
Знаете, это у вас заплатки получаются какие-то, причем даже не в том месте. Ваша реализация всё ещё работает некорректно. Пример — пары (1, 2), (3, 4), (1, 3),. Получается parents = {{1,2},{3,1}}, и проверим are_synonymous(2, 4) — выдаёт false. Да даже are_synonymous(3, 4) теперь выдаст false, хотя у нас есть прямо такая пара.
Я-же не привел никакую реализацию, только описание, а вы даже по нему нашли ошибки, снимаю шляпу :)
Я так не умею, пришлось-таки проверять в Питоне.
Вот такой вариант add_synonyms работает без ошибок. Ну, как минимум, покрывает ваш случай и то, что я смог придумать:
Я так не умею, пришлось-таки проверять в Питоне.
Вот такой вариант add_synonyms работает без ошибок. Ну, как минимум, покрывает ваш случай и то, что я смог придумать:
def unite_roots(self, root1, root2):
self.root_values[root2].extend(self.root_values[root1])
for syn in self.root_values[root1]:
self.parents[syn] = root2
self.root_values.pop(root1)
self.parents[root1] = root2
self.root_values[root2].append(root1)
def add_synonyms(self, w1, w2):
if self.are_synonymous(w1, w2):
return
if w1 in self.root_values and w2 in self.root_values:
self.unite_roots(w1, w2)
return
if w1 in self.root_values and w2 in self.parents:
self.unite_roots(w1, self.parents[w2])
return
if w2 in self.root_values and w1 in self.parents:
self.unite_roots(w2, self.parents[w1])
return
if w1 in self.parents and w2 in self.parents:
self.unite_roots(self.parents[w1], self.parents[w2])
return
if w1 in self.root_values:
self.parents[w2] = w1
self.root_values[w1].append(w2)
return
if w2 in self.root_values:
self.parents[w1] = w2
self.root_values[w2].append(w1)
return
if w1 in self.parents:
self.parents[w2] = w1
self.root_values[w1].append(w2)
return
if w2 in self.parents:
self.parents[w1] = w2
self.root_values[w2].append(w1)
return
self.parents[w1] = w2
self.root_values[w2]=[w1]
А теперь прикиньте сложность полученного кода…
Алгоритмическую — кодовую сложность я уже вижу.
Такую плотность минного поля для опечаток w1/w2 можно только в рамочку :)
Алгоритмическую — кодовую сложность я уже вижу.
Такую плотность минного поля для опечаток w1/w2 можно только в рамочку :)
Опечатки, по идее, должны все вылечиться на этапе тестирования.
Вся «сложность» это проверка наличия слов в двух словарях, 4 варианта когда оба слова находятся в одном, или разных словарях и 4 варианта когда одно из слов находится в каком-нибудь словаре, а другое нет.
Такой вариант будет проигрывать по памяти варианту из статьи, но, вероятно, будет выигрывать по быстродействию.
А если вдруг будет стоять задача, когда словарь синонимов читается один раз и больше не меняется, то памяти будет выигрывать (вплоть до двух раз, в зависимости от данных), ибо словарь root_values используется только на этапе заполнения словаря и не используется в are_synonymous, так что можно изменить класс DisjointSet соответствующи образом, чтоб после заполнения синонимами память root_values освобождалась.
Вся «сложность» это проверка наличия слов в двух словарях, 4 варианта когда оба слова находятся в одном, или разных словарях и 4 варианта когда одно из слов находится в каком-нибудь словаре, а другое нет.
Такой вариант будет проигрывать по памяти варианту из статьи, но, вероятно, будет выигрывать по быстродействию.
А если вдруг будет стоять задача, когда словарь синонимов читается один раз и больше не меняется, то памяти будет выигрывать (вплоть до двух раз, в зависимости от данных), ибо словарь root_values используется только на этапе заполнения словаря и не используется в are_synonymous, так что можно изменить класс DisjointSet соответствующи образом, чтоб после заполнения синонимами память root_values освобождалась.
ds = DisjointSet()
ds.add_synonyms("a", "b")
ds.add_synonyms("b", "c")
ds.add_synonyms("d", "c")Так всё же, какая сложность O-большое?
Почему вы решили что решение будет выигрывать по быстродействию?
Я не говорил, что мое решение обязательно будет выигрывать по быстродействию, я написал, что вероятно будет выигрывать.
Сложнось О(1) кроме случаев, когда надо объединять ветки, как в примере mk2: (1, 2), (3, 4), (1, 3), тогда будет цикл по элементам ветки. Кроме того, когда емкости словарей заканчиваются, тогда добавление нового элемента в словарь стоит O(n).
В реализации из статьи также в основном сложность O(1) и также увеличение емкости словаря стоит O(n) для словаря.
Однако циклы там, вероятно, будут случаться чаще, просто потому-что в предложенном алгоритме значением для всех элементов синонимов должен быть наименьший синоним и периодически надо уходить в цикл, менять цепочки элементов.
Написал и сам с трудом понял, что написал, попробую показать на примере.
Допустим мы добавили пару синонимов: (4, 5). В parents у нас будут 2 записи: [4]=4 и [5]=4.
Добавили (3, 5), получили [3]=3, [4]=3, [5]=4.
Добавили (2, 5), получили [2]=2, [3]=2, [4]=3, [5]=3
Добавили (1, 5), получили [1]=1, [2]=1, [3]=2, [4]=3, [5]=2
Каждый раз циклом заходим все глубже и еще остаются элементы для обновления.
Я не знаю, какой вариант будет на самом деле быстрее, возможно зависит от данных. Хотя, подозреваю, что мой вариант наверняка рассматривался среди других альтернатив DisjointSet и если от него отказались в пользу того, что в статье, наверное он все-таки хуже.
Сложнось О(1) кроме случаев, когда надо объединять ветки, как в примере mk2: (1, 2), (3, 4), (1, 3), тогда будет цикл по элементам ветки. Кроме того, когда емкости словарей заканчиваются, тогда добавление нового элемента в словарь стоит O(n).
В реализации из статьи также в основном сложность O(1) и также увеличение емкости словаря стоит O(n) для словаря.
Однако циклы там, вероятно, будут случаться чаще, просто потому-что в предложенном алгоритме значением для всех элементов синонимов должен быть наименьший синоним и периодически надо уходить в цикл, менять цепочки элементов.
Написал и сам с трудом понял, что написал, попробую показать на примере.
Допустим мы добавили пару синонимов: (4, 5). В parents у нас будут 2 записи: [4]=4 и [5]=4.
Добавили (3, 5), получили [3]=3, [4]=3, [5]=4.
Добавили (2, 5), получили [2]=2, [3]=2, [4]=3, [5]=3
Добавили (1, 5), получили [1]=1, [2]=1, [3]=2, [4]=3, [5]=2
Каждый раз циклом заходим все глубже и еще остаются элементы для обновления.
Я не знаю, какой вариант будет на самом деле быстрее, возможно зависит от данных. Хотя, подозреваю, что мой вариант наверняка рассматривался среди других альтернатив DisjointSet и если от него отказались в пользу того, что в статье, наверное он все-таки хуже.
Если быть честным, на мой взгляд единственный кейс, когда можно применять мой вариант, это когда мы загружаем все синонимы один раз, а дальше во время работы только проверяем на синонимность. В этом случае у него будет выигрыш по памяти.
Дело в том, что «по памяти» разница может быть (а может и нет) при исполнении. Оценка О большое по памяти у них равная, О(N+M).
Оценка скорости (насколько я смог прикинуть, я не большой спец) тоже одинаковая вообще (и я бы посчитал её амортизированной О(1)). У вас дороже вставка, но опять же, амортизированная сложность выглядит той же.
Так всё же, почему падает
ds.add_synonyms(«a», «b»)
ds.add_synonyms(«b», «c»)
ds.add_synonyms(«d», «c»)
?
Оценка скорости (насколько я смог прикинуть, я не большой спец) тоже одинаковая вообще (и я бы посчитал её амортизированной О(1)). У вас дороже вставка, но опять же, амортизированная сложность выглядит той же.
Так всё же, почему падает
ds.add_synonyms(«a», «b»)
ds.add_synonyms(«b», «c»)
ds.add_synonyms(«d», «c»)
?
Дело в том, что «по памяти» разница может быть (а может и нет) при исполнении.
Я имею ввиду довольно специфичный случай, когда нам надо загрузить синонимы один раз и больше не менять, а вся остальная работа будет проверка на синонимность.
Тогда загрузку всех синонимов можно вынести в инициализацию класса, туда-же поместить root_values и после инициализации память root_values будет освобождаться. А в parents в моем случае в ключах хранятся не все синонимы, а только те, что не являются в значениями других синонимов, следовательно записей там будет меньше, чем в варианте из статьи, т.к. там в словаре все синонимы — ключи, просто некоторые записи имеют одинаковый и ключ и значение.
Но это весьма специфичный случай, т.к. если нам надо загружать синонимы откуда-то один раз в начале работы, то почему-бы их там, откуда будем загружать, уже не хранить в нужном формате?
Так всё же, почему падает
Ой, я не сразу понял зачем этот пример.
Падает потому-что при переходе из первого варианта ко второму я потерял корни в последних двух условиях, вместо корней использовал ключи. Ладно, пора причесать код, чтоб он стал более наглядным с меньшим шансом на ошибку:
def unite_roots(self, root1, root2):
self.root_values[root2].extend(self.root_values[root1])
for syn in self.root_values[root1]:
self.parents[syn] = root2
self.root_values.pop(root1)
self.parents[root1] = root2
self.root_values[root2].append(root1)
def get_root(self, w):
if w in self.parents:
return self.parents[w]
if w in self.root_values:
return w
return False
def add_synonyms(self, w1, w2):
if self.are_synonymous(w1, w2):
return
root_w1 = self.get_root(w1)
root_w2 = self.get_root(w2)
if root_w1 and root_w2:
self.unite_roots(root_w1, root_w2)
return
if root_w1:
self.parents[w2] = root_w1
self.root_values[root_w1].append(w2)
return
if root_w2:
self.parents[w1] = root_w2
self.root_values[root_w2].append(w1)
return
self.parents[w1] = w2
self.root_values[w2]=[w1]
Очень странный подход — писать код со структурами данных в памяти. Очевидно ведь, что ответ на вопрос, явдяются ли два слова синонимами, не задаётся офицеру поисковой службы, а вычисляется на основе заранее составленного словаря. Соответственно, поиск должен проходить в два шага: приведение запроса к «каноническому» виду по словарю и поиск «канонических» ключевых слов. То есть код достаточно простой, а вот структуры данных — не такие простые.
.
Когда я проходил собеседование в одну аутсорсинговую контору на должность Trainee/Junior (выше не претендовал) Angular Developer, меня тоже поспрашивали теории, потом перешли к практике.
Дали несложную задачку на элементарное умение находить оптимальное решение (уровень Easy LeetCode думаю, т.к. и должность не столь высокая, и фронт-энд разработчику не так остро нужны алгоритмы как другим), но так как я очень разнервинался (первое собеседование в жизни!), с фразой «Не будем привязываться к языку» накатал решение на доске на суржике из Python, псевдокода и JS.
Потому что компилировать код в голове, предвидеть ошибки на тот момент я ещё не умел, анализировать задачу я ещё не умел.
В общем задачки были очень простые, но тоже, со своеобразным подвохом, нужно было подумать.
Это я к чему веду? Я не считаю нужным при решении задач на белой доске привязываться к конкретной технологии/языку. Мы все пользуемся IDE, которая решает большое количество рутинных задач за нас, наша задача остаётся — думать и анализировать возможное решение поставленной задачи.
Кроме SQL конечно, ИМХО, SQL это такой язык, который нужно в голове уметь «запускать», он слишком простой, чтобы не уметь этого делать.
Уровень понимания языка — открывайте GitHub интервьируемого. Теорию можно заучить. А вот умение анализировать и думать в решении задачек подделать крайне сложно, как мне кажется. Разве что если человек перерешает все задачи, которые есть хотя бы с LeetCode. И то к тому моменту он уже сможет выделить общие паттерны решений и решать любые подобные задачи без проблем.
ИМХО, проверку на знание языка на собеседовании есть смысл только в IDE давать, потому что на работе-то всё равно все пользуются IDE'шками.
Дали несложную задачку на элементарное умение находить оптимальное решение (уровень Easy LeetCode думаю, т.к. и должность не столь высокая, и фронт-энд разработчику не так остро нужны алгоритмы как другим), но так как я очень разнервинался (первое собеседование в жизни!), с фразой «Не будем привязываться к языку» накатал решение на доске на суржике из Python, псевдокода и JS.
Потому что компилировать код в голове, предвидеть ошибки на тот момент я ещё не умел, анализировать задачу я ещё не умел.
В общем задачки были очень простые, но тоже, со своеобразным подвохом, нужно было подумать.
Это я к чему веду? Я не считаю нужным при решении задач на белой доске привязываться к конкретной технологии/языку. Мы все пользуемся IDE, которая решает большое количество рутинных задач за нас, наша задача остаётся — думать и анализировать возможное решение поставленной задачи.
Кроме SQL конечно, ИМХО, SQL это такой язык, который нужно в голове уметь «запускать», он слишком простой, чтобы не уметь этого делать.
Уровень понимания языка — открывайте GitHub интервьируемого. Теорию можно заучить. А вот умение анализировать и думать в решении задачек подделать крайне сложно, как мне кажется. Разве что если человек перерешает все задачи, которые есть хотя бы с LeetCode. И то к тому моменту он уже сможет выделить общие паттерны решений и решать любые подобные задачи без проблем.
ИМХО, проверку на знание языка на собеседовании есть смысл только в IDE давать, потому что на работе-то всё равно все пользуются IDE'шками.
Плюсуюсь к вопросу @samsdemon. Я вот тоже типа там и техлид, и тимлид (небольшая команда у нас). Но в нашей работе алгоритмирование нужно на весьма простом уровне, ибо интернет-магазин. Если же нам все-таки нужно будет использовать какой-то сложный алгоритм, то за изобретение велосипеда никто не заплатит, ибо в большинстве случаев есть реализации и они в общем случае лучше, чем был бы наш собственный велосипед. Там больше других сложностей — миграция данных между системами, интеграция различных API (в основном для маркетинга, но и не только), продумывание архитектуры микросервисов (границы, взаимодействие, мониторинг, авторизация/аутентификация, и т.п.). И всё это требует определенного опыта и понимания проблемы. Но всё это, как я понимаю, абсолютно иррелевантно для всяких там MS, Google и подобных им. И у меня, в связи с этим, вопрос, неужели вот прям в каждодневной работе программисты данных корпораций пишут всякие вот такие вещи интересные? Или на самом деле собеседование — ширма, а за ней жесткие рамки и минимум креатива? Как оно по ту сторону собеседования, отражает ли оно вашу каждодневную работу?
у меня коллега вообще сторонник теории, что чем изощреннее собеседование — тем попсовее потом будет работа. Он рассказывал истории из своей карьеры, как его собеседовали на кеши процессоров, а потом посадили .bat файлы писать для внутренней самописной билдсистемы.
Для меня лично: каждодневную — нет. Регулярно сталкиваюсь? Да.
Ну то есть доопределять задачи (а то и вообще ставить их самому по запаху) — ежедневная по сути работа.
Писать нетривиальные алгоритмы — раз в месяц или реже.
Читать и понимать натривиальные алгоритмы — раз в месяц или чаще.
Искать баги в нетривиальных местах — раз в месяц или чаще.
Находить баги в нетривиальных местах — раз или два в квартал.
Ну то есть доопределять задачи (а то и вообще ставить их самому по запаху) — ежедневная по сути работа.
Писать нетривиальные алгоритмы — раз в месяц или реже.
Читать и понимать натривиальные алгоритмы — раз в месяц или чаще.
Искать баги в нетривиальных местах — раз в месяц или чаще.
Находить баги в нетривиальных местах — раз или два в квартал.
Более или менее это бывает и в моей сфере… Но дело в том, что если что-то делаешь один раз, то лично у меня это так — сделал и забыл. То есть если через месяц меня спросят о деталях, то так вот навскидку и не вспомню — ибо уже нахожусь в другом контексте.
Вот, например, я поднимал для внутренних целей (не для продакшна) K8s кластер. Разобрался, сделал, забыл. Сейчас понимаю только в общих чертах. А ведь кто-то может уцепиться за строчку в CV, и начать долбать по тонкостям тюнинга K8s, а я это делал всего один раз в жизни — естественно, что на многие вопросы сходу не отвечу. Со стороны человека, который этим занимается, возможно, каждый день, конечно же это будет выглядеть несоответствием слов и дела.
И вот мне видится, что на собеседованиях надо давать задания близкие если не по теме, то по духу к тому, что будет каждодневной работой. А то, что нужно делать раз в месяц или реже, может быть лишь бонусной задачей, возможно, при приёме влияющей лишь на размер начальной компенсации. ИМХО, конечно.
Вот, например, я поднимал для внутренних целей (не для продакшна) K8s кластер. Разобрался, сделал, забыл. Сейчас понимаю только в общих чертах. А ведь кто-то может уцепиться за строчку в CV, и начать долбать по тонкостям тюнинга K8s, а я это делал всего один раз в жизни — естественно, что на многие вопросы сходу не отвечу. Со стороны человека, который этим занимается, возможно, каждый день, конечно же это будет выглядеть несоответствием слов и дела.
И вот мне видится, что на собеседованиях надо давать задания близкие если не по теме, то по духу к тому, что будет каждодневной работой. А то, что нужно делать раз в месяц или реже, может быть лишь бонусной задачей, возможно, при приёме влияющей лишь на размер начальной компенсации. ИМХО, конечно.
Есть вещи общие (прочел доку — сделал), есть вещи тонкие, когда понимание как устроено меняет с «долбал год» на «сделал за неделю».
Строчка в резюме… Может не добавлять туда такие вещи не в раздел «знаю» а в раздел «сталкивался»? Просто чтоб ставить соответствующие ожидания.
Я считаю что если человек сталкивался, решил, и забыл — это нормально.
Если он каждый день с ними и так и не понял (как выше про SQL и DBA с «огромным» опытом) — это уже звоночек…
Строчка в резюме… Может не добавлять туда такие вещи не в раздел «знаю» а в раздел «сталкивался»? Просто чтоб ставить соответствующие ожидания.
Я считаю что если человек сталкивался, решил, и забыл — это нормально.
Если он каждый день с ними и так и не понял (как выше про SQL и DBA с «огромным» опытом) — это уже звоночек…
Как минимум в Google (а вообще вроде во все +-крупные компании) один из этапов собеседования — system design. Именно про «понять, сколько нужно нод», «нарезать таблички», «спроектировать микросервисы», «задуматься о выходе из строя нод» и тд.
Disclaimer: личный опыт нерепрезентативен
Насчет же алгоритмов в повседневной жизни — до какого-то уровня они нужны, чтобы понимать, где использовать TreeMap, а где HashMap. Навык ДП очень сильно помогает выражать свои мысли в виде алгоритма даже в тех задачах, где не ДП. Ну и раз в сто лет все же нужно что-то реализовать.
Но задачи, такие, как в статье, оценивают и другие навыки, которые уже нужны каждый день. Навык уточнения требований, навык написания несложного кода, навык устного общения на английском, в конце концов.
Disclaimer: личный опыт нерепрезентативен
Насчет же алгоритмов в повседневной жизни — до какого-то уровня они нужны, чтобы понимать, где использовать TreeMap, а где HashMap. Навык ДП очень сильно помогает выражать свои мысли в виде алгоритма даже в тех задачах, где не ДП. Ну и раз в сто лет все же нужно что-то реализовать.
Но задачи, такие, как в статье, оценивают и другие навыки, которые уже нужны каждый день. Навык уточнения требований, навык написания несложного кода, навык устного общения на английском, в конце концов.
Сначала на интервью все такое оптимизированное а потом гмаил по пол часа открывается. Как так?
Сначала на интервью все такое оптимизированное а потом гмаил по пол часа открывается. Как так?
UFO just landed and posted this here
UFO just landed and posted this here
Один я при прочтении задачи подумал, что решал бы её с другого конца?
Я бы не воодил список синонимов (так как живой язык — дело сложное, и синонимы в списки никак не укладываются). Я бы решал от того, что выбирает пользователь при запросе.
То есть, первым пользователям показываем поисковую выдачу по текущему простомы алгоритму. Смотрим, что из этой выдачи он выбирает. Если при разных запросах выбираются одинаковые ссылки — значит, запросы синонимичные. С поправками, коррекциями и расстояниями Левенштейна.
Я бы не воодил список синонимов (так как живой язык — дело сложное, и синонимы в списки никак не укладываются). Я бы решал от того, что выбирает пользователь при запросе.
То есть, первым пользователям показываем поисковую выдачу по текущему простомы алгоритму. Смотрим, что из этой выдачи он выбирает. Если при разных запросах выбираются одинаковые ссылки — значит, запросы синонимичные. С поправками, коррекциями и расстояниями Левенштейна.
Мне кажется, что для серьезной позиции и задачи поиска синонимов нужно какой-то кардинально другой подход к базовому алгоритму. Так как в реальности задача будет постоянно усложняться. И бог его знает как. Добавить ML алгоритмы. Учесть ошибки ввода и т.д. И в результате будет во первых сплошной if… else. Во вторых код будут писать скорее всего разные разработчики, и возможно одновременно. То есть будет постоянная конкуренция за файл с основным циклом. Третье, возможно при большом словаре нужно буде делать горизонтальное масштабирование. Четвертое, задача добавления данных в словари — это задача отличная от задачи поиска. Ее не должно быть в теле основного алгоритма. Так как словарь формируется отдельно.
И это все на мой взгляд более важно и критично, чем сам алгоритм в реальных задачах. То есть умение абстрагироваться от реализации и умение учитывать возможность масштабирования задачи, более важное умения для опытного программиста работающего в большом коллективе и разрабатывающие сложные системы с большими данными. Даже если линейная сложность, и все делать так, как спрашивают, при миллионных записей, рано или поздно на одном ядре все будет тормозить.
И это все на мой взгляд более важно и критично, чем сам алгоритм в реальных задачах. То есть умение абстрагироваться от реализации и умение учитывать возможность масштабирования задачи, более важное умения для опытного программиста работающего в большом коллективе и разрабатывающие сложные системы с большими данными. Даже если линейная сложность, и все делать так, как спрашивают, при миллионных записей, рано или поздно на одном ядре все будет тормозить.
Проблема с задачами такого рода, что всегда человек может предложить сложное решение. Это очевидно: сложная задача с разными вариантами решения, значит можно накрутить пару-тройку оптимизацирующих алгоритмов. И не дай бог вставить сюда метод, который интервьюер не знает. Это крайне негативно скажется на результате собеседования.
Забавное. Заметил, что DisjointSet в статье на самом деле написан неправильно.
В этой структуре есть две эвристики — сжатие путей и подвешивание по рангу/весу. Первая — что при поиске корня мы записываем корень в предки всех, по кому прошли — в коде есть. А вторая — что мы выбираем, какой корень записать в parent другому при слиянии по рангу, или по весу множеств, или хотя бы случайно(это тоже работает, хотя сложнее доказывается) — отсутствует. То есть среднее время на операцию в написанной в статье структуре — O(logn), а вовсе не O(a(n)).
В этой структуре есть две эвристики — сжатие путей и подвешивание по рангу/весу. Первая — что при поиске корня мы записываем корень в предки всех, по кому прошли — в коде есть. А вторая — что мы выбираем, какой корень записать в parent другому при слиянии по рангу, или по весу множеств, или хотя бы случайно(это тоже работает, хотя сложнее доказывается) — отсутствует. То есть среднее время на операцию в написанной в статье структуре — O(logn), а вовсе не O(a(n)).
Sign up to leave a comment.
Разбор задачи с собеседования в Google: синонимичные запросы