10 ms·

Why? Do Google or Facebook engineers live in a magical world in which they need to know off the top of their heads the big-O complexity of every possible sort f

by mpeg 13y ago

Why? Do Google or Facebook engineers live in a magical world in which they need to know off the top of their heads the big-O complexity of every possible sort function ever mentioned in an academic paper? I see this argument used time and time again, but it makes no sense to me. Surely they can just search for it when they need it too :)

sergiotapia 13y ago
They deal is data volumes so large and so interconnected, it can't hurt to know those sort of things. Surely you agree?
- doctorcroc 13y ago
  Agree, but what you described is something that can be googled and quickly learned, whereas all the intangibles op listed should be second-nature.
  - MichaelGG 13y ago
    I highly doubt that someone that does not know what binary search is, that cannot think for a minute and come up with a small implementation, is going to "google and quickly learn" algorithms and the related thinking. The issue isn't if you can write on simple binary search (considering such a search is a intro-to-programming task[1], that should be a given), but if you have an understanding of the topic in general. When your project calls for a certain performance bound, will you flail around or have some idea what you're looking for? 1: "Guess my number between 1 and 100!"
    - randomdata 13y ago
      I don't think it is difficult as you make it sound. The most difficult part is finding the term "binary search", but even that is not very difficult. All you have to do is generalize your problem and state it to Google. Binary search will almost invariably come up in the results. It even works for algorithms that are far more obscure.
      - MichaelGG 13y ago
        My point isn't that if you don't know what binary search is then you're going to have a hard time doing a lot of algorithm searches. Just like if you didn't know what a linked list was, or a hashtable. Writing a hashtable or reasoning out the properties of a linked list, is not the kind of thing you should need to look up. It should be easy to talk it out during an interview. These are basics. Same for strings, too. A programmer should be able to decisively explain how strings work in their language. Where do you draw the line? Arrays are just another data structure, is it OK if they don't know the properties of arrays since they can look it up?
        randomdata 13y ago
        > My point isn't that if you don't know what binary search is then you're going to have a hard time doing a lot of algorithm searches. My point is that you can write a lot of software before you need to know what binary search is, and at the point that you do need it, you will be able to find out about it with ease. Like you said, it is a basic topic, so you don't even need much lead time to bring yourself up to speed. I think where you are going with this is that if you don't know what binary search is, you won't recognize when you need it, which sounds quite logical, but experience has suggested it doesn't actually play out like that in the real world. > is it OK if they don't know the properties of arrays since they can look it up? I think so. For the vast majority of software being written, the only thing you do need to understand is the language's interface to arrays, which are usually presented as abstract collections. The idea of a collection is something that transcends beyond programming and computers and is understood by basically everyone. When the time comes that you do need a lower-level understanding, you can look it up quickly and efficiently. A effective practice for writing efficient software is lazy loading, and I believe it works well for humans too. I might be willing to accept that it is a skill that not all people have taken the time to acquire, however.
        softr 13y ago
        I have seen developers struggle to identify the problem. You can't solve a problem if you don't know what a particular algorithm do for you. I have seen java developers knowing only ArrayList and nothing else in the collection. In numerous forums, people ask for code because they don't know what the problem is. In which case, even search can't help.
- rhizome 13y ago
  Except the thing is that these companies already have established internal libraries and tooling that implement "these sort of things," to a large degree and insulate the business needs from new hires such that any given hire's O(n) skills are not going to touch them until they get put on the task.
- typon 13y ago
  Unless you're being hired a PhD Senior Software Designer, there is exactly 0% chance (in 2014 anyway) that you're going to be working on improving Google's PageRank algorithm.
  - iskander 13y ago
    I was a lowly software engineering intern at Google and spent most of my summer writing MapReduce jobs which would traverse (1) every document in a large index of the web or (2) every book Google has scanned. Even worse, I sometimes needed to compute correlations between pieces of text in the documents. So, not only was the input size huge, the work per document was non-trivial. The remarkable thing about this sort of gig is how utterly unremarkable it is in a large tech company. If there's anything to Big Data beyond hype it's the commoditization of previously incomprehensibly large computations...and everyone doing computation on that scale should at least know the basic language of reasoning about time/space/communication complexity. You don't necessarily need to know the official jargon (though it helps to concisely describe ideas), but you should at least be able to think about how much extra work your program does for each additional input item (and how much extra storage it needs, and how network bandwidth it will eat up).
