Yandex.Interview

Довольно простая задача, которую по крайней мере в 2020 году

на интервью в Apple. Представьте, что вы плаваете в пруду на лодке с тяжелым валуном. Если сбросить его за борт, как изменится уровень воды?

Верно! Валун на дне водоема будет вытеснять меньше воды, чем валун в лодке. В первом случае он вытеснит количество воды, равное его объему, а во втором — равное его весу. Ответ мы нашли

Эту задачу тоже приписывают рекрутерам Apple. У вас две кружки горячего кофе и две небольших чашки холодного молока. В одну кружку кофе вы наливаете молоко сразу, затем ждете около 5 минут и наливаете молоко во вторую. В какой из кружек в этот момент температура будет выше?

В интернете есть разные варианты этой задачи, но во всех условия определены неявно. Вероятно, это намеренно — чтобы проверить не столько умение считать, сколько логику и смекалку.

В первой (куда добавили молоко сразу).

Такой вариант возможен (например, к нему приходят в

), однако мы полагаем, что в условиях задачи данных слишком мало для однозначного ответа, а вот неизвестных — много. Подробный разбор есть

Во второй (добавили молоко спустя 5 минут).

Такой вариант тоже реален при определенных условиях, но из доступных в задаче данных однозначно он не следует. Подробный разбор —

Однозначного ответа нет.

Изучив несколько мнений (

), мы склоняемся к этому варианту. Если кратко, нагрев и остывание подчиняются закону Ньютона-Рихмана, а в нем много переменных, часть которых можно установить только экспериментальным путем. Важна температура среды, она может кардинальным образом влиять на измерения. Отличный разбор задачи —

Вопрос задавали на собеседованиях в LinkedIn (сейчас эта соцсеть принадлежит Microsoft). Некоторые говорят, что его задавали и в Яндексе:

В комнате, где вы находитесь, есть три выключателя, которые связаны с тремя лампами накаливания в соседней комнате, но как связаны — неизвестно. Это и предстоит выяснить. Вы можете совершать разные манипуляции с выключателями, но зайти в соседнюю комнату можно только один раз, а вернуться к выключателям уже не получится. Что делать?

Подсказка: нужно найти дополнительный параметр кроме состояния «вкл. / выкл.». Варианты ответов не предлагаем, поверим вам на слово, если вы решили задачку.

Я решил. Хочу проверить ответ.

Первый выключатель не трогайте. Второй включите на 5−10 минут и выключите. Наконец, включите третий рубильник. Теперь можно идти во вторую комнату. Последний выключатель относится к лампе, которая горит сейчас. Второй — к самой теплой лампочке из двух. Первый — к оставшейся.

Не решил. Скажите, как правильно.

Условия этой, тоже популярной задачи мы адаптировали для российских читателей. Допустим, вам выдали зарплату десятирублевыми монетами, и стопка этих монет по высоте равна

зданию в России — Лахта-центру в Санкт-Петербурге (то есть примерно 500 метрам). Поместились бы эти монеты в вашей комнате дома?

Только если вы живете

под лестницей, как Гарри Поттер. В других случаях — должна поместиться.

По крайней мере, должны! Минимальная высота потолков в РФ — 2,5 м. Значит, нужно уместить в квартире с такими потолками всего 500/2,5 стопок, или 200 стопок. Диаметр монеты — 2,2 см, или 0,022 метра. Чтобы поставить все 200 стопок, нужна площадь около 4,5 метра. По СНиПам РФ, жилая комната не может быть менее 8 метров квадратных.

50 грузовиков стоят на стоянке. Бензобак каждого из них полностью заправлен — его хватит, чтобы проехать 100 км. На какое максимальное расстояние от стоянки можно уехать, используя все грузовики? Заранее скажем, что взять их на буксир не получится — грузовики просто не смогут сдвинуться с места под такой нагрузкой.

Задачу задавали на собеседованиях Google еще в 2010-х, она опубликована в книге «Are You Smart Enough to Work at Google?».

100 км — максимум.

Самый простой ответ, но недостаточно выигрышный. С другой стороны, это лучше, чем ничего.

Можно уехать на 350 км.

Ближе к истине, но можно больше.

Почти 450 км.

Логика простая: грузовики выезжают одновременно, но мы дозаправляем их в пути. После 2 пройденных км во всех грузовиках будет оставаться бензин на 98 км. Значит, с помощью одного грузовика можно заполнить бак у оставшихся 49 до максимума и проехать еще 100/49 — примерно 2,04 км. И так далее. Более элегантно задача

