Parsing Badoo's PHP tasks and a new test. How to get an offer to London in February / Badoo Blog

pmurzakov January 15, 2018 at 16:02

Parsing Badoo's PHP tasks and a new test. How to get an offer to London in February

Hello, Habr!

In July, we held a recruiting event for PHP developers, as a result of which five people received an offer to our London office. We continue to grow rapidly: Android and iOS teams have since grown by 11 people , so we are launching a contest for PHP developers again.

The rules are the same: show high results in the test , successfully pass the interview on February 10 or 11 in Moscow - get an offer to the Badoo London office.

The company takes care of all the costs of arriving for an interview in Moscow, as well as everything related to a further move to London: work visas for family members, 10,000 pounds (≈ 770,000 rubles) for moving, improving English, finding housing.

To complete the test task it was more interesting, according to numerous requests ( 1 , 2 , 3 ) under the cut, we will analyze the tasks from the previous event, consider their correct solutions, and I will explain why we chose them, and also give some examples, statistics and options decisions from candidates.

UPD: event completed. As a result, 7 people joined us.

First of all, I want to note that an online test is a compromise. This is such a synthetic assessment of human knowledge and skills, which, although correlated with the ability to solve real problems, does not always accurately reflect them.

We at Badoo rely on people, on personal qualities. Therefore, we always try to personalize the interviews as much as possible: for us it is important not so much the fact of solving the problem, but how the person thinks and reasones.

Therefore, if you are not lucky with the test, do not be discouraged. Follow us in a standard way - and perhaps you will prove to be better at our regular interview. The same applies to those who do not want to move to London - we have excellent vacancies in Moscow!
Nevertheless, it is somehow necessary to conduct the initial selection, so we still decided to use the online test for this.

To justify the choice of tasks for the test, you first need to explain why we generally use it, what and how to check with it.

So, the test allows us to solve two problems:

it’s easy to select candidates who fit our basic requirements;
Among those suitable for the requirements, choose the best.

Primary selection

We solve the problem of primary selection with the help of tasks for writing SQL and PHP code with automatic verification. Thanks to automation, only 150 of the 950 solutions received were checked by us last time. That is approximately 15%.

As basic, we have established the following requirements:

knowledge of PHP (at the "average" level);
knowledge of SQL (at the "average" level);
general understanding of computer science;
minimum knowledge of English;
the ability to apply these skills to solve problems.

Picking the best

Candidates who have passed the first stage of selection are already quite good. This does not mean their perfect readiness, but a good base is the guarantee that a person is already potentially suitable for us or suitable in the future with proper training.

How to choose the best among the potentially suitable? This process is more difficult to formalize. Therefore, at this stage, we decided to use tasks with great scope to demonstrate knowledge and experience from various fields. And each successful use of such abilities was considered a plus.

It is impossible to cover all areas with one list, so I will give a few examples of topics that we paid attention to:

Linux console
debugging different parts of the LNMP stack;
network view, HTTP (S), TCP / IP;
queues, message brokers, parallel processing;
optimization (My) SQL;
ensuring data integrity (transaction, isolation);
highload-specific things (scaling, sharding, caching);
general idea of the CPU, memory, task scheduler in the OS;
design, systems architecture.
...

Tasks

As a result, we selected six tasks that cover our requirements:

three automatically checked for writing code: two in PHP and one in SQL;
three for free reasoning.

All task texts were written in English, so the minimum knowledge of it was checked automatically.

Here, for convenience, I will cite texts in Russian and reduce them as much as possible, leaving only the essence.

For example, we’ll analyze three tasks from the previous test.

Task number 1. "The sum of large numbers"

Condition A
string is given containing two positive integers, separated by a space. Numbers may be large and may not fit into a 64-bit integer. It is necessary to print the sum of these numbers.

Typical solution

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'));
}

The task is simple. With it, we test the ability to program in PHP. 201 people decided it completely correctly. A further 63 candidates underwent some of the test scenarios, but some boundary cases did not pass.

One of the possible optimizations of the solution is to take in each iteration of the cycle not one bit of the number, but several (N) at once. It is important to take into account that both the numbers consisting of N digits and the sum of two such numbers must fit in 63 bits, since in PHP all ints are signed. It turns out that you can take a maximum of 18 bits at a time.

