23.06.2020 17:11
skoooorik 21 3600 Источник

В мае стартовал первый набор школы 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!


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