Puzzles
I love puzzles, especially hard algorithmic challenges. Here are some of
my favorites, most of which I've been asked in interviews, used in
interviews, or plan to use in interviews. Some of them are just fun, even
though they wouldn't make good interview questions.
You can email me at gundlach at gmail for hints.
Jump to:
Deluge
Picture a two-dimensional mountainscape, like a bar graph of a stock's
price over the course of a month. A giant rainstorm comes and rains over
the mountainscape. When the storm is over, water has filled every valley
to the brim across the mountainscape.
Write a function that takes in an array of heights of the
mountainscape and returns the number of units of water retained after the
storm.
Example: [50, 40, 30, 20, 30, 20, 30, 40, 50] represents a single valley,
and it would hold 140 units of water.
Example: [20, 30, 40, 50, 40, 30, 20] represents a single mountain, and
so all the water would run off the edge and nothing would be retained.
Example: [20, 30, 40, 50, 40, 50, 40, 30, 20] represents a mountain with
a little valley at its peak, and it would store 10 units of water in the
valley.
It can be done in linear time, constant space.
Dividing
Write a function that takes in an array of integers A and returns
a new array B. Each slot B[i] should be equal to the product of A's
elements, divided by A[i].
The catch: you can't use the divide operator, or re-implement it using
other operators like subtraction or log.
Example: if A=[3, 3, 4, 5, 1], B=[180/3, 180/3, 180/4, 180/5, 180/1],
which is [60, 60, 45, 36, 180].
It can be done in linear time, constant space.
Deduping
Write a function that takes in an array of items and returns a
copy of that array with all duplicate items removed.
Example: [A, C, B, C, A, C, A, A] returns [A, C, B].
Example: [A, B, C, D] returns [A, B, C, D].
To make it harder:
- Don't modify the input array -- return a new array.
- Preserve the order of the inputs ([A1, B1, A2, B2] shouldn't return
[A2, B1], it should return [A1, B1].)
- Write a version that preserves the last instance of each
duplicate (e.g. [A1, B1, A2, C1, B2] returns [A2, C1, B2].)
- Write a version that preserves the kth instance of each
duplicate (e.g. if k=3, [A1, B1, C1, A2, B2, A3, B3, C2] returns
[A3, B3].)
All the above can be done in linear time and space.
iPads
You buy a container of used iPads on eBay. The seller tells you that
- 20% of the shipment are in perfect condition
- 50% of the shipment have broken screens
- 40% of the shipment have broken wifi
What percentage of them have an unbroken screen and broken
wifi? How did you get your answer?
Sub hunt
You're hunting a submarine who is on an infinite number line. It moves
at a constant integer velocity per second. It started at some integer
position, so you know that every second it will be at an integer position.
Unfortunately, you don't know what position the sub started at, nor do you
know the sub's velocity.
Your only way to find the sub is to drop a depth charge. You may drop
one per second, anywhere on the number line that you like. It will
either hit the sub and you win, or miss the sub and you can try again
the following second.
You have infinite time to hunt the sub, and infinite depth charges.
You are a very patient hunter.
Is it possible to know for certain that you will eventually hit the
sub?
Example:
- At second 0 you drop a charge at position 100. Miss.
- At second 1 you drop a charge at position -1,000,000. Miss.
- At second 2 you drop a charge at position 4 billion. Miss.
- At second 3 you drop a charge at position 4 billion. Miss.
- At second 4 you drop a charge at position 0. Hit!
In this example, the sub was traveling at -20 units/second, and at second
0 was at position 80, so you hit him. Good job, captain!
Warning: I ain't never met nobody who can solve this, including
myself, without help. Don't feel bad.