Comments 37
Привет :)
Одна из наших служб называется "служба свеже-социального поиска". Название такое сложилось исторически: когда-то давно в ней разрабатывалась поисковая свежесть и некоторые продукты, связанные с соцсетями.
С тех пор служба сильно выросла и занимается много чем ещё, но новое подходящее название мы придумать не смогли. Поэтому так и оставили её службой свеже-социального поиска :)
Внутри этой службы есть группа разработки свеже-социального поиска (а как же иначе?), которой руководит Никита и в которой по-прежнему сосредоточена разработка именно поисковой свежести и связанных с ней продуктов.
О поисковой свежести я писал вот тут: https://habrahabr.ru/company/yandex/blog/329946/, а потом рассказывал вот тут: https://events.yandex.ru/lib/talks/4690/
те, кто владеет алгоритмами, всегда смогут перестроиться и быстро научиться новому.
А вот интересно, а есть на этот счет какие-нибудь исследования? Почему знание алгоритмов помогает быстро перестроится и научится новому, а знание, например, устройства финансовых рынков нет?
Мне кажется, что более-менее любое дополнительное знание способствует тому, что его носитель становится более восприимчив к новым идеям, быстрее учится и так далее, становится лучше, короче (впрочем, это мнение можно при желании оспорить).
В данном случае речь, конечно, не о каком-то магическом превосходстве знания алгоритмов над любыми другими знаниями. Тут намного более простая мысль: если вы разбираетесь в алгоритме, то сумеете относительно быстро его реализовать на более-менее любом употребимом языке программирования.
Если б у меня был выбор, решать за деньги или просто так, я бы выбрал деньги) Объясните, в чем смысл этого Блиц?
Я не настоящий сваршик, но отвечу. Очевидно, это чтобы сэкономить деньги: человекочасы рекрутеров. За участие в интервью, я почти уверен, Яндекс не платит. Вообще не знаю ни одной компании, где бы платили. Это же не тестовое задание, которое с натяжкой и иногда хотя бы теоретически можно где-то использовать. Интервью — это задачки-пазлы на 30-60 минут. Которые интервьювер и так умеет решать.
Со стороны претендентов на работу, этот Блиц — просто замена телефонному интервью. Кому-то это может быть просто приятнее, чем пытаться по телефону что-то объяснить рекрутеру.
С точки зрения участника может быть несколько мотивов.
- Это такое же олимпиадное соревнование, как и любое другое, и поэтому в нём просто будет интересно поучаствовать, попробовать свои силы, решить интересные задачи и научиться чему-то новому. Многие участвуют в подобного рода соревнованиях совершенно бесплатно и с большим удовольствием.
- Победители получают денежные призы, и это тоже может быть небесполезно.
- Это, действительно, способ избежать одного из этапов собеседования в Яндекс, заменив его процедурой более знакомой и приятной для многих, если сравнивать с традиционными интервью.
Ещё у этого соревнования есть особенность: задачи в нём некоторым образом связаны с теми задачами, которые приходится решать разработчикам Яндекса в повседневной жизни. Примеры таких связей мы постарались описать в статье. Это понимание может быть интересно и само по себе, и как способ понять, стоит ли пытаться устроиться на работу в Яндекс.
Не понятно какое значение принимает T_0. По определению T_k — это кол-во разных деревьев с числами
от 1 до k.
Попробуем провести рассуждение для конкретных значений N+1 и t.
Пусть N+1 = 3. Мы хотим найти T_{N+1} = T_{3}.
Ясно, что в корне любого дерева будет находиться некоторое число из множества 1,...,3.
Обозначим это число за t. Положим t=3.
Тогда в силу свойств дерева поиска левое поддерево содержит числа 1,..,3-1 = 1,..2.
А правое 3+1,… Но это больше N+1, поэтому правое поддерево — пустое.
Посмотрим на рисунок — все верно — для t=3, правое поддерево — пустое.
Количество различных возможных способов сформировать левое поддерево тогда равняется T_{2} = 2(это можно самому нарисовать),
а правое T_{3-3} = T_{0}. Но справа деревьев нет, значит T_{0} = 0.
Но тогда получается, что общее кол-во поддеревьев для t=3 = T_{2} * T_{0} = 2 * 0 = 0
Хотя по рисунку — их 2.
Формула работает, только если положить, что T_{0} = 1
Что касается T_0, то в сумме эта величина используется только при t=N или при t=0. В обоих случаях все элементы, кроме корня, попадают только в одно из поддеревьев. Значит, количество таких вариантов совпадает с количеством способов составить дерево поиска из N элементов. Поэтому, действительно, в этой задаче нужно положить T_0 = 1.
Цитата из статьи:
«Ведь нужно проверять фундаментальные знания»
Вы так в этом уверены? Кому именно нужно? Здесь всё же не кафедра университета и не олимпиадный кружок, предлагаю вспомнить, зачем вы вообще ищете человека. Правильно. Писать API, проектировать инфраструктуру, рисовать кнопки, чинить баги, понимать задачу из общения с бизнесом, делать продукт дороже и круче. И делать всё это в срок и за деньги.
Не думаю, что в команде нужно, чтобы все были шикарными алгоритмистами. Знание паттернов, умение писать «чистый» код и прокачанные softskills, как правило, более полезны в реальной работе.
Вы действительно используете свои знания и умения разрабатывать и оценивать алгоритмы на работе. Но на работе у вас для этого есть много времени в спокойной, способствующей обстановке. У вас есть доступ к исследованиям и литературе. У вас есть коллеги, в конце концов, команда. Если у вас этого ничего нет, то это плохая работа. На собеседовании у вас нет ничего этого, а есть только экзамен, нервы и череда каких-то перцев, которых вы первый раз в жизни видите. И это противоположность работе.
Решения алгоритмических задачек на собеседовании не проверяют ваши фундаментальные, нефундаментальные или любые другие знания. Они проверяют одну вещь: скилл решать задачки на собеседовании в стрессовой ситуации. Это отдельный скилл, который после приема на работу больше не нужен. Поэтому, кстати, его надо поддерживать походами на собеседования во время работы.
Решения алгоритмических задачек на собеседовании не проверяют ваши фундаментальные, нефундаментальные или любые другие знания. Они проверяют одну вещь: скилл решать задачки на собеседовании в стрессовой ситуации
Решения алгоритмических задачек на собеседовании проверяют ваши фундаментальные знания.
Далее должна следовать обязательная ремарка про людей, пишущих поисковое ядро Google / Yandex.
Если внимательно прочитать статью, то видно, что данный блиц направлен как раз таки на разработчиков поиска и им подобных:
Хотя для оценки раундов и применяется система ACM, в отличие от спортивного программирования все задания максимально приближены к тем, которые постоянно решают в продакшене Поиска.
Всё упирается в то, что вопросы "Покажите свои коммиты в хром или в какой-нибудь поисковик" спрашивать не имеет смысла. Человек сам об этом расскажет, если такое было.
не олимпиадный кружок
Яндекс больше "олимпиадный кружок", чем какой-нибудь Люксофт или Епам. Мы сейчас не говорим, о том, что Епам богаче Я. Или что Варгейминг богаче Я. Да, богаче. Но разговор не об этом.
Имплементирован простой обход графа в глубину.
При попадании в вершину никакой проверки на наличие других входящих ребер нет.
Получается в первом примере задача решена неправильно.
Буду жутко благодарен за развернутый ответ, особенно если я не прав.
Далее мы решаем исходную задачу, где, по завершении обработки вершины внутри функции DFS, добавляем ее в конец вектора с результатом. Так мы гарантируем, что от добавленной на текущем шаге вершины будут зависеть только вершины, добавленные в этот вектор ранее, связей с вершинами, добавленными после текущей, не будет. Именно так и работает алгоритм топологической сортировки. В самом конце мы выводим этот вектор в обратном порядке и получаем ответ задачи.
Это свойство DFS. Он всегда сначала выйдет из вершины, от которой ничего не зависит. В противном слечае, ДФС бы зашел в зависимую вершину и вышел из нее раньше, чем из текущей. Поэтому достаточно выводить в ответ вершины по мере выхода из них (будет развернутая топологическая сортировка).
Пермутации бинарных деревьев обычно интересны в двух состояниях — максимально сбалансированным и максимально несбалансированном, даже не знаю, зачем могут потребоваться остальные.
Яндекс.Блиц. Почему и какие алгоритмические задачи нужно уметь решать, работая в поиске