Interview Prepbit-manipulationmediumFacebookGoogleAmazon

UTF-8 Validation

Choose your preparation mode4 modes available

Try It Solution Trace

▶

Steps

setup

Initialize remaining continuation bytes counter

Set the counter 'remaining' to 0 before processing any bytes, indicating no continuation bytes are expected yet.

💡 This counter tracks how many continuation bytes we expect after a leading byte; starting at zero means we expect a new character.

Line:remaining = 0

💡 The algorithm starts fresh with no pending continuation bytes.

traverse

Load first byte: 197 (11000101)

Load the first byte 197 and represent it in binary. Since remaining is 0, we check the leading bits to determine character length.

💡 The first byte determines how many continuation bytes follow if any.

Line:

for byte in data:
    if remaining == 0:

💡 We are ready to analyze a new character starting with byte 197.

compare

Check if byte 197 starts a 2-byte character

Shift byte 197 right by 5 bits and compare to binary 110 (6 decimal) to check if it starts a 2-byte character.

💡 Leading bits 110 indicate a 2-byte UTF-8 character start.

Line:

if (byte >> 5) == 0b110:
    remaining = 1

💡 Byte 197 is a valid 2-byte character start, so we expect 1 continuation byte next.

compare

Check if byte 197 starts a 3-byte character

Shift byte 197 right by 4 bits and compare to binary 1110 (14 decimal) to check if it starts a 3-byte character.

💡 Leading bits 1110 indicate a 3-byte UTF-8 character start.

Line:

elif (byte >> 4) == 0b1110:
    remaining = 2

💡 Byte 197 does not start a 3-byte character.

traverse

Load second byte: 130 (10000010)

Load the second byte 130. Since remaining is 1, this byte must be a continuation byte starting with bits 10.

💡 Continuation bytes must start with bits 10 to be valid.

Line:

else:
    if (byte >> 6) != 0b10:
        return False
    remaining -= 1

💡 We will check if byte 130 is a valid continuation byte.

compare

Check if byte 130 is a valid continuation byte

Shift byte 130 right by 6 bits and compare to binary 10 (2 decimal) to verify it starts with bits 10.

💡 Valid continuation bytes start with bits 10.

Line:

if (byte >> 6) != 0b10:
    return False
remaining -= 1

💡 Byte 130 correctly continues the 2-byte character started by 197.

traverse

Load third byte: 1 (00000001)

Load the third byte 1. Since remaining is 0, we check if this byte is a valid single-byte character starting with bit 0.

💡 Single-byte characters start with a leading 0 bit.

Line:

for byte in data:
    if remaining == 0:

💡 We will check if byte 1 is a valid single-byte UTF-8 character.

compare

Check if byte 1 is a valid single-byte character

Shift byte 1 right by 7 bits and compare to 0 to verify it starts with a 0 bit indicating a single-byte character.

💡 Single-byte UTF-8 characters have a leading 0 bit.

Line:

elif (byte >> 7) == 0:
    remaining = 0

💡 Byte 1 is a valid single-byte UTF-8 character.

prune

Check if all continuation bytes processed

After processing all bytes, check if remaining continuation bytes counter is zero to confirm valid UTF-8 encoding.

💡 If remaining is not zero, it means some continuation bytes were expected but missing.

Line:return remaining == 0

💡 All bytes matched expected UTF-8 patterns with no missing continuation bytes.

reconstruct

Return final result: True

Return True indicating the input data is valid UTF-8 encoding.

💡 The algorithm successfully validated all bytes according to UTF-8 rules.

Line:return remaining == 0

💡 The input passes all UTF-8 validation checks.

def validUtf8(data):
    remaining = 0  # STEP 1
    for byte in data:  # STEP 2,4,6
        if remaining == 0:  # STEP 2,6
            if (byte >> 5) == 0b110:  # STEP 3
                remaining = 1
            elif (byte >> 4) == 0b1110:
                remaining = 2
            elif (byte >> 3) == 0b11110:
                remaining = 3
            elif (byte >> 7) == 0:  # STEP 7
                remaining = 0
            else:
                return False
        else:  # STEP 4,5
            if (byte >> 6) != 0b10:
                return False
            remaining -= 1
    return remaining == 0  # STEP 8,9

📊

UTF-8 Validation - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how the algorithm uses bit shifts and masks to identify UTF-8 character boundaries and validate continuation bytes.

Step 1/10

·Active fill★Answer cell

Initialize remaining

💡 No continuation bytes expected at start

Load byte

=197

💡 Current byte to analyze

byte >> 5

=197

────────

💡 Leading bits 110 detected

byte >> 4

=197

──────────

=12

💡 Leading bits not 1110

Load byte

=130

💡 Current byte to validate as continuation

byte >> 6

=130

──────

💡 Leading bits 10 detected

Load byte

💡 Current byte to analyze

byte >> 7

────────────────

💡 Leading bit 0 detected

remaining == 0

────

💡 No continuation bytes left to process

Return True

💡 Valid UTF-8 encoding confirmed

Key Takeaways

✓ The algorithm uses bit shifts to quickly identify the type of UTF-8 byte (leading or continuation).

This insight is hard to see from code alone because the bitwise operations are compact and not visually explicit.

✓ The 'remaining' counter elegantly tracks how many continuation bytes are expected, simplifying validation.

Understanding this counter's role is easier when watching it increment and decrement step-by-step.

✓ Validation fails immediately if a byte does not match expected patterns, preventing unnecessary checks.

Seeing the early return conditions in action clarifies how the algorithm efficiently rejects invalid sequences.

Practice

(1/5)

