This is a repost of my
article from Medium. Also, here is a russian variant.
I visited lots of interviews and was on a both sides of this standoff. Now I want to share most interesting tasks with other. Because I believe, that interview must be interesting and rememberable, not awful and demotivating.
I deliberately don’t want to provide a solution of any task. But I assure you that most of them has a simple and beautiful solution. Enjoy!
Here they are.
Suppose, we have a table with string column and want to find the similar rows by some condition (for example, this is a full-text search or some internal function which receives two values and returns true/false). So, we write a self-join and, obviously, obtain a duplicated rows. I.e. we have a mirror pair in the result. So, question is follows: how to remove a one of the mirror elements (not important which one) and leave only unique pairs without a transposition?
This task is perfect for obtain a knowledge of understanding an SQL basis by a candidate.
Suppose, we have a table with a single integer column. We don’t know anything about minimum/maximum value of it. Moreover, we don’t know amount of rows in the table and, in a common case, this amount is varying. We know, that there is an empty intervals (“holes”) between values. Additionally, we know, that length of this empty intervals not more than one. For example, table with 5 (five) elements: 1, 2, 4, 6, 7. Question: write an single SQL-query using only common operators (without procedures and variable) which has all values of “holes” in the result. For the upper example, it was 3, 5. Remember, there is no NULL values for 3 and 5. This values absences in the table at all.
This one about algorithms and complexity.
Suppose, we have a single-linked list. We know, that probably there is a loop. I.e. one of the following elements is referring to one of the previous elements. Needs to write an algorithm to reliably check this structure of a data to existing of a loop for an finite time. Additionally needs to provide an estimation of resulted algorithm by required memory and time.
Next step. Needs to modify the resulted algorithm to follows requirement: it must has memory consumption O(1).
Write a key-value storage and provide an estimation for required time and memory. Write a method which receive a value and set it for all existed keys. Provide a previously mentioned estimations for this method.
Now, rewite set_all
method for achieve time complexity
O(1).
Can you save initial complexity of get
and
set
methods and satisfy requirement for
set_all
? If yes — write it, of no — provide a proof why this
is impossible.
There is a group of people. Each member has a white or black hat. Distribution of hats colors is unknown. Moreover, no one know color of his own hat. People stay in the line and looking in the back of each other’s heads. Hence, they see all in front of them and hear all that happens behind. In a first moment of time to the back of the last member comes a stranger with revolver and ask him about color of his hat. Member can say only 'white' or 'black'. If the member is right — he is free. Otherwise he will be gunned with a loud sound. Questions is follows:
Provide an estimation for saved lives.
Important condition: before start of this action all people from the group can discuss their strategy together. In those moment the members doesn’t know anything about their position in the line or about color of hats.
That’s all. Now your turn to solve some/all of them and to say about your interesting experience and tasks.