Tech and Developer Interview Questions: Riddles With Solutions
These riddles train you to cut the number of attempts, divide the space of possibilities and choose an algorithm by its time and memory cost. Here are 4 classic riddles, each with its solution explained.
Two Eggs and 100 Floors Puzzle: The Minimum Number of Drops
Tech interview question on finding a threshold with few trials
You have two identical eggs and a 100-floor building. There is a critical floor above which a dropped egg breaks; below it, the egg survives and can be used again. What is the minimum number of drops needed, in the worst case, to find this critical floor?
Need a hint?
A first broken egg forces you to test the floors one by one with the second egg, so choose steps whose gaps keep shrinking.
Show the answer and the solution
Answer: 14 drops at minimum in the worst case, dropping the first egg at floors whose gaps shrink from 14 down to 1.
The reasoning
For each drop of the first egg, we accept that in the worst case we must go through the interval before it floor by floor with the second egg. The first egg is dropped from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, then 100, which gives gaps of 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, then 1. If the first egg breaks at a step, the second egg tests the floors one at a time from the previous step: in the worst case, that is k drops for the k-th step, plus the gap minus one, which always totals 14. The number n of drops must satisfy n(n+1)/2 ≥ 100: for n = 13 we get 91, not enough, and for n = 14 we get 105, which is enough. The answer is therefore 14 drops.
Find the Missing Number in an Array: Sum Formula Solution
Developer interview question on algorithms and complexity
An array contains the integers from 1 to n, except one, and its elements are in no particular order. You know the value of n, but neither the missing number nor the order of the elements. How can you find the missing number as efficiently as possible?
Need a hint?
Think of an arithmetic property of the sequence of integers from 1 to n that lets you recover the missing element without searching for it.
Show the answer and the solution
Answer: Subtract the sum of the array's elements from the expected sum n(n+1)/2: the difference is the missing number, in O(n) time and O(1) extra memory.
The reasoning
The sum of the integers from 1 to n is n(n+1)/2, a formula that only needs to be computed once. If you add up all the elements present in the array, exactly the missing number is absent from that sum, so the actual sum is lower than the expected sum by precisely that number. The difference between the two sums directly gives the value sought. The calculation goes through the array only once, so the complexity is O(n) in time, and only a few variables are needed, that is O(1) extra memory. Another method, just as efficient, is to take the exclusive OR (XOR) of all the numbers present together with the numbers from 1 to n: the result is the missing number.
Guess a Number from 1 to 1000 with Yes or No Questions
Algorithms question on binary search, which halves the interval at each question
I am thinking of a whole number between 1 and 1000. You may ask me questions, to which I answer only yes or no. How many yes-or-no questions are enough, in the worst case, to guess this number for sure?
Need a hint?
Do not test the numbers one by one: choose each question so that it eliminates half of the remaining possibilities.
Show the answer and the solution
Answer: 10 questions: each answer halves the number of possibilities, and 2 to the power 10 is 1024, more than 1000.
The reasoning
Each yes-or-no question splits the remaining possibilities into two groups, for example by asking whether the number is greater than 500. Whatever the answer, we keep one half of the interval and repeat the process on that new half. After k questions, at most about 1000 divided by 2 to the power k possibilities remain. With 9 questions, we can only distinguish 2 to the power 9, or 512 cases, which is not enough for 1000 numbers. With 10 questions, we distinguish 2 to the power 10, or 1024 cases, which is enough. The answer is therefore 10 questions in the worst case. This principle is that of binary search, with complexity O(log n).
Detecting a Cycle in a Linked List Without Extra Memory
Developer interview question on data structures and memory complexity
A linked list is a sequence of nodes, each of which points to the next one. Sometimes a node points back to a node already encountered: the list then forms a loop and never ends. How can you detect whether a loop exists without using extra memory proportional to the size of the list?
Need a hint?
Imagine two runners going through the list at different speeds: what happens if they run forever around a loop?
Show the answer and the solution
Answer: Floyd's algorithm: one pointer advances one node at a time, the other advances two; if they meet, there is a loop (O(n) time, O(1) memory).
The reasoning
Two pointers start at the beginning of the list: the tortoise moves one node per step, the hare moves two nodes per step. If the list ends, the hare reaches the end and we conclude there is no loop. If a loop exists, both pointers eventually enter it: the hare then catches up with the tortoise, since it gains one node at each step, and they meet on the same node. The number of steps is proportional to the size of the list, so the complexity is O(n) in time. Since only two pointers are stored, the extra memory is O(1).
Frequently asked questions
What kinds of riddles are on this tech page?
The page gathers four algorithm riddles: the two eggs and 100 floors question, finding a missing number in an array, finding a number between 1 and 1000 with yes or no questions, and detecting a loop in a linked list. Each comes with a short method and a time and memory cost.
Do you need to know how to code to solve these riddles?
No: the method is first described in sentences, for example halving the number of possibilities at each question, before being translated into code. The code comes afterwards, once the reasoning and its cost are settled.
How do you prepare for these algorithm riddles?
For each riddle, state the method, then give its time and memory cost, as the solutions on this page do. Start with problems that split the space of possibilities, then move on to data structures such as linked lists.
What next?
Reasoning improves like memory: by practising often. Next, test yourself on our general knowledge quizzes.