Katkat
Back

Handle Island Counting When the Grid Does Not Fit in Memory

ByteDanceSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the ability to adapt graph traversal algorithms (like BFS or DFS) to scenarios where the dataset exceeds primary memory, requiring disk-based processing or tiling strategies.

Problem Statement

You are given a massive binary matrix representing a map, where 1s represent land and 0s represent water. This map is too large to fit into RAM and is stored in a structured file format (e.g., partitioned on disk). Your task is to count the total number of distinct islands, where an island is formed by connecting adjacent 1s horizontally or vertically.

Design an algorithm or system approach to solve this when the grid is stored as N x M tiles, where each tile fits in memory, but the entire grid does not. Explain how you manage state across tile boundaries.

Constraints

  • The grid is divided into k x k tiles.
  • You can read/write tiles from/to disk.
  • You must identify islands that span across multiple tiles.

Example Scenario

If you have a 2x2 grid of tiles, where an island starts in Tile (0,0) and continues into Tile (0,1), your logic must treat these as a single connected component.

Requirements

  1. Define the data structure used to track island connectivity between tile boundaries.
  2. Provide the logic for updating component IDs when a merge occurs across tiles.
  3. Discuss the trade-offs between memory usage and disk I/O frequency.

Hints

Hint 1

Consider using a Disjoint Set Union (DSU) data structure to keep track of global island IDs.

Hint 2

Think about how to process tiles row-by-row or using a sliding window to identify boundary connections.

Hint 3

Could you rephrase this as a connectivity problem where you assign local IDs to island segments and then merge them based on edge intersections?

Follow-up questions

  • How would you handle the situation where the number of islands exceeds the capacity of your memory-resident DSU?
  • If the grid is highly sparse (mostly 0s), how can you optimize your disk I/O?
  • How would you modify your approach if the grid was distributed across multiple machines rather than just residing on a single disk?