I've been through a bunch of interviews of late, and I've gotten a lot of good questions. I've done well, but not great, and so I'm still interviewing I thought maybe talking about the puzzle questions that folks have answered might be a better way to get my thinking juices rolling. Here's one that I got recently:

=====Question=====
Given an array of points, find the line through the origin that passes through the most points
=====Question=====

=====My Answer=====
Use a hashset where the key is the slope, and the value is the number of points. Iterate over the points, iterate over the keys, and find the maximum value. Runtime ~ O(2n)

3/9/2008 1:19:37 AM

Q: where do you see yourself in 5 years.

A: being your boss.

3/9/2008 2:22:17 AM

^ that doesn't make any sense...

3/9/2008 3:24:42 AM

^ He forgot this wasn't chit-chat.

3/9/2008 3:31:58 AM

chitchat, wtf you talkin bout?

Thread Title: "Interview Questions/Answers"

open-ended personality questions like that one is probably the most popular interview question out there.

3/9/2008 3:45:55 AM

AHHH, now I get it. I meant technical questions, and so lesson learned

3/9/2008 12:25:33 PM

hardest technical question I had for a Jr. Sys Admin job I ended up getting a few years ago was..

How do you check disk space usage on a *nix server


I honestly thought it was a trick question and actually had to think about it..



df -k

I mean.. I was like WTF... ask me something harder!

3/9/2008 12:40:04 PM

I would be really sad to be asked questions that easy. At the same time, if you're not doing rocket science, then all they need to know is that you know what you're doing...

3/11/2008 10:28:11 AM

Quote :

"=====My Answer===== Use a hashset where the key is the slope, and the value is the number of points. Iterate over the points, iterate over the keys, and find the maximum value. Runtime ~ O(2n)"

Shouldn't you have said something about linear regression or least-squares fitting?

3/11/2008 11:26:45 AM

and so that was my original answer, but the guy said that's not what he was looking for. Because the line has to go through the origin, you aren't looking for the "line of best fit", but the "line through the origin that goes through the most points".

3/11/2008 8:08:04 PM

Hmm, I'm still not sure I follow your solution, but oh well.

My friend had an interview with Epic Games and they asked him this:

There is a 100 story building and you only have 2 xboxes. Your task is to find the absolute maximum height that the xbox can be dropped from with out breaking.

My friend said something about a binary search or setting up a system of equations and then taking a derivative and setting equal to zero. That's not what I would have said.

3/11/2008 8:54:41 PM

^ that's a pretty standard question. The solution I've always heard is that you take the square root of the building height, and drop the xbox (or egg) from increments of the square root. Once it breaks, start at the last height from which it didn't break, and increment in units of 1.

3/12/2008 7:22:09 AM

^Yeah, thats what I would have said, sort of. I'd say start with 2^0 and then increment the exponent until it breaks, back off to the last exponent and increase by 1. If its a CS job, it can't hurt to mention this how TCP does congestion control.

3/12/2008 8:06:03 AM

Now I'm no expert on the structural integrity of an Xbox and how it is effected by fatigue, but couldn't you just go to a first story window and drop it? If it doesn't break, go up a story and drop it again? Repeat until it breaks?

3/12/2008 8:31:49 AM

I forgot to mention that they wanted you to accomplish this in the fewest number of drops.

3/12/2008 8:32:34 AM

Quote :

"Shouldn't you have said something about linear regression or least-squares fitting?"

i agree with the above.

if i were your interviewer monvural, i would have spit in your face and kicked you out right then and there

any n00b knows how to store and keep the values. that was a weak response imo.

but good luck with getting the job

3/12/2008 10:41:13 AM

Now that I think about it more carefully, Linear Regression might not have been the way to go. LR doesn't guarantee that the line will go through even 1 point, but rather it minimizes the overall distance of the points away from the line. So you could have a line with a much greater total error than a LR line, but passes through more points as the LR line could actually go through 0 points.

I think would have said something like start with the lowest y coordinate and use point-slope from the origin to this point. Use this to project out and see if any of the other points in the array are on this line. Go to the next lowest y coordinate and repeat until you're done, and return the max.

