3 ms·

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 doe

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.

cubancigar11 13y ago
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.
davidddavidson 13y ago
I think you are confusing your nomenclature. The term "list" does not necessarily imply that it is a linked list.
- tbrownaw 13y ago
  Binary search requires random access. Things that support random access can be used as lists, but not all lists support random access.
  - auvrw 13y ago
    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.
    - auvrw 13y ago
      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.
      - mden 13y ago
        I imagine you were downvoted for being wrong about binary search (it does require O(1) indexing).
        auvrw 13y ago
        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.
thurn 13y ago
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.

cubancigar11 13y ago

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.

davidddavidson 13y ago

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

tbrownaw 13y ago
Binary search requires random access. Things that support random access can be used as lists, but not all lists support random access.
- auvrw 13y ago
  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.
  - auvrw 13y ago
    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.
    - mden 13y ago
      I imagine you were downvoted for being wrong about binary search (it does require O(1) indexing).
      - auvrw 13y ago
        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.

thurn 13y ago

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.