9 ms·

And this is why you need to know all the algo and data structure "basics" when interviewing at the big G. Because people there are working on these sorts of opt

And this is why you need to know all the algo and data structure "basics" when interviewing at the big G. Because people there are working on these sorts of optimizations in their spare time.

eridius 14y ago
What does knowing this stuff at interview-time have to do with being able to implement it later? I certainly don't remember how b-trees work off the top of my head, but what I do know is how to find out the answer given a computer and an internet connection.
- lifty 14y ago
  Having the details and characteristics of the b-trees(among other things) in memory allows you to consider them as possible solutions to a problem you are facing. If you dont know the details you would probably not know they are a good fit for a particular problem. The more detailed knowledge you have in your memory the bigger your possible solution set will be, thus, you will have a better chance at solving a particular problem. I think Google is not looking for people that can follow specs(although thats valuable also) but people that can come up with brilliant solutions to hard problems.
  - meric 14y ago
    I would think a person who can specialise, learn and memorise the details and characteristics of a particular domain quickly, say b-trees, when he is working on relevant problem, would be more important than knowing about all things computer science related at the same, and lesser, detail. Wouldn't it be more important to have people to come up with brilliant solutions on problems they are working on, rather than hard problems in general that have already been solved?
    - venomsnake 14y ago
      As always in our field it is somewhere in the middle - having knowledge of the platform and the field is something that can give you some hints in advance about potential problems with the approach for a difficult problem. After all a timely - "This is not going to work well because there will be lots of branch mispredictions and you will be going out of the L3 cache a lot, and RAM is terribly slow" can save a lot of time and effort for some classes of tasks that big scalabiliy companies have to deal often.
    - pretoriusB 14y ago
      >Wouldn't it be more important to have people to come up with brilliant solutions on problems they are working on, rather than hard problems in general that have already been solved? Most of the times the guys that can come with "brilliant solutions" on new problems are those that know the solved problems inside and out. The other guys just keep reinventing the wheel (only worse).
    - Scene_Cast2 14y ago
      Typically, one doesn't know that a problem is in a specific implementation domain (b-trees) unless one knows that domain. For example, I have M time slots and N people that need to be scheduled. Each of the N people has a time schedule for the M slots (either free or busy). If a person doesn't know about bipartite graph matching (or even graphs at all), then they're less likely to come up with a polynomial-runtime solution. Now, if a person knows about bipartite matching, they might as well learn the algorithms (max flow, etc) to solve it (even for fun, at least I know I would).
- pretoriusB 14y ago
  >but what I do know is how to find out the answer given a computer and an internet connection. Then you are not good enough for them. They want someone that breaths and knows these things inside out and backwards. Any half-competent dabbler can look them up and implement them. Creating novel solutions takes more deep understanding of them than that.
  - eli_gottlieb 14y ago
    The difference being that novel solutions require actual domain knowledge rather than an n-levels-deep memorization of the entirety of your Algorithms 1 and 2 courses from university.
    - pretoriusB 14y ago
      The domain knowledge when it comes to implementing algorithms is algorithms themselves...
      - eli_gottlieb 14y ago
        Yes, but the algorithms relevant to a domain are not Algorithms 1&2 class algorithms. For example, writing a network protocol requires knowledge of finite-state machines, writing a type-inference engine requires knowledge of unification, writing a thread scheduler requires knowledge of various scheduling algorithms. Knowing the most efficient way to find all the anagrams in a text is not relevant to any of them, though. And yes, I was given that problem in an interview last week. I got it right, but the actual position involved more knowledge of architecture, assembly, and compilation than of Algorithms Guru Yoga.
        DannyBee 14y ago
        Well, I hope you weren't asked that at Google , since it's a banned question. If you were, let me know privately :) I assume you understand the goal of these questions is not to figure out if you can perform memorization of algorithms 1 + 2, but to understand how you think about problems and watch you do it? Note that, at least at Google, they still try to hire generalists (in most cases), so you would still get that "kind" of question there, even for a job involving architecture and assembly. This is a deliberate choice. Of course, i'm sure you also realize that a lot of the algorithms in "architecture, assembly, and compilation" were developed by people who started out more as "Algorithms Guru Yoga" folks. Gregory Chaitan, who developed Graph Coloring for register allocation, was definitely not a compiler guy Only half the folks on the original conference paper for Static Single Assignment form for compilers were compiler people actually trying to solve that problem. Robert Tarjan was not a compiler guy, but his scheme for computing dominators is still the main one used today, and his union-find algorithms (he also proved the upper bound on the already-known versions) are what are used for a lot of type unification algorithms. The list goes on of "Algorithms Guru Yoga" folks who came up with the premiere solutions to problems in the field you are talking about. So when you say "novel solutions require actual domain knowledge rather than an n-levels-deep memorization of the entirety of your Algorithms 1 and 2 courses from university.", it's a bit hard to take that seriously. Novel solutions require both domain level knowledge, and the understanding you learned in Algorithms 1 and 2. Even the question you got about anagrams does not require any n-level wrote memorization. It requires only the most basic understanding of data structures, and an understanding of how to design algorithms.
