10 ms·

Data Structures Reference

287 points by typpo 8y ago

rs86 8y ago
This could benefit greatly from specifying what operations are available for each structure.
kylnew 8y ago
I recently got double slammed with 2 graph questions during an interview after having navigated for years without getting a graph question. It's wholly irrelevant to my day-to-day work but I do hobby game development sometimes which involves more needs for graphing. Still, I can't do much of anything with a graph on a whiteboard. Puzzled as to why it's so important to some companies to grill on this stuff, expecting it to be top-of-mind, even for front end roles.
- nlawalker 8y ago
  >> Puzzled as to why it's so important to some companies to grill on this stuff, expecting it to be top-of-mind, even for front end roles. Either they do consider it important to the role, or they are trying to select for young CS grads, or they just haven't tried to do any better in their hiring process, or they don't know how.
  - cipherzero 8y ago
    Maybe I’m not like the interviewers/companies to which you’re referring, but I ask a DAG topo sort question (dependency resolution/task ordering) not because I expect the candidate to regurgitate the algorithm but because I legitimately want to see how they work through a problem - especially one they may(hopefully) not be familiar with. Most of the time I don’t care if they get the optimal algorithm, rather the can think through something and know where problems might be. Might not be how/why the “others” use that question, but its worked well for me.
- User23 8y ago
  Graphs are arguably the fundamental data structure. If you can’t think about objects and references between them then how do you write nontrivial software?
  - umanwizard 8y ago
    Yes but in normal programming it is uncommon to need to write algorithms that traverse the global object graph. You normally care about some local view of it.
    - gaastonsr 8y ago
      It’s uncommon but it’s used once in a while. I do it 2-3 times a year at least. And believe me, most people wouldn’t even know how to start to do it or would think it’s too hard and prefer to do it in a different way so they don’t need to ever traverse the graph.
      - kylnew 8y ago
        Would you happen to have an example or reference to that kind of problem?
- jopsen 8y ago
  It's no secret that interviews at crazy, it's like an exam, and you should prepare accordingly. Yes, it's largely irrelevant. But an engineer who can't reason about DAG, topological sorting, etc, could easily ruin an otherwise elegant architecture :)
  - platform 8y ago
    Perhaps I do not quite understand what you meant by 'engineer that cannot reason'. Somebody might not be able to write on a white board, during an interview a topological sort or find-a-union (https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/ https://www.hackerearth.com/practice/notes/disjoint-set-unio... ). But does it mean that they will ruin 'elegant architecture'? (compared to somebody who passed the topologica sort exam)? Also, wouldn't an architecture that imposes compile time constraints, good documentation and test cases -- on the usage of its most elegant pieces, be more 'elegant' than the one, that could be easily 'ruined' but somebody who does cannot write out a 'topological sort' during an interview?
    - perfmode 8y ago
      Have you never worked with weak engineers?
      - rmwaite 8y ago
        I think their point is that just because someone can’t whiteboard something doesn’t mean they can’t reason about it.
      - anothergoogler 8y ago
        The problem with using trivia as a hiring filter is it doesn't do a good job of differentiating between those who don't know a thing, and those who know nothing, unfairly penalizing the former.
        ozim 8y ago
        But it is easy to filter out those who think they know something when they blurt out correct responses like machine. But in reality they just lerned canned responses. Usually you want to discuss problem to see reasoning. If there is no reasoning just canned response, that is big red flag. That person probably lacks any depth of knowledge and doesn't understand why the question is asked.
- mianos 8y ago
  Same, in an interview a few months I got a graph one which I did OK in. Then I got asked to write an algorithm to determine if it is acyclic on not. I could remember the visitation flag but I could not remember, of the top of my head, which side of the recursive call it was on. I picked the later side and obviously failed as I didn't get any offer, although that was more likely due to my age. I dodged a bullet in the end.
  - ummonk 8y ago
    Why would you have to remember that to solve it? This is the kind of thing I definitely wouldn't already know, but should be able to reason through.
- jumper_F00BA2 8y ago
  When faced with questions that have answers I could obviously discern by writing and running two lines of code, I willfully shrug, answer by intuition, hoping that's the trap for the wrong answer, and wait for a facial expression. Today I was asked a question about inheritance and references within a constructor, in which the answer was an either/or for the parent or child class. I threw up my hands and deliberately said "I dunno parent, no wait! Child!" because honestly who cares, when you can figure something like that out without even googling for it. A question like that is like asking someone what might they expect a Hello World! program to print. Waste my time, and I waste yours right back. I could care less what you think about me.
  - mosselman 8y ago
    When do you ever have to rely on 100% top of mind knowledge like that when programming anyway? I usually have a console open and google even fairly trivial things because of how much quicker (second or ~10) it is to look at the API than it is to get it wrong when reloading my code and having to try again. Usually I challenge getting silly 'traverse this data structure' questions and want to hear what they expect to get out of it. Side note: The correct expression is "I _couldn't_ care less"
    - iopuy 8y ago
      I thought the same thing until I started doing a significant amount of code reviews. You need to know these things to explain to more junior devs to help them become better programmers.
      - mosselman 8y ago
        Late to reply here, but you don't need to have the exact syntax and code at the top of your mind to review something. You just need the experience to recognise if something can be done in a different way or not. You can always google the exact improvement, implementation, etc later.
      - ItsMe000001 8y ago
- meritt 8y ago
  Because a large proportion of "software engineers" are simply people who know how to use popular libraries/frameworks to crank out a simple website or app (which often satisfies the needs of most companies anyway). Some companies prefer to hire people who can write software.
- timClicks 8y ago
  Surely most interviewers are interested in things that are slightly more abstract than answers to specific data structure question. 1) has requisite base level of knowledge, 2) shows humility/knows own limits, 3) has an ability to explain complex ideas simply, 4) demonstrates an innate curiosity and 5) can work through problems methodically
