(ч.2) Яндекс Школа iOS

27.07.2017

10 мин

Описание школы на сайте Яндекса.

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

В этот раз расскажу об испытаниях при поступлении в Яндекс школу мобильной разработки iOS. Речь пойдет о платформе Яндекс.Контест и о задачах, которые необходимо было решить. Также немного расскажу об очном собеседовании.

Для кого эта статья?

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

Письмо и первые проблемы

После заполнения анкеты я получил письмо, в котором было написано примерно следующее (я немного сократил):

Следующий шаг — решение первого тестового задания. Вот несколько вещей, которые полезно знать заранее:

• На решение дается 9 часов. Начать можете в любой момент до 26 февраля включительно;
• Первое тестовое задание проводится на платформе Яндекс.Контест. Чтобы познакомиться с системой, вы можете поучаствовать в пробном соревновании;
• Если вы сделали несколько попыток по задаче, засчитана будет лучшая из них. По каждой задаче вы можете сделать не более 100 попыток;
• Проверка осуществляется автоматически, и несоблюдение форматов приведёт к тому, что ваше решение не будет засчитано. Обязательно соблюдайте формат ввода и вывода, описанный в задаче;
• Все задачи — это задания по программированию. В них вам нужно отправить на проверку программу, решающую поставленную задачу; Для решения доступны следующие языки программирования: C, C++, PHP, Python 2, Python 3, C#, Java, Perl, Pascal, Go, Basic, Ruby, Rust, Delphi, Objective-C, Scala;
• Через несколько секунд после отправки решения вы увидите результат запуска вашей программы на наших секретных тестах. Если вы видите вердикт ОК, значит все тесты пройдены. Если вы видите какой-то другой вердикт, значит ваша программа неверно работает на некоторых тестах. Подробнее о вердиктах. Мы не показываем, на каком именно тесте ваша программа сработала неверно, но вы можете попробовать найти ошибку и отправить решение ещё раз;
• За каждый успешно пройденный тест вы получаете некоторое количество очков. Суммарное количество очков за решение отображается рядом с вердиктом проверки. Максимальное количество очков за задачу указано в скобках рядом с названием задачи в оглавлении.

После того как я неторопливо прочитал письмо и просмотрел все ссылки в нем, я решил ознакомиться с платформой через пробное соревнование. И тут я вовремя заметил, что письмо пришло в 22:46 и это было воскресенье 26 февраля.

В итоге у меня около часа на пробное соревнование и целая ночь впереди на настоящее. Хорошо, что на работе гибкий график.

Пробное соревнование, а зачем?

Все просто, в основном для того чтобы разобраться что Яндекс.Контест ожидает от вашего кода. Я планировал писать на Objective-C и мне потребовалось вспомнить как работают базовые функции ввода и вывода. А также, разобраться что код надо писать в main. Очевидно? Да, но в реальных проектах для iOS функция main создается автоматически и редко изменяется. А функцией scanf я наверное пользовался в последний раз лет 7 назад, когда учился.

Также в пробном соревновании можно посмотреть как выглядит текст задачи, ограничения по памяти и времени, формат ввода и вывода. Это все было в новинку для меня. Но сами задания очень простые, и даже может показаться, что после этого вы готовы решить что угодно.

Настоящее испытание

На волне успеха в пробном соревновании я добрался до настоящего. Первая задача сразу же вернула меня в реальность Яндекса. В целом предлагалось решить четыре задачи. К сожалению, условия я не записывал и прошло довольно много времени. К тому же я проходил соревнование на рабочем ноутбуке, а затем при увольнении просто удалил учетную запись вместе со всеми решениями. Также из-за переезда потерялась тетрадь, в которой были наброски решений. В связи с этим описание заданий может быть очень неточным.

На сколько я помню во всех задачах были одинаковые ограничения:

• Ограничение по памяти: 64 MB
• Ограничение по времени: 2.0 секунды

1. Простые числа.

На вход передается натуральное число n, 1 ≥ n ≥ 10⁶. Необходимо вывести n-ое простое число.

