company_banner

Как мы провели первый набор в школу Ozon Go: этапы, задачи, их решения и запись демо-дня

    В мае стартовал первый набор школы Ozon Go, за три недели мы получили почти 5 тысяч заявок, ответили на несколько тысяч вопросов, провели 118 собеседований, один онлайн-митап и отловили один баг в задании. Подробности под катом.


    Как проходил отбор


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


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


    Поскольку заявок и решений было много, критерии отбора пришлось сделать строгими. Мы приглашали на собеседование, оценив резюме, решения и присланный код. Кроме того, мы обращали внимание на количество языков, которые использовались для решения задач. Опыт работы важен, две компании и работа в e-commerce — это плюс. Поскольку для нас важно, чтобы после окончания обучения специалист остался в команде Ozon, важным фактором была готовность переехать, если разработчик живет не в Москве и области — а рассматривали мы заявки со всей России, и в итоге пригласили ребят из 9 городов.Поскольку успешным выпускникам мы предложим присоединиться к команде Ozon — и хотелось бы, чтобы таких было 100%, на третьем этапе мы проводили традиционное HR-собеседование.


    И уже тех, кто успешно справился с задачами, прошел собеседование, подтвердил готовность учиться, прислал все необходимые документы, мы пригласили стать студентами школы Ozon Go.


    И немного цифр


    4730 заявок
    2220 разработчиков выполнили тестовые задания
    930 выполнили 4 и более задач
    118 мы пригласили на собеседование
    41 разработчик стал студентом Ozon Go
    Наши студенты живут в 9 городах: Москве, Санкт-Петербурге, Перми, Краснодаре, Пензе, Челябинске, Екатеринбурге, Уфе, Брянске.


    Задачи и их решения


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


    Задача А


    На вход подается большое кол-во целых чисел, все числа кроме одного имеют пару. Найдите единственное непарное число. Эта задача задумывалась как разминка для решения контеста. Существует несколько вариантов ее решения разной оптимальности, как “в лоб” с помощью стандартных средств любого языка программирования, так и более творческие варианты.


    Решения


    Хешмап с встречаемостью значений


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


    Далее пройти по мапе и найти то число, которое встретилось 1 раз.


    Использовать “четность” встречаемости


    Можно обратить внимание, что каждое значение, кроме единственного, встречается 2 раза. Как можно использовать этот факт? Предположим, что у нас есть некоторая операция, которая будучи примененная 2 раза с одним и тем же операндом отменяет сама себя. Аналогично операции NOT для булевых значений. Возьмем изначально значение true, применим к нему операцию NOT — получим false. Применив ту же операцию еще раз мы вернем изначальное значение true.


    Существует ли аналогичная операция, которая может принимать 2 операнда целых числа? Например, NOT (инверсия) по маске — второму операнду. Тогда применив ее с одной и той же маской дважды мы должны получить исходное значение.


    Это потребует проход по массиву сложность O(N), затраты памяти — O(1).


    Пример кода (импорты опущены):


    func main() {
        scanner := bufio.NewScanner(os.Stdin)
    
        var x int
    
        for scanner.Scan() {
            txt := scanner.Text()
            n, err := strconv.Atoi(txt)
            if err != nil {
                fmt.Fprintf(os.Stderr, "Error parsing number: '%v', err: %v\n", txt, err)
                continue
            }
            x ^= n
    
        }
    
        if err := scanner.Err(); err != nil {
            fmt.Fprintf(os.Stderr, "Error: %v:", err)
        }
    
        res := int(0 ^ x)
    
        fmt.Printf("%v\n", res)
    
    }

    Задача B


    Имеется 2 таблицы с тегами и товарами, а также таблица уникальных связок товар-тег. Необходимо найти товар, имеющий все теги. Так мы проверяли владение SQL, группировки и подзапросы.


    Решение


    Один из вариантов решения — подсчитать количество тегов на каждом товаре и проверить для каких товаров количество будет равно количеству тегов.


    SELECT g.* 
    FROM goods g 
    LEFT JOIN goods_tags  gt ON g.id=gt.goods_id 
    GROUP BY gt.goods_id 
    HAVING count(gt.tag_id) = (SELECT count(id) FROM tags);

    Задача F


    Ограничение времени 1.5 секунд (ранее была 1 секунда)
    Ограничение памяти 64Mb
    Дано целое положительное число "target". Также дана последовательность из целых положительных чисел. Необходимо записать в выходной файл "1", если в последовательности есть два числа сумма, которых равна значению "target" или "0" если таких нет.


    Ввод input.txt
    Вывод output.txt
    Формат ввода
    5
    1 7 3 4 7 9


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


    Примечания: Все числа, используемые в задаче, находятся в диапазоне 0 < N < 999999999
    Название входной файл: input.txt
    Название выходной файл: output.txt


    1 секунда оказалась жёстким ограничением, поэтому участникам советовали решать на C# или C++, хотя можно было выбрать любой другой язык программирования. Судя по комментариям участников сложнее всего решалось на PHP и Python.


    Решение


    Тесты к задаче были разбиты на 3 уровня сложности. Первые несколько тестов можно было пройти прямым перебором (сложность O(n2)), главное было не запутаться в решении. Так же были несколько тестов на граничные кейсы.


    Следующий набор тестов проверял знание более оптимального решения. Одним из правильных решений было отсортировать массив входных данных и затем начать поиск любым известным алгоритмом (варианты можно посмотреть тут https://web.stanford.edu/class/cs9/sample_probs/TwoSum.pdf).


    Последние тесты можно было пройти с еще одной оптимизацией. Необходимо было считать входные данные почисельно и пропускать те числа, которые больше либо равны числу target. Сам тест был построен таким образом, что почти всё отведённое время уходило на чтение файла.


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


    Задача D


    Даны два неотрицательных числа A и B (числа могут содержать до 1000 цифр). Вам нужно вычислить их сумму. Тут проверяется умение работать с стандартной библиотекой вывода.


    Формат ввода
    Первая строка ввода содержит числа A и B, разделенные пробелом
    Формат вывода
    Результат сложения двух чисел нужно вывести на отдельной строке.


    Подход к решению


    Решение можно разбить на 3 этапа:


    1. Прочитать входные данные


      Тут проверяется умения работы с стандартной библиотекой ввода, сам по себе шаг простой и не должен вызвать трудностей


    2. Произвести сложение


      Тут есть 2 возможных варианта решения:


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


      2.2. Реализовать сложение самому(как в школе — в столбик). Этот вариант тоже приемлемый, как минимум потому что не в каждом ЯП есть встроенная поддержка работы с большими числами. Так же тут проверяется что человек умеет работать с краевыми случаями (например числа с разным количеством цифр)


    3. Вывести результат



    Задача E


    Необходимо написать функцию func Merge2Channels(f func(int) int, in1 <-chan int, in2 <- chan int, out chan<- int, n int) в package main.


    Описание ее работы:
    n раз сделать следующее
    прочитать по одному числу из каждого из двух каналов in1 и in2, назовем их x1 и x2.
    вычислить f(x1) + f(x2)
    записать полученное значение в out
    Функция Merge2Channels должна быть неблокирующей, сразу возвращая управление.
    Функция f может работать долгое время, ожидая чего-либо или производя вычисления.


    Подход к решению


    Возможное решение
    В цикле:


    a1 := <-in1
    b1 := f(a1)
    a2 := <-in2
    b2 := f(a)
    c := b1 + b2
    out <- c

    Недостаток


    Последовательно ожидаются:


    • чтение из канала 1
    • вычисление функции
    • чтение из канала 2
    • вычисление функции

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


    Правильное решение


    Будем на каждое чтение создавать по 2 горутины, каждая из которых:


    • читает из своего канала
    • вычисляет значение функции
    • пишет его в канал

    После чего будем их параллельно запускать:


    go func() {
      value1 := <-in1
      convertedValue1 := f(value1)
      done1 <- convertedValue1
    }()
    
    go func() {
      value2 := <-in2
      convertedValue2 := f(value2)
      done2 <- convertedValue2
    }()
    
    convertedValue1 := <-done1
    convertedValue2 := <-done2
    
    out <- convertedValue1 + convertedValue2
    
    i++
    

    Язык Go обладает достаточно простым синтаксисом, многие возможности имеющиеся в других языках программирования (обобщенные типы, исключения, наследование) отсутствуют. Однако, в сам язык встроены очень удобные и простые средства параллелизма (горутины, каналы). Задача предполагала начальное владение этими средствами, чтобы ускорить вычисление функции. Мотивировка: функция — запрос на удаленный сервер, долгая работа — сетевые задержки.


    Примеры решения участников


    Номер раз


    package main
    
    func Merge2Channels(f func (int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {
        f1 := make(chan int)
        f2 := make(chan int)
    
        calcF := func(in <-chan int, fo chan<- int) {
            for i := 0; i < n; i++ {
                fo <- f(<- in)
            }
    
        }
    
        go calcF(in1, f1)
        go calcF(in2, f2)
    
        go func() {
            for i := 0; i < n; i++ {
                out <- (<- f1) + (<- f2)
            }
        }()
    }
    

    Номер два


    package main
    
    func Merge2Channels(f func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {
        line := make(chan int, n)
        out2 := make(chan int, n)
        go func() {
            for i := 0; i < n; i++ {
                var count = i
                var x1 = <-in1
                var x2 = <-in2
                go func() {
                    var result = f(x1) + f(x2)
                    out2 <- result
                    line <- count
                }()
            }
        }()
        go func() {
            answer := make(map[int]int)
            for i := 0; i < n; i++ {
                var xL = <-line
                var xO = <-out2
                answer[xL] = xO
            }
            for i := 0; i < n; i++ {
                out <- answer[i]
            }
        }()
    }

    Что пошло не так


    Мы допустили в задании Е сразу несколько ошибок. Go был не заложен в платформу Яндекс.Контест — по нашей просьбе туда добавили специальный компилятор Make. В задание был заложен один чекер-алгоритм проверки решения, для идеального сценария проверки решений нужно несколько чекеров и дополнительных настроек.


    Условия были недостаточно подробными, поэтому мы отправили сообщением всем участникам отбора с уточнениями по формату вывода:


    package main
    
    func Merge2Channels(...) {
    ...
    }

    Чтобы у участников, как и в жизни разработчика, были подробные комментарии с расшифровкой ошибки, необходимо было настроить чекер по-другому. И здесь мы открыли комментарии для участников отбора через специальную настройку, которая позволила выкачать исходники решений и проверочный тест. С помощью полученных исходников у участников отбора получилось разработать хак-решение, которое позволяло принять даже пустое решение, пример:


    package main
    
    import (
      "os"
    )
    
    func Merge2Channels(f func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {
        go func() {
            for ; n > 0; n-- {
                x1 := <-in1
                x2 := <-in2
                out <- f(x1) + f(x2)
            }
        }()
        cheat()
    }
    
    func cheat() {
        file, _ := os.OpenFile("см формат вывода", os.O_RDWR, 0666)
        file.WriteString("true")
        file.Close()
    }

    Задание получилось спорным. Для перехода на следующий этап его решение сделали необязательным — мы засчитывали решение 4 из 5 задач и более как успешное.


    Демо-день Ozon Go


    Чтобы ответить на вопросы, которые неизбежно возникают при отборе, а заодно рассказать о школе и разработке в Ozon, мы провели онлайн демо-день.


    Что было в программе


    Андрей Егоров, ведущий разработчик команды «Главная страница, разделы и базовые сервисы» рассказывал о принципах написания кода, который легко читать и поддерживать


    Владимир Сердюков, ведущий разработчик команды «Личный кабинет» — о сервисах Ozon, написанных на Go.


    Организаторы школы — Оля Зверева и Сергей Федосенко, руководитель отдела разработки «Маршрутизация магистральных перевозок» — о программе, этапах отбора собеседованиях и всем, что касается учебного процесса.



    Let’s Go!


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

    OZON: life in tech
    e-commerce, где есть примерно всё

    Comments 21

      +11

      Решения задачи Е из статьи не работают тоже, проблема в том, что чекер так и не починили

        0
        На Степике есть аналогичная задача, там проверка вроде работает, а тут выложены тесты.
        +3

        Жаль, что не попал в школу, очень надеялся. А уж какой азарт я чувствовал когда пытался решить задачу два канала! Давно я так не был увлечен.


        Зато пока проходил контест нашел работу golang разработчиком в Wildberries, хотя резюме обновлял только чтобы отправить заявку на участие. Так что думаю, все-таки мне повезло.


        И все-же не смотря на все проблемы с контестом я отлично провел время. Спасибо.

          +3
          skoooorik
          А почему решили скрыть лидерборд? Спрашиваю, потому что люди решившие только 2 задачи писали что их приглашали на собеседование, а многих кто решил 4 не пригласили.
            –4
            Мы приглашали тех, кто решил 4 из 5 задач, но поскольку конкурс большой, важную роль играли и другие факторы, например, опыт работы — и вот в этом случае лидерборд уже не показателен. Можем, кстати, проверить, если вы знаете логины людей, которые решили те самые две задачи. И в любом случае — спасибо за обратную связь. Да, совсем не идеально получилось, но мы исправим и сделаем лучше)
              0
              опыт работы — и вот в этом случае лидерборд уже не показателен

              понятно, значит нужно было больше заморачиваться с резюме, а не с задачами.
                +1
                Ребят, это дерьмо. Ну прям дерьмо. Либо говорим что оценка экспертная и мы сами выберем, тогда никакого конкурса, а просто тестовое задание. Либо беспристрасный конкурс. Печально.
              +5
              Я был участником этого мероприятия, и со всей ответственностью могу заявить — с точки зрения организации оно было провальным.

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

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

              На второй или третий день организаторы прислали письмо — мол, тем кто решал задачи не под тем email, с которого регистрировался в мероприятии, нужно сообщить об этом. Окей, отправляю письмо, в ответ — тишина.

              Стоит ли говорить, что после окончания контеста, организаторы тоже ничего не сообщили участникам? Информационный вакуум в чистом виде.

              P.S. Я решил 4 задачи из 5 (задачу E так и не победил), но приглашения не получил. Начинаю верить тем, кто утверждал, что большее значение имело не решение задач, а релевантный опыт в резюме.
                +1

                в задаче Е чекер неправильно работает, поэтому невозможно его сделать

                  +1

                  всегда будет WA

                    –1
                    Действительно, поскольку это был первый набор и интерес к школе оказался огромным, больше, чем изначально рассчитывали, организаторы допускали ошибки и не всегда отвечали вовремя. И по той же причине решение 4 из 5 задач было только одним из ряда факторов — при конкурсе в 55 человек на место иначе просто не получится. В любом случае спасибо — и за участие и за обратную связь. Мы точно знаем, что нужно сделать лучше, и исправимся обязательно.
                      0
                      Ну, у меня более чем релевантный опыт в резюме и все задачи я решил на Go, но на собеседование меня не позвали, еще и прислали оригинальную отписку про «побольше практики». Видимо просто взяли первую пачку из тех, кто решил 4 задачи и их прособеседовали, остальным прислали отписки.
                      На мой взгляд задачи для такого конкурса были слишком простые и наверняка легко гуглящиеся, не понятно почему при таком конкурсе озон решил не делать второй тур
                      0
                      В условии сказано что функцию можно вызывать параллельно.

                      Вы неправы, в условии нет указания о thread-safety этой функции
                      habrastorage.org/webt/xq/-z/lw/xq-zlwiz2w02k_vewcxqk-h9pju.png

                      Если бы указание было, то быстрый вариант — запустить сразу столько goroutines, сколько данных во входных каналах (2*n штук), тогда есть шанс получить результат быстрее.
                        0
                        Также дана последовательность из целых положительных чисел. Необходимо записать в выходной файл «1», если в последовательности есть два числа сумма, которых равна значению «target» или «0» если таких нет.

                        Поправьте запятую, я мозг сломал
                          +3
                          Последняя фраза из отказного письма — «Побольше практики: участвуйте в проектах, чемпионатах, олимпиадах.» Я правильно понимаю, что вы ~5000 человек ответили — иди, мальчик, поучись сначала? Молодцы
                            –4
                            На самом деле нет. Такое письмо получили те, кто решил 3 и меньше задач, а суть сообщения была в том, что наши задачи и другие конкурсные могут отличаться от тех, что приходится решать в работе. В любом случае не хотели никого обидеть.
                              +4
                              Значит я уже и до 4 считать не умею. Деградирую просто на глазах.
                              Я нисколько не оспариваю ваше право принимать решения на каком угодном основании, в том числе и как в анекдоте — не люблю неудачников. И вы совсем не обязаны как-то обосновывать ваше решение. Но раз уж решили написать, то можно было бы обойтись без подобных нерелевантных и оскорбительных формулировок.
                            0

                            Спасибо, что все-таки написали статью с разбором задач :)

                              +1
                              На этом этапе мы никого не отсеивали, попробовать свои силы мог любой желающий даже несмотря на требования от года опыта промышленного программирования.

                              Мы приглашали на собеседование, оценив резюме, решения и присланный код.

                              В это поверить сложно, т.к. за такие короткие сроки проштудировать все 4650 выполненных заданий и 930 резюме, провести анализ и вынести решение в целом невозможно. Поэтому написали бы честно «мы отсортировали выбранные решения по количеству попыток и скорости выполнения и сняли первые 40».

                              Я одно не понимаю: зачем надо было тратить время соискателей, если было заранее известно о таком конкурсе? Можно же было отложить саму школу на «чуть позже» и первым этапом провести собеседования и\или тестирование, тем самым сократив конкурс. Либо в целом ограничить поток желающих.

                              PS Вот эта вот отписка (судя по всему — массовая рассылка):
                              Побольше практики

                              — высокомерное отношение к своим соискателям, отбивающее желание в дальнейшем участвовать.
                                0

                                skoooorik Как получилось, что я участвуя в "отборе" и явно указав на ошибку в задании "Е", (приложив код задания, полученный из Яндекс.Контеста) по почте не получил ни да, ни нет, а только "Мы работаем над проблемой, чтобы дать больше информации об ошибках"?

                                  0
                                  Впечатление своебразное.
                                  Задача D
                                  Вот такое решение тоже сработало:
                                  # Числа могут содержать до 1000 цифр,
                                  # но в Python3 целые числа автомагически могут быть очень большими.
                                  a, b = [int(x) for x in input().split()]
                                  result = a + b
                                  print(str(result))
                                  ¯\_(ツ)_/¯

                                  Задача F
                                  Ограничение времени 1.5 секунд (ранее была 1 секунда)
                                  Ограничение памяти 64Mb
                                  Перебрал несколько языков (постепенно меняя алгоритм):
                                  Python3 (9: memory-limit-exceeded 205ms / 121.40Mb),
                                  Python2 (9: memory-limit-exceeded 206ms / 92.96Mb),
                                  Free Pascal (9: time-limit-exceeded 1.076s / 132.00Kb),
                                  Perl (7: memory-limit-exceeded 305ms / 82.15Mb),
                                  C++11 (9: memory-limit-exceeded 0.794s / 64.21Mb,
                                  9: time-limit-exceeded 1.091s / 124.00Kb,
                                  наконец, ОК: 9: ok 12ms / 120.00Kb) —
                                  и тут они добавляют полсекунды (O_o).

                                  Задача E
                                  Про это сказали и без меня.
                                  Не «решил» только её. (Да, при одном из запусков видел загадочную ошибку
                                  main_test.go:1:1: expected 'package', found 'IDENT' trueage,
                                  которая, как говорят, вызвана тем, что тест был поломан кем-то другим ¯\_(ツ)_/¯)
                                  И да, сейчас попробовал снова отправить одно из предыдущих решений, дававших «WA»:
                                  теперь «ok 0.785s 49.06Mb».

                                  Only users with full accounts can post comments. Log in, please.