- maxcut 8y ago
  I have given a lot of thought to the interview process over the years. As a candidate I really disliked whiteboard questions and trying to come up with clever solutions on the spot with hard time and resource constraints. I was always frustrated with how different the interview experience was from actual day to day work. As an interviewer I much prefer a hands on experience with internet access. For that I have prepared a short app riddled with some bugs and half baked features to be completed. For me it is really important to see how a candidate copes with an existing codebase as most people work in environments with large and mature ones. It is also important as the interview progresses to see when and how the candidate resorts to online resources and how they conduct their search. Some just continue to bang their head when they encounter a problem or DFS into the first search result they encounter while others cleverly start opening a few tabs and evaluate proposed solutions before selecting the one that is most suitable for the current problem they are trying to solve. Most candidates after completing the interview stated that they preferred this method to 'traditional' ones and some even said that they enjoyed it.
- gaius 8y ago
  Puzzled as to why it's so important to some companies to grill on this stuff Because contrary to the narrative, there is no shortage of developers, there is in fact a glut so companies can not only afford to be choosy, they actually need to filter early to keep volume of applicants manageable. At least that is my interpretation of the evidence, I am curious if there is another explanation. I can remember when there really was a shortage of developers, the dotcom boom. Companies couldn’t shove people in the door fast enough, an interview was a quick chat followed by “when can you start?”. Today it’s nothing like that. In a genuine shortage there is no ageism etc either, noone can afford it.
  - godelmachine 8y ago
    If you have read Cracking the Coding Interview, the author describes a guy who was hired in her company because there was super shortage of developers. The guy barely knew HTML. He used to come late to office, play ping pong and take off before sundown. I believe things were quite similar in India during the dotcom bubble. Candidates were asked to do some addition programs, hir d immidietely, and within weeks their H1B was sponsored.
  - throwawaymath 8y ago
    "Shortage" is always a funny term in these discussions, and it always starts a debate. It's too simplistic and disagreeable a term. I agree with your point but I think it should be clarified. There is probably not a theoretical shortage of people who can be called "software developers" compared to the number of jobs available. But I find that shortages are relative. Companies make their own bars for who they're willing to hire, and how far above or below a given baseline level of competency they'd like to target. Not all software developers with that title can be software developers at any given company. This is not just because they don't know the underlying theory or because they don't know "real" engineering. So it's much harder to discern if there's actually a shortage, because obviously not all jobs with the same title involve the same specialization or skill requirements. I think that a more charitable interpretation is Google and other such companies use these interviewing practices because their ideation of a "software developer" is substantially different from the all-inclusive title. It's not just an arbitrary way to reduce the stack of resumes, it's an imperfect proxy for their actual criteria.
