Interesting tasks from technical interviews

I visited many interviews and was on both sides of the confrontation. Now it's time to share the most interesting puzzles with others. For the interview should be interesting and memorable, and not miserable and demotivating.

A few notes

• All tasks for logic and / or programming. No psychological overtones and round hatches.
• The decision is not given intentionally. However, I assure you that almost all problems have a simple and beautiful solution. Enjoy!

Tasks

Here they are.

Mirror Strings in SQL

Suppose we have a table with a string column and we want to find similar rows based on some condition (for example, it can be a full-text search or some internal function that takes two values ​​and returns true / false). So, we write self-join and, of course, we get duplicates among the values. That is, we have mirror pairs as a result, and the final values ​​are exactly two times more than we would like. Question: how to remove from the result one element from each mirror pair and leave there only unique values ​​up to permutations?

Finding holes with SQL

This is an excellent task for assessing knowledge of all basic SQL capabilities.

Suppose that we have a table with a single column. We know nothing about the minimum / maximum values ​​in it. Also, we do not know anything about the number of rows in a table and, in general, it varies and we should not rely on it. We also know that among the values ​​there are gaps, the length of which does not exceed unity. For example, for a table of 5 (five) elements: 1, 2, 4, 6, 7. Question: Write one SQL query using only basic operators (that is, without a procedure and variables) that returns the value of all the "holes". For the above example, the result should be 3, 5. Remember that there are no NULL values ​​in place of gaps. Values ​​3 and 5 are not physically in the table.

Cycles in a single-linked list

This is a task about algorithms and complexity.

Suppose then we have a finite simply linked list. We know that there may be a cycle in it. That is, one of the following elements refers to one of the previous ones. It is necessary to describe the method of finding cycles in such a structure in a finite time. Also, you need to provide an estimate of the time and memory needed to perform the proposed algorithm.

Continuation

It is necessary to modify the result so that the complexity of the memory was O (1). That is, so that the memory consumption does not depend on the size of the list.

Key-value storage

Another task for writing code together and discussing it as you write.

Write key-value storage in any desired language. Add a set_all function that accepts a value as an input and sets it for all existing keys. Evaluate the time and memory costs for the resulting implementation.

Now make set_all working for O (1).

And you can make it so that the complexity of the get and set methods remains at the very beginning, and set_all continues to work for O (1)? If yes, then implement. If not, prove why this is impossible.

Saving people

And in this task it is necessary to think and speculate with the interviewee. And implementation is a matter of technology and is not particularly interesting.

Imagine that we have a group of people. The number does not matter. The whole group is lined up in the back of the head to each other and each one is dressed in a black or white hat. No one knows the color of the hat that he wears. However, everyone sees what is happening in front of them and heard what is happening behind them. After that, a stranger with a pistol goes to the back of the last of the group. He asks "what is your hat color?" The answer can only be "black" or "white." There can be no other messages. If a person guessed it - they let him go. Otherwise, a shot occurs and, in any case, the process repeats with the “new” last member in the queue.

An important clarification: before starting this inhuman experience, all members of the group can meet and think through their own survival strategy.

Question: how to maximize the number of survivors and is there an accurate estimate of the number of survivors depending on the size of the group?

That's all. Now it's your turn to solve one of the tasks and tell about your interesting selection with / for interviews.