Log in

No account? Create an account

Previous Entry | Next Entry

I've been meaning to comment on an entry I found on the Facebook CareerCup page The Toughest Interview Question:

"Take an array of n values where each value is an int between 1 and n-1, for example 5 numbers between 1 and 4. Obviously, there must be at least one duplicate number in this array. Write a function that finds a duplicate value. Okay, easy enough. However, the interviewer insisted that the code cannot allocate any new memory (so i can't keep a hash table of what I've read so far, or allocate a new array) and it also must be O(n) (so i can't just look at the first number then scan the whole array looking for the same number).."

Now despite the fact that I know the "trick" that's used to get this answer, I didn't think of it. Granted, I was really busy when I first read the entry, so I didn't really spend much time on it. But I was a little disappointed that the answer did not come to me quickly. But if I should ever need to be interviewed again, it's less likely that I'll be stumped by this, because it'll be in the back of my mind somewhere.

Just a few days ago, I interviewed a candidate for a position in my group. Without going into too many details, I confirmed some of what I've written on the subject of tech interviews here and elsewhere. I will say however that the candidate was very enthusiastic, which made an impression on everyone in my group who spoke to him. The significance of this is clear, and it's something I'll need to work on. I'm sure that in some of my interviews from hell, I had a "deer in headlights" look on my face and tone of voice.

The experience of being on the other side of the table was informative and refreshing. I think the time I've spent researching and discussing tech interviews will make me a better interviewer, and hopefully a better interviewee, should the need arise.



( 3 comments — Leave a comment )
Apr. 10th, 2009 09:16 pm (UTC)
What was the answer?

Chuck's response:
"Using the example of five numbers ranging from 1 to 4, 4*(4+1)/2 = 10. If there were two 3s, the sum would be 13 and easily discovered by simple math."

wouldn't be correct since there could be more than one duplicate (1, 1, 1, 5, 5) which would sum to 13.

I didn't get how the rule of 78 worked :(

Ah this also explains my interview failures since I can't express enthusiasm.
Apr. 10th, 2009 09:34 pm (UTC)
Oops! the range is 1 - 4 so a (1, 1, 3, 4, 4) would still sum to 13 but 3 wouldn't be a duplicate.

I ended up finding the answer online.
Apr. 11th, 2009 02:30 am (UTC)
Is this what you found?

Finding Duplicate Elements in an Array :: Phil! Gold

When I first encountered the question on Facebook, I didn't read it carefully. Upon rereading it, I realize your interpretation is correct. The solutions are (IMO) not obvious – beyond the level at which people picked at random from the software profession would be able to answer. (And the people who specialize in such algorithm analyses could not answer other questions that are routine in different specialties.)
( 3 comments — Leave a comment )

Latest Month

December 2017

Page Summary

Powered by LiveJournal.com
Designed by Tiffany Chow