- xtiansimon 8y ago
  Once in an interview a senior designer walked in on my interview. They were introduced. Hung out for a minute. Wrote something on the whiteboard, then left. My interview ended, I was left in the room for a minute and I stared at that frackn whiteboard wondering what that was about. I didn't get the job, but I had to assume this was something that senior designer was into--something they cared about, something they used, a skill they wanted to manage, a subject they wanted to discuss. User ItsMe000001 says he was asked about a 'right join', choked during the interview, was still hired, and later became the go to guy for writing queries. If a question is in the interview, it's relevant to someone in some way unless it's a psychological mind-frack test. So the question would be, Who was also hired, and later had their head flipped?
gameguy43 8y ago
Founder of Interview Cake here. Thanks for the post! Down to chat about coding interviews and answer questions here!
- hmottestad 8y ago
  Hi. I got an interview question a little while ago that the interviewer said “was not a datasteuctures/algorithm question” because it was too specific. I call bullshit, but I don’t actually know what the algorithm would be called. Problem: A tree of resources that you can get granted access rights to. When you get access to a node in the tree, you inherit rights to children transitivley. You can also have rights explicitly blocked. The ordering is important. An example, you start of as head of IT and have all the IT stuff granted, but explicitly no access to the IT security department. Then you make CEO and are granted right to everything, so that should overrule your previous restriction for the IT security department.
  - justinclift 8y ago
    Hmmm, since they specifically said it's not a data structures/algorithm thing, maybe they're looking for other aspects? One potential that springs to mind is (say) governance or oversight considerations of the given situation? Not sure how that'd apply directly either though. Feels like there's more info needed from the interviewer first, to give a hint as to the direction. :)
  - philipov 8y ago
    The problem you described doesn't ask a question. What are they asking you to do: implement the described data structure (not enough information), or untangle their department hierarchy? I think the correct answer is "IT Security should be a peer of IT, not a subdepartment."
  - gameguy43 8y ago
    Hmmm. Can't get in your interviewer's head, but here's my guess: this might be one of those questions where the bulk of the discussion is supposed to be about weighing tradeoffs of different choices for the data model. For example: how do you store the explicit blocks? More specifically, how do you articulate that head of IT is blocked from this subtree, but the CEO isn't? Some options: - store the block as pairwise (individual, subtree) - same idea, but instead of blocks you store explicit /allowances/ (and allow a tree node to have a flag set of "ignore the tree-based permission system here, and just lock everyone out who doesn't have an explicit permission") - instead of blocking individuals, you could add an abstraction layer, e.g. user_groups, and assign permissions to /groups/.. You could also add an abstraction layer on top of the treenodes themselves (object_permission_groups?). Different tradeoffs with these options. Again, hard to know exactly where your interviewer was trying to steer the conversation. But that'd be my guess!
