3 ms·

Based on your testimony, it seems the interviewer did not ask you a question about big-O, and you thought he did.

• buro9 14y ago
  No, he did. The question was roughly: "As you seem to like algorithms could you explain what skip lists are, draw on the whiteboard if necessary.". After that came, "Now, using Big-O, explain why this could be better than a normal linked list". Before finally the "Why wouldn't you use skip lists?" and that classic answer. And there were 2 interviewers in the room. One was leading and the other was observing and learning how to interview.
  • cube13 14y ago
    >Before finally the "Why wouldn't you use skip lists?" and that classic answer. That answer was a non-answer, though. Saying "You pick the best structure for the data" doesn't answer the question "Why would you not use a skiplist". A few reasons, off the top of my head: 1. Size of the list structures can get gigantic, especially as the total size of the list increases. This is especially true with 64-bit pointers, and small data(ASCII names, integers, etc.). 2. While the list is very good(O(log n) ) for searches, additions and deletions can be problematic, especially if they're more common than lookups. 3. Depending on the implementation/language, it might be a good idea to pre-allocate the pointer array. Increasing the list size above the supported pointer array size can be a major headache.