Round 1
Questions: Design a data structure to represent a terrain of islands in a sea of water, where each island is denoted by a coordinate (x, y). The data structure needed to support two methods:
add(x, y)– Add a piece of land.is_island(x, y)– Query whether a coordinate is land or water.
Follow-up question:
- "Add another method,
island_count()– which returns the number of islands at the time of the query."
Candidate's Approach
Initially, the candidate considered using a matrix and then a list but realized that a simple set could effectively represent the islands. The candidate suggested using Union-Find to efficiently handle the island count without recalculating it every time. However, they struggled with the implementation, particularly with path compression and logic gaps, leading to a rushed completion of the code.
Interviewer's Feedback
The interviewer pointed out gaps in the candidate's logic, such as not checking the nei for water and not properly defining what id represented. The interviewer seemed dismissive and in a hurry to wrap up the interview.