Разбор PHP-задач Badoo и новый тест. Как получить оффер в Лондон в феврале

Привет, Хабр!

В июле мы проводили рекрутинговое мероприятие для PHP-разработчиков, по результатам которого пять человек получили оффер в наш лондонский офис. Мы продолжаем быстро расти: Android- и iOS-команды с того времени стали на 11 человек больше, поэтому мы снова запускаем конкурс для PHP-разработчиков.

Правила те же: покажи высокий результат в тесте, успешно пройди интервью 10 или 11 февраля в Москве — получи оффер в лондонский офис Badoo.

Все расходы по приезду на интервью в Москву компания берёт на себя, равно как и всё связанное с дальнейшим переездом в Лондон: рабочие визы членам семьи, 10 000 фунтов стерлингов (≈ 770 000 рублей) на переезд, совершенствование английского, поиск жилья.

Чтобы выполнять тестовое задание было интереснее, по многочисленным просьбам (1, 2, 3) под катом мы разберём задачи с предыдущего мероприятия, рассмотрим их правильные решения, и я объясню, почему мы выбрали именно их, а также приведу некоторые примеры, статистику и варианты решений от кандидатов.
Прежде всего хочу отметить, что онлайн-тест — это некий компромисс. Это такая синтетическая оценка знаний и умений человека, которая хоть и коррелирует со способностью решать реальные задачи, но не всегда точно отражает их.

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

Поэтому, если вам не повезло с тестом, не расстраивайтесь. Подавайтесь к нам по стандартной схеме — и, возможно, на нашем обычном собеседовании вы проявите себя лучше. Это же относится и к тем, кто не хочет переезжать в Лондон — у нас есть отличные вакансии в Москве!
Тем не менее провести первичный отбор как-то нужно, поэтому мы всё-таки решили использовать для этого онлайн-тест.

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

Итак, тест позволяет нам решить две задачи:

• легко отобрать кандидатов, которые подходят под наши базовые требования;
• среди подходящих под требования выбрать лучших.

Первичный отбор

Проблему первичного отбора мы решаем при помощи задач на написание SQL- и PHP-кода с автоматической проверкой. Благодаря автоматизации в прошлый раз из 950 полученных решений только 150 мы проверяли вручную. То есть примерно 15%.

В качестве базовых мы установили такие требования:

• владение PHP (на «среднем» уровне);
• владение SQL (на «среднем» уровне);
• общие представления о computer science;
• минимальные знания английского языка;
• возможность применять перечисленные навыки для решения задач.

Выбор лучших

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

Как же выбрать лучших среди потенциально подходящих? Этот процесс формализовать сложнее. Поэтому на этом этапе мы решили использовать задачи с большим простором для демонстрации знаний и опыта из различных областей. И каждое удачное применение таких способностей считали плюсом.

Охватить одним списком все области невозможно, поэтому я приведу несколько примеров тем, на знание которых мы обращали внимание:

• консоль Linux;
• отладка разных частей LNMP-стека;
• представление о сети, HTTP(S), TCP/IP;
• очереди, брокеры сообщений, параллельная обработка;
• оптимизация (My)SQL;
• обеспечение целостности данных (транзакционность, изоляция);
• highload-специфичные вещи (масштабирование, шардинг, кеширование);
• общее представление о работе CPU, памяти, планировщике задач в ОС;
• проектирование, архитектуры систем.
• ...

Задачи

В результате мы выбрали шесть задач, которые покрывают наши требования:

• три автоматически проверяемые на написание кода: две на PHP и одну на SQL;
• три на рассуждения в свободной форме.

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

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

Для примера разберём три задачи из прошлого теста.

Задача №1. «Сумма больших чисел»

Условие
Дана строка, содержащая два положительных целых числа, разделённых пробелом. Числа могут быть большими и не умещаться в 64-битное целое. Нужно вывести сумму этих чисел.

Типичное решение

function sum_str($str)
{
    list($s1, $s2) = explode(' ', $str); 
    $l1 = strlen($s1);
    $l2 = strlen($s2);
    
    $result = "";
    $rest = 0;
    
    for($i = 1; $i <= max($l1, $l2) + 1; $i++) {
        $d1 = $s1[$l1 - $i] ?? 0;
        $d2 = $s2[$l2 - $i] ?? 0;
        
        $sum = $d1 + $d2 + $rest;
        $rest = intval($sum > 9);
        
        $result .= $sum % 10;
    }

    return strrev(rtrim($result, '0'));
}

Задача простая. С её помощью мы проверяем умение программировать на PHP. Полностью правильно её решил 201 человек. Ещё у 63 кандидатов проходила часть проверочных сценариев, но не проходили какие-то краевые случаи.

Одна из возможных оптимизаций решения — в каждой итерации цикла брать не один разряд числа, а сразу несколько (N). Тут важно учесть, что как сами числа, состоящие из N разрядов, так и сумма двух таких чисел, должны умещаться в 63 бита, поскольку в PHP все int’ы знаковые. Выходит, что за раз можно брать максимально 18 разрядов.