We marked such decisions as interesting, although only a few resorted to them.

After the task was published, we found out that the platform does not allow you to manage the available PHP extensions to solve it. Therefore, the problem could also be solved using GMP (gmp_add ()) and BC Math (bcadd ()). We regarded such decisions as true on a par with the others, despite the fact that in this case they came down to a couple of lines of code.

Task number 2. "Parentheses"

Condition
At the input there is a line containing only brackets from the set {} () []. It must be determined whether it is balanced or not.

By balanced is meant a string in which three conditions are satisfied:

for each opening bracket there is a corresponding closing;
the corresponding closing bracket must be after the opening;
between the two corresponding brackets there are no other brackets without matches between these brackets.

That is, [([] {[]})] is balanced, but {[}], [{)] and] {} [is not.

Typical solution

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";
}

The task tests both general knowledge of PHP and computer science (algorithms). Totally correctly, 231 people decided it. Another 99 candidates passed some test scenarios, but not all.

The shortest way to solve this problem is to delete all combinations “()”, “{}” and “[]” from the string in a loop until the string stops changing. Although we made such a decision, we marked it as non-optimal. In this case, it is required to make many passes along the line and memory allocations, while the decision on the stack is performed in one pass and has O (N) complexity.

Some participants used SplStack instead of array () to implement the stack. We considered such solutions to be equivalent, although, however, SplStack used units.

Task number 3. Wikipedia

Condition
There is a task to download all the pages of the English-language Wikipedia (HTML only, without pictures, CSS, JS).

There are ten servers (24 cores on each), an endless fast disk and RAM, and gigabit Internet.

It is necessary to evaluate the time required to complete the task and justify it by describing the solution algorithm. No code is required.

Explanation
With this task, we wanted to evaluate the ability of candidates to decompose a real task “out of life”, to separate important information from the condition and correctly determine / justify the time frame.

There is no reference solution here, so I bring the main points to which we paid attention in the first place:

determine the number of pages on Wikipedia (currently 5,548,604), find the index of its pages ;
figure out how long it takes to transfer content in terms of network bandwidth. If you take the average page size of 30 Kb, then the entire Wikipedia will occupy 5548604 * 30 Kb ≈ 166 GB. Transmission over the network will take (5548604 * 30000 * 8) bits / 10 ^ 9 bits / s ≈ 1331 s. ≈ 22 min .;
Estimate network response time. If we take 50 milliseconds for the average response time, then the sum of all delays will be equal to 5548604 * 0.05 = 277430.2 s. ≈ 3.2 days;
propose to parallelize the task within each server and servers. Any working decisions were made: start somewhere a queue server, a database, somehow break up the task into parts;
justify the choice of the number of parallel handlers (N). Since the processor time is much less than the response time over the network, N can be taken more than the number of cores (> 10 * 24). Also here we can mention the possibility of using “asynchronous code” within a single thread of execution (event loop, curl_multi_exec, etc.);
for example, at N = 1000 we get 5548604 * 0.05 / 1000 = 277 s. ≈ 4.6 min., Which is already very small compared with the time for implementation;
add some time to develop, debug, and run. We took any more or less reasonable period, while studying the decision we paid attention mainly to justification. There were candidates who offered quite long periods (weeks or more) without any explanation of what this time would take. We considered such decisions not very successful.

More or less successfully, 12 people coped with this task. Another 55 have partially solved it.

Where to take the new test.

Now that it has become clear how we select tasks and evaluate their solutions, it's time to remind you that a detailed description of the event, conditions and a fresh test is here . You can go through it until January 26.

You can learn more about the team and tasks from the announcement of the previous event on Habré. And here you can read the success story about the move to London of our colleague Anton Rusakov.

Have questions? Feel free to ask them in the comments or send me to Habropost.

Take the test, come to our interview - and join our friendly team! It will be interesting!

Good luck!

Pavel Murzakov, PHP Team Lead, Badoo.

UPD: we will give an answer until February 7-8.
UPD2:event completed. As a result, 7 people joined us.

Tags:

Parsing Badoo's PHP tasks and a new test. How to get an offer to London in February / Badoo Blog