- deleted 14y ago
  [deleted]
- KMag 14y ago
  I averaged somewhere between one and two interviews per week during my 4 years with Google. Google has (or at least had) more applicants than they can shake a stick at. They have the choice between smart people who can look up things on the Internet but aren't interested enough to memorize the basics, and smart people who are interested enough in the subject matter to have the basics memorized (or at least are smart enough to put on a good show of loving the subject matter). Maybe having the basics memorized isn't necessary for the job, but it's a good signal that you're not a zombie banging out code without really being interested or thinking critically about what you're doing. It's not a perfect signal, but it's still a useful signal. Everyone knows you need to know your basic data structures for a Google interview. If you don't know your data structures, cram for a week or two before your interview. The basic data structures are just the basic starting point for the data structures interview questions. The interviewer needs to know you know the basic data structures before they start throwing curveballs at you to see how you think about and solve hard data structures problems. The people who think they're too smart or too cool for the basic data structures questions are just going to drown, so if they bomb the basic data structures questions, the interviewer justs moves on and pretends that was where the question ended. There's no sense in frustrating the interviewee and making the whole company look mean and forcing the interviewee to answer questions they lack the background knowledge to begin solving. On top of that, if you can't even be bothered to cram some basic data structures for an interview, you're not going to fit in well at Google. I also asked some constrained bin packing questions, related to scheduling distributed computations in a cluster and placing files in a distributed filesystem, but I'd simplify the problem a bit and make up some slightly silly story about kids selling candy or something. The simplification and the non-computer back story helps reduce the amount of assumed specialized knowledge, and keeps people from over-thinking the thing, thinking it's a trick question, or otherwise running off into the weeds. Silly stories really do help people accept the simplified problem and not get lost thinking they're supposed to be thinking outside the box. If you ask a question about networking, people will suggest reducing the number of intermediate switches or maybe even swapping the network media with something with a higher signal propagation velocity. Rephrase it as kids playing Pokemon with cards, and they're moere likely to notice that O(N^2) network traffic can be reduced to O(Log(N)). Some people just thought some problem involving candy or trading cards instead of computers was beneath them and silly, obviously missing that the underlying problem had real implications for computing at massive scales. If they got upset about the problem, I just let it go, since arguing with them or making them feel dumb by pointing out the isomorphism would just rile them up for their next interviewer. I usually genuinely hoped they'd do better with the next interviewer. Good engineers are hard to find, and if I'm the only person they rubbed the wrong way, they're unlikely to be working with me anyway. If you notice how the simplified silly problem is probably related to a real problem the interviewer has had to solve, it's probably best to make a nonchalant comment. "Oh, so it looks like a constrained bin packing problem, maybe with applications in distributed storage or distributed process scheduling, or something like that. Let's see, you said the Hershey Bars can't be kept near dogs, so let me think about the heuristic of allocating them first. They're each $X and Y Calories, so ..." If you think an interview question is silly, make sure you hide that opinion well from the interviewer. You're likely missing something, especially if your interviewer appears otherwise bright.
