Count islands and implement BFS variant
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a 2D grid of characters '1' (land) and '0' (water), count the number of distinct land regions where connectivity is four-directional (up, down, left, right). Implement a solution of your choice that runs in O(mn) time and explain its correctness and complexity. Then implement a second version that uses breadth-first search explicitly. Handle edge cases such as an empty grid, all-water grid, and very large dimensions, and provide tests to validate your solution on multiple nontrivial cases.
Quick Answer: This question evaluates a candidate's ability to apply grid and graph traversal concepts—counting connected components with four-directional connectivity—implement breadth-first search variants, and reason about correctness and linear-time (O(mn)) complexity.