Entrevista técnica: Validar una secuencia de bytes UTF-8

Prompt y alcance

Este es un problema de manipulación de bits y codificación de caracteres. La entrada es un arreglo de bytes, no una cadena Unicode ya decodificada. Determine si cada escalar utiliza de 1 a 4 bytes y rechace secuencias truncadas o mal formadas. LeetCode 393 utiliza las mismas restricciones: longitud máxima de 2 * 10^4, donde cada entero aporta sus 8 bits menos significativos. La RFC 3629 define los formatos UTF-8 de 1 a 4 bytes y el rango de valores escalares válidos.

Qué evalúa el entrevistador

• Deducir la cantidad de bytes de continuación a partir del patrón del byte inicial (leading byte).
• Verificar estrictamente el prefijo de continuación 10xxxxxx.
• Rechazar bytes de continuación sobrantes, truncamientos y patrones iniciales de cinco bytes.
• Producir una solución en una sola pasada con tiempo O(n) y espacio adicional O(1).

Aclaraciones que conviene hacer primero

Confirme si se garantiza que cada elemento está en 0..255; de lo contrario, rechace primero los valores fuera de rango. Aclare también si la tarea evalúa solo el formato de los bytes o si debe rechazar codificaciones sobrelargas (overlong encodings), puntos de código subrogados (surrogates) y valores superiores a U+10FFFF. La versión de LeetCode se enfoca en el formato de los bytes; un analizador para producción debería aplicar las reglas más estrictas de valores escalares de la RFC 3629.

Respuesta en 30 segundos

Mantenga remaining, la cantidad de bytes de continuación que aún se requieren para el carácter actual. Para un byte inicial, utilice su patrón de bits altos para establecer 0, 1, 2 o 3; para un byte de continuación, exija (byte & 0b11000000) === 0b10000000 y decremente el contador. Rechace un byte inicial ilegal, una continuación inesperada o el fin de la entrada con remaining !== 0. El recorrido solo mantiene este contador.

Solución paso a paso

1. Reconocer patrones de bytes iniciales

0xxxxxxx es un carácter de un solo byte; 110xxxxx, 1110xxxx y 11110xxx requieren 1, 2 y 3 bytes de continuación. Pruebe los prefijos con máscaras: verifique 0x80, luego 0xE0, 0xF0 y finalmente 0xF8. Si la prueba 0xF8 sigue siendo distinta de cero, el byte inicia un formato de cinco bytes o más largo y debe ser rechazado.

2. Validar bytes de continuación en línea

Cuando remaining > 0, el byte actual debe coincidir con 10xxxxxx. Decremente después de una comprobación exitosa. Un byte inicial ASCII u otro byte inicial multibyte en este estado es inmediatamente inválido. No se necesita retroceso (backtracking) ni segmentación (slicing), y el truncamiento se detecta cuando finaliza la entrada.

3. Implementación de referencia

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. Rigor a nivel de producción

El conteo de prefijos por sí solo acepta algunas codificaciones sobrelargas, como representar un valor con tres bytes cuando uno bastaría, y puede aceptar valores subrogados. Un analizador para producción debería acumular el valor escalar y verificar el valor mínimo para su longitud, el rango de subrogados y el límite superior U+10FFFF; decida explícitamente si se permite un BOM. Establezca primero los límites del ejercicio y luego explique esta extensión en lugar de mezclar reglas silenciosamente.

5. Pruebas y complejidad

Cubra [197,130,1] como verdadero, [235,140,4] como falso, una continuación aislada [128], un truncado [226,130], un byte inicial de cinco bytes [248,128,128,128,128] y el arreglo vacío. Cada byte se escanea una vez: tiempo O(n) y espacio adicional O(1), donde n es la longitud del arreglo.

Respuesta modelo

Separo el reconocimiento del byte inicial de la validación del byte de continuación. Un byte inicial que coincide con 0xxxxxxx, 110xxxxx, 1110xxxx o 11110xxx establece remaining en 0, 1, 2 o 3; el estado de continuación solo acepta 10xxxxxx y decremente el contador. Un byte inicial de cinco bytes, una continuación inesperada, un elemento fuera de rango o el fin de la entrada con un carácter incompleto retorna falso. La implementación consiste en una sola pasada O(n) con espacio O(1). Para producción, acumule el valor escalar para rechazar codificaciones sobrelargas, subrogados y valores superiores a U+10FFFF.

Errores comunes

• Contar bytes de continuación sin verificar cada prefijo 10.
• Tratar 111110xx como un formato válido de cinco bytes.
• Olvidar la comprobación final remaining y aceptar truncamientos.
• Delegar a un decodificador del lenguaje sin mostrar el invariante a nivel de bits o el índice de error.
• Mezclar la comprobación de formato de LeetCode con las reglas de valores escalares de la RFC sin aclarar el alcance.
• Tratar byte como con signo y no normalizarlo a 0..255 antes de las operaciones a nivel de bits.

Preguntas de seguimiento

¿Cómo devolvería el índice del primer error?

Devuelva {valid, errorIndex, reason}. Registre el índice actual cuando falle una comprobación de byte inicial, de continuación o de fin de entrada. El estado de escaneo no cambia, por lo que los llamadores pueden resaltar el byte original.

¿Cómo admitiría entradas en streaming por fragmentos (chunks)?

Mantenga remaining y el estado escalar parcial en un objeto de analizador entre fragmentos. Un carácter solo se completa después de que un fragmento posterior suministre todos los bytes de continuación; el fin de la secuencia con remaining != 0 sigue siendo un error de truncamiento.

¿Por qué no usar únicamente una expresión regular?

Una expresión regular puede expresar algunas reglas de prefijo, pero una máquina de estados es más clara para límites de fragmentos, índices de error y restricciones de valores escalares. El contador utiliza espacio constante para entradas de longitud arbitraria y se extiende de forma natural hacia una validación estricta.

¿Cómo se rechazan las codificaciones sobrelargas?

Registre la longitud de la secuencia y el valor acumulado a partir del byte inicial, luego exija que el valor cumpla con el rango mínimo de dicha longitud. Rechace también 0xD800..0xDFFF y los valores superiores a 0x10FFFF.

¿Cómo maneja entradas sobredimensionadas y hostiles?

Permita que el llamador imponga un límite de bytes, un tiempo de espera (timeout) y una política de muestreo de errores. El analizador en sí mantiene el estado O(1) y realiza un cortocircuito ante el primer error definitivo, por lo que una entrada mal formada no requiere un búfer adicional.