4 ms·

A set of interesting interview questions.

11 points by raju 18y ago

smanek 18y ago
I think there was an error in his analysis of the naive solution for finding loops in linked lists (at http://20bits.com/2008/04/17/interview-questions-loops-in-linked-lists/ http://20bits.com/2008/04/17/interview-questions-loops-in-li...) I don't know Ruby, so correct me if I'm mistaken, but I believe the naive solution presented runs in O(n) space and O(n^2) time (not O(n) time, as the author suggests). If you used a hash table to keep track of nodes seen so far, you could do O(n) time and space. The tortoise and the hare solution is quite elegant though.
- cperciva 18y ago
  The tortoise and the hare solution is quite elegant though. This approach is more correctly known as Floyd's cycle-finding algorithm, and while it is suboptimal, it comes within a constant factor of the optimum for logspace algorithms.
  - smanek 18y ago
    Just for my own edification, what is the optimal solution? I haven't yet seen a proof on the lower bound of cycle detection, so I don't know if other quicker solutions (like Brent's algorithm) are optimal or are just the best we've found. And I don't think there is anything incorrect with referring to Floyd's cycle-finding algorithm as the tortoise and the hare algorithm. Most literature I've seen mentions the alias too.
- utnick 18y ago
  How many of you could have came up with the tortoise and hare solution on your own without seeing this problem previously? Its an elegant solution, but extremely non obvious. I'm kind of bitter about this question cause Microsoft asked me that question when I interviewed... and I only came up with the naive solution :) and then the interviewer smugly explained the tortoise and hare one haha
tonystubblebine 18y ago
Some people don't like gotcha questions of this type for the reason that they often aren't relevant to the type of work you're hiring for. If you're more concerned with productivity, a good technique I've used is to sit someone down at a computer and give them a simple programming task. Then sit near them and listen to how fast they type. Almost everyone is going to make noises about being nervous (because it is nerve wracking) but you can usually tell right away who is practiced in writing code and who is merely familiar with the theory of writing code. It's often hard to tell the two apart just by asking questions. Of course, you should look at the code afterward but a surprisingly high number of people don't make enough noise on their keyboard for you to even bother. An example web development task might be to create a form that asks for a search term and then returns all matching rows in a database. Easy, right? It's supposed to be. Of course, you could also limit yourself to hiring people with open source projects. But of all the people I've hired, the one who did best on the gotcha questions was also the least productive in terms of building software. So you want to get proof of productivity somehow.
jfarmer 18y ago
I wish there a way to be notified when a URL from a certain domain is submitted to hacker news! I would've voted it up sooner. Anyhow, thanks for submitting this. There are more questions to come so keep your eyes out.
- raju 18y ago
  Hey jfarmer! I was not aware that you were on Hacker News. Came across your articles and figured this would be the best community to share it with. Thanks, and keep 'em coming. Enjoyed the articles.

11 points by raju 18y ago

I think there was an error in his analysis of the naive solution for finding loops in linked lists (at http://20bits.com/2008/04/17/interview-questions-loops-in-linked-lists/ http://20bits.com/2008/04/17/interview-questions-loops-in-li...) I don't know Ruby, so correct me if I'm mistaken, but I believe the naive solution presented runs in O(n) space and O(n^2) time (not O(n) time, as the author suggests). If you used a hash table to keep track of nodes seen so far, you could do O(n) time and space. The tortoise and the hare solution is quite elegant though.

cperciva 18y ago
The tortoise and the hare solution is quite elegant though. This approach is more correctly known as Floyd's cycle-finding algorithm, and while it is suboptimal, it comes within a constant factor of the optimum for logspace algorithms.
- smanek 18y ago
  Just for my own edification, what is the optimal solution? I haven't yet seen a proof on the lower bound of cycle detection, so I don't know if other quicker solutions (like Brent's algorithm) are optimal or are just the best we've found. And I don't think there is anything incorrect with referring to Floyd's cycle-finding algorithm as the tortoise and the hare algorithm. Most literature I've seen mentions the alias too.
utnick 18y ago
How many of you could have came up with the tortoise and hare solution on your own without seeing this problem previously? Its an elegant solution, but extremely non obvious. I'm kind of bitter about this question cause Microsoft asked me that question when I interviewed... and I only came up with the naive solution :) and then the interviewer smugly explained the tortoise and hare one haha

tonystubblebine 18y ago

Some people don't like gotcha questions of this type for the reason that they often aren't relevant to the type of work you're hiring for. If you're more concerned with productivity, a good technique I've used is to sit someone down at a computer and give them a simple programming task. Then sit near them and listen to how fast they type. Almost everyone is going to make noises about being nervous (because it is nerve wracking) but you can usually tell right away who is practiced in writing code and who is merely familiar with the theory of writing code. It's often hard to tell the two apart just by asking questions. Of course, you should look at the code afterward but a surprisingly high number of people don't make enough noise on their keyboard for you to even bother. An example web development task might be to create a form that asks for a search term and then returns all matching rows in a database. Easy, right? It's supposed to be. Of course, you could also limit yourself to hiring people with open source projects. But of all the people I've hired, the one who did best on the gotcha questions was also the least productive in terms of building software. So you want to get proof of productivity somehow.

jfarmer 18y ago

I wish there a way to be notified when a URL from a certain domain is submitted to hacker news! I would've voted it up sooner. Anyhow, thanks for submitting this. There are more questions to come so keep your eyes out.

raju 18y ago
Hey jfarmer! I was not aware that you were on Hacker News. Came across your articles and figured this would be the best community to share it with. Thanks, and keep 'em coming. Enjoyed the articles.