12 ms·

How to Rock an Algorithms Interview

435 points by harrisreynolds 15y ago

lpolovets 15y ago
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. 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-during-interviews http://www.quora.com/What-is-needed-to-write-flawless-code-d...
ernestipark 15y ago
Real good advice. Totally agree with the brute force thing, I usually resort to that first just to put something down. Related note, Palantir was at the MIT Career Fair recently and when talking to prospective candidates, they asked them a little brain teaser as a filter on the spot.
ohyes 15y ago
>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.
- shabble 15y ago
  Divide and conquer: Assign all applicants randomly to teams. Run competitive coding competition. Reject all but the winning team. Split the winning team into smaller ones, and repeat.
- 0x12 15y ago
  Epic, really. That's one for the 'best of HN'. I'd hate to work for you though ;)
  - gwern 15y ago
    I dunno, it might be fun to work at a company run with algorithm #4.
    - eru 15y ago
      Didn't Bill Gates search for a mate among the employees?
      - william42 15y ago
        It's why Microsoft Bob was released, IIRC.
- Jun8 15y ago
  Two more approaches: 1) There's the well-known Secretary (or Marriage, or Sultan's Dowry) Problem (http://en.wikipedia.org/wiki/Secretary_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 http://en.wikipedia.org/wiki/Stable_marriage_problem) to pick the best candidates for each.
MattLaroche 15y ago
Disclaimer: I work at Palantir Technologies. These are my own opinions and not my company's. 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-google.html 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.
- rhizome 15y ago
  You mean the anti-Wikileaks Palantir?
  - jobu 15y ago
    Yes (http://www.businessinsider.com/palantir-wikileaks-2011-2 http://www.businessinsider.com/palantir-wikileaks-2011-2), but they have since have since apologized for that (http://www.businessinsider.com/palantir-wikileaks-apology-2011-2+ http://www.businessinsider.com/palantir-wikileaks-apology-20...
Jun8 15y ago
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 http://en.wikipedia.org/wiki/How_to_Solve_It)
- gbeeson 15y ago
  Thanks for the link for the article - I appreciate it.
njharman 15y ago
>Given a whiteboard and one hour, 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.
- VladRussian 15y ago
  speaking about value of the online anonymity :)
- tom_b 15y ago
  I am a strong believer that hackers need a portfolio of work for potential employers. 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 15y ago
  What about people who don't use their real name online? Do people really give recruiters their reddit username?
  - william42 15y ago
    YC uses HN usernames internally.
  - njharman 15y ago
    More than one application I've handled recently has included links to HN and LinkedIn profiles. Most list github account.
dabent 15y ago
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.
jtchang 15y ago
Recognize the name because palantir sponsored one of the super happy dev houses. Rather insightful talk was given. Seems like you guys do a lot of number crunching which involve a lot of algorithms work.
dsimms 15y ago
"Error establishing a database connection". heh.
- regs 15y ago
  Whoops - yeah, we're working on that problem right now - at the moment it's back up.
  - rytis 15y ago
    Was that a O(n!) query killing the DB? :)
  - ryan-c 15y ago
    It looks like it should stay up now - the traffic from this is much more than we usually get, but it's doing fine now that the server has more resources available to it.
    - jarek 15y ago
      You sure there couldn't have been an algorithm you could have optimized instead of just throwing more resources at the problem? Your solution seems awfully real world.
beachgeek 15y ago
I had an interview back in 2009 where the CTO of the startup asked me a question, I answered it, after which he very confidently corrected me with the wrong answer(!) Needless to say I didn't join them. The startup also went belly up about 6 months after I interviewed there. How do guys like this get funded?
dr_rezzy 15y ago
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.
- eric-hu 15y ago
  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.
  - dr_rezzy 15y ago
    That would only be a risk if we were talking about a typical high school multiple choice test. I would think that a cheater would be filtered out by this point in their career (this point being applying to a high tech company). However, collaborating on a solution is not necessarily a bad thing. I think the goal here is to find candidates which can deliver unique, valuable, and insightful problem solving skills. To go ahead and bottle that process up into a pre determined steps or a 1 hour drill doesnt serve your goals very well. Who knows, maybe these guys have a recipe which works for them. From my own experiences, I would disagree.
