User: psychomaniac8

Re:Find missing number 1-10

On: How Should You Interview a Programmer?

Your solution is more flexible, but your O(n) solution is killing O(n) memory at the same time.

Sorry, I'm bored. Can someone set my karma to bored?

Re:VERY FAST O(n) solution

On: How Should You Interview a Programmer?

Well, I guess this solution is no better than

{
answer = 55

loop over i
answer -= numbers[i]
}

I was thinking of

{
answer = 0

loop over i
answer += numbers[i]

answer = 55 - answer
}

I guess the xor solution still works on larger numbers, but it is the same number of instructions.

Re:Find missing number 1-10

On: How Should You Interview a Programmer?

Depends on the application and size of n. If your n is very large, O(n) might not be good enough.

I guess I just like performance (and bit twiddling) and that is what I tried to acheive with my solution.

Also, adding comments in your code esp. about the limits of your function/algorithm helps with readablity problems. I would encourage applicants to add comments if they are being interviewed.

Steve

VERY FAST O(n) solution

On: How Should You Interview a Programmer?

quicker than sum subtract and works with big numbers. Up to around 4 billion on 32 bit machine instead of around 32k with the sum solution.

uint findmissing(uint *numbers)
{
uint answer = 11 // magic 1-10 starting value.

for i=0 to 8
answer ^= numbers[i]

return(answer)
}
okay mark this as redundant or the other. Didn't know which thread was better :)

Re:I Am Confused

On: How Should You Interview a Programmer?

Good idea, but you don't get the job :)

You should loop 0 to 8. You could do the compliment of this with fewer negates

number = 0
for i = 0 to 8:
number |= (1 (num[i]-1))
return log2(number^0x3ff)+1

This probably still has a bug. This whole AND/OR/shift/log2 stuff is still slower (even though it is clever) than a bunch of ADDs and one SUB. Plus you have storage requirement problems for numbers greater than 31 (assuming 32 bit machine). The sum thing runs out at around 32k (same 32 bit machine) if you multiple in the right order. Don't even think about using floats for large values.

You can also use xor's to get the answer which is one instruction quicker and doesn't have terrible bit storage requirements.

For example 1-15 then the answer would be

number = 0
for i = 0 to 14:
number ^= num[i]

If you wanted to do 1-10 then the answer would be

number = 11 ^ 12 ^ 13 ^ 14 ^ 15;
for i = 0 to 8:
number ^= num[i]

Funny, in this case, 11 ^ 12 ^ 13 ^ 14 ^ 15 = 11. Makes me wonder.

Can I get a new job now?

Lots of different answers.