How are algorithmic sections at interviews in Yandex

How are algorithmic sections at interviews in Yandex


The algorithmic section with writing code on a blackboard or paper is one of the most important stages of the interview for developers to get work in Yandex. We decided to tell you more about how these sections are arranged to help future candidates to prepare. In addition, I hope many of those who do not dare to come to Yandex for an interview, fearing too complicated tests, after this story will realize that in reality everything is not so scary!


So we prepared for you the following materials:


  • A special contest containing tasks similar to those we give an interview.
  • This post . It tells why you need to conduct such sections, and also understands all the tasks of the contest.
  • Two videos that deal with tasks from the contest: in first is a simpler task in by the author - two tasks are more complicated. From these videos, you will learn about common mistakes made during the passage of algorithmic sections, and when writing production code.



How we interview the developers


Any developer’s interview consists of several stages:


  • preliminary section with a recruiter;
  • Skype technical interview;
  • several in-person sections;
  • final interviews with hiring managers.

At the preliminary section, the recruiter meets the candidate, learns his interests and motives in order to understand what positions it makes sense to consider him. Technical Skype interview is designed to pre-assess the skills of the candidate and eliminates those who clearly can not cope with the in-person sections.


Face-to-face sections - the main stage. In-person sections give an answer to the question of what a candidate can do. Algorithmic section - one of the full-time technical sections. In addition to algorithmic, there are other face-to-face tests: for example, candidates for senior developers must pass a section on architecture, and future managers also answer questions on managing teams and projects. In general, if a candidate has some kind of strength in a specific area (machine learning, low-level optimization, development of high-loaded systems, mobile development, or any other), we will definitely organize a section with a specialized specialist.


The algorithmic section checks whether a candidate is able to come up with algorithms to solve simple tasks, assess the complexity of these algorithms and implement them without errors, while maintaining a balance between the quality of testing and the speed of the solution.


Why write code on a blackboard or paper


The natural state for a programmer is programming in an integrated development environment with syntax highlighting and traceability. Therefore, the idea of ​​an interview to write code on a blackboard or paper initially seems not too natural. However, this method allows you to check two properties that are very important for each developer.


The first of these is the ability to quickly understand how the code works by eye. Imagine that when writing each cycle that occurs in a program, the developer needs to spend time trying to test its performance by tracing; or that when a service crashes in production, he always needs to run the code under the debugger.It is clear that writing and debugging even simple programs will take an inadmissibly long amount of time. Of course, it is useful to be able to read the code even with the code review.


The second important feature is the ability to think through a solution plan in advance and then follow it. If there is no plan, this will result in a large number of corrections, deletions (on paper) and rewriting large pieces of code. In real life, all this greatly slows down development, but is partly masked by the speed of work in the code editor. Board and paper in this sense are merciless surfaces.


Naturally, we consider that writing code by hand is not too fast. Therefore, our tasks usually involve a solution that is not much longer than a dozen lines, and the number of tasks that need to be solved within one section is usually two or three.


Algorithmic sections and sports programming


Sports programming develops in the future developer, among other things, the ability to quickly and without errors implement simple algorithms according to a predetermined plan. Therefore, candidates with experience in sports programming really do a good job with algorithmic sections during interviews. You can often observe a situation where future interns can easily cope with the algorithmic section, solving all problems in 15–20 minutes, while more experienced programmers spend an hour on the same tasks.


At the same time, the code-writing algorithmic section is just one of the sections that tests the minimum necessary skills for any developer. Not only Olympiad programmers, but also experienced industrial developers will cope with this section. The future senior developer or team leader is waiting for the architectural section, where he can reveal his greatest strengths; Of course, this section is never put to interns and junior developers.


Contest to prepare for an interview


Especially so that you can roughly imagine the content of the tasks that we give in the algorithmic sections, we have collected contest , which can be used in preparation for interviews. Try to solve all the problems, never running a debugger; write a solution in Notepad without syntax highlighting; come up with the shortest possible solution, which will pass all tests; think over all possible problems in advance and hand over the decision the first time.


The contest contains five tasks. You can try to solve them yourself, or you can read the analysis in advance: it will still be useful, because You will be able to practice your skill of error-free coding of a previously known algorithm.


Parsing contest tasks

Problem A. Stones and ornaments


Two lines of lowercase Latin characters are given: string J and string S. Characters included in string J are “jewels” included in string S — stones. It is necessary to determine how many symbols from S are at the same time “jewels”. Simply put, you need to check how many characters from S are included in J.

This is a very simple warm-up task to which solutions are applied in several programming languages ​​so that participants can get comfortable with the testing system.

< br/>

The algorithm is quite simple: from the line with the "jewels" you need to build a set, then go through the line with the "stones" and check each character for entry into this set.Use this implementation of the set to guarantee the linear complexity of the solution obtained, despite the fact that the input lines are very short and therefore it is possible to pass even an algorithm that is quadratic in complexity.


Problem B. Successive units


It is required to find the longest sequence of units in a binary vector and output its length.

The solution algorithm is as follows: go through all the elements of the array; having met one, it is necessary to increase the counter of the length of the current sequence, and, having met zero, it is necessary to reset this counter. In the end, you need to display the maximum of the values ​​that the meter took.


Check that you handle the situation correctly when the array ends with the desired sequence of units. With careful implementation, this situation does not require special treatment.


Try to use only the constant amount of additional memory.


Task C. Removing duplicates


Given an array of 32-bit integers in non-decreasing order. You need to remove all repetitions from it.