mcantor 15y ago
FTA: 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)?
- tikhonj 15y ago
  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!
alain94040 15y ago
... 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?
- Thrymr 15y ago
  "as an R&D software developer, I probably had to worry about complexity maybe about 0.1% of my time." Yes, but does it scale? If you deal with 10x, or 100x, or 1000x the data, that % will grow. Fast.
pmf 15y ago
Great article about this http://ycombinator.com/munger.html http://ycombinator.com/munger.html
gammarator 15y ago
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.
steve8918 15y ago
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.
- regs 15y ago
  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.
Blunt 15y ago
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.
- pjscott 15y ago
  I don't think anybody's asking you to write a red-black tree of the top of your head, but it would be nice if everybody knew what a balanced tree was and why they might be useful.
  - dhugiaskmak 15y ago
    It would be nice, but I bet the former question is asked far more frequently than the latter.
ankimal 15y ago
Sign up at topcoder.com (https://www.topcoder.com/reg/ https://www.topcoder.com/reg/) and do a BFS (Breadth First Search) of their Algorithm (Single Round Matches) SRMs (http://apps.topcoder.com/wiki/display/tc/Algorithm+Overview http://apps.topcoder.com/wiki/display/tc/Algorithm+Overview). Oh and if you want to brush up on your Algorithm Basics (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index http://community.topcoder.com/tc?module=Static&d1=tutori...).
h3h 15y ago
I don't agree with Aaron Swartz on very much, but we agree on hiring practices: http://www.aaronsw.com/weblog/hiring http://www.aaronsw.com/weblog/hiring
nosequel 15y ago
Step 1, send your resume and skills to wikileaks or other whistle blowing operation Step 2, Palantir assists HBGary Federal in the hacking of wikileaks and wikileaks supporters Step 3, Get hired when they read through your skills
deleted 15y ago
[deleted]
MattGrommes 15y ago
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.
deleted 15y ago
[deleted]
99tokens 15y ago
- Start writing on the board. : start making diagrams on what you think the problem is. Most of the time this half solves the problem - Talk it through : Sometimes interviewer will prod you into right direction, if you are just off. And sometimes get more impressed with the way you are thinking, then the final problem. Worst case: interviwer get stuck on his pre-defined solution. - Think algorithms, Think data structures : This go hand in hand. - Think about related problems you’ve seen before and how they were solved : This is would do after you have broken down the problem in smaller parts - Modify the problem by breaking it up into smaller problems : do this before 5: mostly 1 step will help you here - Don’t be afraid to backtrack: start with the worst case solution, but obvious, then optimize the heck out of it!
jchonphoenix 15y ago
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.
zobzu 15y ago
why those quizz interview sux is simple: anyone can look up the questions, learn them in 2 weeks of time (going slowly) if they've any kind of basic programming knowledge. so basically the questions are wasting the interviewed person's time. if the person fails that test, it means they just didnt care much about that job. but i'm pretty sure any skilled interviewer can figure that out through a much quicker process.
kamaal 15y ago
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.
- lutorm 15y ago
  "In fact if you are [an algorithm expert], you are not likely to take big risks. You are more than happy with the addiction towards that monthly salary." Please elaborate on the evidence for a correlation between knowledge of algorithms and risk taking? Seriously....
  - kamaal 15y ago
    I have seen most people with degrees and especially brilliant ones hesitate to take risks. Probably that's because they feel after all the hardwork its better to have some safer alternatives than risks which don't necessarily guarantee returns. Now don't ask me to come up with survey/research paper. No one goes out and spends time/money/energy to prove each debating point. But I agree with you as well, there is no co relation between them. But unfortunately truth is often stranger than fiction.
phossal 15y ago
This is a well-written article. You've acknowledged an interview process, and you've provided very good advice for candidates who may encounter a similar one. Ideally, both hirer and hiree would obtain perfect insight during the interview, and an alignment of skills, personalities and potential could be determined and made obvious to both parties. We cannot obtain such insight, and yet hiring decisions are still made every day. Some work out, some don't. As in most things, companies must optimize toward some strategy that produces results consistent with their priorities. If each of your programmers must be able to define - not just implement, but actually recall - breadth first, depth first, big-o notation, and others, I suppose your strategy will have to include such questions. What better way to determine whether your candidate can memorize definitions than to ask them for them? But some parts of the common technical interview exist simply because the interviewers themselves aren't aware of any better strategy to obtain the insight that really matters. Is your culture easy-going? Do you need a certain kind of creative influence on your team? Is it really true that your programmers need to program algorithms at all? My point is really quite simple: to alleviate the feeling that we're passing over good people, we should alter the interview process to give the candidate ample opportunities to show us they're a good fit (and that we're a good fit for them. For the record, I never accept offers from companies that ask me lexical structure or algorithm questions, especially if those questions are posed by peer-level interviewers - it suggests a non-performing competitive rather than cooperative atmosphere). We should identify, if we can, the priorities of our team, and then attempt to find a strategy that is optimized for presenting the candidates we're seeking in a favorable light. (I'm leaving this comment because you've written a post that is less about improving the recall or application of algorithms, and more about helping a candidate show you they're capable.)
alttag 15y ago
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.
plant_meme 15y ago
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. * http://www.salon.com/news/opinion/glenn_greenwald/2011/02/15/palantir http://www.salon.com/news/opinion/glenn_greenwald/2011/02/15... * http://www.reuters.com/article/2011/02/17/idUS121866071120110217 http://www.reuters.com/article/2011/02/17/idUS12186607112011...

435 points by harrisreynolds 15y ago

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. 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-during-interviews http://www.quora.com/What-is-needed-to-write-flawless-code-d...

ernestipark 15y ago

Real good advice. Totally agree with the brute force thing, I usually resort to that first just to put something down. Related note, Palantir was at the MIT Career Fair recently and when talking to prospective candidates, they asked them a little brain teaser as a filter on the spot.

ohyes 15y ago

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

shabble 15y ago
Divide and conquer: Assign all applicants randomly to teams. Run competitive coding competition. Reject all but the winning team. Split the winning team into smaller ones, and repeat.
0x12 15y ago
Epic, really. That's one for the 'best of HN'. I'd hate to work for you though ;)
- gwern 15y ago
  I dunno, it might be fun to work at a company run with algorithm #4.
  - eru 15y ago
    Didn't Bill Gates search for a mate among the employees?
    - william42 15y ago
      It's why Microsoft Bob was released, IIRC.
Jun8 15y ago
Two more approaches: 1) There's the well-known Secretary (or Marriage, or Sultan's Dowry) Problem (http://en.wikipedia.org/wiki/Secretary_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 http://en.wikipedia.org/wiki/Stable_marriage_problem) to pick the best candidates for each.

MattLaroche 15y ago

Disclaimer: I work at Palantir Technologies. These are my own opinions and not my company's. 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-google.html 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.

rhizome 15y ago
You mean the anti-Wikileaks Palantir?
- jobu 15y ago
  Yes (http://www.businessinsider.com/palantir-wikileaks-2011-2 http://www.businessinsider.com/palantir-wikileaks-2011-2), but they have since have since apologized for that (http://www.businessinsider.com/palantir-wikileaks-apology-2011-2+ http://www.businessinsider.com/palantir-wikileaks-apology-20...

Jun8 15y ago

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 http://en.wikipedia.org/wiki/How_to_Solve_It)

gbeeson 15y ago
Thanks for the link for the article - I appreciate it.

njharman 15y ago

>Given a whiteboard and one hour, 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.

VladRussian 15y ago
speaking about value of the online anonymity :)
tom_b 15y ago
I am a strong believer that hackers need a portfolio of work for potential employers. 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 15y ago
What about people who don't use their real name online? Do people really give recruiters their reddit username?
- william42 15y ago
  YC uses HN usernames internally.
- njharman 15y ago
  More than one application I've handled recently has included links to HN and LinkedIn profiles. Most list github account.

dabent 15y ago

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.

jtchang 15y ago

Recognize the name because palantir sponsored one of the super happy dev houses. Rather insightful talk was given. Seems like you guys do a lot of number crunching which involve a lot of algorithms work.

dsimms 15y ago

"Error establishing a database connection". heh.

regs 15y ago
Whoops - yeah, we're working on that problem right now - at the moment it's back up.
- rytis 15y ago
  Was that a O(n!) query killing the DB? :)