adamnemecek 14y ago
Or maybe it's self-selection bias.
- andreasvc 14y ago
  I don't understand what this is supposed to add to the observation that these subjects are important at Google interviews. It seems tautological to refer to interview requirements as "selection bias".
  - adamnemecek 14y ago
    What I meant is that maybe the people working at Google were interested in algorithms even before working at Google and therefore they went to work for Google and therefore they work on algo in their free time. I did not say selection bias, I said self-selection bias http://en.wikipedia.org/wiki/Self-selection_bias http://en.wikipedia.org/wiki/Self-selection_bias
Smerity 14y ago
Agreed. When I was working on Google App Engine, the Quota team sat next to me. The Quota team are the service that just about every other service at Google calls to ensure a user isn't abusing "The Google". That means that they need to have insanely small response times to ensure that all the services run on time. They hit an issue no-one really thinks about: resizing hash tables. No-one thinks about it, as it happens transparently under the surface, but for them, the few milliseconds it took to resize the hash tables would have enormously detrimental effects on just about every other Google service. The solutions they were talking about were really quite amazing. That's the insanity they face. So, if anyone hasn't seen Google Sparsehash[1], check it out: it's another near drop-in improvement to the STL. Two bits per entry of overhead and insanely fast. I can't remember if the Quota team used it specifically, but I wouldn't be surprised if it's one of the results of their work. [1]: http://code.google.com/p/sparsehash/ http://code.google.com/p/sparsehash/
- pilooch 14y ago
  Actually sparsehash is not optimized for speed, but reduces the usual hash map memory footprint. In practice it is on par or slower than STL unordered_map.
  - Smerity 14y ago
    I should have specified earlier: Google Sparsehash also contains Densehash which is optimised for speed, not space. It, however, is also more space efficient than most other hash implementations. Check out dense_hash_map[1] [1]: http://sparsehash.googlecode.com/svn/trunk/doc/implementation.html http://sparsehash.googlecode.com/svn/trunk/doc/implementatio...
- jzwinck 14y ago
  No one thinks about resizing hash tables...except for any high-frequency trading firm worth its salt. And probably several game companies. I'm sure there are others. It gets weirder when we talk about C++ in particular: did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n)? Erase by key actually has better performance despite the extra lookup. People do think about these things, in a few places, but it can be hard to get ideal performance standardized...even in C++.
deleted 14y ago
[deleted]

And this is why you need to know all the algo and data structure "basics" when interviewing at the big G. Because people there are working on these sorts of optimizations in their spare time.

eridius 14y ago

What does knowing this stuff at interview-time have to do with being able to implement it later? I certainly don't remember how b-trees work off the top of my head, but what I do know is how to find out the answer given a computer and an internet connection.

lifty 14y ago
Having the details and characteristics of the b-trees(among other things) in memory allows you to consider them as possible solutions to a problem you are facing. If you dont know the details you would probably not know they are a good fit for a particular problem. The more detailed knowledge you have in your memory the bigger your possible solution set will be, thus, you will have a better chance at solving a particular problem. I think Google is not looking for people that can follow specs(although thats valuable also) but people that can come up with brilliant solutions to hard problems.
- meric 14y ago
  I would think a person who can specialise, learn and memorise the details and characteristics of a particular domain quickly, say b-trees, when he is working on relevant problem, would be more important than knowing about all things computer science related at the same, and lesser, detail. Wouldn't it be more important to have people to come up with brilliant solutions on problems they are working on, rather than hard problems in general that have already been solved?
  - venomsnake 14y ago
    As always in our field it is somewhere in the middle - having knowledge of the platform and the field is something that can give you some hints in advance about potential problems with the approach for a difficult problem. After all a timely - "This is not going to work well because there will be lots of branch mispredictions and you will be going out of the L3 cache a lot, and RAM is terribly slow" can save a lot of time and effort for some classes of tasks that big scalabiliy companies have to deal often.
  - pretoriusB 14y ago
    >Wouldn't it be more important to have people to come up with brilliant solutions on problems they are working on, rather than hard problems in general that have already been solved? Most of the times the guys that can come with "brilliant solutions" on new problems are those that know the solved problems inside and out. The other guys just keep reinventing the wheel (only worse).
  - Scene_Cast2 14y ago
    Typically, one doesn't know that a problem is in a specific implementation domain (b-trees) unless one knows that domain. For example, I have M time slots and N people that need to be scheduled. Each of the N people has a time schedule for the M slots (either free or busy). If a person doesn't know about bipartite graph matching (or even graphs at all), then they're less likely to come up with a polynomial-runtime solution. Now, if a person knows about bipartite matching, they might as well learn the algorithms (max flow, etc) to solve it (even for fun, at least I know I would).
