Coding Interview Horrorshows

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Coding Interview Horrorshows

Xerophyte: Mar 17, 2008; This space intentionally left blank

Off-topic, but re: Fibonacci discussion earlier, someone came up with a non-iterative integer math solution:

code:

 def fib(n):
        return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

It's still slower than the matrix exponentiation approach because the integers involved are loving enormous, but it's pretty neat that it works. You can now confuse the poo poo out of whoever asks you to code Fibonacci-related things on your next interview.

# ¿ May 1, 2016 18:54

Adbot: ADBOT LOVES YOU

# ¿ May 11, 2024 14:55

Xerophyte: Mar 17, 2008; This space intentionally left blank

sarehu posted:

Here's a hint: you can make an implementation for 64-bit numbers that uses the plus sign 6 times. And you can make one for 32-bit numbers that uses the plus sign 5 times.

To beat around the bush less, the basic idea is that if you know the popcount of the first n/2 bits and the last n/2 bits then you can just add them together to get the popcounts for all the n bits. Further, you can compute those two popcounts in parallel if n is small enough for machine integer arithmetic.

Initially, each bit of the input is its own popcount. First iteration assigns each pair of bits their popcount by adding neighboring bits together. Then each 4 bit word by adding neighboring pairs, then each 8 bit word by adding 4 bit words and so on.

For 32 bits, stolen from Sean Eron Anderson's bit twiddling hacks.

C++ code:

uint32_t v; // count bits set in this (32-bit value)
uint32_t c; // store the total here
static const uint32_t S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const uint32_t B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];

You can technically shave it down to even fewer operations:

C++ code:

v = v - ((v>> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

The basic idea isn't terribly difficult but I would not expect anyone to know or derive that on an interview. There's a simpler LUT approach which I'd think most coders could at least be prodded towards.

Xerophyte fucked around with this message at 16:50 on Jun 20, 2016

# ¿ Jun 20, 2016 16:46

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Coding Interview Horrorshows