emersion 8y ago
Damn. Too many javascripts on this page, including Facebook's. I guess I'll pass.
philphil 8y ago
Good one but this is even more comprehensive: https://news.ycombinator.com/item?id=17427190 https://news.ycombinator.com/item?id=17427190
deleted 8y ago
[deleted]
deckarep 8y ago
“Hashtable: like an array but instead of an index you can set arbitrary keys for each value.” This sounds like a gross over simplification of what a Hashtable really is underneath the covers. Any candidate that shows up with that definition better be ready to dive in on what it really is and when you’d want to use it.
- cup-of-tea 8y ago
  That doesn't even describe a hash table, it describes an associative array, or map. A hash table as one way to implement that, the other main one being self-balancing binary trees.
  - ummonk 8y ago
    Or more broadly, self-balancing trees (the best performing balanced tree, the B-tree, is not generally a binary tree). And then there is the skip list.
    - cup-of-tea 8y ago
      Yes, quite right. Is a B-tree worth it when the structure is fully in memory, though? I would say that when talking about maps people are thinking of in memory structures.
      - ummonk 8y ago
        It absolutely is! You get significantly better cache utilization with a B-tree.
A_Person 8y ago
It just amazes me that employers ask complicated CS-type questions for ordinary programming jobs. I've been out of the game for 20 years, and only did a few interviews anyway (as the interviewer), so what would I know! But FWIW, here's the kind of question I'd ask. "I'm going to write a few lines of code on the whiteboard, tell me what you think of them." The code would be something like this: If f(a,b) then X=6 Elseif flag1 then X=8 Endif My bet is, people would fall into one of three camps. (1) The Bemused :-) These people would have no idea what to say. That would be fine for a new developer, I'd just prod them in the right direction. For example, "what do you think about inline constants?" But if an experienced developer had nothing to say about that code, that would be a big red flag for me. (2) The Defiant! These folk would say, "Gee that looks like very old code, I'm really more interested in functional languages, do you guys do any Haskell?" This would also be a big red flag. First, he's saying that he has no interest in my priorities as the interviewer, he'll just ignore my questions and substitute his own. Second, he shows that he's not really interested in code as such. It's like a guy who says he likes cars, you take him around the corner and show him your one-off Porsche EVO hybrid, and he says "Wow, an infinity pool! What did that cost?" Fail. (3) What I'd Expect Here's what I'd expect from an experienced developer, off the top of his/her head: "Ok, I see in-line constants, and short variable and function names. Those are often undesirable, I can talk about that more if you like. But the more interesting thing, is that X is only set if one of the two conditions is true. If neither condition is true, X does not get set to anything. That might be a bug: the programmer meant to initialise X before the first test, but forgot. Or perhaps X is initialised much higher up. But if that was the case, I'd like to refactor the code to bring that initialisation closer to the code on the whiteboard; and/or rename X to something less likely to be used by mistake in the middle; or at least, add a comment saying "X initialised above". Or you could just add an else branch to the code on the whiteboard, to ensure that X gets set even when both conditions are false. Another slight possibility is that when the first condition is false, the second condition is necessarily true, and the developer has written in the second condition as a form of comment. But in that case, I'd rather make it more explicit, by changing "Elseif flag1 then", to "Else /* flag1 must be true */"; or even asserting that, just to be sure. Also, if the code in question is really complex, or just messy from years of maintenance, there might still be cases where X does not get set at all. In that case you could initialise it to an impossible value, say NULL, right at the start, then assert not null at the end. Or you could even re-write the code in truth table style, which I can talk about more if you'd like." Me: "The truth table approach sounds good. How would you do that? What kind of data structures would you use?" And so on. Does everyone really use CS-type questions these days? Does anyone take the different approach displayed above?
newscracker 8y ago
Off topic. I really got turned off by the "me@gmail.com" placeholder in the signup form at the bottom of the page. So I decided not to sign up. Email != Gmail. It's one of the last decentralized systems holding up. Please don't stick one more dagger into it.
BerislavLopac 8y ago
Well, both types of trees mentioned in the article are just subtypes of graph, which has numerous other subtypes. I love this sentence from the technical docs of the NetworkX library, for pure surrealism: A lobster is a tree that reduces to a caterpillar when pruning all leaves.
- oreganoz 8y ago
  By that logic, lists are just trees with one child per node. Except graphs are just 2d lists if you define them via an adjacency matrix. So we've come full circle. But we both know they are not very much alike in practice.

