You can email me at gundlach at gmail for hints.

Jump to:

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.

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.

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.

- 20% of the shipment are in perfect condition
- 50% of the shipment have broken screens
- 40% of the shipment have broken wifi

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!

*Warning: I ain't never met nobody who can solve this, including
myself, without help. Don't feel bad.*