In this mock programming interview, a software engineer with 3.5 years of experience preps for an upcoming interview by tackling a hard algorithmic problem. Watch as the interviewee works through problem clarification, proposes a brute-force baseline, and then derives an efficient recursive quad-search solution...all while managing time and communicating their thought process clearly. 🧩 The Problem: Counting Black Holes with Quadtree Binary Search (Hard) 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. Chapters - 0:00 Introductions & interview format - 4:10 Problem statement presented - 7:31 Clarifying questions: inputs, outputs, and constraints - 13:56 Brute-force approach & transition to binary/quad search - 30:41 Coding the recursive quad-search solution - 44:50 Dry run & edge case walkthrough - 50:40 Feedback session Concepts Problem Clarification & Constraint Gathering - Confirmed inputs (bottom-left and top-right coordinate pairs) and output (integer count of black holes) - Identified coordinate range (0–1,000 for both x and y axes) - Clarified behavior of the helper function, including single-cell queries and boundary conditions Brute-Force Baseline & Optimization Motivation - Proposed iterating over every cell as an O(n) time, O(1) space baseline - Identified the practical constraint on total helper function calls as the driver for optimization - Used the brute-force analysis to justify transitioning to a logarithmic approach Divide-and-Conquer (Quadtree) Strategy - Key insight: splitting a 2D region requires dividing into four quadrants, not two halves - Recursive structure: if a region returns false, prune immediately; if true, subdivide further - Base cases: return 0 if no black hole present, return 1 if the region collapses to a single coordinate point Coordinate Handling & Edge Cases - Carefully computed midpoints for both x and y axes to define quadrant boundaries - Added boundary guards to prevent out-of-bounds calls to the helper function (e.g., mid_x + 1 ≤ top_x) - Discussed edge cases: empty grid, single-row or single-column regions, and single-point regions Time & Space Complexity Analysis - Time complexity: O(m log n), where m is the number of black holes and n is the total number of cells - Space complexity discussion: tied to the recursive call stack depth rather than the black hole count - Interviewer noted the importance of thoroughly justifying space complexity, not just stating the result Interview Execution & Communication - Strong proactive communication: thought process was visible throughout, clarifying questions were well-timed - Brute-force solution was proposed early and used as a written baseline for optimization - Areas for improvement: read the problem output specification more carefully before proposing a return type; dry-run the code proactively rather than waiting to be prompted; consider wrapping the solution in an input-validation function for added polish 👉 Book coaching or watch more mock interviews: https://www.interviewing.io 📝 Interview transcript & feedback: https://interviewing.io/mocks/faang-python-black-hole-quadtree-search 🔗 Explore more FAANG interviews: https://interviewing.io/mocks?company=faang Disclaimer: All interviews are shared with explicit permission from the interviewer and interviewee. All candidates remain anonymous.