mgkimsal 13y ago
I suspect when they search for it they're going to find their own published writings/blogs ;) I do think some people at FB/Google need to know this stuff cold, but even that isn't going to be 100% of their engineers.
- potatolicious 13y ago
  Agreed. I think there's a tinge of arrogance to the claim that Google/FB/what have you need The Best(tm) while everyone else does not. The reality is that there are some jobs (a small minority) at these companies that require incredibly deep algorithmic knowledge - they really do do some complicated things. But the majority of jobs at TwitGooFace are your run of the mill programming jobs, where the requirement and the reality don't call for anyone at that level, and hiring someone at that level is just going to make them bored. Indeed, the vast majority of people I know at these companies aren't algorithmic encyclopedia, they're just solidly competent engineers. Having worked at a "AAA" tech giant and many more places across the country, I'm happy to report that for the most part there's nothing exceptional about Silicon Valley jobs and what they require. For the most part, barring a minority of highly specialized high-level positions, engineering ability trumps computer science knowledge.
  - mgkimsal 13y ago
    "For the most part, barring a minority of highly specialized high-level positions, engineering ability trumps computer science knowledge." +1
    - RogerL 13y ago
      That is what gets me about these interview questions. I know a lot of very clever people. I am carefully differentiating 'clever' from 'smart', by the way. So many that are superficially fast and smart about solving whiteboard problems are terrible at all the things that actually seem to matter when it comes to creating value: * Keeping a project on budget and schedule * being able to create a budget * managing people and resources * Grinding out boring, but bug free code * Writing clean code * Being able to refactor * Design software that is maintainable * not tick off the people around you SW engineering is a big, fuzzy, ill-defined optimization task in n-dimensional space. There are plenty of clever people that aren't very good at that sort of real-world iterative process. Sure, it is great to have a few people that can quote Knuth (if you don't know what algorithms are available, you'll often choose a substandard one), but by and large I want an engineer, not a scientist. A good one can learn red-black trees, or whatever, when it becomes necessary. The converse (a CS-y type person becoming productive in an engineering environment) seems less likely to occur, in my experience.
vinkelhake 13y ago
It's not about knowing the complexity of every possible sort function. It's about having a good base to stand on, a nicely sized toolbox. If you're working on a solution to an actual problem, it's a pretty damn good to have an idea about the complexity of it. You don't need to be an expert, but developing some kind of intuition for it is very helpful. If your attitude towards these things is "I'll just Google it" then you're not going to be quite as useful when it comes to discussions. Your toolbox needs to be bigger than that.
- mattmanser 13y ago
  Again, what's the point of having a tool you never use? I have had to implement a sort once in 10 years of professional programming, it was in IE6's painfully slow js to fix a slow table sort. More than most. I didn't do a CS degree, the people around me with CS degrees didn't know the answer. I googled it. After the 15 minutes it took to find and implement it I mentioned it to one of the CS people, he promptly reeled off the definition to me, but couldn't see how it solved the problem. Give me someone who never cuts and pastes over someone who know algos any day.
  - ahomescu1 13y ago
    It's not about "sorting" or any particular algorithm, it's about whether you're actually considering the costs and tradeoffs of the code you're writing (which is actually a big part of software engineering), and are equipped to handle those. Now, one cost is execution time, another is memory usage, another is development time, another is maintenance effort and so on. These costs are spread across different domains, but it's important that a programmer considers them.
    - mattmanser 13y ago
      It's really not a big part (apart from the rare times when it is). Firstly you're almost always wrong about what you think will be slow. Add to that it's rare you actually know how a programm will really be used. Secondly most programs never get stressed so it was a complete waste of time. Third, you just made the program complex for no actual good reason, just inexperience and flawed logic. So all that knowledge, those tools, is useless and we know it is. You could fill volumes about the cock ups and bad code caused by premature optimisations. A for each. That's what you'll use 80% of the time, a for 20% and your algos 0%, for all intents and purposes.
