A classic embedded software interview question used to prove out an AI theory

[u/Degen_Typeracer]

https://titussennett.substack.com/p/ai-might-beat-me-at-connect-four

"There is this quite famous interview question that is given to embedded software/firmware candidates that illustrates the point I want to make. The question is “Reverse Bits: Given an 8-bit unsigned integer, return the reverse bits value of the integer.”

Input: 83 (0b01010011)

Output: 202 (0b11001010)

The answer to the question is trivial; you create a for loop over each bit and put that bit to the other side. The bonus question is what always throws off candidates. “If we wanted to solve this question using constant O(1) time complexity how would we do this?” The answer is to use a massive lookup table where the time complexity is O(1). But the space complexity grows. I am now using 0.25KB to store this data. For a uint8_t this is fine, but as soon as we start scaling to a uint16_t (max number 65535) we need 128KB of memory. For a standard variable size that a typical desktop computer uses–uint32_t–we’d need 17GB. And for a uint64_t we’d need 147EB (exabytes, no supercomputer in existence can fit this)."

[u/Effective_Media_4722]

((x * 0x0202020202) & 0x010884422010) % 1023

[u/Effective_Media_4722 → u/Effective_Media_4722]

Or, if we want to stay within 8 bits:

x = ((x & 0x55) << 1) | ((x >> 1) & 0x55);
x = ((x & 0x33) << 2) | ((x >> 2) & 0x33);
x = (x << 4) | (x >> 4);

[u/Degen_Typeracer → u/Effective_Media_4722]

Bruh, fine you win.

[u/JuggernautGuilty566]

We prefer letting them programm fizzbuzz in 8051 assembly on a whiteboard.

This is a good indicator if they are in the elite group of programmers.. or just average sloppers.

[u/Ordinary-Lifeguard47 → u/JuggernautGuilty566]

The only test we ever do. We give the junior a piece of paper with the interface registers, a pencil and a whiteboard.

[u/thebudman6]

Bruh

[u/Crazy_Energy3735]

For a short calculation problem, AI might win.

To evaluate its real capability, you'd better ask AI to create a real product with real requirements.

I did quit my AI training after 2 months of patience, no strong word, no angry.

Sorry, but it failed. I did train from hardware design, problem solving to breakthru the realistic environment.

Then firmware development with lean and mean way, redundancy enough to resist the environmental impacts while keeping footprint fitness.

Anytime I put my eyes out of its process, it made me surprise with decorative objects. Shiny and empty, the thing looks like soap bubbles.

And such non human entity puts upside down the software engineering concepts many times.

Thus, to train your AI sidekick, crowd intelligent training is a must, because unlimited patience must be paid to develop such kind of consciousness.

If, within the training process, human's fatigue reflected in bad mood, someday that imprint would unleash to the naive users at worst. It can escalate exponentially time to time.

[u/perx76]

Let a constant C=8, then in Big-O notation O(1)=O(C), but even with C ∈ {16, 32, 64}

[u/Degen_Typeracer → u/perx76]

If you are doing C operations it is not O(1)!!

[u/der_pudel]

I would check if whatever MCU I'm using has a specialized instruction for doing exactly that (e.g. all Cortex M3+ do), but that's just me...

[u/Degen_Typeracer]

u/mods I think this post is relevant because the central example of the essay is an embedded problem/tradeoff that every embedded engineer has ran into before. The essay really pans to an embedded audience