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 hard 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 grid shortest-path and tree DP | TikTok Coding Question

Quick Overview

This question pair evaluates proficiency in fundamental algorithmic techniques: finding shortest paths in a grid via breadth-first search and applying dynamic programming on trees to maximize a sum under adjacency constraints, assessing graph traversal, state management, optimal substructure recognition, and complexity handling.

Solve grid shortest-path and tree DP

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

### Problem A — Shortest path in a maze (BFS) You are given a 2D grid representing a maze: - `grid[r][c]` is either `'.'` (open cell) or `'#'` (wall). - You are also given a start coordinate `S = (sr, sc)` and an end coordinate `E = (er, ec)`. - From an open cell, you may move **up/down/left/right** by 1 cell (no diagonals). - You cannot move outside the grid or into walls. **Task:** Return the minimum number of steps from `S` to `E`. If `E` is unreachable, return `-1`. **Input (conceptual):** `grid`, `S`, `E` **Output:** minimum steps as an integer **Constraints (typical):** - `1 <= rows, cols <= 2000` (assume potentially large) - Start/end are within bounds and on open cells. --- ### Problem B — Max sum of non-adjacent nodes in a binary tree You are given the root of a binary tree where each node has an integer value (can be 0 or positive). You want to select a set of nodes to maximize the sum of their values subject to the constraint: - If you select a node, you **cannot** select its direct children. **Task:** Return the maximum achievable sum. **Input (conceptual):** `root` of a binary tree **Output:** maximum sum as an integer **Constraints (typical):** - Number of nodes up to `10^5` - Values up to `10^4`

Quick Answer: This question pair evaluates proficiency in fundamental algorithmic techniques: finding shortest paths in a grid via breadth-first search and applying dynamic programming on trees to maximize a sum under adjacency constraints, assessing graph traversal, state management, optimal substructure recognition, and complexity handling.

Part 1: Shortest Path in a Maze

You are given a rectangular maze represented as a list of strings. Each cell is either '.' for an open space or '#' for a wall. You are also given a start coordinate and an end coordinate, both as zero-indexed (row, col) pairs. From any open cell, you may move exactly one step up, down, left, or right. You may not move outside the grid or into a wall. Implement `solution(grid, start, end)` and return the minimum number of steps needed to reach `end` from `start`. If the end is unreachable, return `-1`.

Constraints

1 <= number of rows, columns <= 2000
All rows in `grid` have the same length
`start` and `end` are within bounds
Moves are allowed only in 4 directions: up, down, left, right
For valid inputs, `start` and `end` are on open cells

Examples

Input: (['...', '.#.', '...'], (0, 0), (2, 2))

Expected Output: 4

Explanation: The wall in the center blocks the direct route, so the shortest path goes around it in 4 steps.

Input: (['.#', '##', '..'], (0, 0), (2, 1))

Expected Output: -1

Explanation: The start cell has no reachable open neighbors, so the end cannot be reached.

Input: (['.'], (0, 0), (0, 0))

Expected Output: 0

Explanation: Edge case: start and end are the same cell.

Input: (['..#..', '#.#.#', '#...#', '###.#', '.....'], (0, 0), (4, 4))

Expected Output: 8

Explanation: A narrow valid route exists through the middle and lower rows; the shortest path length is 8.

Hints

Because every move costs the same amount, breadth-first search explores cells in increasing distance order.
Mark cells as visited as soon as you add them to the queue, so you never process the same cell twice.

Part 2: Maximum Sum of Non-Adjacent Tree Nodes

You are given a binary tree and must choose a set of nodes with maximum total value. The restriction is that if you choose a node, you may not choose either of its direct children. For this problem, the tree is provided as a level-order list named `values`, where `None` represents a missing child. Implement `solution(values)` and return the maximum sum you can obtain.

Constraints

0 <= number of nodes <= 100000
0 <= node values <= 10000
The tree is represented in level-order with `None` for missing children
You should aim for an O(n) solution

Examples

Input: [3, 2, 3, None, 3, None, 1]

Expected Output: 7

Explanation: Choose the root (3), the left-right grandchild (3), and the right-right grandchild (1). Total = 7.

Input: [3, 4, 5, 1, 3, None, 1]

Expected Output: 9

Explanation: The optimal choice is 4 + 5 = 9. Taking the root would lead to a smaller total.

Input: []

Expected Output: 0

Explanation: Edge case: an empty tree has sum 0.

Input: [10]

Expected Output: 10

Explanation: Edge case: with only one node, the best answer is to take it.

Input: [4, 1, None, 2, None, 3]

Expected Output: 7

Explanation: The best selection is 4 and 3, which are not direct parent and child.

Hints

For each node, track two answers: the best sum if you take this node, and the best sum if you skip it.
A postorder traversal is useful because a parent's answer depends on results already computed for its children.

Quick Overview