287 points by typpo 8y ago

rs86 8y ago

This could benefit greatly from specifying what operations are available for each structure.

I recently got double slammed with 2 graph questions during an interview after having navigated for years without getting a graph question. It's wholly irrelevant to my day-to-day work but I do hobby game development sometimes which involves more needs for graphing. Still, I can't do much of anything with a graph on a whiteboard. Puzzled as to why it's so important to some companies to grill on this stuff, expecting it to be top-of-mind, even for front end roles.

nlawalker 8y ago
>> Puzzled as to why it's so important to some companies to grill on this stuff, expecting it to be top-of-mind, even for front end roles. Either they do consider it important to the role, or they are trying to select for young CS grads, or they just haven't tried to do any better in their hiring process, or they don't know how.
- cipherzero 8y ago
  Maybe I’m not like the interviewers/companies to which you’re referring, but I ask a DAG topo sort question (dependency resolution/task ordering) not because I expect the candidate to regurgitate the algorithm but because I legitimately want to see how they work through a problem - especially one they may(hopefully) not be familiar with. Most of the time I don’t care if they get the optimal algorithm, rather the can think through something and know where problems might be. Might not be how/why the “others” use that question, but its worked well for me.
User23 8y ago
Graphs are arguably the fundamental data structure. If you can’t think about objects and references between them then how do you write nontrivial software?
- umanwizard 8y ago
  Yes but in normal programming it is uncommon to need to write algorithms that traverse the global object graph. You normally care about some local view of it.
  - gaastonsr 8y ago
    It’s uncommon but it’s used once in a while. I do it 2-3 times a year at least. And believe me, most people wouldn’t even know how to start to do it or would think it’s too hard and prefer to do it in a different way so they don’t need to ever traverse the graph.
    - kylnew 8y ago
      Would you happen to have an example or reference to that kind of problem?
