Return to Question

I was asked this problem in an interview, and this is the solution I came up with. I was told it's not the most efficient solution, but I can't think of any other solution. This is the problem.

Problem: Given a byte array and a fixed 3-bit pattern 0b101, we need to count the number of times this 3-bit pattern appears within the array. The pattern can span across byte boundaries, meaning it can be formed using bits from consecutive bytes.

int count_pattern_occurrences(const uint8_t* array, size_t size, uint8_t pattern = 0b110) {
    if (size == 0 || pattern > 0b111) {
        return 0;  // Array is empty or invalid pattern
    }

    int count = 0;
    uint32_t value = 0;  // To hold the accumulated bits
    int bit_count = 0;

    for (size_t i = 0; i < size; ++i) {
        value = (value << 8) | array[i];
        bit_count += 8;

        // Check within the current byte
        for (int bit_pos = bit_count - 8; bit_pos <= bit_count - 3; ++bit_pos) {
            if (((value >> (bit_count - 3 - bit_pos)) & 0b111) == pattern) {
                ++count;
            }
        }

        // Prepare for the next iteration, keeping only the last 2 bits
        value &= 0b11;
        bit_count = 2;
    }

    return count;
}

I aimed to minimize space usage by implementing this with O(1) space complexity. However, I'm not sure if there's a more efficient way than iterating through the byte arrays. Is it possible to optimize this further, or am I missing something?

I was asked this problem in an interview, and this is the solution I came up with. I was told it's not the most efficient solution, but I can't think of any other solution. This is the problem.

Problem: Given a byte array and a fixed 3-bit pattern 0b101, we need to count the number of times this 3-bit pattern appears within the array. The pattern can span across byte boundaries, meaning it can be formed using bits from consecutive bytes.

int count_pattern_occurrences(const uint8_t* array, size_t size, uint8_t pattern = 0b101) {
    if (size == 0 || pattern > 0b111) {
        return 0;  // Array is empty or invalid pattern
    }

    int count = 0;
    uint32_t value = 0;  // To hold the accumulated bits
    int bit_count = 0;

    for (size_t i = 0; i < size; ++i) {
        value = (value << 8) | array[i];
        bit_count += 8;

        // Check within the current byte
        for (int bit_pos = bit_count - 8; bit_pos <= bit_count - 3; ++bit_pos) {
            if (((value >> (bit_count - 3 - bit_pos)) & 0b111) == pattern) {
                ++count;
            }
        }

        // Prepare for the next iteration, keeping only the last 2 bits
        value &= 0b11;
        bit_count = 2;
    }

    return count;
}

I aimed to minimize space usage by implementing this with O(1) space complexity. However, I'm not sure if there's a more efficient way than iterating through the byte arrays. Is it possible to optimize this further, or am I missing something?

I was asked this problem in an interview, and this is the solution I came up with. I was told it's not the most efficient solution, but I can't think of any other solution. This is the problem.

Problem: Given a byte array and a fixed 3-bit pattern 0b101, we need to count the number of times this 3-bit pattern appears within the array. The pattern can span across byte boundaries, meaning it can be formed using bits from consecutive bytes.

int count_pattern_occurrences(const uint8_t* array, size_t size, uint8_t pattern = 0b101) {
    if (size == 0 || pattern > 0b111) {
        return 0;  // Array is empty or invalid pattern
    }

    int count = 0;
    uint32_t value = 0;  // To hold the accumulated bits
    int bit_count = 0;

    for (size_t i = 0; i < size; ++i) {
        value = (value << 8) | array[i];
        bit_count += 8;

        // Check within the current byte
        for (int bit_pos = bit_count - 8; bit_pos <= bit_count - 3; ++bit_pos) {
            if (((value >> (bit_count - 3 - bit_pos)) & 0b111) == pattern) {
                ++count;
            }
        }

        // Prepare for the next iteration, keeping only the last 2 bits
        value &= 0b11;
        bit_count = 2;
    }

    return count;
}

I aimed to minimize space usage by implementing this with O(1) space complexity. However, I'm not sure if there's a more efficient way than iterating through the byte arrays. Is it possible to optimize this further, or am I missing something?

I was asked this problem in an interview, and this is the solution I came up with. I was told it's not the most efficient solution, but I can't think of any other solution. This is the problem.

Problem: Given a byte array and a fixed 3-bit pattern 0b101, we need to count the number of times this 3-bit pattern appears within the array. The pattern can span across byte boundaries, meaning it can be formed using bits from consecutive bytes.

int count_pattern_occurrences(const uint8_t* array, size_t size, uint8_t pattern = 0b110) {
    if (size == 0 || pattern > 0b111) {
        return 0;  // Array is empty or invalid pattern
    }

    int count = 0;
    uint32_t value = 0;  // To hold the accumulated bits
    int bit_count = 0;

    for (size_t i = 0; i < size; ++i) {
        value = (value << 8) | array[i];
        bit_count += 8;

        // Check within the current byte
        for (int bit_pos = bit_count - 8; bit_pos <= bit_count - 3; ++bit_pos) {
            if (((value >> (bit_count - 3 - bit_pos)) & 0b111) == pattern) {
                ++count;
            }
        }

        // Prepare for the next iteration, keeping only the last 2 bits
        value &= 0b11;
        bit_count = 2;
    }

    return count;
}

I aimed to minimize space usage by implementing this with O(1) space complexity. However, I'm not sure if there's a more efficient way than iterating through the byte arrays. Is it possible to optimize this further, or am I missing something?