Implement encoding validation and grid shortest path
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.
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.
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.