через гармонический ряд.

Если переливать бензин из бака в бак, максимум — примерно 449,9 км. Но в книге «Are You Smart Enough to Work at Google?» приводят еще

— при определенных рассуждениях можно проехать 1500 км, если загрузить (особые) грузовики баками с бензином. Но мы этот ответ не засчитаем, потому что в условиях обозначили, что грузовики у нас не очень мощные.

Есть 2 маленькие сковородки и 3 сырые котлеты. На каждую сковороду помещается только одна котлета. Котлеты нужно обжаривать с каждой из двух сторон по 1 минуте. Сколько времени нужно, чтобы пожарить все котлеты?

Ответ напрашивается сам собой, но он не верный.

Именно так! Сначала нужно обжарить 2 котлеты с одной стороны, потом перевернуть одну из них, а вторую отложить и положить вместо нее третью. Через 2 минуты первая будет готова, а две оставшиеся — готовы наполовину. Нужна еще минута, чтобы их обжарить. Итого — 3 минуты.

Это не реалистично)

Любимая задачка Илона Маска, которую он

кандидатам в SpaceX. Представьте, что вы стоите на поверхности Земли. Вы проходите одну милю на Юг, одну милю на Запад и одну милю на Север. В конце пути вы оказываетесь ровно в той точке, откуда начинали движение. Где вы находитесь?

На Северном полюсе.

Самый логичный вариант: на Северном полюсе такая траектория превратится в треугольник. Получив ответ, Маск обычно спрашивал: где еще это возможно? Это уже сложнее. Верный ответ: возле Южного полюса, на одну милю севернее параллели, длина которой равна одной миле! Подробное решение —

В бермудском треугольнике.

Доподлинно это неизвестно.

Нет, в ту же точку на экваторе вы не придете.

Простая логическая задача звучала

при приеме в финансовую компанию T3 Trading Group. Ровно в полдень ученый помещает бактерию в чашку Петри. Каждую минуту бактерия делится надвое. В 13:00 чашка заполнена бактериями до краев. Сколько времени было, когда чашка была заполнена наполовину?

Это была плохая попытка.

Да, все просто. Если каждую минуту число бактерий удваивается, значит ровно минуту назад их было в два раза меньше.

Нет правильного ответа.

В коробке 12 одинаковых черных носков и 12 одинаковых белых. Если взять 2 носка наугад, какова вероятность, что выпадет пара? Вопрос можно было

на собеседованиях в индийском подразделении Amazon.

50% — либо совпадут, либо нет.

Этот ответ дают чаще всего, но он не совсем корректный.

100% — всегда будем вытягивать пару.

Попробуйте провести эксперимент дома)

47,8% — шанс, что выпадет пара.

Как ни странно, да. Вероятность, что первый выбранный носок будет черным = 12 из 24, то есть 50%. Но когда дело доходит до второго носка, шансы, что он будет черным, меняются до 11 из 23. Соответственно, шанс подобрать пару черных носков будет произведением этих вероятностей. Для белой пары то же самое. Теперь складываем вероятности и получаем 47,8%. Решение есть

Закончим простым вопросом. На циферблате часов — час ночи, за окном идет ливень. Будет ли светить солнце через 72 часа?

Да нет, вполне хватает)

Если и будет, то на другой стороне Земли.

Точно не будет.

Конечно. 72 часа — это ровно трое суток, значит, снова будет час ночи (а по ночам нет солнца).

Возможно, вы просто гуманитарий.

Это не преступление!

Вы способны мыслить логически.

Значит, можете стать программистом и укрепить знания. Почитайте

о востребованных языках программирования, например.

Кажется, вы уже работаете в IT.

Если нет, то точно могли бы!

Яндекс. Интервью

Подготовка к очному собеседованию в Яндекс Дзене по направлению “Стажёр во frontend разработку”.

Тестовая задача вакансии

Дана доска размером M × N клеток. Клетка может находиться в одном из двух состояний: 1 — живая, 0 — мёртвая. Каждая клетка взаимодействует с восемью соседями. Правила таковы:

  • Живая клетка, у которой меньше двух живых соседей, погибает.
  • Живая клетка, у которой два или три живых соседа, выживает.
  • Живая клетка, у которой больше трёх живых соседей, погибает.
  • Мёртвая клетка, у которой три живых соседа, возрождается.