jopsen 8y ago
It's no secret that interviews at crazy, it's like an exam, and you should prepare accordingly. Yes, it's largely irrelevant. But an engineer who can't reason about DAG, topological sorting, etc, could easily ruin an otherwise elegant architecture :)
- platform 8y ago
  Perhaps I do not quite understand what you meant by 'engineer that cannot reason'. Somebody might not be able to write on a white board, during an interview a topological sort or find-a-union (https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/ https://www.hackerearth.com/practice/notes/disjoint-set-unio... ). But does it mean that they will ruin 'elegant architecture'? (compared to somebody who passed the topologica sort exam)? Also, wouldn't an architecture that imposes compile time constraints, good documentation and test cases -- on the usage of its most elegant pieces, be more 'elegant' than the one, that could be easily 'ruined' but somebody who does cannot write out a 'topological sort' during an interview?
  - perfmode 8y ago
    Have you never worked with weak engineers?
    - rmwaite 8y ago
      I think their point is that just because someone can’t whiteboard something doesn’t mean they can’t reason about it.
    - anothergoogler 8y ago
      The problem with using trivia as a hiring filter is it doesn't do a good job of differentiating between those who don't know a thing, and those who know nothing, unfairly penalizing the former.
      - ozim 8y ago
        But it is easy to filter out those who think they know something when they blurt out correct responses like machine. But in reality they just lerned canned responses. Usually you want to discuss problem to see reasoning. If there is no reasoning just canned response, that is big red flag. That person probably lacks any depth of knowledge and doesn't understand why the question is asked.
mianos 8y ago
Same, in an interview a few months I got a graph one which I did OK in. Then I got asked to write an algorithm to determine if it is acyclic on not. I could remember the visitation flag but I could not remember, of the top of my head, which side of the recursive call it was on. I picked the later side and obviously failed as I didn't get any offer, although that was more likely due to my age. I dodged a bullet in the end.
- ummonk 8y ago
  Why would you have to remember that to solve it? This is the kind of thing I definitely wouldn't already know, but should be able to reason through.
jumper_F00BA2 8y ago
When faced with questions that have answers I could obviously discern by writing and running two lines of code, I willfully shrug, answer by intuition, hoping that's the trap for the wrong answer, and wait for a facial expression. Today I was asked a question about inheritance and references within a constructor, in which the answer was an either/or for the parent or child class. I threw up my hands and deliberately said "I dunno parent, no wait! Child!" because honestly who cares, when you can figure something like that out without even googling for it. A question like that is like asking someone what might they expect a Hello World! program to print. Waste my time, and I waste yours right back. I could care less what you think about me.
- mosselman 8y ago
  When do you ever have to rely on 100% top of mind knowledge like that when programming anyway? I usually have a console open and google even fairly trivial things because of how much quicker (second or ~10) it is to look at the API than it is to get it wrong when reloading my code and having to try again. Usually I challenge getting silly 'traverse this data structure' questions and want to hear what they expect to get out of it. Side note: The correct expression is "I _couldn't_ care less"
  - iopuy 8y ago
    I thought the same thing until I started doing a significant amount of code reviews. You need to know these things to explain to more junior devs to help them become better programmers.
    - mosselman 8y ago
      Late to reply here, but you don't need to have the exact syntax and code at the top of your mind to review something. You just need the experience to recognise if something can be done in a different way or not. You can always google the exact improvement, implementation, etc later.
    - ItsMe000001 8y ago
meritt 8y ago
Because a large proportion of "software engineers" are simply people who know how to use popular libraries/frameworks to crank out a simple website or app (which often satisfies the needs of most companies anyway). Some companies prefer to hire people who can write software.
timClicks 8y ago
Surely most interviewers are interested in things that are slightly more abstract than answers to specific data structure question. 1) has requisite base level of knowledge, 2) shows humility/knows own limits, 3) has an ability to explain complex ideas simply, 4) demonstrates an innate curiosity and 5) can work through problems methodically
maxcut 8y ago
I have given a lot of thought to the interview process over the years. As a candidate I really disliked whiteboard questions and trying to come up with clever solutions on the spot with hard time and resource constraints. I was always frustrated with how different the interview experience was from actual day to day work. As an interviewer I much prefer a hands on experience with internet access. For that I have prepared a short app riddled with some bugs and half baked features to be completed. For me it is really important to see how a candidate copes with an existing codebase as most people work in environments with large and mature ones. It is also important as the interview progresses to see when and how the candidate resorts to online resources and how they conduct their search. Some just continue to bang their head when they encounter a problem or DFS into the first search result they encounter while others cleverly start opening a few tabs and evaluate proposed solutions before selecting the one that is most suitable for the current problem they are trying to solve. Most candidates after completing the interview stated that they preferred this method to 'traditional' ones and some even said that they enjoyed it.
gaius 8y ago
Puzzled as to why it's so important to some companies to grill on this stuff Because contrary to the narrative, there is no shortage of developers, there is in fact a glut so companies can not only afford to be choosy, they actually need to filter early to keep volume of applicants manageable. At least that is my interpretation of the evidence, I am curious if there is another explanation. I can remember when there really was a shortage of developers, the dotcom boom. Companies couldn’t shove people in the door fast enough, an interview was a quick chat followed by “when can you start?”. Today it’s nothing like that. In a genuine shortage there is no ageism etc either, noone can afford it.
- godelmachine 8y ago
  If you have read Cracking the Coding Interview, the author describes a guy who was hired in her company because there was super shortage of developers. The guy barely knew HTML. He used to come late to office, play ping pong and take off before sundown. I believe things were quite similar in India during the dotcom bubble. Candidates were asked to do some addition programs, hir d immidietely, and within weeks their H1B was sponsored.
