# Counting Black Holes with Quadtree Binary Search

#### Watch someone solve the counting black holes with quadtree binary search problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

### Interview Summary

#### Problem type
Counting Black Holes with Quadtree Binary Search

#### Interview question
Given the bottom-left and top-right coordinates of a 2D region of space (with coordinate values ranging from 0 to 1,000), and a black-box helper function `blackhole_present(bottom_left, top_right)` that returns `true` if one or more black holes exist within a given sub-region, design an efficient algorithm to count the total number of black holes in the region. The challenge is that each call to the helper function is expensive, so a brute-force, cell-by-cell scan is impractical; the solution must minimize the number of calls using a divide-and-conquer, quad-search strategy.

### Interview Feedback

**Feedback about Distinguished Dromedary (the interviewee)**

- Advance this person to the next round?
  -  Yes
- How were their technical skills? 4/4
- How was their problem solving ability? 4/4
- What about their communication ability? 4/4

#### Strengths and what went well:
- **Communication:** 
  - At all time I could understand your thought process. You did very well in explaining the different approaches for a solution as well as pros and cons. You did a good job in writing your thinking on the IDE for the interviewer to see as well as going over the examples, edge cases, etc...
  - You received my feedback candidly and applied it right away, as well as asking clarifying questions.

- **Problem Solving**
  - You did an excellent progression from proposing a brute force solution to an optimized binary search.
  - Great job in figuring out the particular quad-binary search variant as well as the formula for dividing the coordinates in squares
  - You proactively identified the base cases of the recursive solution and how to go about counting the black holes

- **Coding**
  - Code was syntactically correct, extensible, and well formatted.
  - You dry ran the solution with example inputs to demonstrate it works and has no bugs

#### Areas of Improvement:
- **Communication:** Write down the approach of every proposed solution concisely.
- **Problem solving:** 
  - Review problems that have complex recursive branching and their time and space complexity.
  - Ask clarifying questions more thoroughly.

- **Coding:**  
  - Add a validation step to discard bad inputs. 
  - Add minimal comments to the code.

#### Advise for Future interviews 
- Track practice on a spreadsheet and identify areas for improvement.
- Be proactive in asking clarifying questions about variables, edge cases, expected outcomes, etc...

### Interview Transcript

#### Ferocious Lightning:
Hello. Hi, can you hear me?

#### Distinguished Dromedary:
Good, how are you?

#### Ferocious Lightning:
Not bad. Let's proceed.

#### Distinguished Dromedary:
Sure, I'm a software engineer. I've been working for about 3.5 years now. I'm focusing on time management and edge cases for technical problems.

#### Ferocious Lightning:
Okay, let's go straight into a hard problem.

### Problem Details

*Given:* bottom-left and top-right coordinates with black holes present.
*Task:* Design an efficient algorithm using divide-and-conquer to count them.

### Proposed Solution
1. **Base Cases:**
   - Return 0 if `blackhole_present` returns false.
   - Return 1 if coordinates are the same.
2. **Divide the Region into Quadrants:*
   - Recursively call `count_blackholes` for four quadrants.
3. **Summation:** Return total count from all four quadrants.

### Time and Space Complexity
- Time Complexity: O(m log n)
- Space Complexity: O(M)

### Final Remarks
- Regular practice and understanding of algorithm patterns is crucial.

Thank you for your feedback: Keep practicing!