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

What role is this question designed for?

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

Implement encoding validation and grid shortest path

Quick Overview

This question evaluates proficiency in bit-level data validation and graph traversal algorithms by testing byte-encoding validation using bit-pattern recognition and an 8-neighbor shortest-path search on a binary grid, and it falls under the Coding & Algorithms domain.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Part A — Byte-encoding validation: You are given an array of integers in [0, 255] representing bytes. Determine whether the sequence encodes valid characters under a variable-length scheme where: ( 1) A single-byte character starts with leading bit 0; ( 2) A multi-byte character uses k bytes for k in {2,3,4}, whose first byte has a prefix of exactly k ones followed by a zero (e.g., 110xxxxx, 1110xxxx, 11110xxx); ( 3) Each continuation byte starts with the bit pattern 10xxxxxx; ( 4) The sequence cannot end mid-character. Return true/false and specify the time and space complexity of your approach. Part B — 8-neighbor grid shortest path: Given an n×n grid of 0s (open) and 1s (blocked), find the length of the shortest path from (0, 0) to (n−1,n− 1) moving in any of the 8 directions to adjacent open cells. Count both start and end cells in the length; if no path exists, return −1. Discuss the algorithm and its complexity.

Quick Answer: This question evaluates proficiency in bit-level data validation and graph traversal algorithms by testing byte-encoding validation using bit-pattern recognition and an 8-neighbor shortest-path search on a binary grid, and it falls under the Coding & Algorithms domain.

Byte-Encoding (UTF-8) Validation

You are given an array of integers `data`, each in the range [0, 255], representing a sequence of bytes. Determine whether the sequence encodes valid characters under a variable-length scheme: 1. A single-byte character starts with a leading bit of `0` (i.e. `0xxxxxxx`). 2. A multi-byte character uses k bytes for k in {2, 3, 4}, whose first byte has a prefix of exactly k ones followed by a zero: `110xxxxx` (k=2), `1110xxxx` (k=3), `11110xxx` (k=4). 3. Each continuation byte must start with the bit pattern `10xxxxxx`. 4. The sequence cannot end in the middle of a character. Only the lowest 8 bits of each integer are used. Return `true` if the entire sequence is a valid encoding, otherwise `false`. Example: `data = [197, 130, 1]` → `true` (a 2-byte char `11000101 10000010` followed by the single byte `00000001`). `data = [235, 140, 4]` → `false` (`11101011` claims a 3-byte char, but `00000100` is not a valid continuation byte).

Constraints

1 <= data.length, but data may also be empty (an empty sequence is vacuously valid).
0 <= data[i] <= 255 (only the lowest 8 bits are used).
A character spans at most 4 bytes.

Examples

Input: ([197, 130, 1],)

Expected Output: True

Explanation: 11000101 (2-byte leader) + 10000010 (continuation) form one char, then 00000001 is a single-byte char. Valid.

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

Expected Output: False

Explanation: 11101011 claims a 3-byte char, 10001100 is a valid continuation, but 00000100 is not a continuation byte. Invalid.

Input: ([],)

Expected Output: True

Explanation: An empty sequence encodes zero characters and is vacuously valid.

Input: ([0],)

Expected Output: True

Explanation: 00000000 is a single-byte (ASCII) character.

Input: ([255],)

Expected Output: False

Explanation: 11111111 has more than 4 leading ones, which is not a valid leader.

Input: ([240, 162, 138, 147],)

Expected Output: True

Explanation: 11110000 is a 4-byte leader followed by three valid 10xxxxxx continuation bytes.

Input: ([237],)

Expected Output: False

Explanation: 11101101 is a 3-byte leader but the sequence ends with two continuation bytes missing (ends mid-character).

Input: ([128],)

Expected Output: False

Explanation: 10000000 is a continuation byte appearing where a leader is expected.

Input: ([145],)

Expected Output: False

Explanation: 10010001 begins with 10, a continuation pattern, but no leader preceded it.

Hints

Track how many continuation bytes you still expect. Start at 0.
When the counter is 0, classify the next byte as a leader: count the leading ones (0 → single byte, 2/3/4 → multi-byte, 1 or >4 → invalid).
When the counter is > 0, the byte must match 10xxxxxx; decrement the counter. At the very end the counter must be back to 0, otherwise the sequence ended mid-character.

Shortest Path in a Binary Grid (8 Directions)

Given an `n x n` grid where each cell is `0` (open) or `1` (blocked), return the length of the shortest clear path from the top-left cell `(0, 0)` to the bottom-right cell `(n-1, n-1)`. You may move to any of the 8 adjacent cells (horizontal, vertical, or diagonal) that are open. The path length counts the number of visited cells, including both the start and the end cell. If no such path exists, return `-1`. Note: if the start or the end cell is blocked, no path exists. Example: `grid = [[0,1],[1,0]]` → `2` (move diagonally from (0,0) to (1,1)). `grid = [[0,0,0],[1,1,0],[1,1,0]]` → `4`.

Constraints

1 <= n <= 100 (grid is n x n).
grid[i][j] is 0 (open) or 1 (blocked).
Movement is allowed to any of the 8 neighbors; only open cells may be entered.
Path length counts cells visited, including start and end.

Examples

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

Expected Output: 2

Explanation: Move diagonally from (0,0) to (1,1); 2 cells visited.

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

Expected Output: 4

Explanation: (0,0) -> (0,1) -> (0,2)/(1,2) -> (2,2); shortest path uses 4 cells.

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

Expected Output: -1

Explanation: Start cell (0,0) is blocked, so no path exists.

Input: ([[0]],)

Expected Output: 1

Explanation: Single open cell that is both start and end; path length is 1.

Input: ([[1]],)

Expected Output: -1

Explanation: The only cell is blocked, so there is no valid path.

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

Expected Output: 2

Explanation: Move diagonally from (0,0) to (1,1); 2 cells visited.

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

Expected Output: -1

Explanation: The destination is isolated by blocked cells; no path exists.

Hints

Because every step has equal cost (one cell), plain BFS from the start finds the shortest path in terms of cells.
Immediately return -1 if either the start or the destination cell is blocked.
Use all 8 direction offsets and a visited matrix; the distance stored when you first dequeue the destination is the answer.

Quick Overview