UTF-8 validation of a list of bytes

You get a list of integers, each standing for one byte. Decide whether the bytes form a valid UTF-8 encoding.

Interface

Unless you agree on a different interface with the interviewer, assume:

• valid_utf8(data: list[int]) -> bool — only the lowest 8 bits of each integer are used. The rules:
  • A one-byte character starts with bit 0: 0xxxxxxx.
  • An n-byte character for n in 2 to 4 starts with n ones and a zero (110xxxxx, 1110xxxx, 11110xxx) and is followed by n - 1 continuation bytes.
  • Every continuation byte starts with 10.
  • The data may not end in the middle of a character.

Example

valid_utf8([197, 130, 1])            ->  True    # 11000101 10000010 | 00000001
valid_utf8([235, 140, 4])            ->  False   # 11101011 needs two continuations; 00000100 is not one
valid_utf8([240, 162, 138, 147])     ->  True    # one 4-byte character
valid_utf8([145])                    ->  False   # a continuation byte cannot start a character
valid_utf8([250, 145, 145, 145, 145]) ->  False   # five leading ones
valid_utf8([230, 136])               ->  False   # ends mid-character

Constraints

• 0 <= len(data) <= 2 * 10^4. An empty list is valid.

Clarifying questions

• Do we check only the bit patterns, or also overlong encodings and surrogate code points?
• Can a value be above 255? Should I mask it to 8 bits?
• Is an empty input valid?

What a strong answer covers

• One pass with a counter of continuation bytes still expected. When it is zero, read the leading ones of the byte to start a character; otherwise check for 10 and count down.
• Bit masks (b >> 7 == 0, b >> 5 == 0b110, ...) instead of string conversion.
• Rejecting one leading 1 and more than four leading ones, and checking the counter is zero at the end.
• O(n) time and O(1) space. Tests: every byte length, a truncated character, a stray continuation byte.

Follow-ups

• Also reject overlong encodings and code points above U+10FFFF.
• Validate a stream of bytes arriving in chunks that may split a character.
• Count the characters, or decode them to code points.