5 ms·

The biggest misconception I ever came across was during a job interview in which I was the interviewee. After explaining skip-lists and sketching up the Big-O

by buro9 14y ago

The biggest misconception I ever came across was during a job interview in which I was the interviewee. After explaining skip-lists and sketching up the Big-O complexities for best and worst case for sorted and unsorted data... the interviewer turned to me and asked why wouldn't I use a skip-list (it should already have rung bells that it wasn't "in which instances might you not use"). My answer was that each problem should be understood in terms of the data and task before choosing a data structure and algorithm. That answer was rejected. The interviewers answer: "No, you shouldn't use skip lists because the memory of all those extra pointers is too much for the JVM." The biggest misconception I've come across is that Big-O says anything at all about the language you're coding in and your implementation. I did point this out, but was shot down pretty fast. The company in that scenario was AWS, the position was architect level. I didn't take the job. Interestingly they offered me another job different from the one that I had been interviewed devoid of any product dev at all on the basis that I was "too technical" for any role that included product. Big-O doesn't care for your implementation.

jiggy2011 14y ago
Weird, I don't quite understand how the pointers would be "too much for the JVM". I suppose this will depend on how many layers your skip list has and how big it is etc. Is there some reason (related to GC or whatever?) that it is bad in particular to use pointer heavy data structures on the JVM?
- buro9 14y ago
  I questioned the same thing, but he answered with "the list might have millions of items". Java isn't my strong point but I struggled to think how it might be an issue. Interviews aren't the place to possibly end up making the interviewer look foolish. I just let it go. If I was working with him I'd say "Show me". As I'm still curious as to whether it makes any difference. Wasn't the point though, Big-O still doesn't care about the implementation.
  - dbaupp 14y ago
    Java isn't my strong point either, so this is more of a question than an answer. But Java is built around objects (and so everything is a pointer), so the JVM is designed to work with pointer-heavy code, I would think. (Or is that incorrect?)
    - jiggy2011 14y ago
      Java does have primitive types like int , char etc which I believe are stack allocated. Java programmers do like to "box" these into classes like "Integer" etc though. What I find confusing about the answer is that it implies that there is some reason that a skip list (compared to another structure) would be particularly inefficient in the JVM (compared to say native C++). Basically a skip list will cost you some extra memory by storing more pointers which allow you to "skip" ahead the list but as you add extra layers each layer will have less pointers than the one below it. A skip list might be a bad idea if you are working a severely memory constrained system and saving memory is more important than lookup speed on your data structure. They would also of course be a bad idea if there is another structure better suited to what you are doing (B tree or whatever). But saying "Skip lists are bad because there are too many pointers for Java" just seems like a big wtf to me, unless there is something I am missing here.
      - Espressosaurus 14y ago
        While he worded it poorly, he is correct. Kinda. In a skip list with millions of items, you're going to have something like n log(n) SkipListObjects. The references are virtually free. The objects are not. On a typical JVM implementation, each object takes ~100 bytes. IIRC even an empty ArrayList will cost you something like 60-80 bytes. If the extra log(n) of space complexity is going to make a difference, then a skip list might not make sense. But honestly, if you've got millions of objects, you might want to consider a different language/environment. Java is pretty fast these days, but it will still chew up considerably more memory than most native solutions.
        14y ago
vph 14y ago
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.

by buro9 14y ago

jiggy2011 14y ago

Weird, I don't quite understand how the pointers would be "too much for the JVM". I suppose this will depend on how many layers your skip list has and how big it is etc. Is there some reason (related to GC or whatever?) that it is bad in particular to use pointer heavy data structures on the JVM?

buro9 14y ago
I questioned the same thing, but he answered with "the list might have millions of items". Java isn't my strong point but I struggled to think how it might be an issue. Interviews aren't the place to possibly end up making the interviewer look foolish. I just let it go. If I was working with him I'd say "Show me". As I'm still curious as to whether it makes any difference. Wasn't the point though, Big-O still doesn't care about the implementation.
- dbaupp 14y ago
  Java isn't my strong point either, so this is more of a question than an answer. But Java is built around objects (and so everything is a pointer), so the JVM is designed to work with pointer-heavy code, I would think. (Or is that incorrect?)
  - jiggy2011 14y ago
    Java does have primitive types like int , char etc which I believe are stack allocated. Java programmers do like to "box" these into classes like "Integer" etc though. What I find confusing about the answer is that it implies that there is some reason that a skip list (compared to another structure) would be particularly inefficient in the JVM (compared to say native C++). Basically a skip list will cost you some extra memory by storing more pointers which allow you to "skip" ahead the list but as you add extra layers each layer will have less pointers than the one below it. A skip list might be a bad idea if you are working a severely memory constrained system and saving memory is more important than lookup speed on your data structure. They would also of course be a bad idea if there is another structure better suited to what you are doing (B tree or whatever). But saying "Skip lists are bad because there are too many pointers for Java" just seems like a big wtf to me, unless there is something I am missing here.
    - Espressosaurus 14y ago
      While he worded it poorly, he is correct. Kinda. In a skip list with millions of items, you're going to have something like n log(n) SkipListObjects. The references are virtually free. The objects are not. On a typical JVM implementation, each object takes ~100 bytes. IIRC even an empty ArrayList will cost you something like 60-80 bytes. If the extra log(n) of space complexity is going to make a difference, then a skip list might not make sense. But honestly, if you've got millions of objects, you might want to consider a different language/environment. Java is pretty fast these days, but it will still chew up considerably more memory than most native solutions.
      - 14y ago

vph 14y ago

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.