Напишите программу, которая будет:

  • случайным образом генерить стартовое состояние;
  • уметь получать его из файла (способ выбирается через параметры запуска в консоли);
  • каждую секунду выводить в консоль новое состояние доски.

Камни и украшения

Даны две строки строчных латинских символов: строка J и строка S. Символы, входящие в строку J, — «драгоценности», входящие в строку S — «камни». Нужно определить, какое количество символов из S одновременно являются «драгоценностями». Проще говоря, нужно проверить, какое количество символов из S входит в J.

Формат ввода

На двух первых строках входного файла содержатся две строки строчных латинских символов: строка J и строка S. Длина каждой не превосходит 100 символов.

Формат вывода

Выходной файл должен содержать единственное число — количество камней, являющихся драгоценностями.

Последовательно идущие единицы

Требуется найти в бинарном векторе самую длинную последовательность единиц и вывести её длину.

Желательно получить решение, работающее за линейное время и при этом проходящее по входному массиву только один раз.

Первая строка входного файла содержит одно число n, n ≤ 10000. Каждая из следующих n строк содержит ровно одно число — очередной элемент массива.

Выходной файл должен содержать единственное число — длину самой длинной последовательности единиц во входном массиве.

Пример

Дан упорядоченный по неубыванию массив целых 32-разрядных чисел. Требуется удалить из него все повторения.

Желательно получить решение, которое не считывает входной файл целиком в память, т.е., использует лишь константный объем памяти в процессе работы.

Первая строка входного файла содержит единственное число n, n ≤ 1000000.

На следующих n строк расположены числа — элементы массива, по одному на строку. Числа отсортированы по неубыванию.

Выходной файл должен содержать следующие в порядке возрастания уникальные элементы входного массива.

Пример 1