Такие решения мы помечали как интересные, хотя и прибегли к ним единицы.

После публикации задачи мы выяснили, что платформа не позволяет управлять доступными PHP-расширениями для её решения. Поэтому задачу можно было решить также при помощи GMP (gmp_add()) и BC Math (bcadd()). Мы расценивали такие решения как верные наравне с остальными, несмотря на то, что в таком случае они сводились к паре строк кода.

Задача №2. «Скобки»

Условие
На входе есть строка, содержащая только скобки из набора {}()[]. Необходимо определить, является ли она сбалансированной или нет.

Под сбалансированной подразумевается строка, в которой выполняются три условия:

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

То есть [([]{[]})] — сбалансированная, а {[}], [{)] и ]{}[ — нет.

Типичное решение

function balanced($str)
{
    $braces = [
                '}' => '{',
                ')' => '(',
                ']' => '[',
        ];
    
    $stack = [];
    for($i = 0; $i < strlen($str); $i++) {
        $char = $str[$i];
        
        if (isset($braces[$char])) {
            $el = array_pop($stack);
            if ($el != $braces[$char]) {
                return 'NO';
            }
        } else {
            array_push($stack, $char);
        }
    }
    
    return $stack ? "NO" : "YES";
}

Задача проверяет как общее знание PHP, так и computer science (алгоритмов). Полностью правильно её решил 231 человек. Ещё у 99 кандидатов проходили некоторые тестовые сценарии, но не все.

Самый короткий способ решить эту задачу — в цикле удалять из строки все сочетания “()”, “{}” и “[]” до тех пор, пока строка не перестанет меняться. Такое решение мы хоть и принимали, но помечали как неоптимальное. В этом случае требуется совершать множество проходов по строке и перевыделений памяти, в то время как решение на стеке выполняется за один проход и обладает сложностью O(N).

Некоторые участники использовали для реализации стека SplStack вместо array(). Мы считали такие решения равнозначными, хотя, впрочем, SplStack использовали единицы.

Задача №3. «Википедия»

Условие
Есть задача скачать все страницы англоязычной «Википедии» (только HTML, без картинок, CSS, JS).

В наличии имеется десять серверов (на каждом по 24 ядра), бесконечный быстрый диск и ОЗУ, гигабитный Интернет.

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

Пояснение
С помощью этой задачи мы хотели оценить способность кандидатов декомпозировать реальную задачу «из жизни», отделять важную информацию из условия и верно определять/обосновывать сроки.

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

• определить количество страниц в «Википедии» (на данный момент 5 548 604), найти индекс её страниц;
• прикинуть, сколько времени займёт трансфер содержимого с точки зрения пропускной способности сети. Если взять за средний размер страницы в 30 Кб, то вся “Википедия” будет занимать 5548604 * 30 Кб ≈ 166 Гб. Передача по сети займёт (5548604 * 30000 * 8) бит / 10^9 бит/с ≈ 1331 с. ≈ 22 мин.;
• оценить время отклика сети. Если взять за среднее время отклика 50 миллисекунд, то сумма всех задержек будет равна 5548604 * 0,05 = 277430.2 с. ≈ 3,2 дня;
• предложить распараллелить задачу в рамках каждого сервера и по серверам. Принимались любые работающие решения: завести где-то сервер очередей, БД, каким-то другим образом разбить задачу на части;
• обосновать выбор количества параллельных обработчиков (N). Поскольку процессорное время значительно меньше времени ожидания ответа по сети, N можно брать больше, чем количество ядер (> 10*24). Также здесь можно упомянуть возможность использования “асинхронного кода” в рамках одного потока выполнения (event loop, curl_multi_exec и т. д.);
• например, при N = 1000 получаем 5548604 * 0.05 / 1000 = 277 с. ≈ 4,6 мин., что уже очень мало по сравнению со временем на реализацию;
• добавить какое-то время на разработку, отладку и запуск. Мы принимали любой более-менее обоснованный срок, при изучении решения уделяли внимание в основном как раз обоснованию. Были кандидаты, которые предлагали достаточно длительные сроки (недели и больше) без какого-либо объяснения, на что это время уйдёт. Такие решения мы считали не очень удачными.

Более-менее успешно с этой задачей справились 12 человек. Ещё 55 решили её частично.

Где пройти новый тест

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

Более подробно о команде и задачах можно узнать из анонса предыдущего мероприятия на Хабре. А здесь можно прочитать success story о переезде в Лондон нашего коллеги Антона Русакова.

Есть вопросы? Смело задавайте их в комментариях или присылайте мне на Хабропочту.

Проходите тест, приходите к нам на интервью — и присоединяйтесь к нашей дружной команде! Будет интересно!

Good luck!

Павел Мурзаков, PHP Team Lead, Badoo.

Let's block ads! (Why?)