InternDoor

Can every flood be avoided?

Hardgreedy · binary search · union-find

Reported in interviews at (where)

  • MongoDB

All lakes start empty. On day i, if rains[i] > 0, it rains over lake number rains[i] and fills it; if that lake was already full, it floods. If rains[i] == 0, the day is dry and you may empty any one lake of your choice (emptying an empty lake does nothing).

Return true if you can choose what to empty on the dry days so that no lake ever floods, and false if a flood cannot be avoided.

Example 1
Input
rains = [4,0,7,4,0,7]
Output
true

Empty lake 4 on day 1 and lake 7 on day 4, each just before it rains there again.

Example 2
Input
rains = [3,0,8,8]
Output
false

The only dry day comes before lake 8 is first filled, so it cannot help when lake 8 is filled a second time.

Limits

  • 1 <= rains.length <= 100000
  • 0 <= rains[i] <= 1000000000

Hints

Hint 1

Do not decide on a dry day what to empty. Wait until rain is about to fall on a lake that is already full.

Hint 2

Then use the earliest unused dry day after that lake was last filled. Finding it quickly takes a sorted set, or a "next free dry day" pointer kept with path compression.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.