Hacker News Reader

Comment by nappy-doo | Hacker News Reader

sigh Unless your nomenclature is all screwed up, and you're confusing arrays and lists, finding an element in a sorted list takes O(N) time -- binary search doesn't work on lists.

I do a lot of interviewing (at my company). Here's other common misconceptions lots of candidates have:

* Quicksort is O(N^2) -- don't make that mistake.

* There are plenty of "faster than O(NlogN) sorting algorithms, but they're all special cases. (Radix, Merge on multiple processors, etc.)

* Hashing is not a panacea. Collisions are always worth mentioning.

View on HN

A standard Quicksort implementation is absolutely worst-case O(N^2). Variants do exist like median-of-medians quicksort or introsort, but I would never describe O(N^2) as wrong. In fact, I would be very happy if candidates knew the difference between worst-case and average-case analysis.

I think you are confusing your nomenclature. The term "list" does not necessarily imply that it is a linked list.

Binary search requires random access. Things that support random access can be used as lists, but not all lists support random access.

first of all, it's all nomenclature, and i don't want to make a whole thing out of this, but binary search requires that you can randomly go left or right every time you subdivide the (linear) ordering, not that you can randomly index to any element.

EDIT also, perhaps against better judgment, i'm going to throw a possibly inflammatory remark out there and say that the big-O thing is really not that difficult or important (although i suppose that it's important that it not be difficult). what i can see taking some skill/experience (which i totally don't have) is knowing a bunch of algorithms and being able to consider the time/space tradeoffs of the algorithms you already know quickly. being able to prove the time-complexity of some new algorithm is good, but, sadly, perhaps, i don't think most companies hire people to do that.

i wish people would comment when they downvote. i made the final comment already knowing (and stating!) that it might rub someone the wrong way but hoping that it might provoke discussion. it's a reasoned and reasonably-informed comment, not just noise-making or an attempt to troll. downvoting without comment in that situation doesn't really further the discussion.

I imagine you were downvoted for being wrong about binary search (it does require O(1) indexing).

of course, when there are two or three items left, choosing between left and right is the same as choosing an arbitrary index. that's nomenclature. whether you follow the rote textbook definition and do that indexing up front or delay it until you've paired down your possibly-large list into a manageable (whatever that might mean for the problem domain you're dealing with) size, it's still pretty much the same algorithm.

and since you're imagining rather than being certain, that means people continue to downvote without comment, and i continue to cheerily object to that.

Merge is indeed faster on multiple processors than, say, heap sort. Though it will still be nlogn.

Regarding hashes - it is not clear if you want the cadidate to mention collisions or not.

Reply on news.ycombinator.com