1. Consider the following code snippet implementing the optimal approach for bitwise AND of numbers range. What is the output when calling rangeBitwiseAnd(5, 7)?

easy

A. 4

B. 5

C. 0

D. 7

Solution

Step 1: Trace initial values
left = 5 (binary 0101), right = 7 (binary 0111)
Step 2: Execute loop iterations
First iteration: right = 7 & 6 = 6 (0110) Second iteration: right = 6 & 5 = 4 (0100) Now right (4) <= left (5) is true, loop ends.
Final Answer:
Option A -> Option A
Quick Check:
Final returned value is 4 after clearing differing bits [OK]

Hint: Bit-clearing reduces right until common prefix found [OK]

Common Mistakes:

Confusing loop condition
Off-by-one in bit clearing
Returning right too early

2. You need to generate all permutations of n distinct elements efficiently. Which approach best balances time and space by using a compact representation of visited elements and avoids redundant recomputation?

easy

A. Backtracking with a boolean visited array and recursion without memoization

B. Greedy algorithm that picks the next smallest unused element at each step

C. Bitmask DP with iterative tabulation that uses bitmasks to track visited elements and builds permutations bottom-up

D. Dynamic programming on subsets without bitmasking, using nested loops over all permutations

Solution

Step 1: Understand the problem constraints
Generating all permutations requires enumerating all orderings of n elements, which is factorial in size. Efficient tracking of visited elements is crucial.
Step 2: Identify the approach that uses bitmasking
Bitmask DP uses an integer to represent visited elements compactly, enabling memoization and iterative building of permutations without redundant recomputation.
Final Answer:
Option C -> Option C
Quick Check:
Bitmask DP with iterative tabulation is the known optimal approach for this problem [OK]

Hint: Bitmask DP uses bits to track visited elements efficiently [OK]

Common Mistakes:

Assuming greedy can generate all permutations correctly
Using DP without bitmasking leads to inefficient state tracking

3. You are given an array where exactly two elements appear only once and all the other elements appear exactly twice. Which approach guarantees finding these two unique elements in linear time and constant space?

easy

A. Use XOR of all elements, then partition the array by a set bit of the XOR result and XOR partitions separately.

B. Sort the array and scan linearly to find the two unique elements.

C. Use a hash map to count occurrences and then collect elements with count one.

D. Use a greedy approach to pick elements that appear once by checking neighbors.

Solution

Step 1: Understand the problem constraints
Two unique elements appear once, others appear twice. We want O(n) time and O(1) space.
Step 2: Identify the approach that uses XOR partitioning
XOR all elements to get xor = num1 ^ num2. Find a set bit in xor to partition elements into two groups, each containing one unique number. XOR each group separately to find the unique numbers.
Final Answer:
Option A -> Option A
Quick Check:
Sorting is O(n log n), hash map uses extra space, greedy fails on duplicates [OK]

Hint: XOR partitioning splits unique numbers by differing bit [OK]

Common Mistakes:

Assuming sorting is linear time
Using hash map violates O(1) space
Greedy fails on duplicates

4. Consider the following buggy Python code intended to generate Gray code sequence. Which line contains the subtle bug that breaks the Gray code property?

medium

A. Line 2: Using XOR with (i << 1) instead of (i >> 1)

B. Line 3: Incorrect range boundary in range(1 << n)

C. Line 1: Missing base case for n=0

D. Line 5: Printing the result instead of returning

Solution

Step 1: Identify the bitwise operation used
The code uses i ^ (i << 1) instead of the correct i ^ (i >> 1).
Step 2: Understand impact on Gray code property
Left shifting i doubles the value, causing incorrect bit patterns and breaking the one-bit difference property between consecutive numbers.
Final Answer:
Option A -> Option A
Quick Check:
Correct Gray code uses right shift, not left shift [OK]

Hint: XOR with right shift generates Gray code; left shift breaks it [OK]

Common Mistakes:

Confusing left and right bit shifts in XOR formula
Ignoring base case n=0 which is trivial but not critical here
Misunderstanding range boundaries or print vs return

5. What is the time and space complexity of the optimal bitwise FSM solution for the Single Number II problem?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n), Space: O(n)

C. Time: O(n^2), Space: O(1)

D. Time: O(n log n), Space: O(n)

Solution

Step 1: Identify complexity of outer and inner loops
The algorithm iterates once over the input array (n elements), performing constant time bitwise operations per element.
Step 2: Check if recursion stack adds extra space
No recursion or extra data structures are used; only fixed variables 'ones' and 'twos' consume constant space.
Final Answer:
Option D -> Option D
Quick Check:
Linear time and constant space confirmed by single pass and fixed variables [OK]

Hint: Bitwise FSM uses fixed variables, no extra data structures [OK]

Common Mistakes:

Assuming sorting or hash map space/time
Confusing bit operations cost

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Initialize remaining continuation bytes counter

Load first byte: 197 (11000101)

Check if byte 197 starts a 2-byte character

Check if byte 197 starts a 3-byte character

Load second byte: 130 (10000010)

Check if byte 130 is a valid continuation byte

Load third byte: 1 (00000001)

Check if byte 1 is a valid single-byte character

Check if all continuation bytes processed

Return final result: True

Key Takeaways

Practice

Solution

Step 1: Trace initial values

Step 2: Execute loop iterations

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that uses bitmasking

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that uses XOR partitioning

Final Answer:

Quick Check:

Solution

Step 1: Identify the bitwise operation used

Step 2: Understand impact on Gray code property

Final Answer:

Quick Check:

Solution

Step 1: Identify complexity of outer and inner loops

Step 2: Check if recursion stack adds extra space

Final Answer:

Quick Check:

Ready to prove it?