- throwawaymath 8y ago
  "Shortage" is always a funny term in these discussions, and it always starts a debate. It's too simplistic and disagreeable a term. I agree with your point but I think it should be clarified. There is probably not a theoretical shortage of people who can be called "software developers" compared to the number of jobs available. But I find that shortages are relative. Companies make their own bars for who they're willing to hire, and how far above or below a given baseline level of competency they'd like to target. Not all software developers with that title can be software developers at any given company. This is not just because they don't know the underlying theory or because they don't know "real" engineering. So it's much harder to discern if there's actually a shortage, because obviously not all jobs with the same title involve the same specialization or skill requirements. I think that a more charitable interpretation is Google and other such companies use these interviewing practices because their ideation of a "software developer" is substantially different from the all-inclusive title. It's not just an arbitrary way to reduce the stack of resumes, it's an imperfect proxy for their actual criteria.
xtiansimon 8y ago
Once in an interview a senior designer walked in on my interview. They were introduced. Hung out for a minute. Wrote something on the whiteboard, then left. My interview ended, I was left in the room for a minute and I stared at that frackn whiteboard wondering what that was about. I didn't get the job, but I had to assume this was something that senior designer was into--something they cared about, something they used, a skill they wanted to manage, a subject they wanted to discuss. User ItsMe000001 says he was asked about a 'right join', choked during the interview, was still hired, and later became the go to guy for writing queries. If a question is in the interview, it's relevant to someone in some way unless it's a psychological mind-frack test. So the question would be, Who was also hired, and later had their head flipped?

gameguy43 8y ago

Founder of Interview Cake here. Thanks for the post! Down to chat about coding interviews and answer questions here!

hmottestad 8y ago
Hi. I got an interview question a little while ago that the interviewer said “was not a datasteuctures/algorithm question” because it was too specific. I call bullshit, but I don’t actually know what the algorithm would be called. Problem: A tree of resources that you can get granted access rights to. When you get access to a node in the tree, you inherit rights to children transitivley. You can also have rights explicitly blocked. The ordering is important. An example, you start of as head of IT and have all the IT stuff granted, but explicitly no access to the IT security department. Then you make CEO and are granted right to everything, so that should overrule your previous restriction for the IT security department.
- justinclift 8y ago
  Hmmm, since they specifically said it's not a data structures/algorithm thing, maybe they're looking for other aspects? One potential that springs to mind is (say) governance or oversight considerations of the given situation? Not sure how that'd apply directly either though. Feels like there's more info needed from the interviewer first, to give a hint as to the direction. :)
- philipov 8y ago
  The problem you described doesn't ask a question. What are they asking you to do: implement the described data structure (not enough information), or untangle their department hierarchy? I think the correct answer is "IT Security should be a peer of IT, not a subdepartment."
- gameguy43 8y ago
  Hmmm. Can't get in your interviewer's head, but here's my guess: this might be one of those questions where the bulk of the discussion is supposed to be about weighing tradeoffs of different choices for the data model. For example: how do you store the explicit blocks? More specifically, how do you articulate that head of IT is blocked from this subtree, but the CEO isn't? Some options: - store the block as pairwise (individual, subtree) - same idea, but instead of blocks you store explicit /allowances/ (and allow a tree node to have a flag set of "ignore the tree-based permission system here, and just lock everyone out who doesn't have an explicit permission") - instead of blocking individuals, you could add an abstraction layer, e.g. user_groups, and assign permissions to /groups/.. You could also add an abstraction layer on top of the treenodes themselves (object_permission_groups?). Different tradeoffs with these options. Again, hard to know exactly where your interviewer was trying to steer the conversation. But that'd be my guess!

emersion 8y ago

Damn. Too many javascripts on this page, including Facebook's. I guess I'll pass.

philphil 8y ago

Good one but this is even more comprehensive: https://news.ycombinator.com/item?id=17427190 https://news.ycombinator.com/item?id=17427190

deleted 8y ago

[deleted]

deckarep 8y ago

“Hashtable: like an array but instead of an index you can set arbitrary keys for each value.” This sounds like a gross over simplification of what a Hashtable really is underneath the covers. Any candidate that shows up with that definition better be ready to dive in on what it really is and when you’d want to use it.

