2 ms·
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
by 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.