Поиск простого числа распространенная задача, но здесь были свои нюансы. Самый простой способ найти простое число — перебрать интервал и проверял делимость на первые простые числа 2, 3, 5, 7, 11 и тд. Но здесь на вход может быть передано огромное число и нужен более разумный подход.

Самое первое что я нашел — Решето Эратосфена. Готовых алгоритмов было достаточно Habrahabr или MAXimal. Но проблема в том, что непонятно какого размера нужно построить решето, чтобы в него попало n-ое простое.

Я продолжил поиск и со временем нашел решение на Habrahabr, правда опять на C++. Автор решения берет решето определенного размера, и затем увеличивает его если n-ое простое не попадает в него. Там же ему подсказывают, что есть примерная оценка интервала Гипотеза Римена.

В итоге задача сводилась к тому, чтобы немного изменить готовое решение и протестировать локально в Xcode. Я решил не тратить время и не переписывать его на Objective-C. На эту задачу ушло около 1.5 часов и она прошла тесты на платформе с первой попытки. Начало неплохое)

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

2. Преобразование строк

На вход передается строка. Необходимо ее трансформировать (сжать), а затем вывести. Например если вход: aaabb77daa8ccc, на выходе: 3a2b27d2a83c.

На мой взгляд это самое простое задание, я написал его на Objective-C. Позже узнал как все это называется на Wiki. Я снова обрадовался, решение прошло все тесты с первого раза. После этого я уже немного расслабился, да и было ближе к 3⁰⁰.

3. Крестики и нолики

Необходимо определить исход игры при идеальной игре каждого, если известен текущий расклад поля. Также известно, что было сделано 1, 2 или 3 хода. Одним ходом считать действие обоих игроков. На вход передается три строки с символами: X — крестик, O — нолик и # — пустая клетка. На выход нужно вывести: Won X — если победит крестик, Won O — если победит нолик или Draw — если ничья.

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

// TODO: Вернуться к этой задаче позже

Вернулся я уже ближе к 7 утра. Голова не работала, но я накидал примерные ситуации на Objective-C. Идея была в обработке шаблонных ситуаций. Например, если X в центре, а O не в диагональной клетке при идеальной игре X победит. Проверки на возможность создания ситуаций, в которых на следующем ходу можно победить (вилки). После нескольких попыток и исправлений я решил, что лучше сейчас уже не сделаю. В итоге я не набрал максимальный бал по этой задаче.

Возможно эту задачу можно решить используя минимакс или схожее дерево решений, но с ходу я не могу придумать как правильно взвешивать ситуации при идеальной игре каждого. Если кто-то знает, буду рад если поделитесь в комментариях.

4. Графы

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

Уже точно не помню лимиты на количество точек, ребер и индексов. Я почти уверен, что больше чем 10⁶.

Последний раз я работал с графами в 2012 году, когда занимался созданием приложения для проектирования квартир на ActionScript 3.0. После реализации, очень интересно было просто разбивать большие квартиры на множество комнат.

Для решения задачи я посмотрел как искать компоненты связности, нашел примеры реализации и применил их. Вроде ничего сложного. Для быстрого удаления ребер нужно просто использовать подходящие структуры данных. Я отправил решение на проверку и увидел примерно следующее: Time Limit: 2.056.

После этого я переписывал решение еще десятки раз. Я слабо знаю C++, да и в графах не силен. Почитал о структурах данных, пытался переписать разными способами. Потом я понял, что если количество удаляемых ребер равно количеству всех ребер, то количество компонент связности будет равно количеству точек!) Быстро добавил проверку и отправил. Получил примерно Time Limit: 2.049.

К этому моменту я уже потратил пару часов на решение этой задачи и скорее всего уже было 6 утра. Я понял, что пора возвращаться к крестикам и ноликам... В конце концов я набрал на этой задаче примерно 60–70% баллов. Я скопировал свой код, чтобы показать коллеге на работе.

Может показаться, что задача очень сложная. Но... меня ждал сюрприз. Коллега сказал, что в алгоритме все хорошо и особых проблем не видит. Хотя подметил, что совсем не обязательно выводить количество компонент связности после каждого удаления через printf. Особенно когда это может происходить по миллиону раз...

