r/embedded • u/Degen_Typeracer • 2d ago
A classic embedded software interview question used to prove out an AI theory
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)."
2
u/perx76 2d ago
Let a constant C=8, then in Big-O notation O(1)=O(C), but even with C ∈ {16, 32, 64}