- ryan-c 15y ago
  It looks like it should stay up now - the traffic from this is much more than we usually get, but it's doing fine now that the server has more resources available to it.
  - jarek 15y ago
    You sure there couldn't have been an algorithm you could have optimized instead of just throwing more resources at the problem? Your solution seems awfully real world.

beachgeek 15y ago

I had an interview back in 2009 where the CTO of the startup asked me a question, I answered it, after which he very confidently corrected me with the wrong answer(!) Needless to say I didn't join them. The startup also went belly up about 6 months after I interviewed there. How do guys like this get funded?

dr_rezzy 15y ago

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.

eric-hu 15y ago
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.
- dr_rezzy 15y ago
  That would only be a risk if we were talking about a typical high school multiple choice test. I would think that a cheater would be filtered out by this point in their career (this point being applying to a high tech company). However, collaborating on a solution is not necessarily a bad thing. I think the goal here is to find candidates which can deliver unique, valuable, and insightful problem solving skills. To go ahead and bottle that process up into a pre determined steps or a 1 hour drill doesnt serve your goals very well. Who knows, maybe these guys have a recipe which works for them. From my own experiences, I would disagree.

mcantor 15y ago

FTA: 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)?

tikhonj 15y ago
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!

alain94040 15y ago

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

Thrymr 15y ago
"as an R&D software developer, I probably had to worry about complexity maybe about 0.1% of my time." Yes, but does it scale? If you deal with 10x, or 100x, or 1000x the data, that % will grow. Fast.