В целом задачи были не сложные. Вторая была очень простая. Первую и последнюю можно было решить даже если вы не знаете нужных алгоритмов. На просторах интернета хватает информации, все сводится к поиску и применению. Третья задача наверное была самой сложной для меня, к ней сложно найти почти готовое решение или даже идею решения. Ночью я измучился рисовать и разбирать большое количество ситуаций. Возможно днем я бы справился с ней быстрее. В целом я набрал максимальные баллы только по первым двум задачам. По двум остальным что-то около 60–70%, на сколько я помню. В итоге этого было достаточно, чтобы попасть на очное собеседование.

Очное собеседование

Наверное спустя неделю мне пришло письмо. Необходимо было выбрать время и прийти в офис компании Яндекс. К этому собеседованию я почти не готовился, только просмотрел еще раз онлайн задачи. Мне наивно казалось, что будет скорее организационная часть и возможно устные технические вопросы и может по этим же задачам.

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

Собеседование было разбито на две части: техническая и организационная. На каждую часть отводилось по 30 минут.

На технической части мне продиктовали задачу на преобразование строк. Сама задача была не сложная, но ее нужно было написать на существующем языке программирования (возможно ООП) на листке бумаги А4. После реализации меня попросили изменить решение без использования дополнительной памяти и определить сложность алгоритма. В целом задание мне показалось легким, я написал его на Objective-C.

В организационной части были различные вопросы об образовании, опыте разработки, желании обучаться в школе. Мне показалось, я как раз провалил эту часть. Дело в том, что у меня уже был хороший опыт и возникали сомнения в моей заинтересованности в стажировке после обучения. А основная цель, как я понимаю, привлечь и обучить будущих сотрудников.

Почти конец

В этой статье я описал лишь свои идеи решения задач. А где же код?! К сожалению, оригинальный код был утерян. Об этом я писал чуть выше. Но, я не поленился и решил еще раз все задачи на Swift. И уже собирался добавить решения в статью. И потом задумался, а какая разница как я решил эти задачи? Намного важнее как решите их вы, когда это потребуется!)

Поэтому я подготовил возможность повторить это испытание, любому кто захочет, на платформе Codewars. По ссылке я создал коллекцию из 4 испытаний под названием Yandex iOS School Entrance Exam для языка Swift. Все что вам нужно, зарегистрироваться (можно с Github аккаунта) и вы сможете решать эти задачи своим способом. Затем ваше решение должно пройти тесты, основанные на моем решении. Пишите, если будут проблемы. У меня пока желтый пояс по программированию.

Заключение

Какие выводы я сделал для себя?

• В Яндексе очень любят давать задачи на применение алгоритмов и структур данных. Не важно на каком языке вы пишите. Не важно какой у вас опыт. Нужно хорошо понимать как писать не только рабочий, но и оптимальный код. Могу порекомендовать статью: How to get started with algorithms to be a better developer.
• Вам необходимо знать как минимум один язык программирования (желательно ООП) на таком уровне, чтобы вы могли писать на нем почти с закрытыми глазами. Речь идет именно об языке и его стандартной библиотеке. Написание циклов, работа со строками, коллекциями, файлами, и тп. Это не включает знание конкретной платформы, инструментов и тп.
• В онлайн испытании важно не написать идеальный алгоритм своими руками, а уметь определить тип задачи и подобрать необходимые средства для реализации за определенное время. Думаю я бы не смог сдать столько задач если бы писал все на Objective-C и не знал бы основ C/C++.
• И самый простой вывод. К всему этому нужно готовиться. Мне кажется идеальных знаний просто не бывает. Тем более собеседования, соревнования и тп. — это всегда стресс.

Идеал — цель, которая всегда меняется. Нельзя останавливаться.

В следующей части

Я расскажу о самом обучении в школе, поделюсь впечатлением о домашних заданиях и лекциях. Было очень интересно) Скорее всего это будет последняя часть.

На этом пока все. И конечно, если статья была вам интересна, подписывайтесь в Twitter. С помощью подписки вы узнаете о следующей части.