Дано целое число n. Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически (см. https://ru.wikipedia.org/wiki/Лексикографический_порядок).

В задаче используются только круглые скобки.

Желательно получить решение, которое работает за время, пропорциональное общему количеству правильных скобочных последовательностей в ответе, и при этом использует объём памяти, пропорциональный n.

Единственная строка входного файла содержит целое число n, 0 ≤ n ≤ 11

Выходной файл содержит сгенерированные правильные скобочные последовательности, упорядоченные лексикографически.

Даны две строки, состоящие из строчных латинских букв. Требуется определить, являются ли эти строки анаграммами, т. е. отличаются ли они только порядком следования символов.

Входной файл содержит две строки строчных латинских символов, каждая не длиннее 100 000 символов. Строки разделяются символом перевода строки.

Выходной файл должен содержать единицу, если строки являются анаграммами, и ноль в противном случае.

Даны k отсортированных в порядке неубывания массивов неотрицательных целых чисел, каждое из которых не превосходит 100. Требуется построить результат их слияния: отсортированный в порядке неубывания массив, содержащий все элементы исходных k массивов.

Длина каждого массива не превосходит 10 ⋅ k.

Постарайтесь, чтобы решение работало за время k ⋅ log(k) ⋅ n, если считать, что входные массивы имеют длину n.

Выходной файл должен содержать отсортированный в порядке неубывания массив, содержащий все элементы исходных массивов.

Даны две строки строчных латинских символов: строка J и строка S.
Символы, входящие в строку J, — «драгоценности», входящие в строку S — «камни».
Нужно определить, какое количество символов из S одновременно являются «драгоценностями».
Проще говоря, нужно проверить, какое количество символов из S входит в J.

Это разминочная задача, к которой мы размещаем готовые решения. Она очень простая и нужна для
того, чтобы вы могли познакомиться с нашей автоматической системой проверки решений.
Ввод и вывод осуществляется через файлы, либо через стандартные потоки ввода-вывода,
как вам удобнее.

Желательно получить решение, работающее за линейное время и при этом проходящее по входному
массиву только один раз.

Удаление дубликатов

Дан упорядоченный по неубыванию массив целых 32-разрядных чисел.
Требуется удалить из него все повторения.

Желательно получить решение, которое не считывает входной файл целиком в память, т.е.,
использует лишь константный объем памяти в процессе работы.

Генерация скобочных последовательностей

Дано целое число n. Требуется вывести все правильные скобочные последовательности длины
2 ⋅ n, упорядоченные лексикографически (см.
Лексикографический порядок).

Желательно получить решение, которое работает за время, пропорциональное общему
количеству правильных скобочных последовательностей в ответе, и при этом использует
объём памяти, пропорциональный n.

Больше половины сотрудников Яндекса вовсе не менеджеры по руководству общими вопросами и не операторы кофейных машин, а самые что ни на есть разработчики. Яндексу как воздух нужны front-end и back-end разработчики на С++, Python, Perl, Java, JavaScript. В основном в компании используются UNIX-плафтормы, но есть и разработка под Windows. Во многих сервисах формируются команды мобильной разработки, которые пишут под iOS, Android и Windows Phone.

Самая острая потребность в разработчиках C++. При этом все чаще появляются вакансии, связанные с машинным обучением, big data, распознаванием изображений и голоса, распределенными вычислениями. Далеко не всегда опыт работы с этими технологиями требуется обязательно. Есть команды разработчиков, которые занимаются исследовательскими задачами.

Вакансии открыты в Поиске, Браузере, Картах, Диске, Маркете. И в каждой из команд — своя специфика. Так, в Поиске и Картах больше востребовано знание алгоритмов, причем в Поиске уклон в сторону теории вероятностей и математической статистики, а в Картах — на графы. В Браузере больше сложных инженерных задач, поэтому требуются в первую очередь технические знания и в меньшей степени — алгоритмы.

Кого в Яндексе ждут больше всего?

  • Разработчик поиска С++
  • Разработчик Яндекс.Диска (С++ для Windows)
  • Разработчик качества поиска Яндекс.Картинок (С++)
  • Разработчик C ++ систем распознавания речи (мобильные платформы)
  • Разработчик С++ (компьютерное зрение)
  • Разработчик распределенной системы хранения и обработки данных С++

Как проходит собеседование

Ольга Пономарёва, старший рекрутер группы подбора разработчиков, Яндекс

Если вы успешно справилсьи с тестовыми задачами на company.yandex.ru, мы предложим созвониться по скайпу. По сути, это будет первое знакомство, где мы немного поговорим про выбранный язык программирования и предложим пару математических или алгоритмических задачек. Для первого разговора иногда достаточно 10–15 минут, и уж точно не больше часа.

Мы друг другу понравились? Отлично, тогда приглашаем в гости: у Яндекса есть десять офисов разработки в разных городах, вместе выберем подходящий. Обычно на собеседование приходят несколько разработчиков из разных команд: кому-то вы можете понравиться больше, и тогда он будет за вас биться. Правда, не сразу. Перед этим нужно написать код для решения предложенных задач. Чем быстрее напишешь — тем быстрее можно пойти домой :). Еще на встрече бывают задачки на сообразительность. В первую очередь нам интересен ход ваших мыслей, не обязательно решить всё. Если кандидат претендует на позицию senior-разработчика, поговорим об архитектуре систем.

Иногда для того, чтобы понять, «наш» человек или нет, требуется несколько встреч. Однако если вам нужно срочно определиться с местом работы — скажите нам об этом, что-нибудь придумаем.

Спрашивает Андрей Плахов, руководитель службы функциональности поиска в Яндексе

Дана функция на языке Python. Завершится ли когда-нибудь вызов dio()? Почему?

def dio():
   x = 1L
   while 1:
       for y in xrange(1, x):
           for z in xrange(1, y):
               if x*x == y*y + 12752041*z*z:
                   return “Found it”
       x = x + 1

Задача 2

Что делает эта программа на языке С++?

Спрашивает Кирилл Сюзев, руководитель группы разработки Яндекс. Картинок

Есть исходный код программы:

Что напечатается на экране и почему? Как изменится вывод, если заменить cout на cerr?

Задача 4

В программировании есть понятие LRU-кеша.

Если кратко: любой кеш содержит элементы, к которым мы хотим обращаться, но размер кеша ограничен. Поэтому надо принимать решение, какие элементы в кеше мы храним, какие нет.

LRU-кеш таким образом выбирает: если места под элементы больше нет, он выбрасывает элемент, к которому дольше всего не обращались, и вместо него кладет новый.

Задача — написать такой кеш в виде С++ класса/классов.

Мы ждем ваших задачек!

Задачки сами собой не решатся! Шли нам свои ответы, а айтишные компании будут дарить тебе бесплатные айфоны.

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
CompSch.com