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.

Solve UTF-8 Validation & Shortest Path

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question LeetCode 393. UTF-8 Validation LeetCode 1091. Shortest Path in Binary Matrix https://leetcode.com/problems/utf-8-validation/description/ https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

Quick Answer: This pair of problems evaluates skills in data encoding interpretation and graph traversal, examining competency in validating byte-oriented input formats and computing shortest paths on binary matrices.

UTF-8 Validation

Given an integer array `data` representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters). A character in UTF-8 can be from 1 to 4 bytes long, subjected to the following rules: 1. For a 1-byte character, the first bit is a `0`, followed by its Unicode code. 2. For an n-bytes character, the first n bits are all ones, the (n+1)-th bit is `0`, followed by n-1 bytes with the most significant 2 bits being `10`. This is how the UTF-8 encoding would work: ``` Number of Bytes | UTF-8 Octet Sequence | (binary) --------------------+----------------------------------------- 1 | 0xxxxxxx 2 | 110xxxxx 10xxxxxx 3 | 1110xxxx 10xxxxxx 10xxxxxx 4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx ``` `x` denotes a bit in the binary form of a byte that may be either `0` or `1`. **Note:** The input is an array of integers. Only the least significant 8 bits of each integer are used to store the data. This means each integer represents only 1 byte of data. **Example 1:** ``` Input: data = [197,130,1] Output: true Explanation: data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character. ``` **Example 2:** ``` Input: data = [235,140,4] Output: false Explanation: data represents the octet sequence: 11101011 10001100 00000100. The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character. The next byte is a continuation byte which starts with 10 and that's correct. But the second continuation byte does not start with 10, so it is invalid. ```

Constraints

1 <= data.length <= 2 * 10^4
0 <= data[i] <= 255
Only the least significant 8 bits of each integer are used as data.

Examples

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

Expected Output: True

Explanation: Octets 11000101 10000010 00000001 = a 2-byte char (110xxxxx + 10xxxxxx) then a 1-byte char (0xxxxxxx). Valid.

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

Expected Output: False

Explanation: 11101011 declares a 3-byte char; the second continuation 00000100 does not start with 10, so invalid.

Input: ([255],)

Expected Output: False

Explanation: 11111111 is not a valid leading byte (no UTF-8 char starts with five 1s).

Input: ([0],)

Expected Output: True

Explanation: 00000000 is a valid 1-byte character.

Input: ([],)

Expected Output: True

Explanation: Edge case: an empty sequence is vacuously valid.

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

Expected Output: True

Explanation: 11110000 declares a 4-byte char; the three following bytes all start with 10. Valid.

Input: ([145],)

Expected Output: False

Explanation: 10010001 starts with 10, which can only be a continuation byte — it cannot lead a character.

Input: ([237, 145, 191, 145],)

Expected Output: False

Explanation: 11101101 declares a 3-byte char (1 leader + 2 continuations), but a 4th continuation byte follows with no leader, so it is invalid.

Hints

Track how many continuation bytes you still expect. When that counter is 0 you are reading a leading byte; otherwise you are reading a continuation byte.
Mask each integer with `& 0xFF` first, then inspect the top bits to classify it: `0xxxxxxx` is a 1-byte char, `110xxxxx` starts 2 bytes, `1110xxxx` starts 3, `11110xxx` starts 4.
Every continuation byte must start with `10`. If a leading byte is malformed (e.g. starts with `10` or `11111`), or you run out of bytes mid-character, the encoding is invalid. At the end the expected-continuation counter must be 0.

Shortest Path in Binary Matrix

Given an `n x n` binary matrix `grid`, return the length of the shortest clear path in the matrix. If there is no clear path, return `-1`. A clear path in a binary matrix is a path from the top-left cell (i.e., `(0, 0)`) to the bottom-right cell (i.e., `(n - 1, n - 1)`) such that: - All the visited cells of the path are `0`. - All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner). The length of a clear path is the number of visited cells of this path. **Example 1:** ``` Input: grid = [[0,1],[1,0]] Output: 2 ``` **Example 2:** ``` Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4 ``` **Example 3:** ``` Input: grid = [[1,0,0],[1,1,0],[1,1,0]] Output: -1 Explanation: The start cell is blocked. ```

Constraints

n == grid.length == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Examples

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

Expected Output: 2

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

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

Expected Output: 4

Explanation: (0,0)->(0,1)->(0,2)->(1,2)->(2,2) skirts the right edge; 4 cells.

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

Expected Output: -1

Explanation: The start cell (0,0) is blocked, so no clear path exists.

Input: ([[0]],)

Expected Output: 1

Explanation: Edge case: a 1x1 open grid — start equals end, path length is 1.

Input: ([[1]],)

Expected Output: -1

Explanation: Edge case: a 1x1 blocked grid — start is also the end and it is 1, so -1.

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

Expected Output: 3

Explanation: A fully open grid: the main diagonal (0,0)->(1,1)->(2,2) gives the shortest 3-cell path.

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

Expected Output: -1

Explanation: The end cell (1,1) is blocked, so no clear path reaches it.

Hints

Because every move has the same cost (one cell), the shortest path is found by Breadth-First Search, not DFS.
Movement is 8-directional, so each cell has up to 8 neighbors: the four orthogonal plus the four diagonal offsets.
Handle the trivial blockers first: if the start `(0,0)` or the end `(n-1,n-1)` is `1`, return -1 immediately. Mark cells visited when you enqueue them (not when you dequeue) to avoid revisiting and inflating the queue.

Quick Overview

This pair of problems evaluates skills in data encoding interpretation and graph traversal, examining competency in validating byte-oriented input formats and computing shortest paths on binary matrices.