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 Bytedance.

What role is this question designed for?

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

Solve Sliding Window and Grid Search | Bytedance Coding Question

Quick Overview

This question evaluates proficiency in string algorithms and constrained shortest-path/search problems, covering sliding-window techniques for bounded-distinct substrings and grid pathfinding with stateful fuel, recharge mechanics, and cost accumulation.

Solve Sliding Window and Grid Search

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

In a Software Engineer phone screen, the candidate was asked to solve two coding problems. 1. **Longest substring with at most k distinct characters** Given a string `s` and an integer `k`, return the length of the longest contiguous substring that contains at most `k` distinct characters. Example: - Input: `s = "eceba"`, `k = 2` - Output: `3` 2. **Minimum-cost path in a grid with fuel and recharge cells** You are given an `m x n` grid with the following inputs: - `cost[i][j]`: the cost to enter cell `(i, j)` - `blocked[i][j]`: `true` if cell `(i, j)` cannot be entered - `recharge[i][j]`: `true` if entering cell `(i, j)` immediately refills your fuel back to `K` - `K`: the maximum fuel capacity Start at cell `(0, 0)` and reach cell `(m - 1, n - 1)`. Assume the start and destination cells are not blocked. Rules: - You may move one step at a time in the four cardinal directions: up, down, left, or right. - Each move consumes `1` unit of fuel. - You start with `K` units of fuel. - Every time you enter a cell, add that cell's `cost` to the total cost. The starting cell's cost must also be counted. - If you enter a recharge cell, your fuel is reset to `K` after the move. - Reaching the destination with exactly `0` fuel is allowed. Return the minimum total cost to reach the destination, or `-1` if it is impossible. **Follow-up:** If `K` is very large, how would you improve on an `O(m * n * K)` state-space solution?

Quick Answer: This question evaluates proficiency in string algorithms and constrained shortest-path/search problems, covering sliding-window techniques for bounded-distinct substrings and grid pathfinding with stateful fuel, recharge mechanics, and cost accumulation.

Part 1: Longest Substring With At Most K Distinct Characters

Given a string s and a non-negative integer k, return the length of the longest contiguous substring that contains at most k distinct characters.

Constraints

0 <= len(s) <= 200000
0 <= k <= len(s)
s may contain any printable characters

Examples

Input: ('eceba', 2)

Expected Output:

Explanation: The longest valid substring is 'ece', which has length 3.

Input: ('aa', 1)

Expected Output:

Explanation: The whole string contains only 1 distinct character.

Input: ('abaccc', 2)

Expected Output:

Explanation: The longest valid substring is 'accc'.

Input: ('', 3)

Expected Output:

Explanation: An empty string has no substrings, so the answer is 0.

Input: ('abc', 0)

Expected Output:

Explanation: With k = 0, no non-empty substring is allowed.

Hints

Try maintaining a sliding window [left, right] that always satisfies the constraint.
Use a frequency map so you can quickly tell when the window has more than k distinct characters.

Part 2: Minimum-Cost Path in a Grid With Fuel and Recharge Cells

You are given three m x n grids: cost, blocked, and recharge, plus an integer K. Start at cell (0, 0) with K units of fuel and reach (m - 1, n - 1). You may move one step at a time in the four cardinal directions. Each move consumes 1 fuel. Entering a cell adds that cell's cost to the total cost, including the starting cell. Blocked cells cannot be entered. If you enter a recharge cell, your fuel is immediately reset to K after the move. Reaching the destination with exactly 0 fuel is allowed. Return the minimum total cost, or -1 if the destination cannot be reached.

Constraints

1 <= m, n <= 30
0 <= cost[i][j] <= 10^6
0 <= K <= 60
blocked, recharge, and cost have the same dimensions
The start and destination cells are not blocked
All costs are non-negative integers

Examples

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

Expected Output:

Explanation: One minimum-cost path is (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2), with total cost 1 + 2 + 1 + 1 + 1 = 6.

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

Expected Output:

Explanation: The recharge cell allows the trip to continue: total cost is 1 + 1 + 1 + 1 = 4.

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

Expected Output:

Explanation: The destination is 2 moves away, but only 1 unit of fuel is available and there is no recharge.

Input: ([[7]], [[False]], [[True]], 0)

Expected Output:

Explanation: Start and destination are the same cell, so only the starting cell's cost is counted.

Hints

A state is not just a cell; the remaining fuel matters too.
Because all costs are non-negative, Dijkstra's algorithm over states (row, col, fuel) is a good fit.

Part 3: Minimum-Cost Grid Path When K Is Very Large

This problem uses the same grid rules as Part 2, but now K may be as large as 10^9. A solution whose time or memory depends linearly on K will be too slow. Compute the minimum total cost to reach the destination, or -1 if it is impossible.

Constraints

1 <= m, n <= 60
0 <= cost[i][j] <= 10^6
0 <= K <= 10^9
blocked, recharge, and cost have the same dimensions
The start and destination cells are not blocked
All costs are non-negative integers

Examples

Input: ([[1, 100, 100], [1, 100, 1], [1, 1, 1]], [[False, False, False], [False, False, False], [False, False, False]], [[False, False, False], [False, False, False], [False, False, False]], 1000000000)

Expected Output:

Explanation: Fuel is effectively unlimited for this grid, so the answer is the cheapest weighted path: down, down, right, right.

Input: ([[1, 1], [1, 1]], [[False, True], [True, False]], [[False, False], [False, False]], 1000000000)

Expected Output:

Explanation: The destination is disconnected by blocked cells.

Input: ([[9]], [[False]], [[False]], 0)

Expected Output:

Explanation: Single-cell grid: the start is already the destination.

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

Expected Output:

Explanation: Even in the optimized version, moderate K values must still be handled correctly; the recharge cell makes the trip possible.

Hints

Between two refuels, an optimal path never needs to revisit a cell when all costs are non-negative.
That means the useful fuel level can be capped by the number of traversable cells minus 1. If fuel can already cover any simple path, you can ignore fuel entirely and run ordinary Dijkstra on the grid.

Quick Overview