3 ms·

I have mixed feelings about algorithmic interview questions. There is the camp that says that you shouldn't memorize something you can look up, but I am of the

I have mixed feelings about algorithmic interview questions. There is the camp that says that you shouldn't memorize something you can look up, but I am of the opinion that having something memorized fundamentally changes the flow of thought. If you just know the lookup times of various datastructures, your thought process is much less jumbled than someone who must look them up while problem solving. I'm not suggesting that it's necessary for someone be able to whiteboard an implementation of a red-black tree, but knowing what it is, and its advantages and disadvantages compared to an AVL tree or something is very useful. As an aside, in a graduate CS class I took (about search engines), the prof asked "What is the lookup time of a balanced binary tree" to various students, two of whom gave wrong answers before she got to me. One said "n lg n" and the other said "n". It was evident that they were basically guessing. My point is that if you actually understand what a binary tree is, the lookup time of it should be obvious. Same for most other basic datastructures, linked list, hash table, etc. I think asked basic, high-level questions about these are totally fair game.

seiji 13y ago
If you just know the lookup times of various data structures, The problem isn't knowing complexity, but rather with expecting someone to code something elaborate from memory while being timed, watched, and judged by a stranger. "Code a Fibonacci heap right now, live, with no references. Begin." Nobody is arguing you shouldn't know the complexity of everything off the top of your head. You absolutely should [1], but you should also be able to figure it out pretty quickly if you don't know it. That means understanding what lg n means and understand what 2^n means, etc. (Yes, we're agreeing here, I'm just reiterating.) [1]: http://bigocheatsheet.com http://bigocheatsheet.com
ndr 13y ago
[pedantic] Technically, look up on a balanced binary tree is still O(n) as it says nothing about the ordering. If it was a balanced binary search tree then it would be O(log(n)) which I guess is the answer you gave. [/pedantic] A part from that I totally agree with you on the importance of knowing by heart the implications of some technical choices.
- nostrademons 13y ago
  (I upvoted you because you're pedantically correct, but being even more pedantic: if it's not a balanced binary search tree, is "lookup" even a valid operation on it?)
  - marcosdumay 13y ago
    Well, lookup is a valid operation on any dataset.
    - nostrademons 13y ago
      Not really: "lookup" is not part of the API (as taught in a typical data-structures class) for stacks, queues, and priority queues, and technically arrays/vectors let you lookup by integer but the O(N) lookup by object is only an extension that most languages provide as a convenience. If we really want to be pedantic, we'd have to define what the binary tree is used for, because there's no convention for what "lookup" means in this case. A heap, for example, can be implemented as a balanced binary tree, but the only methods it provides are push, pop, and top.
- gizmo686 13y ago
  The lookup time of a binary search tree is also in O(n). Personally, regardless of the algorithm, I prefer to just say that it is in O(Ackermann(n,n)).
