Bytedance·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Bytedance coding round, one problem that's basically a harder version of Number of Islands. Manageable if you've done the prep, but the rotation/reflection part is where people get tripped up.

Questions Asked (1)

Given a 2D grid with multiple islands, determine how many distinct island shapes exist, where two islands are considered the same shape if one can be translated, rotated, or reflected to match the other.

Algorithms & Data Structures

Author's notes

The basic translation-only version I had down cold.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, traverse the grid to identify each island using DFS/BFS, recording its cells. For each island, normalize its shape by generating all 8 symmetries (rotations and reflections) and translating each to a canonical form (e.g., min row and col at 0). Use a hash set to count distinct normalized shapes.

Pro tip: When normalizing, ensure you consider all 8 transformations and pick a canonical representation that is invariant under translation, rotation, and reflection. Also, handle edge cases like single-cell islands and large grids efficiently by using a set of tuples for shape signatures.

1. Identify Islands

Use DFS or BFS to find all connected components of land cells (1s) in the grid, collecting the coordinates of each island.

2. Normalize Each Island

For each island, generate all 8 possible transformations (4 rotations × 2 reflections) and translate each so that the minimum row and column are 0. Convert each transformed shape to a canonical tuple representation.

3. Canonicalize Shape

Among all transformed versions of an island, choose the lexicographically smallest tuple as the canonical signature for that island.

4. Count Distinct Shapes

Insert each island's canonical signature into a hash set. The number of distinct shapes is the size of the set.

Key Points to Mention

Graph traversal (DFS/BFS) to find islands
Translation normalization by subtracting min row and col
Generating all 8 symmetries: 4 rotations and 2 reflections
Canonical representation using sorted tuple of coordinates
Using a hash set to deduplicate shapes
Time and space complexity analysis: O(R*C) for traversal, O(K) per island for normalization

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.