UTF-8 Validation

📋

UTF-8 Validation

Edge cases:

</>

IDE

def validUtf8(data: list[int]) -> bool:public boolean validUtf8(int[] data)bool validUtf8(vector<int> &data)function validUtf8(data)

def validUtf8(data):
    # Write your solution here
    pass

class Solution {
    public boolean validUtf8(int[] data) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool validUtf8(vector<int> &data) {
    // Write your solution here
    return false;
}

function validUtf8(data) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for input [235, 140, 4]Not validating continuation bytes properly; accepting invalid continuation bytes.✅ Check each continuation byte with (byte >> 6) == 0b10 and return false if invalid.

Wrong: true for input [145]Accepting continuation bytes without preceding leading bytes.✅ Track expected continuation bytes and reject continuation bytes if none expected.

Wrong: true for input [240, 162, 138]Not verifying the exact number of continuation bytes required by leading byte.✅ Check that i + num_bytes <= n before processing continuation bytes.

Wrong: true for input [250, 145, 145, 145, 145]Accepting invalid leading byte patterns beyond 4-byte UTF-8 characters.✅ Reject leading bytes that do not match valid UTF-8 leading byte masks.

Wrong: true for input [197, 197, 130, 1]Off-by-one error in index increment causing misinterpretation of bytes.✅ Increment index by num_bytes after processing each character.

✓

Test Cases

Focus on base cases like empty input and single bytes to solidify your logic.

Test your code against tricky cases with invalid byte sequences and off-by-one errors.

Ensure your solution is efficient enough to handle large inputs within time limits.

t1_01basic

Input[197,130,1]

Expectedtrue

⏱ Performance - must finish in 2000ms

197 (11000101) starts a 2-byte character, 130 (10000010) is a valid continuation byte, 1 (00000001) is a valid 1-byte character.

💡 Check the leading bits of each byte to determine character length.

💡 Use bitmasks to verify continuation bytes start with '10'.

💡 Ensure the number of continuation bytes matches the leading byte's indication.

Why it failed: Failed basic case: likely incorrect detection of leading byte patterns or continuation byte validation. Fix by correctly checking leading bits and verifying continuation bytes with (byte >> 6) == 0b10.

✓ Correctly identifies valid UTF-8 sequences including multi-byte characters.

t1_02basic

Input[235,140,4]

Expectedfalse

⏱ Performance - must finish in 2000ms

235 (11101011) indicates a 3-byte character, but 4 (00000100) is not a valid continuation byte (does not start with '10').

💡 Verify that all continuation bytes start with '10' in their two most significant bits.

💡 Count the expected number of continuation bytes from the leading byte's pattern.

💡 Return false immediately if a continuation byte is invalid or missing.

Why it failed: Failed basic case: continuation byte validation incorrect or missing. Fix by checking each continuation byte's leading bits with (byte >> 6) == 0b10.

✓ Correctly rejects invalid UTF-8 sequences with improper continuation bytes.

t2_01edge

Input[]

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty input is trivially valid UTF-8 as there are no bytes to invalidate.

💡 Consider the case when input array is empty.

💡 An empty sequence should be considered valid UTF-8.

💡 Return true immediately if input length is zero.

Why it failed: Failed edge case: code does not handle empty input correctly, possibly causing index errors. Fix by returning true if input is empty.

✓ Correctly handles empty input as valid UTF-8.

t2_02edge

Input[0]

Expectedtrue

⏱ Performance - must finish in 2000ms

Single byte 0 (00000000) is a valid 1-byte UTF-8 character.

💡 Check single byte inputs for valid 1-byte UTF-8 characters.

💡 Leading bit 0 indicates a 1-byte character.

💡 Return true if all bytes are valid single-byte characters.

Why it failed: Failed edge case: single byte characters not handled correctly. Fix by accepting bytes with leading bit 0 as valid single-byte characters.

✓ Correctly validates single byte UTF-8 characters.

t2_03edge

Input[145]

Expectedfalse

⏱ Performance - must finish in 2000ms

145 (10010001) is a continuation byte without a preceding leading byte.

💡 Check if a continuation byte appears without a valid leading byte before it.

💡 Continuation bytes must follow a leading byte indicating multi-byte character.

💡 Return false if a continuation byte is found unexpectedly.

Why it failed: Failed edge case: continuation bytes without leading bytes accepted. Fix by tracking expected continuation bytes and rejecting unexpected continuation bytes.

✓ Correctly rejects continuation bytes without preceding leading bytes.

t2_04edge

Input[240,162,138,138]

Expectedtrue

⏱ Performance - must finish in 2000ms

240 (11110000) indicates a 4-byte character, followed by three valid continuation bytes (all starting with '10').

💡 Verify that the number of continuation bytes matches the leading byte's indication.

💡 Check that all continuation bytes start with '10'.

💡 Return true if all bytes form valid UTF-8 characters.

Why it failed: Failed edge case: not correctly validating 4-byte characters with exact continuation bytes. Fix by ensuring continuation byte count matches leading byte.

✓ Correctly validates 4-byte UTF-8 characters with proper continuation bytes.

t3_01corner

Input[240,162,138]

Expectedfalse

⏱ Performance - must finish in 2000ms

240 (11110000) indicates a 4-byte character but only 2 continuation bytes follow instead of 3.

💡 Count the number of continuation bytes required by the leading byte.

💡 Verify that the input length matches the expected number of bytes for each character.

💡 Return false if continuation bytes are fewer than expected.

Why it failed: Failed corner case: code does not check for exact number of continuation bytes. Fix by verifying i + num_bytes <= n before checking continuation bytes.

✓ Correctly rejects sequences with insufficient continuation bytes.

t3_02corner

Input[250,145,145,145,145]

Expectedfalse

⏱ Performance - must finish in 2000ms

250 (11111010) does not match any valid UTF-8 leading byte pattern (max 4-byte chars).

💡 Check that leading bytes match only valid UTF-8 patterns (1 to 4 bytes).

💡 Leading bytes with more than 4 leading 1 bits are invalid.

💡 Return false if leading byte pattern is invalid.

Why it failed: Failed corner case: invalid leading byte patterns accepted. Fix by rejecting leading bytes not matching 1-4 byte UTF-8 patterns.

✓ Correctly rejects invalid leading byte patterns.

t3_03corner

Input[197,197,130,1]

Expectedfalse

⏱ Performance - must finish in 2000ms

Second 197 (11000101) is a leading byte but is followed by 130 (10000010) which is valid, but the first 197 is not followed by a continuation byte, causing misalignment.

💡 Ensure that after processing a multi-byte character, the index moves correctly to the next character.

💡 Check that continuation bytes are not mistaken for leading bytes.

💡 Return false if continuation bytes are missing or misaligned.

Why it failed: Failed corner case: off-by-one error in index increment causing misinterpretation of bytes. Fix by incrementing index by num_bytes after processing each character.

✓ Correctly processes multi-byte characters and advances index properly.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n) time complexity; solution must complete within 2 seconds.