pretoriusB 14y ago
>but what I do know is how to find out the answer given a computer and an internet connection. Then you are not good enough for them. They want someone that breaths and knows these things inside out and backwards. Any half-competent dabbler can look them up and implement them. Creating novel solutions takes more deep understanding of them than that.
- eli_gottlieb 14y ago
  The difference being that novel solutions require actual domain knowledge rather than an n-levels-deep memorization of the entirety of your Algorithms 1 and 2 courses from university.
  - pretoriusB 14y ago
    The domain knowledge when it comes to implementing algorithms is algorithms themselves...
    - eli_gottlieb 14y ago
      Yes, but the algorithms relevant to a domain are not Algorithms 1&2 class algorithms. For example, writing a network protocol requires knowledge of finite-state machines, writing a type-inference engine requires knowledge of unification, writing a thread scheduler requires knowledge of various scheduling algorithms. Knowing the most efficient way to find all the anagrams in a text is not relevant to any of them, though. And yes, I was given that problem in an interview last week. I got it right, but the actual position involved more knowledge of architecture, assembly, and compilation than of Algorithms Guru Yoga.
      - DannyBee 14y ago
        Well, I hope you weren't asked that at Google , since it's a banned question. If you were, let me know privately :) I assume you understand the goal of these questions is not to figure out if you can perform memorization of algorithms 1 + 2, but to understand how you think about problems and watch you do it? Note that, at least at Google, they still try to hire generalists (in most cases), so you would still get that "kind" of question there, even for a job involving architecture and assembly. This is a deliberate choice. Of course, i'm sure you also realize that a lot of the algorithms in "architecture, assembly, and compilation" were developed by people who started out more as "Algorithms Guru Yoga" folks. Gregory Chaitan, who developed Graph Coloring for register allocation, was definitely not a compiler guy Only half the folks on the original conference paper for Static Single Assignment form for compilers were compiler people actually trying to solve that problem. Robert Tarjan was not a compiler guy, but his scheme for computing dominators is still the main one used today, and his union-find algorithms (he also proved the upper bound on the already-known versions) are what are used for a lot of type unification algorithms. The list goes on of "Algorithms Guru Yoga" folks who came up with the premiere solutions to problems in the field you are talking about. So when you say "novel solutions require actual domain knowledge rather than an n-levels-deep memorization of the entirety of your Algorithms 1 and 2 courses from university.", it's a bit hard to take that seriously. Novel solutions require both domain level knowledge, and the understanding you learned in Algorithms 1 and 2. Even the question you got about anagrams does not require any n-level wrote memorization. It requires only the most basic understanding of data structures, and an understanding of how to design algorithms.
