Avoid Flood in The City

Avoid Flood in The City

What is this problem about?

The Avoid Flood in The City interview question presents a scenario with several lakes. On a rainy day, rain falls over a specific lake. If it rains on a lake that is already full, it floods. On a sunny day, you can choose one full lake to dry. You are given an array representing the weather for each day (0 for sunny, x > 0 for rain on lake x). The goal is to find a schedule for drying lakes that avoids all floods. This Avoid Flood in The City coding problem is a greedy strategy challenge with future-lookahead logic.

Why is this asked in interviews?

Google and Amazon ask this to test advanced data structure usage. It requires a Greedy approach: when it's sunny, which lake should you dry? The best choice is the lake that is scheduled to receive rain the soonest. This tests your ability to use Hash Maps for tracking and Binary Search or Heaps to find the optimal dry day.

Algorithmic pattern used

This uses the Array, Hash Table, Binary Search, Heap (Priority Queue), Greedy interview pattern.

1. Store the indices of sunny days in a sorted list.
2. Use a Hash Map to track which lakes are currently full and when they were last rained on.
3. When a lake is about to be rained on again, use binary search to find the earliest available sunny day after its last rain.

Example explanation

rains = [1, 2, 0, 1, 2]

• Day 0: Rain on 1. Lake 1 is full.
• Day 1: Rain on 2. Lake 2 is full.
• Day 2: Sunny! Store this day.
• Day 3: Rain on 1. Flood! We must use our sunny day (Day 2) to dry Lake 1.
• Day 4: Rain on 2. Flood! We have no more sunny days. Result: In this case, it's impossible.

Common mistakes candidates make

• Greedy Error: Drying the "wrong" lake on a sunny day (e.g., drying a lake that won't rain again for a long time).
• Time Complexity: Using a linear search to find a sunny day, leading to O(N^2) when O(N log N) is required.
• Ordering: Trying to dry a lake on a sunny day that occurred before the lake was even full.

Interview preparation tip

When you have a limited resource (sunny days) that must be used to prevent a future failure (flood), always look for the "earliest upcoming failure" to prioritize your resource allocation.