tegeek 13y ago
I can do time complexity etc. I know about compilers, trees, graphs & other shit data structures and I can read academic papers on any new shit with a comfortable head. I can learn any new imperative, oop or functional language in a week. But I still can't find a job in Google.
- deleted 13y ago
  [deleted]
vijucat 13y ago
This is needed more for the people inside than outside. I used to be at a famous hedge fund, and then at banks like Goldman Sachs where this attitude was common : "We hire selectively; only 1 in 750 applications is given an offer". Now how does that make you feel to be an employee? It's an amazing feeling, isn't it? To know you're special, that you're a diamond in the dust. It makes it easier for the employer to then demand you to create great things, eh? You're going to pressurize yourself to show them you're worth it. But in reality, what happened, at least in my experience, is that the top talent almost always left because a) they never really got to use that Longest Common Subsequence algorithm that they quizzed on, so the actual daily work-experience was sappy compared to the hype or b) it was just one more conquest anyway; off to better / greater things that challenged their abilities The real gems, in my not-so-objective perspective, were the in-betweeners : people who may not be brilliant, but those who worked hard enough to pass the interview and were really thankful to have a great employer. They stuck around and worked sincerely and were an asset to the firm in every way possible. IMHO, a firm needs 90% ordinary folks, and only a handful of brilliant crazy geniuses.
- JabavuAdams 13y ago
  Why I Never Hire Brilliant Men (1924): https://en.wikisource.org/wiki/Why_I_Never_Hire_Brilliant_Men https://en.wikisource.org/wiki/Why_I_Never_Hire_Brilliant_Me...
meritt 13y ago
Because small to medium sized companies are looking for people to help grow their business and revenue. Large companies tend to already have very stable revenue and now need people to make their systems more efficient in order to decrease expense.
rhizome 13y ago
As evidenced by countless anecdotes and accounts by people who used to work at these companies, they don't. It's not about needing that knowledge, it's about removing those people from the employee pool available to competitor companies and the entrepreneur class.
fayyazkl 13y ago
You might be working in a scenario where you can't just look those things up. You have to code them through. Learning them then through general concept AND THEN implementing is too much. For instance, if you work in the embedded domain, you won't have the liberty to use public / standard / open source libraries.

by mpeg 13y ago

sergiotapia 13y ago

They deal is data volumes so large and so interconnected, it can't hurt to know those sort of things. Surely you agree?

doctorcroc 13y ago
Agree, but what you described is something that can be googled and quickly learned, whereas all the intangibles op listed should be second-nature.
- MichaelGG 13y ago
  I highly doubt that someone that does not know what binary search is, that cannot think for a minute and come up with a small implementation, is going to "google and quickly learn" algorithms and the related thinking. The issue isn't if you can write on simple binary search (considering such a search is a intro-to-programming task[1], that should be a given), but if you have an understanding of the topic in general. When your project calls for a certain performance bound, will you flail around or have some idea what you're looking for? 1: "Guess my number between 1 and 100!"
  - randomdata 13y ago
    I don't think it is difficult as you make it sound. The most difficult part is finding the term "binary search", but even that is not very difficult. All you have to do is generalize your problem and state it to Google. Binary search will almost invariably come up in the results. It even works for algorithms that are far more obscure.
    - MichaelGG 13y ago
      My point isn't that if you don't know what binary search is then you're going to have a hard time doing a lot of algorithm searches. Just like if you didn't know what a linked list was, or a hashtable. Writing a hashtable or reasoning out the properties of a linked list, is not the kind of thing you should need to look up. It should be easy to talk it out during an interview. These are basics. Same for strings, too. A programmer should be able to decisively explain how strings work in their language. Where do you draw the line? Arrays are just another data structure, is it OK if they don't know the properties of arrays since they can look it up?
      - randomdata 13y ago
        > My point isn't that if you don't know what binary search is then you're going to have a hard time doing a lot of algorithm searches. My point is that you can write a lot of software before you need to know what binary search is, and at the point that you do need it, you will be able to find out about it with ease. Like you said, it is a basic topic, so you don't even need much lead time to bring yourself up to speed. I think where you are going with this is that if you don't know what binary search is, you won't recognize when you need it, which sounds quite logical, but experience has suggested it doesn't actually play out like that in the real world. > is it OK if they don't know the properties of arrays since they can look it up? I think so. For the vast majority of software being written, the only thing you do need to understand is the language's interface to arrays, which are usually presented as abstract collections. The idea of a collection is something that transcends beyond programming and computers and is understood by basically everyone. When the time comes that you do need a lower-level understanding, you can look it up quickly and efficiently. A effective practice for writing efficient software is lazy loading, and I believe it works well for humans too. I might be willing to accept that it is a skill that not all people have taken the time to acquire, however.
        softr 13y ago
        I have seen developers struggle to identify the problem. You can't solve a problem if you don't know what a particular algorithm do for you. I have seen java developers knowing only ArrayList and nothing else in the collection. In numerous forums, people ask for code because they don't know what the problem is. In which case, even search can't help.