The correct algorithm sequentially processes the elements of the array, comparing them with the last one output. You need to remember to update the variable containing the last displayed element and, moreover, not to be mistaken when processing the last element.


In this task, you also do not need to use additional memory.


Task D. Generate bracket sequences


Given an integer $ n $ . It is required to display all correct bracket sequences of length $ 2 \ cdot n $ , ordered lexicographically (see https://ru.wikipedia.org/wiki/Lexographic_order ). The task uses only parentheses.

This is an example of a relatively complex algorithmic problem. We will generate a sequence of one character; at any moment we can add either an opening bracket or a closing bracket to the current sequence. The opening bracket can be added if less than n opening brackets were added before, and the closing bracket - if in the current sequence the number of opening brackets exceeds the number of closing brackets. Such an algorithm, when carefully implemented, automatically guarantees the lexicographical order in the answer; it works for a time proportional to the product of the number of elements in response to n; it requires a linear amount of additional memory.


An example of an inefficient algorithm would be the following: we will generate all possible bracket sequences, and then we derive only those that are correct. At the same time, the volume of the answer will not allow solving the problem faster than the algorithm that will result above.


Task E. Anagrams


This rather simple task is a typical example of a task for which solution it is necessary to use associative arrays. When deciding it is necessary to take into account that the characters can be repeated, therefore it is necessary to use dictionaries, not sets,Therefore, the solution will be as follows: we will compile a dictionary from each line that will store the number of its repetitions for each character; then compare the resulting dictionaries. If they match, you must output the unit, otherwise - zero.


Alternative solution: sort the input lines and then compare them. This solution is worse in that it is slower and also changes the input data. But this solution does not use additional memory.


If during the interview process you had several solutions that differ in their characteristics, tell us about it. It's always great when a developer knows several solutions to a problem and can tell about their strengths and weaknesses.


Problem F. Merge $ k $ sorted lists


Given $ k $ sorted in non-decreasing order arrays of non-negative integers, each of which does not exceed 100. It is required to construct the result of their merging: an array sorted in non-decreasing order, containing all elements of the source $ k $ arrays. The length of each array does not exceed $ 10 \ cdot k $ .

For each array, create a pointer; initially, each pointer is located at the beginning of the corresponding array. The elements corresponding to the positions of the pointers are placed in any data structure that supports minimum retrieval - it can be a multiset or, for example, a heap. Next, we will extract the minimal element from this structure, place it in response, shift the pointer position in the corresponding array and place the next element from this array in the data structure.


In this task, many have difficulty with the input format. Notice that the first elements of the lines do not describe the elements of the arrays, they describe the lengths of the arrays!


contest contest


A: I definitely wrote the correct code, but the tests do not pass; probably an error in them?
Q: No, all tests are correct. Consider: you probably haven't foreseen any unusual situation.


A: I write in X, he definitely needs more memory in task Y. Raise the limits!
Q: All limits are set in such a way that the solution is possible using any of the available languages. Try to check if you accidentally read the entire input file in tasks with strict limits on the memory used.


A: Some tasks can be solved much easier due to these limitations. Why are you so?
Q: We have specially simplified input in some tasks, so that participants can more easily concentrate on the implementation of the algorithm and not think, for example, about the speed of data loading or some other things important in sports programming. Try to implement exactly the algorithms that we recommend - only in this situation you will get the maximum benefit from the contest.


A: I do not want to pass the contest. Can I not?
Q: Of course! The contest is not obligatory for decision by all candidates. However, I still recommend to solve it: it will be useful in any case.


A: What else do you recommend for preparation?
Q: Read our tips on the official page about Yandex interviews: https://yandex.ru/jobs/ya-interview . From myself I will add that solving the problems on leetcode.com is extremely useful for any practicing developer, regardless of whether he plans to have an interview in the near future or to participate in programming competitions. Even a small amount of practice allows you to feel more confident in solving work problems.


Conclusion


I often attend conferences for developers and development managers, I’m in many development chats, I spent several hundred interviews and hired a huge number of developers at Yandex. Experience suggests that algorithmic sections of writing code on a board or paper often raise questions. In conclusion, the article I will answer the most popular ones.


Why conduct an interview in an environment that is so different from the actual working conditions of the developer?
This allows you to understand whether a candidate is able to find problems in programs without starting a debugger; whether he can come up with a plan of the algorithm in advance and then follow it without error; can he come up with a small, but sufficient, test suite and then test his implementation for compliance with this test suite.


Do these sections give an unfair advantage to sports programmers?
Athletic programming develops some very useful skills in developers, so participants in programming olympiads really do a good job with algorithmic sections. So there is an advantage, but it is fair. Algorithmic section is only one of many, so each candidate will have enough opportunities to show their strengths!


Why carry out algorithmic sections, if all the algorithms have long been implemented, and you just need to be able to look for their implementation in ready-made libraries?
On algorithmic sections that are common to all developers, we check only the minimally necessary skills: the ability to invent and implement without errors a simple algorithm containing cycles, condition checks and, possibly, the use of associative arrays. This type of code constantly has to be written to implement custom services.


What is the point in a section that does not test a huge amount of developer skills?
The algorithmic section, in fact, checks only the minimum set of skills necessary for any developer. We test other skills with other sections.


Do you spend algorithmic sections for developers of all specialties?
Yes. Algorithmic sections are held for backend developers, analysts, mobile and front-end developers, developers of infrastructure and machine learning methods, and so on.

Source text: How are algorithmic sections at interviews in Yandex