Implement encoding validation and grid shortest path

Q: Implement encoding validation and grid shortest path

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

A single-byte character starts with leading bit 0; (
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); (
Each continuation byte starts with the bit pattern 10xxxxxx; (
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,
to (n−1,n−
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.

Implement encoding validation and grid shortest path

Overview

Comments (0)