rhizome 13y ago
Except the thing is that these companies already have established internal libraries and tooling that implement "these sort of things," to a large degree and insulate the business needs from new hires such that any given hire's O(n) skills are not going to touch them until they get put on the task.
typon 13y ago
Unless you're being hired a PhD Senior Software Designer, there is exactly 0% chance (in 2014 anyway) that you're going to be working on improving Google's PageRank algorithm.
- iskander 13y ago
  I was a lowly software engineering intern at Google and spent most of my summer writing MapReduce jobs which would traverse (1) every document in a large index of the web or (2) every book Google has scanned. Even worse, I sometimes needed to compute correlations between pieces of text in the documents. So, not only was the input size huge, the work per document was non-trivial. The remarkable thing about this sort of gig is how utterly unremarkable it is in a large tech company. If there's anything to Big Data beyond hype it's the commoditization of previously incomprehensibly large computations...and everyone doing computation on that scale should at least know the basic language of reasoning about time/space/communication complexity. You don't necessarily need to know the official jargon (though it helps to concisely describe ideas), but you should at least be able to think about how much extra work your program does for each additional input item (and how much extra storage it needs, and how network bandwidth it will eat up).

mgkimsal 13y ago

I suspect when they search for it they're going to find their own published writings/blogs ;) I do think some people at FB/Google need to know this stuff cold, but even that isn't going to be 100% of their engineers.

potatolicious 13y ago
Agreed. I think there's a tinge of arrogance to the claim that Google/FB/what have you need The Best(tm) while everyone else does not. The reality is that there are some jobs (a small minority) at these companies that require incredibly deep algorithmic knowledge - they really do do some complicated things. But the majority of jobs at TwitGooFace are your run of the mill programming jobs, where the requirement and the reality don't call for anyone at that level, and hiring someone at that level is just going to make them bored. Indeed, the vast majority of people I know at these companies aren't algorithmic encyclopedia, they're just solidly competent engineers. Having worked at a "AAA" tech giant and many more places across the country, I'm happy to report that for the most part there's nothing exceptional about Silicon Valley jobs and what they require. For the most part, barring a minority of highly specialized high-level positions, engineering ability trumps computer science knowledge.
- mgkimsal 13y ago
  "For the most part, barring a minority of highly specialized high-level positions, engineering ability trumps computer science knowledge." +1
  - RogerL 13y ago
    That is what gets me about these interview questions. I know a lot of very clever people. I am carefully differentiating 'clever' from 'smart', by the way. So many that are superficially fast and smart about solving whiteboard problems are terrible at all the things that actually seem to matter when it comes to creating value: * Keeping a project on budget and schedule * being able to create a budget * managing people and resources * Grinding out boring, but bug free code * Writing clean code * Being able to refactor * Design software that is maintainable * not tick off the people around you SW engineering is a big, fuzzy, ill-defined optimization task in n-dimensional space. There are plenty of clever people that aren't very good at that sort of real-world iterative process. Sure, it is great to have a few people that can quote Knuth (if you don't know what algorithms are available, you'll often choose a substandard one), but by and large I want an engineer, not a scientist. A good one can learn red-black trees, or whatever, when it becomes necessary. The converse (a CS-y type person becoming productive in an engineering environment) seems less likely to occur, in my experience.

