Slashdot Mirror
Tech-Interview Riddles
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."
for more tech interview questions and answers try http://www.techinterview.org/
The "official" answer (which Microsoft was still using as recently as a couple of years ago, according to some friends of mine who interviewed there) is so the covers won't fall through the hole.
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.....
Well, crikey. But ask yourself this - if not round, well, what?
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 answers from the hard section:
.2 with an average payoff of $5. That means that the probability of getting a face card is .8 with a payoff of 11.5. Using more precise figures, i.e. not .2 and .8, the average payoff is about 10.0857 (706/70)
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
Another good resource: the Princeton Mathclub
my other sig is a 500 page novel
I only ask one "tech" question when interviewing prospective programmers:
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.
What would Lemmy do?
You're neither one as 1334 as you think.
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.
I did a lot of interviews at MS when I was there, and I quickly learned not to ask riddles. First off, it makes people who don't get them uncomfortable and angry. Second, it doesn't actually show that the person can write software.
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.
In 1998 I was interviewed by the Technical Director of a small company in the UK. Their standard tech question was "write a function to rotate a monochrome bitmap". The idea was not to come up with necessarily the correct answer (as if there was *one* correct answer), but to see how you tackled the problem. The only problem with that particular question is that there was a danger that some otherwise perfectly adequate programmers would freeze like a rabbit caught in headlights.
OTOH I've never seen a company with a higher concentration of good programming skills.
All I want is a secure system where it's easy to do anything I want. Is that too much to ask ~~ Randall Munroe
Actually you do not need the man pages. Correct me if I am wrong here... BUT...
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?
"You can't make a race horse of a pig"
"No," said Samuel, "but you can make very fast pig"
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.
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.