Interesting tasks from technical interviews

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.

Several remarks

  1. All tasks about a logic and/or a programming. There is no any psychological implication.

  2. 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!

Tasks

Here they are.

Similar rows in SQL

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?

▼ Hints (click)
  • There is some unobvious property of a string and of a common SQL operators.

Finding “holes” using SQL

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.

▼ Hints (click)
  • If this is difficult for you try to use procedure and then move to a single query.
  • Strong tip: most beautiful query must be for a query with result 3, 5, 8 from the upper example.

Loop in a single-linked list

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).

▼ Hints (click)
  • Remember about conversion of a time complexity to a memory one and vice versa.

Key-value storage

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.

Save the people

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:

  • how to save the most lives?

  • 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.

▼ Hints (click)
  • Think, how each member can aggregate all existed information in a single bit of data and how they can exchange this information.
  • Strong tip: maybe an even/odd or a xor can help you?

That’s all. Now your turn to solve some/all of them and to say about your interesting experience and tasks.

SQL interesting tasks algorithms interview tasks logic

comments powered by Disqus