For the other 98% of companies, there's just no need. I've also never ever had to do strange things with binary trees.
90% of programming is problem solving. Knowing how to solve a problem is much more useful than being able to spout out the right answer.
(To echo the first poster. Number of times in 20 years outside of a job interview I've had to implement a Linked List: 0)
IMHO Google, Facebook et al are largely the cause of the current recruiting mess because companies who don't understand what makes a good employee for their company have been cargo-culting Google, Facebook et al in the hope that will "make it rain" for them.
You can't look for an answer if you don't know what question to ask.
This has to do with that whole "conscious competence learning matrix" stuff, more entertainingly described by Steve Schwartz as "shit you know, shit you know you don't know and shit you don't know you don't know" .
The purpose of interview questions about algorithms and data structures is to see whether the candidate has the basic understanding of how the most fundamental data structures work and when to use them; whether they understand the concept of complexity and why it matters.
If you think these things don't matter, you're taking them too literally. Knowing when to use a linked list, when to use a binary search tree and when to use a hash map might be the difference between your software being able to scale or not.
Asking algorithm trivia questions will tell you nothing about whether or not the candidate can apply that knowledge in the real world.
A large part of what I do involves coming into teams that are struggling with delivery, and helping them get back onto the path of productivity.
More than once, I have had developers that could (and have) leave and easily pass a Google interview. They knew more about computer science than I probably ever will.
And in many of these cases, the code they wrote was actively harmful. Unreadable, tangled messes, that nobody else on the team could unwind.
Knowing how and when to use monads, or bloom filters, or any number of other fun tools separates the supermen from the mere humans.
But before you need to care about that, there are more fundamental concepts that matter. Like being able to write readable code that conveys intent, knowing how to write tests that are flexible yet specific, and so on.
While we're at it, who said anything about monads and bloom filters? The former aren't really data structures or algorithms, the latter would hardly qualify as "the most fundamental data structures".
Also, I don't remember saying anything about the irrelevance of writing readable code and flexible-yet-specific tests.
In short, you're certainly disagreeing, but apparently not with me.
As far as companies attempting to emulate Google or Facebook when it comes to interviewing, this sort of thing is even older than either of those companies -- in the mid-90s it was common to attempt your own spin on the "Microsoft interview".
I totally agree with the basic point, though... for all of the supposed rational thinking that goes on in tech, hiring people is mostly cargo cult and voodoo magic.
I'm currently a CS student and I do find many of the startups locally do involve loads of problem solving on the job, which is beneficial from general algorithm knowledge. Although I believe it's more so the ability to understand the concepts as opposed to spouting knowledge for any specific abstract data type or algorithm.
But by any means all companies are not similar, and outside of the purpose of prodding for problem solving aptness it is definitely not the best topic to discuss in an interview to find the /right/ employee for many of the companies of which do ask it.
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 :)
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.
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.
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.
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.
If you don't have a good idea of what is likely to be slow, we have a problem. It's usually I/O, especially synchronous network I/O.
During initial development, maybe you don't know how a program will be used, but maintenance is usually a bigger phase than initial development, so you should have some idea of how things are used.
> Secondly most programs never get stressed so it was a complete waste of time.
What are you working on? Everything I've worked on that has users could go faster. It doesn't take that much complexity to get something that takes 100 ms; and making that take 50 ms instead is an easily perceptible difference.
> 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.
You could fill volumes about the cock ups and bad code caused by completely garbage performance because people didn't stop to think about how to do things right. Simple things like reducing the number of round trips to the database, or avoiding calculations until you know you need them could be called premature optimizations or just doing the job right. Having knowledge of algorithms (and knowing what algorithms are likely to underly the abstraction layers you're using) helps you avoid writing code that will blow up.
Saying it's "I/O" is so abstract and ultimately useless. A simple SQL query could hold a dark secret of a missing index on a table with a billion rows. Yes, that's technically I/O, but for today's programming that's so obtusely abstract it's pointless calling it that. It's a couple of lines of code that all the algo knowledge in the world won't have stopped the problem happening.
It's simply common sense. This is what we're trying to tell you. This is what we're trying to explain to you. Performance problems are almost always unintended consequences rather than "I'll suck it and see". Knowing how to implement the sort yourself won't save you, you have to spot the problem first, which is the hard part.
Basic multiplication is not algos. Knowing that a 100 loops of a thousand loops of a 1ms method is bad doesn't require magical knowledge. Algorithms was always a smoke and mirror trick, the ones you need are usually already in your language written much better than you could and the rest simply hides the truth that performance is mainly down to unexpected I/O bottlenecks usually buried under many layers of abstraction (SQL) or the occasional loop within a loop hidden in a long call stack.
I accept the point that over optimizing is the root of all evil and the rest of the philosophy along those lines. But knowing algorithms and data structures inside out, because where and when you have to choose what - i doubt one can be called a programmer without all that.
And i would say again, i am yet to find some body renowned, who has made their mark as a programmer, and doesn't regard all of this stuff high enough.
Having said all that, if you work in a high level language and develop client facing / application layer desktop/web related stuff - and not involving too much scaling, you won't need these things most of the times. But if not, you can't live with out these.
Lastly, since college and probably since learning to program, the best of the breed usually were the guys who went on to acm and top coder kinda stuff. It is true that building products is not synonymous, but it definitely plays an undeniable part albeit i must agree that it is slightly over valued, nothing else.
And who is renowned in this industry? Game programmers. Not Sass, enterprise or consumer web programmers, who make up the vast majority of working programmers. No, one of the tiny subsets of programmers who do need algos.
You're stuck in your own bubble thinking it's bigger than it is (and seemingly thinking it's "proper" programming). So you're wrong because your premise is flawed. 95% of programmers do "high level language and develop client facing / application layer desktop/web related stuff". Simply open a job website and search for "developer". Add them up by SASS/Enterprise/Consumer Web and then everything else. The first category will be much bigger, 20-30 times bigger.
So the whole line of reasoning is irrational to me. Never tried saying systems programming is more main stream then web or desktop or enterprise.
Talking about renowned, Yes people who have written kernels, operating systems, network stacks / protocols - there is huge list of renowned ones. Do you want me to spell the names out starting with Torvalds or Stallman?
One of the biggest culprits of truely awful programs are graphics card makers. I bet they all know algos, the problem is that they think they know how to program when they're little more than amateurs or hobbyists.
But I still can't find a job in Google.
Large companies tend to already have very stable revenue and now need people to make their systems more efficient in order to decrease expense.
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.
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.
Source: worked with multiple Math PhDs. Have a few friends who are Math PhD working on some esoteric problems that I could not understand.
* 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
Yes... I ran a small group where we all got too inward focused being clever in our code and optimizations, all the while ignoring (for various reasons) that we had less income each month, and eventually folded.
I've since seen this firsthand at a couple other companies, on the inside and outside, where engineering types get way too focused on trying to hyperoptimize for a theoretically possible scenario X, while ignoring real world tickets that are costing them customers daily. They don't seem to realize that... when enough days pass, and enough customers leave, there is no more money to pay them.
Having lived through a couple failures (personal and professional), it's probably easier for me to spot these behaviors (again, because I used to do it myself). In my case, I wish I'd had someone early on beat that out of me - I simply wasn't aware of what was going on. As much as you can say "people have to learn for themselves", I don't believe that's the right attitude to take when the fate of a dept or company rides on what you're doing - too many other lives are involved.
This is in reaction to your 'budget' stuff above - I don't expect people to be Excel/Quickbooks/Peachtree gurus nor CPAs, but understand that you have to get stuff out, on time, and sometimes have to choose your battles and put out less than optimal code, then have a plan to address the known shortcomings.
I agree too on the CS adapting to engineering being more rare than engineering adapting to CS.
Minimizing the CPU and memory usage of your application is engineering more than science; however, doing it requires a lot of CS knowledge.
The issue isn't if you can write on simple binary search (considering such a search is a intro-to-programming task, 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!"
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?
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.
In numerous forums, people ask for code because they don't know what the problem is. In which case, even search can't help.
I'm sure anyone who is a CS researcher would disagree with you, but I'm probably taking your point out of context.
> I have seen java developers knowing only ArrayList and nothing else in the collection.
And I have seen a full-fledged computer science graduate, from a top school for CS, use MS Access for everything, including projects that had nothing to do with databases, because he didn't know how to use any other tools, and didn't appear to have the know-how to take full advantage of that specific environment. Bad programmers are bad programmers.
> In numerous forums, people ask for code because they don't know what the problem is. In which case, even search can't help.
Technically speaking, isn't that still a search? The only difference to using Google is that the results are indexed by humans instead of machines. I think this further emphasizes that most people really can recognize when they need a new tool and can find the right one on demand with very little trouble.
And, like I said, I am willing to believe that it is a skill that is acquired. Skills, by nature, come with varying degrees of ability. Perhaps the least skillful stand out most predominantly in your mind? The best are probably so good at it that you don't even realize that they are doing it.
intersection = ary1 & ary2
Here's one where they are: In python, the in operator works on both lists and sets. For one, large numbers of elements will perform very quickly. For the other, it will perform very slowly. If a developer doesn't understand how they work, and where it's appropriate to use each, they can still do something completely terrible without even straying away from basic APIs.
Case in point, 10s of Googling produced this link:
http://stackoverflow.com/questions/2831212/python-sets-vs-li... ...and I don't even use Python yet.
Is it helpful to understand? Definitely.