1-bit and 2-bit Characters

1-bit and 2-bit Characters

What is this problem about?

In the 1-bit and 2-bit Characters coding problem, you are given an array representing a stream of bits. There are two types of characters:

1. A single-bit character represented by 0.
2. A two-bit character represented by either 10 or 11. The goal is to determine if the very last character in the array must be a one-bit character (0).

Why is this asked in interviews?

This is a popular Easy difficulty question at Microsoft and Bloomberg because it evaluates a candidate's ability to implement "greedy" logic and pointer manipulation. It’s a test of how cleanly you can traverse data with variable-sized elements.

Algorithmic pattern used

This problem utilizes a Linear Scan (Array interview pattern). Since a 1 always indicates the start of a two-bit character, you can jump your index pointer based on the value you encounter. If you see a 0, move 1 step. If you see a 1, move 2 steps.

Example explanation

Consider the bits: [1, 1, 1, 0].

• Start at index 0. It's a 1, so it must be a two-bit character (11). Move to index 2.
• At index 2, it's a 1. This must be a two-bit character (10). Move to index 4.
• Since we landed exactly at index 4 (past the last index 3), the last character was part of a two-bit pair. The answer is False.

Common mistakes candidates make

• Overcomplicating with Recursion: While backtracking could work, it is overkill. A simple while loop is more memory-efficient ($O(1)$ space).
• Off-by-one errors: Miscalculating the loop termination condition and missing the second-to-last element.
• Confusing the bits: Forgetting that a 0 can never start a two-bit character.

Interview preparation tip

Practice "jumping" through arrays. When the current element dictates how many steps you take next, a while loop is usually more flexible than a standard for loop.