vinkelhake 13y ago

It's not about knowing the complexity of every possible sort function. It's about having a good base to stand on, a nicely sized toolbox. If you're working on a solution to an actual problem, it's a pretty damn good to have an idea about the complexity of it. You don't need to be an expert, but developing some kind of intuition for it is very helpful. If your attitude towards these things is "I'll just Google it" then you're not going to be quite as useful when it comes to discussions. Your toolbox needs to be bigger than that.

mattmanser 13y ago
Again, what's the point of having a tool you never use? I have had to implement a sort once in 10 years of professional programming, it was in IE6's painfully slow js to fix a slow table sort. More than most. I didn't do a CS degree, the people around me with CS degrees didn't know the answer. I googled it. After the 15 minutes it took to find and implement it I mentioned it to one of the CS people, he promptly reeled off the definition to me, but couldn't see how it solved the problem. Give me someone who never cuts and pastes over someone who know algos any day.
- ahomescu1 13y ago
  It's not about "sorting" or any particular algorithm, it's about whether you're actually considering the costs and tradeoffs of the code you're writing (which is actually a big part of software engineering), and are equipped to handle those. Now, one cost is execution time, another is memory usage, another is development time, another is maintenance effort and so on. These costs are spread across different domains, but it's important that a programmer considers them.
  - mattmanser 13y ago
    It's really not a big part (apart from the rare times when it is). Firstly you're almost always wrong about what you think will be slow. Add to that it's rare you actually know how a programm will really be used. Secondly most programs never get stressed so it was a complete waste of time. Third, you just made the program complex for no actual good reason, just inexperience and flawed logic. So all that knowledge, those tools, is useless and we know it is. You could fill volumes about the cock ups and bad code caused by premature optimisations. A for each. That's what you'll use 80% of the time, a for 20% and your algos 0%, for all intents and purposes.

tegeek 13y ago

I can do time complexity etc. I know about compilers, trees, graphs & other shit data structures and I can read academic papers on any new shit with a comfortable head. I can learn any new imperative, oop or functional language in a week. But I still can't find a job in Google.

deleted 13y ago
[deleted]

vijucat 13y ago

This is needed more for the people inside than outside. I used to be at a famous hedge fund, and then at banks like Goldman Sachs where this attitude was common : "We hire selectively; only 1 in 750 applications is given an offer". Now how does that make you feel to be an employee? It's an amazing feeling, isn't it? To know you're special, that you're a diamond in the dust. It makes it easier for the employer to then demand you to create great things, eh? You're going to pressurize yourself to show them you're worth it. But in reality, what happened, at least in my experience, is that the top talent almost always left because a) they never really got to use that Longest Common Subsequence algorithm that they quizzed on, so the actual daily work-experience was sappy compared to the hype or b) it was just one more conquest anyway; off to better / greater things that challenged their abilities The real gems, in my not-so-objective perspective, were the in-betweeners : people who may not be brilliant, but those who worked hard enough to pass the interview and were really thankful to have a great employer. They stuck around and worked sincerely and were an asset to the firm in every way possible. IMHO, a firm needs 90% ordinary folks, and only a handful of brilliant crazy geniuses.

JabavuAdams 13y ago
Why I Never Hire Brilliant Men (1924): https://en.wikisource.org/wiki/Why_I_Never_Hire_Brilliant_Men https://en.wikisource.org/wiki/Why_I_Never_Hire_Brilliant_Me...

meritt 13y ago

Because small to medium sized companies are looking for people to help grow their business and revenue. Large companies tend to already have very stable revenue and now need people to make their systems more efficient in order to decrease expense.

rhizome 13y ago

As evidenced by countless anecdotes and accounts by people who used to work at these companies, they don't. It's not about needing that knowledge, it's about removing those people from the employee pool available to competitor companies and the entrepreneur class.

fayyazkl 13y ago

You might be working in a scenario where you can't just look those things up. You have to code them through. Learning them then through general concept AND THEN implementing is too much. For instance, if you work in the embedded domain, you won't have the liberty to use public / standard / open source libraries.