How to Rock an Algorithms Interview

I'd hate to work for you though ;)

1) There's the well-known Secretary (or Marriage, or Sultan's Dowry) Problem (http://en.wikipedia.org/wiki/Secretary_problem). It has three caveats, though:

* Solution assumes that you have a lot of (e.g. ~20) candidates.

* It is assumed that you can sum up each candidate's ability in a single number. This is the hardest part, since the human mind works relationally and assigning absolute numbers to anything is hard.

* The probability of picking the best candidate is only 1/e.

But at least there's a guaranteed bound on the probability of success, that some of the other methods lack.

2) (If possible) Hire the engineer and HR person at the same time and have the HR candidates evaluate the engineering candidates. Then run Knuth's stable marriage algorithm (http://en.wikipedia.org/wiki/Stable_marriage_problem) to pick the best candidates for each.

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!

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.

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.

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.

- 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.

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.

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.

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.

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).

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%.

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.

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.

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.

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.

What a waste!

I'm self-taught and I've read and learned about computational complexity several times from various CS books and later Internet since I was maybe fifteen years old. I know how O(1), O(lg n), O(n lg n), O(n), O(n^x), and O(x^n) scale and which kind of algorithms roughly belong to which order of complexity.

However, keyword being several times.

I so rarely bump into these that I don't actively remember if heapsort is lg n or n lg n, or how the best-case, average-case, and worst-case complexities differ exactly between heapsort, quicksort, and mergesort. (I do remember that mergesort had a good worst-case behaviour in comparison to the others, at least quicksort, but I'd really have to check the bounds separately.) To mitigate this, I've guiltily re-learned them several times--I like reading Knuth or other CS books per se, just for fun--but like anything you don't need you do have a hard time remembering.

However, I do recognize them all being lg-something and looking up the various bounds is just a Google search away. Further, I do recognize the complexity orders in the sense that I might prototype something and initially stash items into a linked list but make a mental note that accessing the list can potentially become a bottleneck because it's O(n) so I shall reserve some mind power to change it into some O(lg) tree or ordered array at some point.

But at the other end the truth is that you just have to have some idea about complexity. You generally don't need more than that, and when you do you can just re-study that portion of the subject in detail from a huge number of web pages.

For example, it's useful to recognize the obvious bottlenecks of O(n^x) and O(x^n) but if you do, you don't bump into them anymore. You might bump into O(n) bottlenecks because you left them there yourself, probably on purpose, but since you recognize what linear complexity can do you will generally just change the relevant data structures into O(lg something) and be done with it. And if O(lg something) code becomes a bottleneck, you usually have stupid access patterns elsewhere in the code; I don't remember ever seeing a binary tree alone having become the real bottleneck in any program with the rest of the code being optimal.

What's interesting is that I more often bump into problems with the physical representation of the data structure than the computational complexity. A big naive hash table can cause lots of cache misses unless you deliberately work to align your items withing as few cachelines as possible. The difference between accessing five cachelines rather than five hundred cachelines can be blasting. I know this kind of optimization wouldn't scale towards n⇒∞ generally but it can have a big effect on real-world programs.

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.

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.

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.

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.

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.

Yes, but does it scale? If you deal with 10x, or 100x, or 1000x the data, that % will grow. Fast.

Please elaborate on the evidence for a correlation between knowledge of algorithms and risk taking?

Seriously....