pmf 15y ago

Great article about this http://ycombinator.com/munger.html http://ycombinator.com/munger.html

gammarator 15y ago

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.

steve8918 15y ago

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.

regs 15y ago
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.

Blunt 15y ago

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.

pjscott 15y ago
I don't think anybody's asking you to write a red-black tree of the top of your head, but it would be nice if everybody knew what a balanced tree was and why they might be useful.
- dhugiaskmak 15y ago
  It would be nice, but I bet the former question is asked far more frequently than the latter.

ankimal 15y ago

Sign up at topcoder.com (https://www.topcoder.com/reg/ https://www.topcoder.com/reg/) and do a BFS (Breadth First Search) of their Algorithm (Single Round Matches) SRMs (http://apps.topcoder.com/wiki/display/tc/Algorithm+Overview http://apps.topcoder.com/wiki/display/tc/Algorithm+Overview). Oh and if you want to brush up on your Algorithm Basics (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index http://community.topcoder.com/tc?module=Static&d1=tutori...).

h3h 15y ago

I don't agree with Aaron Swartz on very much, but we agree on hiring practices: http://www.aaronsw.com/weblog/hiring http://www.aaronsw.com/weblog/hiring

nosequel 15y ago

Step 1, send your resume and skills to wikileaks or other whistle blowing operation Step 2, Palantir assists HBGary Federal in the hacking of wikileaks and wikileaks supporters Step 3, Get hired when they read through your skills

deleted 15y ago

[deleted]

MattGrommes 15y ago

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.

deleted 15y ago

[deleted]

99tokens 15y ago

- Start writing on the board. : start making diagrams on what you think the problem is. Most of the time this half solves the problem - Talk it through : Sometimes interviewer will prod you into right direction, if you are just off. And sometimes get more impressed with the way you are thinking, then the final problem. Worst case: interviwer get stuck on his pre-defined solution. - Think algorithms, Think data structures : This go hand in hand. - Think about related problems you’ve seen before and how they were solved : This is would do after you have broken down the problem in smaller parts - Modify the problem by breaking it up into smaller problems : do this before 5: mostly 1 step will help you here - Don’t be afraid to backtrack: start with the worst case solution, but obvious, then optimize the heck out of it!

jchonphoenix 15y ago

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.

zobzu 15y ago

why those quizz interview sux is simple: anyone can look up the questions, learn them in 2 weeks of time (going slowly) if they've any kind of basic programming knowledge. so basically the questions are wasting the interviewed person's time. if the person fails that test, it means they just didnt care much about that job. but i'm pretty sure any skilled interviewer can figure that out through a much quicker process.

kamaal 15y ago

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.

lutorm 15y ago
"In fact if you are [an algorithm expert], you are not likely to take big risks. You are more than happy with the addiction towards that monthly salary." Please elaborate on the evidence for a correlation between knowledge of algorithms and risk taking? Seriously....
- kamaal 15y ago
  I have seen most people with degrees and especially brilliant ones hesitate to take risks. Probably that's because they feel after all the hardwork its better to have some safer alternatives than risks which don't necessarily guarantee returns. Now don't ask me to come up with survey/research paper. No one goes out and spends time/money/energy to prove each debating point. But I agree with you as well, there is no co relation between them. But unfortunately truth is often stranger than fiction.

phossal 15y ago

This is a well-written article. You've acknowledged an interview process, and you've provided very good advice for candidates who may encounter a similar one. Ideally, both hirer and hiree would obtain perfect insight during the interview, and an alignment of skills, personalities and potential could be determined and made obvious to both parties. We cannot obtain such insight, and yet hiring decisions are still made every day. Some work out, some don't. As in most things, companies must optimize toward some strategy that produces results consistent with their priorities. If each of your programmers must be able to define - not just implement, but actually recall - breadth first, depth first, big-o notation, and others, I suppose your strategy will have to include such questions. What better way to determine whether your candidate can memorize definitions than to ask them for them? But some parts of the common technical interview exist simply because the interviewers themselves aren't aware of any better strategy to obtain the insight that really matters. Is your culture easy-going? Do you need a certain kind of creative influence on your team? Is it really true that your programmers need to program algorithms at all? My point is really quite simple: to alleviate the feeling that we're passing over good people, we should alter the interview process to give the candidate ample opportunities to show us they're a good fit (and that we're a good fit for them. For the record, I never accept offers from companies that ask me lexical structure or algorithm questions, especially if those questions are posed by peer-level interviewers - it suggests a non-performing competitive rather than cooperative atmosphere). We should identify, if we can, the priorities of our team, and then attempt to find a strategy that is optimized for presenting the candidates we're seeking in a favorable light. (I'm leaving this comment because you've written a post that is less about improving the recall or application of algorithms, and more about helping a candidate show you they're capable.)

alttag 15y ago

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.

plant_meme 15y ago

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. * http://www.salon.com/news/opinion/glenn_greenwald/2011/02/15/palantir http://www.salon.com/news/opinion/glenn_greenwald/2011/02/15... * http://www.reuters.com/article/2011/02/17/idUS121866071120110217 http://www.reuters.com/article/2011/02/17/idUS12186607112011...