How are algorithmic sections at interviews in Yandex
Algorithmic section with writing code on a blackboard or paper is one of the most important stages of the interview of developers to get a job 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 have prepared for you the following materials:
- Special contest , containing tasks similar to those that we give to the 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 the first - the task is simpler, in the second - two tasks are more complicated. From these videos you will learn about typical mistakes made during the passage of algorithmic sections, and when writing production code.
How do we interview the developers
An interview of any developer consists of several stages:
- preliminary section with a recruiter;
- technical skype interview;
- several full-time sections;
- final interviews with hiring managers.
At the preliminary section, the recruiter meets with the candidate, learns his interests and motives in order to understand what positions it makes sense to consider him. Technical Skype interview is intended to pre-assess the skills of the candidate and weed out those who definitely cannot cope with the in-person sections.
Full-time section - 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 strong point 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 specialist.
The algorithmic section checks whether the candidate is able to invent algorithms for solving simple tasks, assess the complexity of these algorithms and implement them without errors, in the process keeping 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 test two properties that are very important for each developer.
The first of them is the ability to quickly understand the performance of the code "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 with code review.
The second important feature is the ability to think over the 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 imply a solution that is not much longer than a dozen lines, and the number of tasks that need to be solved in 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 trainees 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 checks the minimum 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 the interview
Especially so that you can roughly imagine the content of the tasks that we give in the algorithmic sections, we have collected a contest , which can be used in preparing 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.
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 come 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.
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.
It is required to find the longest sequence of units in the binary vector and output its length.
The solution algorithm is as follows: walk 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 of this situation does not require special handling.
Try to use only the constant amount of additional memory.
Given an ordered array of 32-bit integers in non-decreasing order. It is required to remove all repetitions from it.
The correct algorithm sequentially processes the elements of the array, comparing them with the last output. It is necessary not to forget to update the variable containing the last displayed element and, moreover, not to be mistaken when processing the last element.
In solving this problem, you also do not need to use additional memory.
Task D. Generate bracket sequences
Given an integer . It is required to display all correct bracket sequences of length. , 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 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.
This rather simple task is a typical example of a problem 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, rather than 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 strings 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 you have several solutions that differ in their characteristics, tell us about it. It is always great when a developer knows several solutions to a problem and can tell about their strengths and weaknesses.
Are given sorted in non-decreasing order of 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 original arrays. The length of each array does not exceed .
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. Please note that the first elements of the lines do not describe the elements of the arrays, they describe the lengths of the arrays!
Contest FAQ
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 language X, he definitely needs more memory in task Y. Raise 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 the indicated 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 those algorithms that we recommend - only in such a situation you will get the maximum benefit from the contest.
A: I do not want to pass a 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 would you advise for preparation?
Q: Read our tips on the official page about interviews in Yandex: 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 tasks.
Conclusion
I often attend conferences for developers and development managers, I have been in many development chats, conducted several hundred interviews and hired a huge number of developers to 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 under conditions 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, set of tests and then check his implementation for compliance with this set of tests.
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 conduct algorithmic sections if all the algorithms have been implemented for a long time, 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. Other skills we test with other sections.
Do you conduct 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: https://habr.com/ru/post/449890/
All Articles