How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Solve two grid problems (islands + min-cost path)

Quick Overview

This pair of problems evaluates grid-based algorithm competencies, specifically connected-component detection and translation-invariant shape recognition for distinct-island counting, plus shortest-path/graph-search reasoning under unit-change costs for the directed-grid minimum-cost path.

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two separate coding questions. ## Problem A: Count distinct islands (translation-equivalent) Given an `m x n` binary grid `grid` (0 = water, 1 = land), an **island** is a maximal 4-directionally connected group of `1`s. Two islands are considered the **same shape** if one can be translated (shifted up/down/left/right) to match the other exactly. Rotations and reflections **do not** count as the same. **Task:** Return the number of **distinct** island shapes in the grid. **Input:** `grid: List[List[int]]` **Output:** `int` **Notes/constraints (assume typical interview constraints):** - `1 <= m, n <= 500` - Grid can be large; aim for about `O(mn)` time. --- ## Problem B: Minimum cost to create a valid path in a directed grid You are given an `m x n` grid `dir` where each cell contains a direction pointing to a neighbor: - `1` = right, `2` = left, `3` = down, `4` = up Starting at `(0,0)`, if you follow directions, you move to the indicated neighboring cell (if within bounds). A **valid path** is a path that reaches `(m-1, n-1)`. You may **change** the direction in any cell at a cost of `1` per changed cell (each cell can be changed to any of the 4 directions). **Task:** Return the minimum total cost to ensure there exists at least one valid path from `(0,0)` to `(m-1,n-1)`. **Input:** `dir: List[List[int]]` **Output:** `int` **Notes/constraints (assume typical interview constraints):** - `1 <= m, n <= 1000` - Aim for near-linear time in number of cells.

Quick Answer: This pair of problems evaluates grid-based algorithm competencies, specifically connected-component detection and translation-invariant shape recognition for distinct-island counting, plus shortest-path/graph-search reasoning under unit-change costs for the directed-grid minimum-cost path.

Part 1: Count Distinct Translation-Equivalent Islands

You are given a rectangular binary grid where 0 represents water and 1 represents land. An island is a maximal group of land cells connected 4-directionally: up, down, left, or right. Two islands are considered the same shape if one can be translated, or shifted, to exactly match the other. Rotations and reflections do not count as the same shape. Return the number of distinct island shapes in the grid.

Constraints

1 <= len(grid) <= 500
1 <= len(grid[0]) <= 500
grid[i][j] is either 0 or 1
The grid is rectangular
Aim for O(m * n) time

Examples

Input: ([[0]],)

Expected Output: 0

Explanation: There is no land, so there are no island shapes.

Input: ([[1]],)

Expected Output: 1

Explanation: There is exactly one island consisting of one cell.

Input: ([[1, 1, 0, 0, 0], [1, 0, 0, 1, 1], [0, 0, 0, 1, 0], [1, 1, 0, 0, 0], [1, 0, 0, 1, 1]],)

Expected Output: 2

Explanation: There are multiple L-shaped islands with the same translation-normalized shape, plus one horizontal domino shape.

Input: ([[1, 1, 0, 1, 1], [1, 0, 0, 0, 1]],)

Expected Output: 2

Explanation: The two islands are mirror images, but reflections do not count as the same shape.

Input: ([[1, 0, 1], [0, 1, 0], [1, 0, 1]],)

Expected Output: 1

Explanation: Diagonal land cells are not connected, so there are five single-cell islands, all with the same shape.

Hints

For each island, record every land cell relative to the island's first discovered cell.
Store a canonical representation of each normalized island shape in a set.

Part 2: Minimum Cost to Create a Valid Path in a Directed Grid

You are given an m x n grid where each cell contains a direction: 1 means right, 2 means left, 3 means down, and 4 means up. Starting from cell (0, 0), following a cell's direction moves you to the indicated neighboring cell if that neighbor is inside the grid. You may change the direction of any cell to any of the four directions, with cost 1 per changed cell. Return the minimum total cost needed so that there exists at least one valid path from (0, 0) to (m - 1, n - 1).

Constraints

1 <= len(dir) <= 1000
1 <= len(dir[0]) <= 1000
dir[i][j] is one of 1, 2, 3, or 4
The grid is rectangular
Aim for near-linear time in the number of cells

Examples

Input: ([[1]],)

Expected Output: 0

Explanation: The start cell is already the destination.

Input: ([[1, 1, 3], [3, 2, 2], [1, 1, 4]],)

Expected Output: 0

Explanation: Following the existing directions already reaches the bottom-right cell.

Input: ([[1, 2], [4, 3]],)

Expected Output: 1

Explanation: Follow right from the start, then change the top-right cell to point down.

Input: ([[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]],)

Expected Output: 3

Explanation: At least three downward moves are needed, and each downward move requires changing a cell's direction.

Input: ([[4, 4, 4], [4, 4, 4], [4, 4, 4]],)

Expected Output: 4

Explanation: All arrows point upward, so every right or down move on a shortest path requires a direction change.

Hints

Model each cell as a graph node. Moving in the cell's current direction has cost 0; moving in any other valid direction has cost 1.
Because all edge weights are only 0 or 1, use 0-1 BFS with a deque instead of ordinary BFS.

Quick Overview