LordHumungous 13y ago
In college an old physics professor of mine once told me that you don't really know something until you can clearly explain it to other people. And you can't explain things to other people unless you have the basic concepts memorized. I think about that every time people complain that it's not fair for interviewers to ask them to explain basic programming concepts.
RogerL 13y ago
Yes, and no. ;) These are important things to know. But, they are also easy to know. I don't care too much if somebody doesn't know them, it's just knowledge. All I care is if they can learn and understand it. I am not always on my A game, but when I interview I basically probe until I find an area where they are not strong or familiar. I don't care too much about the questions they get right (they've already been vetted as to actually knowing the language they claim to know). It's just knowledge. But, when they get to something they don't know, that is when it is interesting, and telling. If they can't give you the time of search on a binary tree, awesome! Awesome because now you can actually measure how they think and take on new info, rather than regurgitate stuff (some people have prodigious memory, and can mirror back almost anything, after all). Ask them how they would figure it out. Ask what the structure of a tree is. Ask for the math for # of leafs vs depth, that sort of thing. Help them out when they get the deer in the headlight look. Once they get an answer, immediately change the question and see if they can derive the answer for that new question (say, switch from binary tree to trie). In some ways college was hard for me - for whatever reason I didn't internalize a lot of the algorithm stuff until I got to grad school, where I ended up TAing for the grad level algorithms course after awhile. Of course, a common thought is that the algorithms question are meant to test thinking, not memory. I claim that is hogwash. Most of these classic algorithms were invented by giants in the field, alongside other giants that did not think of the algorithm. And some random person, off the street, is supposed to just re-invent a classic algorithm off the cuff? Right. Chances are great that unless you are Google, if that person actually did do it they'd end up so bored at your company that they'd leave in a few months anyway. Look for what the candidate doesn't know, give them the info, and see if they can synthesize it and do something with it. Don't try to see if they are CAR Hoare - they aren't, and you don't need to hire him anyway. IMO, of course.

seiji 13y ago

If you just know the lookup times of various data structures, The problem isn't knowing complexity, but rather with expecting someone to code something elaborate from memory while being timed, watched, and judged by a stranger. "Code a Fibonacci heap right now, live, with no references. Begin." Nobody is arguing you shouldn't know the complexity of everything off the top of your head. You absolutely should [1], but you should also be able to figure it out pretty quickly if you don't know it. That means understanding what lg n means and understand what 2^n means, etc. (Yes, we're agreeing here, I'm just reiterating.) [1]: http://bigocheatsheet.com http://bigocheatsheet.com

ndr 13y ago

[pedantic] Technically, look up on a balanced binary tree is still O(n) as it says nothing about the ordering. If it was a balanced binary search tree then it would be O(log(n)) which I guess is the answer you gave. [/pedantic] A part from that I totally agree with you on the importance of knowing by heart the implications of some technical choices.

nostrademons 13y ago
(I upvoted you because you're pedantically correct, but being even more pedantic: if it's not a balanced binary search tree, is "lookup" even a valid operation on it?)
- marcosdumay 13y ago
  Well, lookup is a valid operation on any dataset.
  - nostrademons 13y ago
    Not really: "lookup" is not part of the API (as taught in a typical data-structures class) for stacks, queues, and priority queues, and technically arrays/vectors let you lookup by integer but the O(N) lookup by object is only an extension that most languages provide as a convenience. If we really want to be pedantic, we'd have to define what the binary tree is used for, because there's no convention for what "lookup" means in this case. A heap, for example, can be implemented as a balanced binary tree, but the only methods it provides are push, pop, and top.
gizmo686 13y ago
The lookup time of a binary search tree is also in O(n). Personally, regardless of the algorithm, I prefer to just say that it is in O(Ackermann(n,n)).

LordHumungous 13y ago

In college an old physics professor of mine once told me that you don't really know something until you can clearly explain it to other people. And you can't explain things to other people unless you have the basic concepts memorized. I think about that every time people complain that it's not fair for interviewers to ask them to explain basic programming concepts.

RogerL 13y ago

Yes, and no. ;) These are important things to know. But, they are also easy to know. I don't care too much if somebody doesn't know them, it's just knowledge. All I care is if they can learn and understand it. I am not always on my A game, but when I interview I basically probe until I find an area where they are not strong or familiar. I don't care too much about the questions they get right (they've already been vetted as to actually knowing the language they claim to know). It's just knowledge. But, when they get to something they don't know, that is when it is interesting, and telling. If they can't give you the time of search on a binary tree, awesome! Awesome because now you can actually measure how they think and take on new info, rather than regurgitate stuff (some people have prodigious memory, and can mirror back almost anything, after all). Ask them how they would figure it out. Ask what the structure of a tree is. Ask for the math for # of leafs vs depth, that sort of thing. Help them out when they get the deer in the headlight look. Once they get an answer, immediately change the question and see if they can derive the answer for that new question (say, switch from binary tree to trie). In some ways college was hard for me - for whatever reason I didn't internalize a lot of the algorithm stuff until I got to grad school, where I ended up TAing for the grad level algorithms course after awhile. Of course, a common thought is that the algorithms question are meant to test thinking, not memory. I claim that is hogwash. Most of these classic algorithms were invented by giants in the field, alongside other giants that did not think of the algorithm. And some random person, off the street, is supposed to just re-invent a classic algorithm off the cuff? Right. Chances are great that unless you are Google, if that person actually did do it they'd end up so bored at your company that they'd leave in a few months anyway. Look for what the candidate doesn't know, give them the info, and see if they can synthesize it and do something with it. Don't try to see if they are CAR Hoare - they aren't, and you don't need to hire him anyway. IMO, of course.