💡 Use a single pass over the data array.

💡 Avoid nested loops or exponential checks.

💡 Track expected continuation bytes with a counter.

Why it failed: TLE detected: likely using nested loops or exponential complexity. Fix by implementing a single pass with a continuation byte counter.

✓ Solution runs in O(n) time and passes performance constraints.

Practice

1. Given the following Python code, what is the output of isPowerOfFour(16)?

easy

A. True

B. False

C. Raises an error due to floating point precision

D. None

Solution

1. Step 1: Calculate log2(16)

   log2(16) = 4, dividing by 2 gives 2.0.

2. Step 2: Check if 2.0 equals int(2.0)

   2.0 == 2 is True, so the function returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   16 is 4^2, so output True is expected [OK]

Hint: log2(16)/2 = 2.0 equals int(2) -> True

Common Mistakes:

• Assuming floating point error causes failure
• Confusing power of two with power of four

2. The following code attempts to generate all permutations of n elements using bitmask DP with iterative tabulation. Identify the line containing the subtle bug that causes dp[(1 << n) - 1] to remain empty.

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]
    # Missing initialization of dp[0]
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in dp[mask]:
                    dp[mask | (1 << i)].append(perm + [i])
    return dp[(1 << n) - 1]

medium

A. Line 2: dp initialization with empty lists

B. Line 7: Incorrect bitmask check condition

C. Line 5: Incorrect mask iteration range

D. Line 3: Missing dp[0] = [[]] initialization

Solution

1. Step 1: Check base case initialization

   dp[0] must be initialized to contain an empty permutation to start building others.

2. Step 2: Identify impact of missing dp[0] initialization

   Without dp[0] = [[]], dp[mask] lists remain empty, so no permutations are generated.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding dp[0] = [[]] fixes the empty result issue [OK]

Hint: dp[0] must be initialized to start building permutations [OK]

Common Mistakes:

• Forgetting to initialize dp[0]
• Misunderstanding bitmask iteration order

3. Identify the bug in the following code snippet for Single Number II using the bitwise FSM approach:

medium

A. Line with 'twos |= ones & num'

B. Line with 'ones ^= num'

C. Line with 'common_mask = ~(ones | twos)'

D. Line with 'ones &= common_mask'

Solution

1. Step 1: Compare common_mask calculation with correct formula

   The correct mask is the negation of the AND of ones and twos, i.e., ~(ones & twos), not ~(ones | twos).

2. Step 2: Understand impact of wrong mask

   Using OR instead of AND causes bits to be cleared incorrectly, failing to reset bits appearing thrice properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct mask uses AND, not OR, to clear bits appearing three times [OK]

Hint: Mask must clear bits appearing in both ones and twos simultaneously [OK]

Common Mistakes:

• Using OR instead of AND in mask
• Misordering bit updates

4. What is the time complexity of the optimal XOR and partition approach to find two unique numbers in an array of size n?

medium

A. O(n log n) due to sorting step

B. O(n) because it traverses the array a constant number of times

C. O(n^2) because of nested loops in partitioning

D. O(n) but uses O(n) extra space for partitions

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm traverses the array twice: once to XOR all elements, once to partition and XOR groups.

2. Step 2: Analyze time and space complexity

   Each traversal is O(n), no nested loops. Space used is constant (variables only), no extra arrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes, constant space [OK]

Hint: Two passes over array -> O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops in partition
• Forgetting constant space usage

5. If the input number n can be negative or zero, and you want to check if its absolute value is a power of four, which modification to the optimal logarithm-based approach is correct?

hard

A. Remove the check for n <= 0 and directly compute log2(n)/2

B. Add a check to return False if n is zero or negative before applying logarithm on abs(n)

C. Use the brute force iterative division approach instead, as logarithm fails for negative inputs

D. Take the absolute value of n before the logarithm check and keep the rest unchanged

Solution

1. Step 1: Consider input domain

   Since n can be zero or negative, these are not powers of four, so must return False immediately.

2. Step 2: Apply logarithm check on absolute value

   After filtering invalid inputs, apply logarithm on abs(n) to check power of four.

3. Step 3: Finalize correct approach

   Adding a check to return False for zero or negative inputs before log check ensures correctness and avoids math domain errors.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Zero and negatives are filtered out before log check on abs(n) [OK]

Hint: Filter invalid inputs before log check on abs(n)

Common Mistakes:

• Removing input validation
• Applying log on negative numbers causing errors