deleted 14y ago
[deleted]
KMag 14y ago
I averaged somewhere between one and two interviews per week during my 4 years with Google. Google has (or at least had) more applicants than they can shake a stick at. They have the choice between smart people who can look up things on the Internet but aren't interested enough to memorize the basics, and smart people who are interested enough in the subject matter to have the basics memorized (or at least are smart enough to put on a good show of loving the subject matter). Maybe having the basics memorized isn't necessary for the job, but it's a good signal that you're not a zombie banging out code without really being interested or thinking critically about what you're doing. It's not a perfect signal, but it's still a useful signal. Everyone knows you need to know your basic data structures for a Google interview. If you don't know your data structures, cram for a week or two before your interview. The basic data structures are just the basic starting point for the data structures interview questions. The interviewer needs to know you know the basic data structures before they start throwing curveballs at you to see how you think about and solve hard data structures problems. The people who think they're too smart or too cool for the basic data structures questions are just going to drown, so if they bomb the basic data structures questions, the interviewer justs moves on and pretends that was where the question ended. There's no sense in frustrating the interviewee and making the whole company look mean and forcing the interviewee to answer questions they lack the background knowledge to begin solving. On top of that, if you can't even be bothered to cram some basic data structures for an interview, you're not going to fit in well at Google. I also asked some constrained bin packing questions, related to scheduling distributed computations in a cluster and placing files in a distributed filesystem, but I'd simplify the problem a bit and make up some slightly silly story about kids selling candy or something. The simplification and the non-computer back story helps reduce the amount of assumed specialized knowledge, and keeps people from over-thinking the thing, thinking it's a trick question, or otherwise running off into the weeds. Silly stories really do help people accept the simplified problem and not get lost thinking they're supposed to be thinking outside the box. If you ask a question about networking, people will suggest reducing the number of intermediate switches or maybe even swapping the network media with something with a higher signal propagation velocity. Rephrase it as kids playing Pokemon with cards, and they're moere likely to notice that O(N^2) network traffic can be reduced to O(Log(N)). Some people just thought some problem involving candy or trading cards instead of computers was beneath them and silly, obviously missing that the underlying problem had real implications for computing at massive scales. If they got upset about the problem, I just let it go, since arguing with them or making them feel dumb by pointing out the isomorphism would just rile them up for their next interviewer. I usually genuinely hoped they'd do better with the next interviewer. Good engineers are hard to find, and if I'm the only person they rubbed the wrong way, they're unlikely to be working with me anyway. If you notice how the simplified silly problem is probably related to a real problem the interviewer has had to solve, it's probably best to make a nonchalant comment. "Oh, so it looks like a constrained bin packing problem, maybe with applications in distributed storage or distributed process scheduling, or something like that. Let's see, you said the Hershey Bars can't be kept near dogs, so let me think about the heuristic of allocating them first. They're each $X and Y Calories, so ..." If you think an interview question is silly, make sure you hide that opinion well from the interviewer. You're likely missing something, especially if your interviewer appears otherwise bright.

adamnemecek 14y ago

Or maybe it's self-selection bias.

andreasvc 14y ago
I don't understand what this is supposed to add to the observation that these subjects are important at Google interviews. It seems tautological to refer to interview requirements as "selection bias".
- adamnemecek 14y ago
  What I meant is that maybe the people working at Google were interested in algorithms even before working at Google and therefore they went to work for Google and therefore they work on algo in their free time. I did not say selection bias, I said self-selection bias http://en.wikipedia.org/wiki/Self-selection_bias http://en.wikipedia.org/wiki/Self-selection_bias

Smerity 14y ago

Agreed. When I was working on Google App Engine, the Quota team sat next to me. The Quota team are the service that just about every other service at Google calls to ensure a user isn't abusing "The Google". That means that they need to have insanely small response times to ensure that all the services run on time. They hit an issue no-one really thinks about: resizing hash tables. No-one thinks about it, as it happens transparently under the surface, but for them, the few milliseconds it took to resize the hash tables would have enormously detrimental effects on just about every other Google service. The solutions they were talking about were really quite amazing. That's the insanity they face. So, if anyone hasn't seen Google Sparsehash[1], check it out: it's another near drop-in improvement to the STL. Two bits per entry of overhead and insanely fast. I can't remember if the Quota team used it specifically, but I wouldn't be surprised if it's one of the results of their work. [1]: http://code.google.com/p/sparsehash/ http://code.google.com/p/sparsehash/

pilooch 14y ago
Actually sparsehash is not optimized for speed, but reduces the usual hash map memory footprint. In practice it is on par or slower than STL unordered_map.
- Smerity 14y ago
  I should have specified earlier: Google Sparsehash also contains Densehash which is optimised for speed, not space. It, however, is also more space efficient than most other hash implementations. Check out dense_hash_map[1] [1]: http://sparsehash.googlecode.com/svn/trunk/doc/implementation.html http://sparsehash.googlecode.com/svn/trunk/doc/implementatio...
jzwinck 14y ago
No one thinks about resizing hash tables...except for any high-frequency trading firm worth its salt. And probably several game companies. I'm sure there are others. It gets weirder when we talk about C++ in particular: did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n)? Erase by key actually has better performance despite the extra lookup. People do think about these things, in a few places, but it can be hard to get ideal performance standardized...even in C++.

deleted 14y ago

[deleted]