[Edited on March 12, 2008 at 12:47 PM. Reason : .]

3/12/2008 12:42:37 PM

Q: where do you see yourself in 5 years.

A: On a boat with your daughter.

laugh laugh, nod, laugh. Now let's play golf.

3/12/2008 2:06:53 PM

Quote :

"I think would have said something like start with the lowest y coordinate and use point-slope from the origin to this point. Use this to project out and see if any of the other points in the array are on this line. Go to the next lowest y coordinate and repeat until you're done, and return the max."

So the challenge is again that it has to go through the origin. This makes the slope of your line y/x, and this y/x becomes the value that you want to use to find which points share a line (which is intuitive after saying it). I think that the challenge is finding the right data structure that will let you hold the slope value, and an associated point count. Otherwise, you'll find yourself going through the array for the number of slopes that you find.

3/21/2008 12:56:10 AM

Quote :

"^ that's a pretty standard question. The solution I've always heard is that you take the square root of the building height, and drop the xbox (or egg) from increments of the square root. Once it breaks, start at the last height from which it didn't break, and increment in units of 1. "

The problem with this approach is that it's very conceivable the xbox will break at the 10th floor AND the 9th/11th floor and all your Xboxes are gone. The only way to be certain you're at the max height is to start from the bottom and work your way up linearly, probably alternating which xbox you drop to minimize degradation due to the stress of repeated droppings.

And if it's a 360, there's a good chance it's broken from the factory

[Edited on March 21, 2008 at 1:19 AM. Reason : ]

3/21/2008 1:05:22 AM

Quote :

"Q: where do you see yourself in 5 years. A: being your boss."

my brother used that when he interviewed for a job in Germany. Needless to say he got the job and the general manager was impressed by his response...as simple as that may sound.

3/21/2008 8:15:49 AM

3/21/2008 8:21:50 AM

3/21/2008 8:25:14 AM

Quote :

" And if it's a 360, there's a good chance it's broken from the factory"

I would definitely have a smartass answer. That's a terrible question.


Or I'd say something like "It's probably been done before, so I'll just need 5 minutes on google and I'll let you know."

3/21/2008 8:42:37 AM

Got raped in an interview recently.

Ok not so much raped, but I was disappointed in my performance.

3/31/2008 9:39:10 AM

details?

3/31/2008 9:56:15 AM

I wasnt technically prepared enough, but I was behaviorally, socially, and prodecure/process driven enough to be considered enough to make it to the last round of interviews (personality and character they wanted in the group).

There were some questions I could have taken a stab at more than I did, but I chose to remain reserved and simply tell them I didnt know.

That was essentially what happened. I didnt feel like I tried hard enough to answer some technical questions. Admittedly one of the team leads said he was going to ask me a question about OSPF which was a trick question anyway. IMO its a pretty dickhead move to ask trick questions in an interview but eh, whatev.

[Edited on March 31, 2008 at 10:19 AM. Reason : .]

3/31/2008 10:15:37 AM

eh


you can't train personality.



all the other shit can come later.

3/31/2008 10:29:02 AM

so i had an interview for a developer position yesterday and they had me write a couple queries and the one i goofed on involved using a having clause to get a subset. on a scale of 1-10 how lame does that make me look?

5/1/2009 10:48:48 AM

Relax, only probably a 7 or 8 in lameness. Interviewers know people get nervous.

As far as the line question, I'd start with a line that was defined by the origin and then do a breadth first search over each of the possible second points in the graph. It takes worst case O(n+m) time and I'd be making the assumption that the line we're looking for would, under the typical case, hit points close to the origin. If this turned out not to be the case, you could adjust the search to be depth first with the same worst case running time and look for the opposite case first.

5/1/2009 11:12:09 AM

I was going for a tech related job a few months ago and i got this question at the end:

=====Question=====
So.. what gets you going in the morning?
=====Question=====

I joked and said coffee. Should have gave a serious answer to a half joke question. Needless to say, i didn't get the job.

5/1/2009 3:02:24 PM

I'm with you on this one. What kind of serious answer is there to a question like that?

I think I'd have responded with, "a breakfast bagel and a quick release with my wife (or your wife)."

5/1/2009 3:13:46 PM