cup-of-tea 8y ago
That doesn't even describe a hash table, it describes an associative array, or map. A hash table as one way to implement that, the other main one being self-balancing binary trees.
- ummonk 8y ago
  Or more broadly, self-balancing trees (the best performing balanced tree, the B-tree, is not generally a binary tree). And then there is the skip list.
  - cup-of-tea 8y ago
    Yes, quite right. Is a B-tree worth it when the structure is fully in memory, though? I would say that when talking about maps people are thinking of in memory structures.
    - ummonk 8y ago
      It absolutely is! You get significantly better cache utilization with a B-tree.

A_Person 8y ago

It just amazes me that employers ask complicated CS-type questions for ordinary programming jobs. I've been out of the game for 20 years, and only did a few interviews anyway (as the interviewer), so what would I know! But FWIW, here's the kind of question I'd ask. "I'm going to write a few lines of code on the whiteboard, tell me what you think of them." The code would be something like this: If f(a,b) then X=6 Elseif flag1 then X=8 Endif My bet is, people would fall into one of three camps. (1) The Bemused :-) These people would have no idea what to say. That would be fine for a new developer, I'd just prod them in the right direction. For example, "what do you think about inline constants?" But if an experienced developer had nothing to say about that code, that would be a big red flag for me. (2) The Defiant! These folk would say, "Gee that looks like very old code, I'm really more interested in functional languages, do you guys do any Haskell?" This would also be a big red flag. First, he's saying that he has no interest in my priorities as the interviewer, he'll just ignore my questions and substitute his own. Second, he shows that he's not really interested in code as such. It's like a guy who says he likes cars, you take him around the corner and show him your one-off Porsche EVO hybrid, and he says "Wow, an infinity pool! What did that cost?" Fail. (3) What I'd Expect Here's what I'd expect from an experienced developer, off the top of his/her head: "Ok, I see in-line constants, and short variable and function names. Those are often undesirable, I can talk about that more if you like. But the more interesting thing, is that X is only set if one of the two conditions is true. If neither condition is true, X does not get set to anything. That might be a bug: the programmer meant to initialise X before the first test, but forgot. Or perhaps X is initialised much higher up. But if that was the case, I'd like to refactor the code to bring that initialisation closer to the code on the whiteboard; and/or rename X to something less likely to be used by mistake in the middle; or at least, add a comment saying "X initialised above". Or you could just add an else branch to the code on the whiteboard, to ensure that X gets set even when both conditions are false. Another slight possibility is that when the first condition is false, the second condition is necessarily true, and the developer has written in the second condition as a form of comment. But in that case, I'd rather make it more explicit, by changing "Elseif flag1 then", to "Else /* flag1 must be true */"; or even asserting that, just to be sure. Also, if the code in question is really complex, or just messy from years of maintenance, there might still be cases where X does not get set at all. In that case you could initialise it to an impossible value, say NULL, right at the start, then assert not null at the end. Or you could even re-write the code in truth table style, which I can talk about more if you'd like." Me: "The truth table approach sounds good. How would you do that? What kind of data structures would you use?" And so on. Does everyone really use CS-type questions these days? Does anyone take the different approach displayed above?

newscracker 8y ago

Off topic. I really got turned off by the "me@gmail.com" placeholder in the signup form at the bottom of the page. So I decided not to sign up. Email != Gmail. It's one of the last decentralized systems holding up. Please don't stick one more dagger into it.

BerislavLopac 8y ago

Well, both types of trees mentioned in the article are just subtypes of graph, which has numerous other subtypes. I love this sentence from the technical docs of the NetworkX library, for pure surrealism: A lobster is a tree that reduces to a caterpillar when pruning all leaves.

oreganoz 8y ago
By that logic, lists are just trees with one child per node. Except graphs are just 2d lists if you define them via an adjacency matrix. So we've come full circle. But we both know they are not very much alike in practice.