>Given a whiteboard and one hour, determine whether the person across from you is someone you’d like to work with, in the trenches, for the next n years.
If we ignore the requirements of one hour...
Brute force: Hire a random candidate that hasn't been hired by you before. Fire them when you get fed up with them. Hire a different candidate. Repeat.
Greedy Algorithm: Develop the model for an ideal candidate, assign that candidate a numerical model and then compute the distance from the current candidate to the ideal candidate.* Hire the candidate with the lowest computed distance. If a candidate comes along with a lower computed distance fire the old candidate and hire the new one.
Simulated Annealing: As with the greedy algorithm, but instead of hiring based solely on lowest computed distance, include a small % chance that you will randomly fire the candidate and hire candidate that is slightly worse. (Optional extension to the algorithm is to keep the best candidate so far cached somewhere, potentially a transporter buffer).
Genetic Algorithms: From your pool of candidates, select the top candidates. Breed these candidates, randomly introducing mutations. Repeat again with the progeny of the previous pool, until one of the candidates passes a satisficing threshold 'distance' score.
* = Notice that this is the actually the most difficult part of (almost any useful application of) these algorithms but I managed to hand-wave right through it.
You should know these data structures inside and out.
What are the insertion/deletion/lookup characteristics?
(O(log n) for a balanced binary tree, for example.)
How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head.
I didn't have a traditional CS education in college. Maybe there's some kind of magic that happens in Algorithms [1-3]01 that permanently etches these characteristics into your brain. But whatever it is, I missed out.
My main problem is that I don't seem to need this information to do what I do. I work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate. Maybe I've been lucky. Maybe it's because none of my personal projects have gotten popular enough to be subjected to the kind of load that reveals such problems. Maybe it's because I haven't worked on the kind of project that needs this sort of attention. Whatever the reason, I simply have never hit a point in my work (which I assure you has been non-trivial at times) when I sat back and said to myself, "Gosh, if only I were more familiar with the complexity breakdown of the classic data structures, I would be able to solve this problem much more effectively or efficiently."
The thing is, I know that I'm perfectly capable of nurturing greater fluency in algorithms, so it seems like a waste to inevitably flub the more demanding portions of algorithm-based interviews. So what should I do? Is the answer as simple as biting the bullet and using flash cards until I know it all by rote (which feels like cheating), or am I "doing it wrong" somehow? Is my lack of fluency preventing me from understanding just how important it is (a la Dunning-Kruger)?
The good thing is that most operations on most data-structures (as well as many of the more common algorithms) don't require solving recurrence equations to determine their asymptotic growth, usually our intuition based on counting tends to be pretty close.
Sketch out your basic data structures on a piece of paper, then just use your finger to trace out how you could do insert, delete, search, etc you can usually tell if something is taking O(lg n), O(n), O(n lg n), etc just by counting the steps you take. After you're comfortable with this, sketch it in your head. You can't forget something that you understand.
The point is that if figuring what out Big O is seems like something you have to memorize to recall quickly, then you very likely don't really understand the underlying data structure/algorithm (and as such you rightfully should do poorly on algorithms interviews). Take the time to make sure you really understand what's going on, and everything else should fall into place.
Our interviews at Palantir test for these for two reasons:
We evaluate a lot of people coming straight out of school in CS. They don't have much experience in development. Thus, the best way to test if a candidate is smart is to see if he's learned his course material well. We do a lot of heavy algorithms and distributed systems, so we ask that, but it also happens to be what students learn.
Running time and Oh, however, in addition to systems knowledge, is extremely important to creating good software in general. If you can't determine how your software will scale with big data, and you can't understand why efficient code that runs quickly with small operations does so, you simply can't write good software.
I realize a lot of people on HN take offense at these claims because they've written programs without this knowledge and claim they are self taught. The reality, however, is that they aren't good programmers. You don't need a good programmer to write a prototype that works and determines market fit. You do need good programmers to scale your product, add features efficiently, and architect solutions without making a crippling mess of your code.
Edit: I realize the above comment sounds a little condescending. It wasn't meant to be. I have met self taught programmers that are amazing. Most people just don't have the self discipline to fully learn a subject matter (I many times don't). So a lot of "self taught" programmers have only taught themselves 10% of what they need to know and never bother learning the other 90%.
What I've found is that I do not remember that, say, a tree map or heap have logarithmic insertion time, but rather have a vague mapping of general concepts to behavior: something like "tree" => logarithms, "list" => lines (linear), "array" => magic (constant). Then I think something like "a hashmap is like an array, so it can be accessed in constant time".
If you're a visual thinker, the "shape" of an algorithm or data structure can be very helpful as well. Imagine it geometrically and think about how, say, the height of a tree compares to the length of a line with the same number of elements.
Of course, practice also helps. I'm lucky enough to get plenty of practice in school, but I think doing various condensed but nontrivial problems (think programming contests/project Euler) is probably both more fun and more practical for somebody out of school.
Ultimately, knowing running time of algorithms and behavior of data structures isn't really what's important; rather, it is just a "symptom" (in a good way) of having a solid grasp of what's going on. Just memorizing the times with flashcards is basically faking it--it might not be completely useless, but you'd be better off actually understanding everything.
I used to not have any idea about this sort of thing. My code worked fine, and I had no problems--I also never thought "hmm, I could have made this more efficient if only I knew about tree maps!". However, I now realize that the reason I never saw this was because I didn't know enough--I didn't even know enough to know I had a problem!
In short: you should learn how the algorithms and data structures work, not just for running times or interview questions, but to make you a better programmer. It definitely won't make you worse!
I'll give you my point of view. I'm young(21), I'm in my third year as an informatics student, and I feel greatly intimidated by all these hard stuff. I can barely write a working web app, even with all the hand-holding modern frameworks give me. I don't consider myself smart(i'm bright enough to be a programmer, but nothing more).
Recently I sat down and thought about where I want to be in 5-10 years. I don't want to be writing django apps in 10 years, I don't want to write software that sort of works some of the time, and i don't want to be a replaceable commodity programmer working on outsourced software that the real programmers didn't feel like working on, so they send it to India, or Eastern Europe(which is where I’m from). Sure, I can make a comfortable living that way, but what I want to be in 10 years is a competent expert.
I want to work in diverse fields, with people much smarter than me, and the little knowledge and experience I can gain in my career I want to pass down to younger programmers. I want to wake up in the morning and be proud that I've build things that actually matter, and not just the latest social networking pop-culture crap that many of us are dealing with now. In short, i want to e a hacker!
To do this, I decided to dedicate myself to actually learn the hard stuff that most people shy away from, just because they can get by with only some python/ruby/php and jquery knowledge. Math, CS(algorithms, data structures, languages, compilers, architectures, networks, operating systems), science, philosophy, history, art, etc. All hard stuff that I'll never need to know in order to build a web store site for a small business that barely gets the web, get paid, and go wash the car on the weekend. Even if i can never learn all of it, even a fraction is better that writing the same simple web apps for 10 years.
"I work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate."
I tend to think of programming tasks being split into two major categories: applications programming and systems programming.
My definition of these terms: applications programming is writing software to be used by a normal person. Systems programming is writing software to be used by another programmer. (These definitions may be a little different from how these terms are commonly used.)
From your self description, you seem to land pretty squarely on the application programming side of that divide. For most application programming tasks, getting good performance consists mostly of selecting libraries, databases, web servers, languages, etc. with the performance characteristics your application requires, and building your application on top of them.
The system programmer is the one writing those libraries, etc. and so those performance requirements fall squarely on them.
So I would say that as long as you stick to applications programming, algorithmic ignorance probably isn't a major problem. But a company like Palantir needs systems programmers (per my definition above, even if the "clients" are just other developers within the company) which is why they need to ask algorithms questions in their interviews.
I didn't do CS as a major in undergrad (I found it too easy... that sound pretentious, but the program at my college simply wasn't difficult enough for me), but I did do a MS in CS afterwards.
It helped a lot with basis for algorithms (terminology so you can understand what you are reading), but it didn't really teach me all of the data-structures and algorithms that I know. (There are really too many to cover everything properly/thoroughly in the extent of a course or two, even at graduate level). Also, I would have been sunk if I hadn't known a lot of it before applying to the program.
So I learned a lot of it through my own natural curiosity.
Everything concrete that I learned about data structures and algorithms started by reading Wikipedia. The CS articles are fairly accurate (it is hard to gain anything by spreading misinformation in them) and there are often times links at the bottom to the actual papers and code describing and implementing them. Start with the overview article and then read the paper. Look up any terms you don't know. Try implementing it in a language you like.
You can also Learn about data-structures in languages that you like (looks like ruby/python for you; you are in luck... those are both open source). Figure out how they are implemented, and performance characteristics. Go ahead and download the source tree and read the code.
Implement naive versions of various datastructures/algorithms yourself. See if you can play with them and improve them for various tasks. (Can I make this hash table use less memory? Give it a faster hash function? Make it a game).
I think flash cards would be a bad move, because then it starts to feel like a chore. Programming and reading and learning shouldn't be taken to like chores, they should be enjoyable and rewarding.
For a significant number of gigs, you don't need to know algorithms and data structures. This continues to surprise me.
I think for interviewers, this approach to quizzing on algorithms and data structures is probably just a well-known practice and probably lacks correlation with the work of a specific job role most of the time.
If you aspire to work somewhere that has a demand for deeper algorithmic work, you do need to understand algorithms and data structures. I think this is probably a smaller number of potential jobs than many of us on HN would like to admit - there is simply a large number of mundane IT/dev jobs where the naive imperative solution will be just fine.
I would skip flash cards, but try to find small projects at work that require algorithmic and data structure thinking. Then you get some applied experience that will "tell a good story" at an interview plus build your analysis skills.
I think for a lot of jobs, even being able to talk about an algorithm and data structure design that you personally did will put you way out in front of a number of candidates.
Author of the post here. I don't think you're "doing it wrong" or missing anything because of a cognitive blindspot. Algo skills are important for certain types of problems (scaling, number crunching), but useless for others (interaction design, API design, ...). It's just one of the skills we're looking for, since a lot of our meatiest problems don't require algorithms at all (beyond a simple hashtable or two). If you've looked at your own coding history and don't see the need to be more fluent with algorithms, then you're probably right.
> I work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate.
Algorithmic complexity isn't about performance, it's about scalability. A hand-written implementation in assembly that's O(N^2) will be slower than an implementation in Basic that's O(N) (or even O(N log N)) for a sufficiently large N.
I suggest picking up Programming Pearls, they had an example of a BASIC program on C64 vs. a Fortran program on a mainframe (the book is from the 80s) demonstrating this.
That said, if building basics web apps is all you want to do (e.g., internal enterprise applications) then you don't need this knowledge. However, the harder stuff (whether algorithmic, systems, etc...) like (but not limited to) what Palantir works is what I find more interesting.
There aren't too many things to remember in order to be useful:
- Operations that take the same amount of time regardless of the input are O(1). ie: 1+1 takes just as long as 10000+10000 (okay, not really, but it's a reasonable assumption.)
- Doing a small sequence of operations runs in O(maximum of all operations). Doing 5 adds (which are O(1)) runs in O(1). Doing an O(n) operation followed by an O(k) (where k > n) runs in O(k) time.
- Looping n times over O(k) operations runs in O(n*k) time. (Assume n is fairly big.)
- Due to the structure of a tree, accessing a node is generally O(depth of the node). Max depth = log_m(number of nodes) for a full tree. (Where m is the number of children each node has. For a binary tree, m=2)
- From there, you can pretty much combine these rules to analyze many algorithms. These aren't by any means all of the rules, but they are some of the most useful in my experience.
> Maybe it's because none of my personal projects have gotten popular enough to be subjected to the kind of load that reveals such problems.
That's probably the case, and there's no shame in that. The companies who ask these questions do so because their engineers deal with these kinds of scaling challenges every day. They can't afford to have people casually slip in an O(n^2) algorithm when an O(n lg n) or O(n) algorithm would do. If you don't have the experience of working in this kind of environment it's not a dealbreaker, you just need to show an awareness of the big-O implications of your algorithms, which will most likely come from some combination of study and practice.
> Is my lack of fluency preventing me from understanding just how important it is
Probably not -- if you're working at a small scale, then big-O probably truly is one of your lesser concerns (unless you write an O(2^n) algorithm, which is less common to happen accidentally).
>My main problem is that I don't seem to need this information to do what I do. I work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate. Maybe I've been lucky.
if you don't know the time it really should take, then you just don't know what you have a performance problem. Dunning-Kruger in application to software engineering. Too typical a situation in the industry.
1) The chance my app will be so heavily used that it requires deep knowledge of many algorithms is pretty low.
2) The chance my app has serious marketing or business model problems is pretty high.
3) The extra cost of using a scalable platform (PaaS) like Appengine, Heroku or plain EC2 is less than both the cost of my time to learn or relearn all of those algorithms and the cost of setting up my own scalable platform.
I see far more business model/marketing problems than scalability/performance ones.
> I don't seem to need this information to do what I do
Are you sure about that? Have you never tried to do something, found it was taking forever, and gave up? Maybe you concluded it was impossible, or you found some way to approximate what you needed.
I am another self-taught programmer, and believe me you are going to be kicking yourself once you do learn a few good algorithms and data structures. Your favorite accomplishments -- intricate beasts that you felt you had tamed with much sweat and effort -- are going to turn into five or six lines. Or maybe two or three small, easy to understand programs. Impossibly large amounts of data are going to look easily tameable.
Related: What books or other resources would HNers recommend for someone with limited algorithm and data structure experience who wants to beef up via self-study?
I'm specifically interested in books/other resources that lend themselves to self-study. It's easy enough to look up what MIT is using for their Intro to Algorithms course, but it's harder to gauge if a book or other resource is suitable for usage outside of a classroom setting. Bonus points if it has a practical focus so that I can quickly add the gleaned knowledge to my real-world toolkit.
Just read the lecture notes for a CS course that covers this already. It will almost always be a course that also covers the sorting algorithms and basic data structures(what is a linked list, tree, graph, etc.) It won't take that long. As for coming up with the Big-O omplexity for a routine on the spot, most job interveiws will throw something at you where it should be intuitive if you know the canonical algorithms. I have yet to read about someone having to solve a recurrence relation on the spot(everyone's already forgotten the cook book approach they learned in school, if they ever learned it at all). It's not a lot to remember, so no big deal if the only thing you use if for is to impress someone.
If you want true "Who gives a shit?" material from academia, try Automata Theory, or whatever the course where you learn about the pumping lemma is called. Never read about that coming up in an interview.
How about the obvious thing, which is to look at the curriculum of undergrad and grad level algorithms courses, pick up some textbooks, and learn it on your own? Flashcards won't help, because it's not a problem of memorization. You need to own the knowledge that lookup in a balanced binary tree is a logarithmic operation.
On like the very first day of algorithms class there was a table with a bunch of data structures down the side and insert, lookup, delete across the table with a bunch of n's and lg n's in the cells. There was also a table very much like it on the first exam, except the cells were empty.
For your next side project, read CLRS and force yourself to complete a reasonable number of the problems (say every other problem, or every nth problem).
Then I think it will stick.
If you really don't need this info, then don't waste your time. To work at a place like Palantir, you do need this info.
It is unfortunate that instead of turning into a discussion about how to excel in an algorithms interview (which is what the original post is about) this thread has wandered into whether it is useful to even learn algorithms.
The collections data structures are more or less designed to achieve certain performance characteristics. So knowing those performance characteristics means knowing what those data structures were designed to do. This seems like a pretty critical part of familiarity to me.
* Find sample questions that similar companies use. Work through them. Discover what you don't know. Find if you're weak on dynamic programming, graph algorithms, algorithm analysis, etc. Then get strong on those. The less you want to do sample problems, the more important they are for you.
* When practicing interview questions, whiteboard at least some. Talk through them. Really go through a question in every detail.
* Before you interview at your dream company, interview elsewhere with similar difficulty questions. In my opinion, it should be another company that you'd like to work at but don't covet. If that doesn't work for you, a technical or even a non-technical friend could play the role of interviewer (you'll have to give the non technical friend questions!). Nerves have been a giant issue for me in interviews - and this has significantly helped.
* Calm down as much as you can and forgive yourself when you make errors. The questions at good companies are calibrated to have non-obvious solutions, interviewers expect you to struggle a bit. Candidates who freeze-up and attach their mind to one (usually wrong track) solution fail interviews. I've done it. If you've practiced with the first three bullet points, this should be less likely.
For me, this blog post represents a step backwards. They open up saying that the 1 hour interview provides absolutely no indication of how well a prospective candidate will perform. Hopefully most people will agree here. Then they go ahead and state that their staple interview will be an on the spot problem solving screening and then list the steps the expect the candidate to take in solving said problem. What does this say about their own problem solving skills? I will leave this upto the reader. Let me throw an alternative out. Why don't you give a prospective candidate a written test/problem and give them as much time as they want, using methods and environments they are comfortable with, and have them return to you a solution of their choosing. Wouldn't this best capture how a person breaks down a problem, solves it, and finally presents a solution? Leave the onsite to better understand someones personality, likableness, and workability. Maybe even ask them to walk you thru how they came up with the solution and how they worked the problem. The options here are plentiful.
Thank you! I came here to post this. I was really disappointed when an alternative wasn't presented after they declared algorithm quizzes useless.
I'm all for code walk-throughs and explanations. You can't bullshit your problem solving process, but you can memorize (or forget) algorithm trivia.
For what it's worth I've failed and succeeded at these kinds of algorithms on the whiteboard interviews. Even after nailing it I felt uncomfortable and disrespected. I think there is a real problem with continuing to do these interviews because it's the cool thing to do, and these smart people don't feel like turning their problem solving skills towards the hiring problem.
That does seem to be an interview technique used at some companies. It comes with its own set of problems, though.
What if someone asks a friend for help or pays someone to solve the problem in its entirety? If your problems aren't unique enough, they could also google the answers.
With that said, I actually prefer your approach. Its pitfalls have to be weighed carefully; hiring someone who knew enough to fake it could be a costly setback for a small company. However, it does remove some unnecessary pressure from the interview process.
One thing I noticed in recent interview is that the problems often test if the candidate can think to use two structures or algorithms to solve a problem. Early on, I made the mistake of thinking of interview questions more as homework problems from college where there was often only one type of data structure or algorithm involved in a problem. That's good when teaching a single concept, but real-world problem are more complex. My advice is to find problems that use multiple structures or concepts together and study and code those.
Also, learn to code the basics so well that you can do them by hand on a basic text editor or whiteboard. Get so good at it that you can write code that has a very good chance of running if it were actually compiled/run. I found that it's very different to code on a whiteboard than it is in an IDE or text editor. When my first interview came up, I struggled to write down things with a dry-erase that would have taken me seconds on-screen.
One strategy that I liked to see an employer use was homework. That might make some job seekers cringe, but gave me a chance to write real code like I would for a job. It was also a filter for how badly I wanted a job. There were jobs I didn't complete the homework for just because the location or employer wasn't something I was genuinely interested in.
I did homework for the position I landed and they did a code review as part of my interview. It went well, because I got to see how my future co-workers would handle giving feedback, and some comfort on my end that this employer actually cared enough to do code reviews.
The interview process at this point, at least in Silicon Valley, is broken.
There's an arms race between interview "gamers" that memorize all the answers to every single question out there, vs interviewers that are asking increasingly ridiculous questions. It's naive to think these days that not knowing the answer to a common question, but coming up with the answer will work. It won't. If 9 candidates know the answer right away, and you don't, but you figure it out, do you honestly think the interviewer will care? I've talked to plenty of interviewers at my company and that's the unwritten rule.
For example, over the phone, one of my friends was asked to design and give an algorithm to solve a maze. It took 10+ mins just to understand exactly what the interviewer wanted, and at that point, time was up, the interviewer was frustrated, and my friend didn't get the job, even though he's better than me, technically.
The only way to interview these days, it to know everything.
It was much cooler to be jaded about the interview process last year.
But in all seriousness, I'm sure there are companies like the one you described and there are many that aren't that way. I'm certain that your blanket characterization of 'the interview process, at least in Silicon Valley' being broken is incorrect.
You don't need to come up with weirder and harder questions. You just want to give them something in a form that they haven't seen before. It makes them listen and think, which is what you're looking for.
I always look at an interview to be more like a code review than a unit test: it's not about getting the right answer, it's how you get there that tells me what kind of an engineer you are. In fact, if you get the answer too quickly or jump to it, even if I don't think you're cheating, I need to ask another question or make you explain yourself in depth so I can probe how you got there.
Frankly, I find this type of interview insulting. Let's face it. Unless you work with "algorithms" on a dialy basis, I'm willing to bet that most who do not cannot regurgitate a red black tree at the drop of a hat. I work in this field off in on as an embedded developer and I'm always going to various texts on the subject to align my thinking with the code I'm writing (C++ in my case). It's one thing to talk through these scenarios in an interview and it's yet another to judge one's ability to solve problems on how well they come up with a solution to an interview question. I give merit to the "talking through" and this is what I do. I find that if a candidate can carry on an intelligent conversation about a particular problem domain, he's hirable material and in 15 years of running my own company I've had only 2 out of 43 people leave my company.
We, hiring folks, aren't limited to just that anymore. There's github, linkedin, hn/reddit posts, random google stalking, etc.
I can find a lot about you, your attitudes, opinions, ability to communicate, style, etc. that, or you for whatever reason (paranoid, on the lam, aren't passionate) have zero online presence).
The face to face interview is mostly to confirm or refute what I've already learned about you.
This is a great, meaty blog post. I really like the first point about always coming up with a brute force solution so that you at least have something, and so that you have a chance to think about the problem a little. I've seen candidates skip the brute force approach too many times so that they can immediately work on a more optimal solution. At the end, they often end up without any solution at all. I guess Knuth's advice about premature optimization applies too interviews as well.
... or you could just forget about O(n) questions in interviews. I know those got really popular with Google, but as an R&D software developer, I probably had to worry about complexity maybe about 0.1% of my time.
How clean is your code? Do you have good coding habits? Do you get lost inside complex data structures? Do you understand concurrency issues?
I'm seeing a lot of great discussion on this thread, but I'd like to point out that you should NEVER rely on memorization to know the asymptotic bounds of operations on data structures.
You should understand how that data structure works and then derive the running time from that.
People seem to know hash sets use O(1) lookup, trees use O(log(n)), and so forth. In reality, they have an in depth understanding of the underlying implementation and are rederiving their answers on the spot with simple mental calculations.
You must hire people for two things to win big today's world. Productivity and Analytical skills. If you are searching people with specific factual knowledge, sure that is important but often that leads only to mediocre or average results.
If you know how to do a thing before hand, that helps only in solving that kind of problems specifically. And that too only if the person is productive enough to do it in time. Any new problem or a change in paradigm of thought will require you to undergo the same regime of work what it would be for a newbie. They don't call learning a never ending process just like that.
The biggest winning point in today's world is not knowing something. But discovering something quickly, and acting on it in time. If you are not hiring people for this you will end with a lot of work force which looks good, but doesn't necessarily translate to doing good.
This is the biggest problem with education systems around the world currently. They impart facts and leave the person just there. Further its the individual responsibility to take that forward.
The most brilliant folks who have done big around me have hardly been algorithm experts. In fact if you are one, you are not likely to take big risks. You are more than happy with the addiction towards that monthly salary. And what helps you pay of those college loans.
The most successful around me are the ones, do a great thing. Think about the next step. Research about it, work on it with full productivity. Deliver.. Next step and the process goes on.
If you hire people for factual knowledge you may hire the best, but you are sure to miss out the exceptional. This is probably the reason, why big companies fail to come with game changers.
You get folks who are great at the regular day to day operations. But anything else, and you see the problems clear.
I think the part that's missing from discussion here is: "First: Make sure you understand the problem". Sure, for strictly algorithmic questions, where there is one mathematically demonstrable optimal answer (or at least, a way to compare solutions), this may seem less important, but for more open-ended questions (e.g., "How many barbers are there in [$LOCATION]?"), clarifying the why is essential, because definitions are important and vary by context. It's also important to seek whether a "good enough" solution is acceptable, or if high optimization is important. (Related, what are the memory/processing/load/runtime constraints, if any.) These are the sorts of questions that, in my mind, demonstrates a candidate's willingness to reflect on his/her own solutions.
Abstracting away the specific content about algorithms, these suggestions are helpful for any kind of technical oral exam, e.g. qualifying exams in grad school. The more clearly you can communicate your thought process to your interviewers, the more accurately they can assess your work.
For an excellent discussion of the approaches outlined here and problem solving heuristics in general check out Polya's How To Solve It, it's a classic (http://en.wikipedia.org/wiki/How_to_Solve_It)
Sincere request to HN readers. If you have ethics, try to avoid working for Palantir. Palantir is an unethical company. They were involved in the HBGary scandal. They tried to smear Glenn Greenwald. They might have the best and hardest interview process and may have the smartest people. But all these technical wizardry is moot when they don't have ethics.
If you're struggling with algorithms I'd suggest reading the book Programming Pearls (2nd edition). It's a little dated but not enough to matter too much. The big thing it helps with is what I think of as "algorithmic thinking". The various chapters go through different approaches to solving problems and help you get a handle on why a particular approach might be O(n^2) versus O(logn) and why that's important. It's very helpful stuff.
[+] [-] ohyes|14 years ago|reply
If we ignore the requirements of one hour...
Brute force: Hire a random candidate that hasn't been hired by you before. Fire them when you get fed up with them. Hire a different candidate. Repeat.
Greedy Algorithm: Develop the model for an ideal candidate, assign that candidate a numerical model and then compute the distance from the current candidate to the ideal candidate.* Hire the candidate with the lowest computed distance. If a candidate comes along with a lower computed distance fire the old candidate and hire the new one.
Simulated Annealing: As with the greedy algorithm, but instead of hiring based solely on lowest computed distance, include a small % chance that you will randomly fire the candidate and hire candidate that is slightly worse. (Optional extension to the algorithm is to keep the best candidate so far cached somewhere, potentially a transporter buffer).
Genetic Algorithms: From your pool of candidates, select the top candidates. Breed these candidates, randomly introducing mutations. Repeat again with the progeny of the previous pool, until one of the candidates passes a satisficing threshold 'distance' score.
* = Notice that this is the actually the most difficult part of (almost any useful application of) these algorithms but I managed to hand-wave right through it.
[+] [-] mcantor|14 years ago|reply
I didn't have a traditional CS education in college. Maybe there's some kind of magic that happens in Algorithms [1-3]01 that permanently etches these characteristics into your brain. But whatever it is, I missed out.
My main problem is that I don't seem to need this information to do what I do. I work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate. Maybe I've been lucky. Maybe it's because none of my personal projects have gotten popular enough to be subjected to the kind of load that reveals such problems. Maybe it's because I haven't worked on the kind of project that needs this sort of attention. Whatever the reason, I simply have never hit a point in my work (which I assure you has been non-trivial at times) when I sat back and said to myself, "Gosh, if only I were more familiar with the complexity breakdown of the classic data structures, I would be able to solve this problem much more effectively or efficiently."
The thing is, I know that I'm perfectly capable of nurturing greater fluency in algorithms, so it seems like a waste to inevitably flub the more demanding portions of algorithm-based interviews. So what should I do? Is the answer as simple as biting the bullet and using flash cards until I know it all by rote (which feels like cheating), or am I "doing it wrong" somehow? Is my lack of fluency preventing me from understanding just how important it is (a la Dunning-Kruger)?
[+] [-] Homunculiheaded|14 years ago|reply
Sketch out your basic data structures on a piece of paper, then just use your finger to trace out how you could do insert, delete, search, etc you can usually tell if something is taking O(lg n), O(n), O(n lg n), etc just by counting the steps you take. After you're comfortable with this, sketch it in your head. You can't forget something that you understand.
The point is that if figuring what out Big O is seems like something you have to memorize to recall quickly, then you very likely don't really understand the underlying data structure/algorithm (and as such you rightfully should do poorly on algorithms interviews). Take the time to make sure you really understand what's going on, and everything else should fall into place.
[+] [-] jchonphoenix|14 years ago|reply
We evaluate a lot of people coming straight out of school in CS. They don't have much experience in development. Thus, the best way to test if a candidate is smart is to see if he's learned his course material well. We do a lot of heavy algorithms and distributed systems, so we ask that, but it also happens to be what students learn.
Running time and Oh, however, in addition to systems knowledge, is extremely important to creating good software in general. If you can't determine how your software will scale with big data, and you can't understand why efficient code that runs quickly with small operations does so, you simply can't write good software.
I realize a lot of people on HN take offense at these claims because they've written programs without this knowledge and claim they are self taught. The reality, however, is that they aren't good programmers. You don't need a good programmer to write a prototype that works and determines market fit. You do need good programmers to scale your product, add features efficiently, and architect solutions without making a crippling mess of your code.
Edit: I realize the above comment sounds a little condescending. It wasn't meant to be. I have met self taught programmers that are amazing. Most people just don't have the self discipline to fully learn a subject matter (I many times don't). So a lot of "self taught" programmers have only taught themselves 10% of what they need to know and never bother learning the other 90%.
[+] [-] tikhonj|14 years ago|reply
If you're a visual thinker, the "shape" of an algorithm or data structure can be very helpful as well. Imagine it geometrically and think about how, say, the height of a tree compares to the length of a line with the same number of elements.
Of course, practice also helps. I'm lucky enough to get plenty of practice in school, but I think doing various condensed but nontrivial problems (think programming contests/project Euler) is probably both more fun and more practical for somebody out of school.
Ultimately, knowing running time of algorithms and behavior of data structures isn't really what's important; rather, it is just a "symptom" (in a good way) of having a solid grasp of what's going on. Just memorizing the times with flashcards is basically faking it--it might not be completely useless, but you'd be better off actually understanding everything.
I used to not have any idea about this sort of thing. My code worked fine, and I had no problems--I also never thought "hmm, I could have made this more efficient if only I knew about tree maps!". However, I now realize that the reason I never saw this was because I didn't know enough--I didn't even know enough to know I had a problem!
In short: you should learn how the algorithms and data structures work, not just for running times or interview questions, but to make you a better programmer. It definitely won't make you worse!
[+] [-] pavelludiq|14 years ago|reply
Recently I sat down and thought about where I want to be in 5-10 years. I don't want to be writing django apps in 10 years, I don't want to write software that sort of works some of the time, and i don't want to be a replaceable commodity programmer working on outsourced software that the real programmers didn't feel like working on, so they send it to India, or Eastern Europe(which is where I’m from). Sure, I can make a comfortable living that way, but what I want to be in 10 years is a competent expert.
I want to work in diverse fields, with people much smarter than me, and the little knowledge and experience I can gain in my career I want to pass down to younger programmers. I want to wake up in the morning and be proud that I've build things that actually matter, and not just the latest social networking pop-culture crap that many of us are dealing with now. In short, i want to e a hacker!
To do this, I decided to dedicate myself to actually learn the hard stuff that most people shy away from, just because they can get by with only some python/ruby/php and jquery knowledge. Math, CS(algorithms, data structures, languages, compilers, architectures, networks, operating systems), science, philosophy, history, art, etc. All hard stuff that I'll never need to know in order to build a web store site for a small business that barely gets the web, get paid, and go wash the car on the weekend. Even if i can never learn all of it, even a fraction is better that writing the same simple web apps for 10 years.
[+] [-] jimbokun|14 years ago|reply
I tend to think of programming tasks being split into two major categories: applications programming and systems programming.
My definition of these terms: applications programming is writing software to be used by a normal person. Systems programming is writing software to be used by another programmer. (These definitions may be a little different from how these terms are commonly used.)
From your self description, you seem to land pretty squarely on the application programming side of that divide. For most application programming tasks, getting good performance consists mostly of selecting libraries, databases, web servers, languages, etc. with the performance characteristics your application requires, and building your application on top of them.
The system programmer is the one writing those libraries, etc. and so those performance requirements fall squarely on them.
So I would say that as long as you stick to applications programming, algorithmic ignorance probably isn't a major problem. But a company like Palantir needs systems programmers (per my definition above, even if the "clients" are just other developers within the company) which is why they need to ask algorithms questions in their interviews.
[+] [-] ohyes|14 years ago|reply
It helped a lot with basis for algorithms (terminology so you can understand what you are reading), but it didn't really teach me all of the data-structures and algorithms that I know. (There are really too many to cover everything properly/thoroughly in the extent of a course or two, even at graduate level). Also, I would have been sunk if I hadn't known a lot of it before applying to the program.
So I learned a lot of it through my own natural curiosity.
Everything concrete that I learned about data structures and algorithms started by reading Wikipedia. The CS articles are fairly accurate (it is hard to gain anything by spreading misinformation in them) and there are often times links at the bottom to the actual papers and code describing and implementing them. Start with the overview article and then read the paper. Look up any terms you don't know. Try implementing it in a language you like.
You can also Learn about data-structures in languages that you like (looks like ruby/python for you; you are in luck... those are both open source). Figure out how they are implemented, and performance characteristics. Go ahead and download the source tree and read the code.
Implement naive versions of various datastructures/algorithms yourself. See if you can play with them and improve them for various tasks. (Can I make this hash table use less memory? Give it a faster hash function? Make it a game).
I think flash cards would be a bad move, because then it starts to feel like a chore. Programming and reading and learning shouldn't be taken to like chores, they should be enjoyable and rewarding.
[+] [-] tom_b|14 years ago|reply
I think for interviewers, this approach to quizzing on algorithms and data structures is probably just a well-known practice and probably lacks correlation with the work of a specific job role most of the time.
If you aspire to work somewhere that has a demand for deeper algorithmic work, you do need to understand algorithms and data structures. I think this is probably a smaller number of potential jobs than many of us on HN would like to admit - there is simply a large number of mundane IT/dev jobs where the naive imperative solution will be just fine.
I would skip flash cards, but try to find small projects at work that require algorithmic and data structure thinking. Then you get some applied experience that will "tell a good story" at an interview plus build your analysis skills.
I think for a lot of jobs, even being able to talk about an algorithm and data structure design that you personally did will put you way out in front of a number of candidates.
[+] [-] hellotoast|14 years ago|reply
[+] [-] strlen|14 years ago|reply
Algorithmic complexity isn't about performance, it's about scalability. A hand-written implementation in assembly that's O(N^2) will be slower than an implementation in Basic that's O(N) (or even O(N log N)) for a sufficiently large N.
I suggest picking up Programming Pearls, they had an example of a BASIC program on C64 vs. a Fortran program on a mainframe (the book is from the 80s) demonstrating this.
That said, if building basics web apps is all you want to do (e.g., internal enterprise applications) then you don't need this knowledge. However, the harder stuff (whether algorithmic, systems, etc...) like (but not limited to) what Palantir works is what I find more interesting.
[+] [-] rcfox|14 years ago|reply
- Operations that take the same amount of time regardless of the input are O(1). ie: 1+1 takes just as long as 10000+10000 (okay, not really, but it's a reasonable assumption.)
- Doing a small sequence of operations runs in O(maximum of all operations). Doing 5 adds (which are O(1)) runs in O(1). Doing an O(n) operation followed by an O(k) (where k > n) runs in O(k) time.
- Looping n times over O(k) operations runs in O(n*k) time. (Assume n is fairly big.)
- Due to the structure of a tree, accessing a node is generally O(depth of the node). Max depth = log_m(number of nodes) for a full tree. (Where m is the number of children each node has. For a binary tree, m=2)
- From there, you can pretty much combine these rules to analyze many algorithms. These aren't by any means all of the rules, but they are some of the most useful in my experience.
[+] [-] haberman|14 years ago|reply
That's probably the case, and there's no shame in that. The companies who ask these questions do so because their engineers deal with these kinds of scaling challenges every day. They can't afford to have people casually slip in an O(n^2) algorithm when an O(n lg n) or O(n) algorithm would do. If you don't have the experience of working in this kind of environment it's not a dealbreaker, you just need to show an awareness of the big-O implications of your algorithms, which will most likely come from some combination of study and practice.
> Is my lack of fluency preventing me from understanding just how important it is
Probably not -- if you're working at a small scale, then big-O probably truly is one of your lesser concerns (unless you write an O(2^n) algorithm, which is less common to happen accidentally).
[+] [-] VladRussian|14 years ago|reply
if you don't know the time it really should take, then you just don't know what you have a performance problem. Dunning-Kruger in application to software engineering. Too typical a situation in the industry.
[+] [-] va_coder|14 years ago|reply
2011 Programmer Cost/Benefit reality:
1) The chance my app will be so heavily used that it requires deep knowledge of many algorithms is pretty low.
2) The chance my app has serious marketing or business model problems is pretty high.
3) The extra cost of using a scalable platform (PaaS) like Appengine, Heroku or plain EC2 is less than both the cost of my time to learn or relearn all of those algorithms and the cost of setting up my own scalable platform.
I see far more business model/marketing problems than scalability/performance ones.
[+] [-] neilk|14 years ago|reply
Are you sure about that? Have you never tried to do something, found it was taking forever, and gave up? Maybe you concluded it was impossible, or you found some way to approximate what you needed.
I am another self-taught programmer, and believe me you are going to be kicking yourself once you do learn a few good algorithms and data structures. Your favorite accomplishments -- intricate beasts that you felt you had tamed with much sweat and effort -- are going to turn into five or six lines. Or maybe two or three small, easy to understand programs. Impossibly large amounts of data are going to look easily tameable.
> How does one achieve this?
Not so hard - read a good book. There are lots.
[+] [-] adbge|14 years ago|reply
I'm specifically interested in books/other resources that lend themselves to self-study. It's easy enough to look up what MIT is using for their Intro to Algorithms course, but it's harder to gauge if a book or other resource is suitable for usage outside of a classroom setting. Bonus points if it has a practical focus so that I can quickly add the gleaned knowledge to my real-world toolkit.
[+] [-] sampsonjs|14 years ago|reply
[+] [-] scott_s|14 years ago|reply
[+] [-] tedunangst|14 years ago|reply
[+] [-] andrewparker|14 years ago|reply
Then I think it will stick.
If you really don't need this info, then don't waste your time. To work at a place like Palantir, you do need this info.
[+] [-] ashr|14 years ago|reply
What a waste!
[+] [-] astrofinch|14 years ago|reply
[+] [-] ericmoritz|14 years ago|reply
[+] [-] rohit89|14 years ago|reply
[+] [-] MattLaroche|14 years ago|reply
The Palantir post is great for how to handle yourself when you are already there. Steve Yegge's "Get That Job at Google" is a great how-to-really-prepare piece. http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...
A couple other suggestions:
* Find sample questions that similar companies use. Work through them. Discover what you don't know. Find if you're weak on dynamic programming, graph algorithms, algorithm analysis, etc. Then get strong on those. The less you want to do sample problems, the more important they are for you.
* When practicing interview questions, whiteboard at least some. Talk through them. Really go through a question in every detail.
* Before you interview at your dream company, interview elsewhere with similar difficulty questions. In my opinion, it should be another company that you'd like to work at but don't covet. If that doesn't work for you, a technical or even a non-technical friend could play the role of interviewer (you'll have to give the non technical friend questions!). Nerves have been a giant issue for me in interviews - and this has significantly helped.
* Calm down as much as you can and forgive yourself when you make errors. The questions at good companies are calibrated to have non-obvious solutions, interviewers expect you to struggle a bit. Candidates who freeze-up and attach their mind to one (usually wrong track) solution fail interviews. I've done it. If you've practiced with the first three bullet points, this should be less likely.
[+] [-] dr_rezzy|14 years ago|reply
[+] [-] enjalot|14 years ago|reply
I'm all for code walk-throughs and explanations. You can't bullshit your problem solving process, but you can memorize (or forget) algorithm trivia.
For what it's worth I've failed and succeeded at these kinds of algorithms on the whiteboard interviews. Even after nailing it I felt uncomfortable and disrespected. I think there is a real problem with continuing to do these interviews because it's the cool thing to do, and these smart people don't feel like turning their problem solving skills towards the hiring problem.
[+] [-] eric-hu|14 years ago|reply
What if someone asks a friend for help or pays someone to solve the problem in its entirety? If your problems aren't unique enough, they could also google the answers.
With that said, I actually prefer your approach. Its pitfalls have to be weighed carefully; hiring someone who knew enough to fake it could be a costly setback for a small company. However, it does remove some unnecessary pressure from the interview process.
[+] [-] dabent|14 years ago|reply
Also, learn to code the basics so well that you can do them by hand on a basic text editor or whiteboard. Get so good at it that you can write code that has a very good chance of running if it were actually compiled/run. I found that it's very different to code on a whiteboard than it is in an IDE or text editor. When my first interview came up, I struggled to write down things with a dry-erase that would have taken me seconds on-screen.
One strategy that I liked to see an employer use was homework. That might make some job seekers cringe, but gave me a chance to write real code like I would for a job. It was also a filter for how badly I wanted a job. There were jobs I didn't complete the homework for just because the location or employer wasn't something I was genuinely interested in.
I did homework for the position I landed and they did a code review as part of my interview. It went well, because I got to see how my future co-workers would handle giving feedback, and some comfort on my end that this employer actually cared enough to do code reviews.
[+] [-] steve8918|14 years ago|reply
There's an arms race between interview "gamers" that memorize all the answers to every single question out there, vs interviewers that are asking increasingly ridiculous questions. It's naive to think these days that not knowing the answer to a common question, but coming up with the answer will work. It won't. If 9 candidates know the answer right away, and you don't, but you figure it out, do you honestly think the interviewer will care? I've talked to plenty of interviewers at my company and that's the unwritten rule.
For example, over the phone, one of my friends was asked to design and give an algorithm to solve a maze. It took 10+ mins just to understand exactly what the interviewer wanted, and at that point, time was up, the interviewer was frustrated, and my friend didn't get the job, even though he's better than me, technically.
The only way to interview these days, it to know everything.
[+] [-] regs|14 years ago|reply
But in all seriousness, I'm sure there are companies like the one you described and there are many that aren't that way. I'm certain that your blanket characterization of 'the interview process, at least in Silicon Valley' being broken is incorrect.
You don't need to come up with weirder and harder questions. You just want to give them something in a form that they haven't seen before. It makes them listen and think, which is what you're looking for.
I always look at an interview to be more like a code review than a unit test: it's not about getting the right answer, it's how you get there that tells me what kind of an engineer you are. In fact, if you get the answer too quickly or jump to it, even if I don't think you're cheating, I need to ask another question or make you explain yourself in depth so I can probe how you got there.
[+] [-] Blunt|14 years ago|reply
[+] [-] njharman|14 years ago|reply
We, hiring folks, aren't limited to just that anymore. There's github, linkedin, hn/reddit posts, random google stalking, etc.
I can find a lot about you, your attitudes, opinions, ability to communicate, style, etc. that, or you for whatever reason (paranoid, on the lam, aren't passionate) have zero online presence).
The face to face interview is mostly to confirm or refute what I've already learned about you.
[+] [-] tom_b|14 years ago|reply
I am not convinced that such a portfolio must exist in an online and easily discoverable package for potential employers.
Having a strong and trusted personal network is probably a stronger signaling system.
Of course, having both a meaningful online presence and a strong referral network is best.
[+] [-] esrauch|14 years ago|reply
[+] [-] VladRussian|14 years ago|reply
[+] [-] lpolovets|14 years ago|reply
There's also a good Quora page that talks about the (complementary) coding side of algorithm questions: http://www.quora.com/What-is-needed-to-write-flawless-code-d...
[+] [-] alain94040|14 years ago|reply
How clean is your code? Do you have good coding habits? Do you get lost inside complex data structures? Do you understand concurrency issues?
[+] [-] Thrymr|14 years ago|reply
Yes, but does it scale? If you deal with 10x, or 100x, or 1000x the data, that % will grow. Fast.
[+] [-] ankimal|14 years ago|reply
Oh and if you want to brush up on your Algorithm Basics (http://community.topcoder.com/tc?module=Static&d1=tutori...).
[+] [-] jchonphoenix|14 years ago|reply
You should understand how that data structure works and then derive the running time from that.
People seem to know hash sets use O(1) lookup, trees use O(log(n)), and so forth. In reality, they have an in depth understanding of the underlying implementation and are rederiving their answers on the spot with simple mental calculations.
[+] [-] kamaal|14 years ago|reply
If you know how to do a thing before hand, that helps only in solving that kind of problems specifically. And that too only if the person is productive enough to do it in time. Any new problem or a change in paradigm of thought will require you to undergo the same regime of work what it would be for a newbie. They don't call learning a never ending process just like that.
The biggest winning point in today's world is not knowing something. But discovering something quickly, and acting on it in time. If you are not hiring people for this you will end with a lot of work force which looks good, but doesn't necessarily translate to doing good.
This is the biggest problem with education systems around the world currently. They impart facts and leave the person just there. Further its the individual responsibility to take that forward.
The most brilliant folks who have done big around me have hardly been algorithm experts. In fact if you are one, you are not likely to take big risks. You are more than happy with the addiction towards that monthly salary. And what helps you pay of those college loans.
The most successful around me are the ones, do a great thing. Think about the next step. Research about it, work on it with full productivity. Deliver.. Next step and the process goes on.
If you hire people for factual knowledge you may hire the best, but you are sure to miss out the exceptional. This is probably the reason, why big companies fail to come with game changers.
You get folks who are great at the regular day to day operations. But anything else, and you see the problems clear.
[+] [-] h3h|14 years ago|reply
http://www.aaronsw.com/weblog/hiring
[+] [-] alttag|14 years ago|reply
[+] [-] gammarator|14 years ago|reply
[+] [-] Jun8|14 years ago|reply
[+] [-] plant_meme|14 years ago|reply
* http://www.salon.com/news/opinion/glenn_greenwald/2011/02/15...
* http://www.reuters.com/article/2011/02/17/idUS12186607112011...
[+] [-] MattGrommes|14 years ago|reply
[+] [-] dsimms|14 years ago|reply