## Problem You have an `n x n` chessboard with rooks placed at given positions. For each rook, find the nearest other rook by Manhattan distance. If multiple rooks are equidistant, return the one with the smallest row index, then smallest column index. ```python def nearest_rook( n: int, rooks: List[Tuple[int,int]] ) -> List[Tuple[int,int]]: # Returns list where result[i] = position of nearest rook to rooks[i] ... ``` **Example:** ``` n = 8 rooks = [(0,0), (0,3), (5,0)] nearest_rook(8, rooks) -> [(0,3), # nearest to (0,0) is (0,3), dist=3 (0,0), # nearest to (0,3) is (0,0), dist=3 (0,0)] # nearest to (5,0) is (0,0), dist=5 ``` ## Follow-ups 1. Your brute-force is O(k^2) for k rooks. How do you use a spatial index (k-d tree) to improve this? 2. How does the answer change if distance is Euclidean instead of Manhattan? 3. For a rook that can attack along rows and columns, find the nearest rook it can attack in one move. 4. If rooks are added and removed dynamically, what data structure supports O(log k) nearest-neighbor queries?

InterviewDB Question

Nearest Rook - Find the Closest Rook on a Chess Board

phone

Question Details

Problem You have an n x n chessboard with rooks placed at given positions. For each rook, find the nearest other rook by Manhattan distance. If multiple rooks are equidistant, return the one with the smallest row index, then smallest column index. Example: Follow-ups Your brute-force is O(k^2) for k rooks. How do you use a spatial index (k-d tree) to improve this? How does the answer change if distance is Euclidean instead of Manhattan? For a rook that can attack along rows and columns, find the…

Full Details

🔒

Unlock all Two Sigma questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a two sigma interview during the phone round.

It covers the following topics: Coding, Onsite, Phone .

Topics

Coding Onsite Phone

Nearest Rook - Find the Closest Rook on a Chess Board

Question Details

Full Details

About This Question

Topics

More Two Sigma Interview Questions