Round 1
Questions: You are given a binary grid of size B x A where:
- 1 represents a fresh orange.
- 0 represents an empty cell.
- Your task is to determine the minimum number of rotten oranges (represented by 2s) that need to be placed in the grid such that all the fresh oranges (represented by 1s) are eventually rotted.
- A rotted orange can rot all adjacent fresh oranges. Adjacent means that the fresh orange is connected in any of the four cardinal directions: up, down, left, or right. You only need to place rotten oranges (i.e., 2s) in positions where they can cover multiple fresh oranges.
Input
1 1 1 1 0 0 1 0 0
Output : 1
Observation :
- There are 6 fresh oranges (represented by 1s).
- The grid contains some empty spots (represented by 0s).
- If you place a rotten orange at the position (1, 1) (the middle position in the grid), it will rot all adjacent fresh oranges.
- Placing one rotten orange at (1, 1) will rot the following oranges: (0, 0), (0, 1), (1, 0), (2, 0)
- Thus, only 1 rotten orange is required to rot all fresh oranges.
Input
1 0 0 0 0 1 0 0 0 1 0 0
Output : 3
Observation
- There are 3 fresh oranges in total.
- The optimal solution is to place rotten oranges at the following positions:
- Place one rotten orange at (0, 1), which rots the fresh orange at (0, 0).
- Place another rotten orange at (0, 2), which rots the fresh orange at (1, 2).
- Finally, place a third rotten orange at (2, 0), which rots the fresh orange at (3, 0).
- Thus, it requires 3 rotten oranges to rot all the fresh oranges.
Brute Force Approach
- Identify all fresh oranges (represented by 1)
- Generate all possible combinations of rotten oranges (represented by 0)
- Check if a combination rots all fresh oranges
- Store the minimum number of rotten oranges needed and return
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.