Tech-Interview Riddles 843
An anonymous submitter writes "A computer engineering student at UC Berkeley has made a comprehensive archive of riddles from technical interviews. Very challenging and loads of fun. Also useful for interview preparation."
more info... (Score:5, Informative)
Re:The date is the riddle. (Score:2, Informative)
Re:One of my favorites (Score:1, Informative)
unsigned triple_protect(unsigned a, unsigned b, unsigned c)
{
unsigned tmp1, tmp2, tmp3;
tmp1 = a & b;
tmp2 = b & c;
tmp3 = a & c;
return (tmp1 | tmp2 | tmp3);
}
google cache.. (Score:2, Informative)
Google Cahce is Ace [216.239.51.100]
Re:Why do interviewers use "riddles"? (Score:4, Informative)
This answer fails on at least two levels:
1) There are plenty of manhole covers (or manhole-cover-like-objects) that aren't round. If you've been observant enough to notice this, you fail.
2) There are plenty of other curves of constant width; an infinite number, in fact. The old Wankel rotary engine used such a shape. Though a circle is the only curve of constant *radius*, that's not the issue. If you know enough math to realize this, you fail.
Another possible answer is that it makes it easier to roll a heavy cover out of the way. Again, one of the other curves of constant width would do just about as well.
The REAL answer is that no one knows.
Personally, I think Microsoft would be better off asking people why using fixed-sized buffers for user input is a bad idea, but hey.....
Re:Why do interviewers use "riddles"? (Score:4, Informative)
Okay, so you're a guy, and you have to put a hole in the street, and put a cover on it. What shape do you make it? Triangular? Well, uh, why? It's pointy, and can fall through the hole. So you wouldn't do that. Square? Well, you really can't roll it, and TRUCKS have to drive over it, so it'll be heavy, so you'd *want* to roll it, rather than heft it.
Hey, circles can roll.
Oh, yeah. And that crap about a Wankel. Why would you want to fiddle around in traffic trying to get it to be oriented properly when a circle HAS a constant radius, as you point out? You can thump it down any old way. Fits!
So, answer: Because it's just better than any other shape.
some selected answers: (Score:4, Informative)
Criminal cupbearers:
Let's assume we only have 10 prisoners and that they each drink from up to 512 bottles. Number the bottles from 0 to 999. Prisoner 9 samples 0 to 511. Prisoner 8 samples 0 to 255 and 512 to 999. Prisoner 7 samples 0 to 127, 256 to 383, 512 to 639, etc. (prisoners alternating between sampling and not sampling blocks of wine in decreasing powers of 2 -- prisoner 0 drinks from every other bottle) Now line up the prisoners after onen month and treat corpses as ones and living prisoners as zeros and you have your answer in binary.
Mysterious Triangle area
Well, to make a long story short, they're not triangles.
100 Prisoners and a Lightbulb
Well if we assume they can all see the bulb every day, they can just toggle the bulb iff this is the first time they've been selected. If the last prisoner has counted the number of times the bulb has been toggled, he can assert that he is the last one to be selected.
Square Formation
Move the "notched" piece to teh righth of the current larger square and put the small square piece in the notch. put the larger of the triangular pieces at the top, horizontal edge of the new formation.
Calendar Cubes
I like this one. You need all the numbers from 0 through 9 plus 0 through 3. That's 14 faces. You will never need 00 though, so you can remove one of the 0s. Also, you will only ever need the 3 with 0 or 1, so you can remove it from one of the blocks. The solution: the numbers 1-6 on one block, and 7-9 and 0-2 on the other. Yeah it works.
Mystery Matrix
4. Entry from row plus Entry from row 2 plus 1 mod 10.
Fork in the road I
"is that the city you come from?" If the response is yes, go there, otherwise turn away.
Fork in the road II
Assume each person is standing on his respective road. "Is one of you a liar?" Yes means he's a truth teller, no means he's a liar.
Egg Dropping
18. Drop from the 10th, 20th, 30th, etc. After it breaks, go back 9 floors and start dropping every floor. You use 18 drops if it can drop from the 98th or 99th floors.
Greedy Pirates
It's not apparent to me that this is the intended answer, but "Throw pirates 3 and 4 overboard and divide up the rest between 1,2, and 5. Pirates 1 and 2 will agree to the largest share, and pirate 5 always has a say after that, since 3 and 4 can't agree to anything, so he's needed for the majority.
Hmm, well it's getting late so I'll just do one more:
Card Game
Bob takes any card over 9. The probability that none will show up is roughly
Re:These are pretty easy (Score:2, Informative)
rec.puzzles (Score:3, Informative)
Another good resource: the Princeton Mathclub [princeton.edu]
Re:Incense riddle (Score:2, Informative)
Re:Why do interviewers use "riddles"? (Score:3, Informative)
void echo(void)
{
char *s;
gets(s);
puts(s);
}
What is wrong with this code ?
The scary thing is, over 50% of the people I ask can't answer it.
Re:One of my favorites (Score:3, Informative)
Here's 4 operations:
return (a ^ b) & c | a & b;
(Extra parens are for wimps.)
Show that it can be done in 3 C ops, or
prove it impossible.
Re:Infuriating,,, (Score:2, Informative)
Why I never asked riddles.... (Score:5, Informative)
I used a much simpler approach, so simple most people think its silly. But thats the point; nobody leaves the interview thinking they were tricked or duped. I always started with implementation of strcpy(). Half of the candidates failed right there! They took most of the hour to get it right (or not), but were able to see point-blank that they were not ready for the job.
Next, I would ask about crashing cases, and if they figured out overlapping memory locations, have them write a 'fixed' version. This weeded out another big chunk. After that, I went into some color counting algorithms.
I stayed well withing the field of what the candidate would expect, and did not try to trick him or make him nervous with off the wall riddles.
This approach worked great, and didn't leave anyone feeling robbed and abused. The ability to solve riddles *is* an indicator of how smart the person is, but it is *not* an indicator of how good a programmer they will be.
Re:Infuriating,,, (Score:2, Informative)
Re:Why do interviewers use "riddles"? (Score:3, Informative)
OTOH I've never seen a company with a higher concentration of good programming skills.
Re:Why do interviewers use "riddles"? (Score:3, Informative)
char *s; get(s); put(s);
Well s is not initialized and pointing at anything. Hence even if get allocated a buffer that value will not be carried back since it is a single pointer. For that to work you would need write get( &s) and then that would work.
Yes?
Re:A Dilemma: (Score:2, Informative)
Re:Spoiler: 100 prisoners and a light bulb (Score:2, Informative)
Unfortunately, Numbers will only be able to increase his tally by one, each time he's picked (less actually, since after a while there will be a high probability that no 'untallied' prisoner has been in the room since he was last there).
If Numbers is called on the average every 100 days, and can increase the tally by one each time, the procedure will take a bit less than 30 years!
Not that my solution is much better:
The prisoners make up their own calendar, in which every month has 100 days. Each prisoner is also assigned a number (1-100).
Now, if a prisoner is called on day N of the 'month', turning the light on is a signal to next guy that he knows for sure that prisoner number N has been in the room. Turning the light off is a signal that he doesn't have a clue about prisoner N.
If a prisoner is called on day N and sees a light, he makes a note that guy number N-1 has been in the room. The first prisoner that has all 100 checked can get the lot sprung.
Initially, each prisoner can only be sure of himself, so things will not start moving until by chance a prisoner is called on his own day. This should happen several times during the first month though. Knowledge of who has been in the room will then slowly spread among the prisoners.
The process won't complete until (some time after) every prisoner has been called on his day at least once. I tried to calculate how long that would be but my math isn't up to it. Probably some decades :-(
Re:Why do interviewers use "riddles"? (Score:3, Informative)
It sounds like the interviewer remembered a typical "impossible" question, but forgot why you ask it. The purpose isn't to think out of the box, the purpose is to examine problem solving skills with a problem the applicant has never seen before. Sure, you don't know anything about gas station density in the US, but you'll eventually be required to answer a question you don't really know anything about. "We've been asked to implement a simple web browser that will run on an embedded system that doesn't exist yet. Give me an estimate for how long it will take." It sucks, but you're going to need to do it.
Because most engineers are loathe to pull estimates out of thin air, it's only fair to explain that you're only looking for a very rough estimate. If the engineer continues to resist, explain that you know he doesn't have good input to work with.
That said, your answer, "check a search engine" isn't that bad of a place to start. (That's what reference materials are for!). When you're told that it's a good place to start, but that it's not an option, start making up numbers and guessing. Make it clear when you're guessing at numbers. "Well, there are about 300 million people in the US, about half don't have cards, so 150 million cars. You typically get gas once per week. A gas station can serve 100 people per day. That's 700 people per week, or about 1,000 for ease of doing the calculation. So you'll need about 150,000 gas stations." I promise that I pulled that answer out of the air. I have no idea how many people are in the US, let alone any of the other numbers, but I'm pretty sure that I'm within an order of magnitude. In fact, quickly searching the web it looks like I'm very close [oldgas.com].
Similar logic can get you surprisingly accurate numbers for the volume of water that flows out of the Mississippi each minute, the number of malls, police stations, high schools in the US, or other seemingly hard to know things. Just take what you do know and make educated guesses.
The string hash function was just stupid, although it might have helped to ask the interviewer what properties he wanted out of the hash. In general, bouncing questions about the problem off the interviewer looks good and can often make the solution easy. The question does sound like an esoteric knowledge question, and those are the worst.
Being asked to solve a tricky technical question? Well, it's a legit, real problem. It's a fair way to gauge your problem solving ability (did you stumble across the same things they did? Good. Did you suggest something new? Great.). I wouldn't worry about their "stealing" your answer. If the problem really is hard, it's unlikely in the ten or twenty minute interview question that you'll find a superior answer to them.
my stab at a proof (Score:2, Informative)
001 0
010 0
011 1
100 0
101 1
110 1
111 1
(a & b) | (a & c) | (b & c ) | ((a & b) & c))
Karnaugh Mapping...
'a'b 'a b a'b a b
c _ x x x
'c _ _ _ x
so the simplifications that can be made....
(c & (a | b) ) | (a & b)
there are no other 'little circles' that can be made on the map (as my EE101 prof was so fond of saying) therefore there are no further simplifications.
Re:my stab at a proof (Score:2, Informative)
well, i cant seem to get it to line up... lets see it this way... wow, that was a PITA