How to get hired (or, 'The silly story of interviewing in the valley')

Post by tedunangst » Mon, Dec 19, 2011, 8:02 PM UTC

prostoalex wrote: post #28

timr wrote: post #3

"Then, acting as though this was the first time I'd seen this problem, I would ask if it was ok if I thought aloud as I worked my way through the problem on the board. I'd mumble to myself about moving-this-piece-over-here and-now-we're-going-to-get-this, and lo-and-behold, I accidentally solved it in constant memory space, in C - a language I didn't even claim to be particularly good at! Only someone with amazing pr…

Unless the end result is a completely incompetent applicant getting an offer, I wouldn't call the system "horribly broken". Very few companies are in the business of reversing linked lists, and hence make binary decisions depending on the outcome of just that one question. I don't think gaming the system is that trivial - an interview is a conversation, so things like computational complexity, runtime restrictions, d…

Post by kenjackson » Mon, Dec 19, 2011, 8:06 PM UTC

tptacek wrote: post #26

kenjackson wrote: post #21

Earlier quoted context omitted.

Linked lists and arrays typically have different perf characteristics (although I don't know how Ruby arrays work). For example if I give you an element of an array/linked list and tell you to insert a new element adjacent to it -- a linked list is a constant time insertion, whereas arrays are typically O(n).

That's a sensible point, but interpreter and runtime overhead crushes any cost savings you might get from adjusting links instead of the whole array backing store. (Ruby arrays, at least in MRI, are basically STL vectors). 1000 inserts to the middle of a 1,000,000 element Ruby array happens so quickly you can barely perceive the delay. The same insert pattern to a basic Ruby linked list sets my machine on fire.

Post by brown9-2 » Mon, Dec 19, 2011, 8:07 PM UTC

rauljara wrote: post #17

I was flabbergasted that someone was asked implement a linked list in Ruby. My initial reaction was 'That is an incredibly stupid thing to do.' My slightly more in depth reaction was "Isn't that what mutable arrays are for?" And my final reaction was, "Maybe I'm missing something." At which point I tried to figure out the benefits of a linked list over a ruby array. I wasn't able to come up with a good reason to use…

Post by tedunangst » Mon, Dec 19, 2011, 8:19 PM UTC

tptacek wrote: post #31

tedunangst wrote: post #30

Earlier quoted context omitted.

My first guess would be that a FIFO queue is more efficient as a list than an array, but maybe there's something weird about ruby that makes that untrue. I'd love to hear why.

Unless you have an extraordinarily clever implementation of "linked list in Ruby" (in which case this is still a terrible interview question), no. Arrays are more efficient for every reasonable access pattern. If the links of your list are references to Ruby objects (which every online "linked list in ruby" page uses), they're not so much "more efficient" as they are "tractable" compared to linked-list's "intractable…

Post by tptacek » Mon, Dec 19, 2011, 8:21 PM UTC

tedunangst wrote: post #38

tptacek wrote: post #31

Earlier quoted context omitted.

Unless you have an extraordinarily clever implementation of "linked list in Ruby" (in which case this is still a terrible interview question), no. Arrays are more efficient for every reasonable access pattern. If the links of your list are references to Ruby objects (which every online "linked list in ruby" page uses), they're not so much "more efficient" as they are "tractable" compared to linked-list's "intractable…

Looks like you're right, interpreter time dominates unless I use rbx, and it's still not a big win for linked lists. But the meaning of your last sentence escapes. Linked lists are tractable compared to intractable linked lists? Antecedent mismatch?

    1000.times { list.insert(500000, 666) }

    1000.times { array.insert(500000, 666) }