Coding interview: Validate a UTF-8 byte sequence

Prompt and scope

This is a bit-manipulation and character-encoding problem. The input is a byte array, not an already decoded Unicode string. Determine whether each scalar uses 1 to 4 bytes and reject truncated or malformed sequences. LeetCode 393 uses the same constraints: length at most 2 * 10^4, with each integer contributing its lowest 8 bits. RFC 3629 defines the 1–4 byte UTF-8 forms and the valid scalar-value range.

What the interviewer is testing

• Deriving the continuation count from the leading-byte pattern.
• Strictly checking the 10xxxxxx continuation prefix.
• Rejecting extra continuation bytes, truncation, and five-byte leading patterns.
• Producing a single pass with O(n) time and O(1) extra space.

Clarifications to ask first

Confirm whether every element is guaranteed to be in 0..255; otherwise reject out-of-range values first. Also clarify whether the task checks only byte shape or must reject overlong encodings, surrogate code points, and values above U+10FFFF. The LeetCode version focuses on byte shape; a production parser should apply the stricter RFC 3629 scalar-value rules.

A 30-second answer

Maintain remaining, the number of continuation bytes still required for the current character. For a leading byte, use its high-bit pattern to set 0, 1, 2, or 3; for a continuation byte, require (byte & 0b11000000) === 0b10000000 and decrement the counter. Reject an illegal leader, an unexpected continuation, or end-of-input with remaining !== 0. The scan keeps only this counter.

Step-by-step solution

1. Recognize leading-byte patterns

0xxxxxxx is a one-byte character; 110xxxxx, 1110xxxx, and 11110xxx require 1, 2, and 3 continuation bytes. Test prefixes with masks: check 0x80, then 0xE0, 0xF0, and finally 0xF8. If the 0xF8 test is still nonzero, the byte starts a five-byte-or-longer form and must be rejected.

2. Validate continuation bytes online

When remaining > 0, the current byte must match 10xxxxxx. Decrement after a successful check. An ASCII leader or another multi-byte leader in this state is immediately invalid. No backtracking or slicing is needed, and truncation is detected when input ends.

3. Reference implementation

isValidUtf8(bytes):
  remaining = 0
  for byte in bytes:
    if byte < 0 or byte > 255: return false
    if remaining > 0:
      if (byte & 0b11000000) != 0b10000000: return false
      remaining -= 1
      continue
    if (byte & 0b10000000) == 0:
      remaining = 0
    else if (byte & 0b11100000) == 0b11000000:
      remaining = 1
    else if (byte & 0b11110000) == 0b11100000:
      remaining = 2
    else if (byte & 0b11111000) == 0b11110000:
      remaining = 3
    else:
      return false
  return remaining == 0

4. Production-level strictness

Prefix counting alone accepts some overlong encodings, such as representing a value with three bytes when one would suffice, and may accept surrogate values. A production parser should accumulate the scalar value and check the minimum value for its length, the surrogate range, and the U+10FFFF ceiling; explicitly decide whether a BOM is allowed. State the exercise boundary first, then explain this extension instead of silently mixing rules.

5. Tests and complexity

Cover [197,130,1] as true, [235,140,4] as false, an isolated continuation [128], a truncated [226,130], a five-byte leader [248,128,128,128,128], and the empty array. Each byte is scanned once: O(n) time and O(1) extra space, where n is the array length.

Model answer

I separate leading-byte recognition from continuation-byte validation. A leader matching 0xxxxxxx, 110xxxxx, 1110xxxx, or 11110xxx sets remaining to 0, 1, 2, or 3; continuation state accepts only 10xxxxxx and decrements the counter. A five-byte leader, unexpected continuation, out-of-range element, or end-of-input with an incomplete character returns false. The implementation is one O(n) pass with O(1) space. For production, accumulate the scalar value to reject overlong encodings, surrogates, and values above U+10FFFF.

Common mistakes

• Counting continuation bytes without checking each 10 prefix.
• Treating 111110xx as a valid five-byte form.
• Forgetting the final remaining check and accepting truncation.
• Delegating to a language decoder without showing the bit-level invariant or error index.
• Mixing the LeetCode shape check with RFC scalar-value rules without stating the scope.
• Treating byte as signed and failing to normalize it to 0..255 before bit operations.

Follow-up questions

How would you return the first error index?

Return {valid, errorIndex, reason}. Record the current index when a leader, continuation, or end-of-input check fails. The scanning state stays unchanged, so callers can highlight the original byte.

How would you support chunked streaming input?

Keep remaining and the partial scalar state in a parser object between chunks. A character completes only after a later chunk supplies all continuation bytes; stream end with remaining != 0 is still a truncation error.

Why not use only a regular expression?

A regular expression can express some prefix rules, but a state machine is clearer for chunk boundaries, error indices, and scalar-value constraints. The counter uses constant space for arbitrarily long input and extends naturally to strict validation.

How do you reject overlong encodings?

Record the sequence length and accumulated value from the leader, then require the value to meet that length’s minimum range. Also reject 0xD800..0xDFFF and values above 0x10FFFF.

How do you handle hostile oversized input?

Let the caller impose a byte limit, timeout, and error-sampling policy. The parser itself keeps O(1) state and short-circuits on the first definite error, so malformed input does not require an extra buffer.