I see basically two categories of solution that aren't bit-by-bit:

0. A table-based approach.
1. A word-oriented approach.

I will get to them, but using this as a hook:

I tried to write it in a generic way just in case a follow up question would come up. Is it a problem?

"Problem" is a bit much, but inherently you will tend to lose opportunities for simplification, or to put it another way, you're making the problem more difficult to solve.

For example, let's say you use a table based approach, using a table with 1024 entries to process 10 bits: 8 bits belonging to the current byte, plus two extra bits that are two last bits from the previous byte. You would form the index into the table by concatenating those things. There is a somewhat annoying case at the start of the array (or the end, depending on how you arrange things), where we must avoid finding instances of the pattern that start before the array. If we know that the pattern is 101, then that automatically doesn't happen if the "left over bits" are initialized as zero. If the pattern can be 000 and other annoying values, it takes some subtle and possibly bug-prone logic to avoid finding pattern matches that would include one or two phantom bits that aren't part of the array.

A word-oriented approach grabs a bigger chunk of the array at once and uses a couple of bitwise operations to turn those bits from the array into a mask indicating where the pattern matches. In the simplest case, if we were looking for the single-bit pattern of 1, the data itself would already be a mask of where the pattern matches (and there wouldn't be any complications from patterns that cross a word-boundary), all that remains is to std::popcount the data word-by-word and sum the results. If we were looking for 0, we first invert the data, and use std::popcount(~word).

For longer patterns, some shifts and ANDs enter the picture. For example to get the mask indicating where the pattern 101 matches, the "core" of the solution could be:

mask = data & (~data << 1) & (data << 2)

It's possible to support variable patterns, using XOR to do conditional inversion. Of course that adds some additional complexity.

You could shift right instead of left. Does that matter? Not really, not at this point.

I've seemingly ignored the "pattern can span across boundaries" problem here, but for the pattern 101 there is an elegant (perhaps not the fastest, but it's nice and simple) solution: work 7 bytes at the time (if you're using uint64_t as your "word"), using 2 of the 8 spare bits that leaves in an uint64_t to put the two extra bits from the adjacent word. That leaves 6 "padding" bits that are in the word but in which no matches must be counted, but here's a nice thing about the pattern 101: that doesn't matter, there will never be a match involving those 6 zeroes. There could have been if a pattern was allowed to end in a zero, though that is not hard to solve, just put an extra bitwise AND to get rid of the invalid matches.

Another option to handle patterns that cross across word boundaries is handling them explicitly, counting them separately from the rest.

If you have access to the kind of shift where you can supply an extra operand of bits to shift into the top/bottom, you can use that to work a full word at the time.

What about SIMD

Most of the "raw processing performance" of a modern high-performance CPU (by which I roughly mean, basically anything that isn't a basic microcontroller; even some fancy microcontrollers have ARM NEON) is locked behind its SIMD/vector processing capabilities, so whether we can use that deserves some thought.

A word-oriented approach is probably more amenable to a SIMD implementation, either manual but especially for auto-vectorization (compilers are, so far, not very eager to turn a table-lookup into a variable-shuffle).

It's not that SIMD cannot do table-lookups; depending on the ISA it can: there is for example tbx/tbl in ARM NEON and SVE, and pshufb (SSSE3), vpermb (AVX512), vpermt2b (AVX512) in x86/x64-land. But a small table means there's not a lot of progress made per lookup; for example a lookup into a 16-entry (4-bit index) table only processes 2 positions if the pattern has a length of 3, a lookup into a 64-entry (6-bit index) table (eg vpermb in AVX512) processes 4 positions - that's something but it's not really reasonable to use a 1024-entry table.

The word-oriented approach mostly "just works" in SIMD. Working 7 bytes at the time is a bit awkward but possible (just shuffle the bytes), maybe it works out better to count the word-boundary-crossing patterns separately, or with AVX512 you could use those "concatenate and shift" instructions such as vpshldq.

There's an assumption about what it means for the bit pattern to "span bytes" - we should document which endianness we're working to. This is part of the requirements-gathering which is often at the heart of good interview questions.

The code is missing some type definitions. Although I can't be sure, my guess is that these types are probably intended to be the corresponding names from std:

#include <cstddef>
#include <cstdint>

using std::size_t;
using std::uint8_t;
using std::uint32_t;

Note that std::uint8_t and std::uint32_t are optionally-defined types - they don't exist on targets that don't have native types of exactly the specified size, so portable code does not use them.

The C-style (pointer+size) interface is limiting. I'd expect a C++ function to accept an input range:

auto count_pattern_occurrences(std::ranges::input_range auto bytes)

More crucially, think about the return type. Given that the input length is a std::size_t, we'll need at least that much range in the return type. And given that there can be as many as four matches per input element, we need to think about how we'll handle overflow in the result - perhaps by throwing, or maybe by saturating at maximum?

Although the problem says that the pattern to search for will be fixed (0b101), the code here is perhaps prematurely generalised. Knowledge of the pattern allows a number of simplifications that are not available to the more general code (e.g. we get to eliminate the bit_count variable - or we could replace the inner loop with masks and a popcnt instruction).

value &= 0b11 is unnecessary, given that bits outside that mask get shifted out of range of our consideration anyway. And std::uint32_t is overkill for value given we only need 10 bits there - I suggest std::uint_fast16_t instead.

I would have liked to have seen at least the beginnings of some unit tests for the function, particularly given the non-obvious shift amount prior to masking. In fact, if I were doing this in an interview, I'd at least talk about how well it's suited to test-driven development.

branch mispredictions

            if ((value ...) == pattern) {
                ++count;
            }

We have a data-dependent branch decision to make here, which essentially looks random to the predictor. Best it can do is predict that we usually skip the increment.

Use https://godbolt.org to learn whether your compiler was smart enough to rewrite this. If not, phrase it as count += (value ...) == pattern. That is, unconditionally add a boolean expression, to avoid mispredictions.

table based approach

int count_pattern_occurrences( ... , uint8_t pattern = 0b101) {

That pattern default is nice, but solving a more general problem can make it difficult to optimize a quite specific one.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Six of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte lookup table of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning data in array,

• add lookup value to counter
• if data value ends with 10 then increment if next byte's LSB is set
• if data value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (as much as 3) to the counter and increment based on the next byte's masked value.

Not an answer to the optimization question, but a remark that might be useful:

The problem text is quite vague. To a professional developer, some questions need clarification before an implementation can be done:

• The byte array is to be interpreted as a sequence of bits. How are the bits ordered? Starting with the highest or the lowest bit of each byte?
• Are overlapping pattern occurrences to be counted or skipped? Are there one or two matches of 101 in 00010101?
• Is code to be optimized for readability, for space efficiency, or for time efficiency? And when going for time efficiency, what is the expected usage pattern (how often called, what is a typical array size)?

If your interviewers are senior developers, they'll expect questions like the ones above, showing that you think (and don't hesitate to ask for clarification) before coding, making sure to implement the requirements that have to be met, and not some mis-interpretation.

IMHO, a good developer isn't necessarily the one with the fastest code, but the one who most reliably produces code that fulfills the various requirements.

I think a precomputed 10-bit lookup table is the way to go. This reduces the number of operations to a minimum and is thus likely much faster. It might introduce caching issues. As always, only benchmarking in the appropriate environment will tell how it compares in practice.

unsigned count = 0;
uint16_t x = 0;
for ( size_t i=0; i<n; ++i ) {
   x = ( ( x & 0x3 ) << 8 ) | buf[ i ];
   count += count_lookup[ x ];
}

I'd personally solve this with a lookup table of 256 elements. Each entry maps a byte value onto the number of '101' bit patterns which appear in that value.

To deal with the problem of bit patterns spanning bytes, the lookup table also holds information on whether a byte starts with a 'partial pattern', i.e. the start or end of the pattern '101'. We can use this to see if the previous byte ended with '1'/'10' while the next byte start with '01'/'1' (respectively).

This, in my opinion, leads to code which is fairly easy to reason about, while only taking a few instructions for each byte. You could improve on the speed by considering multiple bytes at a time / using SIMD, but this is the version I'd write in an interview (and talk about alternatives in the abstract).

#include <stdio.h>
#include <stdint.h>

/**
 * Holds a single entry of our lookup table
 */
typedef struct 
{
    /// The total number of '101' bit patterns which appear in the byte.
    /// E.g. the byte '0101 1010' would have a count of '2'.
    /// We count overlapping patterns of '10101' as having a count of '2'.
    uint8_t count;
    
    /// The number of bits of a partial pattern which appear at the start of the byte.
    /// If the byte starts with '01', this takes the value '2'; if the byte starts with
    /// '1', this takes the value '1'.
    uint8_t startPartial;
    
    /// The number of bits of a partial pattern which appear at the end of a byte.
    /// If the byte ends with '10', this takes the value '2'; if the byte ends with
    /// '1', this takes the value '1'.
    uint8_t endPartial;
} LookupEntry_t;

/// A lookup from byte value -> information about that value
static LookupEntry_t s_lookup[256];

static void BuildLookup(void)
{
    for (int i = 0; i < 256; i++)
    {
        LookupEntry_t* pEntry = &s_lookup[i];

        // Partial pattern at the start of the byte
        if ((i & 0x80) > 0)
        {
            // Starts with '1'
            pEntry->startPartial = 1;
        }
        else if ((i & 0xC0) == 0x40)
        {
            // Starts with '01'
            pEntry->startPartial = 2;
        }
        
        // Partial pattern at the end of the byte
        if ((i & 0x01) > 0)
        {
            // Ends with '1'
            pEntry->endPartial = 1; 
        }
        else if ((i & 0x03) == 0x02)
        {
            // Ends with '10'
            pEntry->endPartial = 2; 
        }
        
        // Number of '101' patterns which appear in the byte
        for (int j = 0; j < 6; j++)
        {
            if (((i >> j) & 0x07) == 0x05)
            {
                pEntry->count++;
            }
        }
    }
}

int main(void) 
{
    BuildLookup();
    
    // 0010 1010 1000 0101
    uint8_t input[] = { 0x2A, 0x85 };
    
    uint32_t count = 0;
    uint8_t prevEndPartial = 0;

    for (size_t i = 0; i < sizeof(input); i++)
    {
        const LookupEntry_t* pEntry = &s_lookup[input[i]];
        
        count += pEntry->count;
        
        // If the previous byte ends with 2 bits of a pattern, and we start with 1 bit;
        // or if the previous byte ends with 1 bit of a pattern and we start with 2 bits,
        // then they combine to form a '101' which is bridged between the two bytes.
        if ((prevEndPartial + pEntry->startPartial) == 3)
        {
            count++;
        }
        
        prevEndPartial = pEntry->endPartial;
    }
    
    printf("Total: %d\n", count);
    
    return 0;
}

Note: that this is pure C, not C++.
Run online.

You mention that feedback reported it was "not the most efficient." That suggests that either you, or the interviewers, were focused on efficiency/performance.

I would suggest building a set of lookup tables. Several people have mentioned 10-bit tables, but I would suggest an array of 8-bit tables instead.

With this approach, you are concerned with two questions: how many times does the pattern occur in a single byte; and what bits were available for partial matches in the lead-up to this byte. There is no concern for following bits, since those will be addressed by considering the last bits of the current byte as "lead-up" bits in the next iteration.

So, at start you have two impossible values. I think you can just use 00 for this, since that won't cause any mismatches. But in the "general" case you might consider a special table for this. A table with 00 lead-up bits followed by 256 possible byte values will tell you how many matches you get for the first byte of the bit array. It should also tell you what the two lead-up bits are for the next table. So you can either compute the bits or store the bits. (Endianness matters here. Is 0x01 the first or last bit of the byte?)

Anyway, compute 4 tables (00, 01, 10, 11 lead-up bits) of 256 values, counting the number of times 0b101 occurs in the lead-up plus 8 bits of the index. Update the lead-up and accumulator for each byte. Decide what, if anything, to do with an array size that is not divisible by 8. (Treat them as all zero, IMO.)

That will get you to byte-oriented processing, with a small number of ops per byte. You may or may not get a speed improvement out of fetching word-sized values and then breaking them into byte-sized chunks. (Actually, this is C++ so I know you don't care about code size - make the tables 16 bits instead...)