Monday, September 2, 2013

Hacking the coding interview

The technical interview process used to hire software engineers/developers hasn't changed much over the years. A couple of coding problems to solve on a whiteboard for roughly an hour a piece over the course of a day. Intersperse lunch & bathroom breaks for fluid I/O needs. Leave feeling exhausted, perhaps regretting how silly you were to forget the algorithm for merge sort on that 3rd interview.

Over the last 7 years I've given and received enough interviews to see a couple of patterns emerge. I think it's rather unfortunate, but proper preparation and foreknowledge of "the process" can make as much difference as simply being the right person for the job. As a result, I've also seen a lot of false positives & negatives occur. I'm really interested in getting to the bottom of this since the most important decision a company makes is who to hire. One rock-star engineer you can trust to get the job done is worth five mediocre ones. Hiring the wrong people can have disastrous consequences on effectiveness, morale and culture.

What I'd like to do is spend the remainder of this post being a hacker who's goal is to get the best offer at a company possible (compensation, position). We will employ all means at our disposal, save for anything dishonest. Think of this as attacker-centric threat modeling. Once we gain an understanding of how one can optimize & exploit the existing process, we can look at flaws and propose a fix.

Know what you're up against
These are the typical steps in the interview process from first contact to offer letter:

At any point, the process can dead end --- for a variety of reasons.  There's a lot to say for each step, but I'd like to focus on the on-site interview for now.

There's a good bit of variety in how on-site interview panels are set up, but at the end of the day this is what will be used to judge whether you get a job or not:
  • 3 to 6 interviewers. Mostly developers, usually includes a hiring manager and sometimes product manager(s). Sometimes you will have 2 interviewers at a time; this usually means a junior interviewer is "shadowing" a more senior one.
  • 45-60 minute interview sessions in a room with a whiteboard. The whiteboard may be replaced with a laptop in some cases, but this is less common.
Some companies are moving away form the last point and doing things like pair programming and live code debugging. I think this move is very interesting, but I haven't seen this applied in a scalable way at larger companies.

Before the Interview
Defining a model for interviews success
I propose the following model as predictor of offer quality:

# of offers = (coding interview skill) x (raw intelligence/skill) x (# companies interviewed)
and
offer quality (position & compensation) = (# of offers) x (Experience in CV)

Out goal is to optimize for offer quality. More offers = more choice = more negotiation leverage = higher pay/better position.

Assuming we can't increase the interviewer's raw intelligence or experience in a short time span, we will focus on the following:
  1. Build a solid "lead generation pipeline" to increase # of companies interviewed
  2. Train the interviewer's brain to be a "coding problem pattern recognizer" to improve coding interview skill
From here on out let's assume you have 1 month to prepare for the interview, nothing lined up, and about 2 hours a day to spend, every day, during evenings and weekends. We'll also assume you're working at a job during this time. Let's be clear, your success will be directly correlated to how much time can be spent studying & on LinkedIn. Remind yourself how badly you want this.

Generating leads
If you're buying a house, you'd be silly to put an offer for the first one you see. Likewise, with interviewing, you should look at as many options as possible. Lead generation is the idea of advertising yourself in such a way that you generate maximum possible interview interest. How can we do this?
  1. LinkedIn --- Update LinkedIn profile as soon as possible to highlight your latest work. Also start reaching out to all friends you have to see if their company is hiring. Get co-workers to write recommendations for you; the more the better. 
  2. A-List --- Identify the companies on your "A-list", places you'd really love to work. If you have any contacts at these companies, reach out to them expressing interest early on. Referrals can work on the inside to get you an interview. Their past experience with you is usually seen as huge plus that can override poor interview feedback in some cases. If you are applying cold to companies on your A-list, go to the careers\job section of their website (these always exist) and apply directly.  
  3. Interview everywhere --- If you're already getting InMail requests on LinkedIn, reply to all of them (even those that you're not interested in). Many requests come from come from headhunters who can connect you with companies you might care about interested in. 
  4. B-List --- For companies that you wouldn't want to work at, but would be easy to interview at, add these to a "B-list". We'll want to interview at these places first to use them as "practice runs".
The idea is that after a couple of weeks you should have a couple of B-list phone screens & on-sites done. If any A-list interview opportunities come up, push them out so that you can have enough B-list preparation. You might even have a couple of offers by the time you start "A-listing". 

Training your Brain
In parallel with lead generation, we need to train your brain to think in terms of coding interviews. This is where you will spend the majority of your time every day. This way of thinking is extremely different from how you approach writing software on your own with an IDE & internet connection. So different, that this is the number one reason for false negatives in interviews.
  1. Language --- First, pick the language you are most comfortable with. I've seen many candidates go into an interview and decide on the spot they wanted to use Scala instead of Ruby. Or C instead of Java. Mistake. Pick one language and stick with it for all your time studying & interviewing. Know the ins and outs of the language so that you can write code without hesitation. Remember, time is limited in interviews, and you don't want to waste it fumbling. Consider picking a language with good library support. Using the provided HashMap in Java beats writing your own from scratch in C.
  2. Study Material --- Next, get a good set of sample interview questions with solutions. We're going to use multiple sources for this. Our mainstay will be Cracking the coding interview which neatly divides problems between discrete domains (get a physical copy off amazon). We'll also be looking at the Berkely cs riddles forum and codercharts.com as backups.
  3. Paper --- From here on out we will only be coding on paper since this mirrors the interview environment best. Being near a computer helps to look up syntax/algorithms, but write everything out by hand. This will help greatly building muscle memory for algorithms. 
  4. Time --- Every day, you should aim to get 4-5 interview questions completed. You will do this until the last day you accept an offer. If you have 15 minutes to spare, do an interview question. This is your new hobby, which you will eat, sleep and breathe.
  5. Work & Study --- In order to buy time for yourself, you'll need to stop doing any overtime at your current job\school. Do the minimum possible to meet your commitments, but no more. Your priority now is your job hunt.
  6. Focus Areas --- In "cracking the coding interview", questions are divided between different categories which require specific approaches we'll want to master. The most important types of problems to master are(in order):
    1. Primary: Trees & Graphs, Recursion & Dynamic Programming, Arrays & Strings, Sorting & Search, Stacks & Queues, OO Design, Linked Lists,  Bit Manipulation, 
    2. Domain Specific (depends on job): Math & Prob, Scalability & Memory, Testing, Databases, Threads & Locks
  7. Bread & Butter Algorithms --- The following algorithms are useful to know in an interview, but you might not use day-to-day: Breadth-first search, Depth-first search, Dynamic Programming, Binary tree traversal, Merge Sort(asked a lot for some reason), Djikstra's algorithm, Tail recursion, Threading & concurrency patterns. 
    • I've seen that the first 4 algorithms in the list apply to a disproportionate amount of interview questions (~1/3).
  8. Tracking --- Track your progress as you go through problems every day. Do all your work in a notebook where you write down each problem on a separate page; this will be useful as you start to see patterns between problems. Keeping a sheet that records all the problems you go through helps build confidence and a sense of accomplishment. Here is an example:

  9. Problem solving approach --- Never, ever jump straight into a question. Think of exactly what clarifying questions you would want to ask had this been an in person interview. Many candidates get dinged for jumping into a question they don't really understand. For each interview question you study, clearly define an interface for the algorithm. If you can think of multiple solutions, learn to pick the best one(see next point #10). Explicitly call out edge cases as you're coding. Once you finish writing code, you're not actually done; verbally go through the code you wrote and confirm it does what it should. Catching bugs in your code without being told is a plus.
  10. O(N) Everything --- Understand Big-O notation and how to apply it to any algorithm you write. Time and space complexity analysis is always asked as part of the coding interview. For every coding problem you solve, you should learn to subconsciously apply this when evaluating the optimal approach.
  11. Talk --- Your ability to verbally communicate your thought process during the interview will be a huge asset. Practice talking to yourself while coding (maybe using the inside voice if you're shy).
  12. Progression --- Your progress will be very slow at first. Painfully so. You won't remember basic algorithms from CS 101 and you'll feel stupid and scared about the interview. You'll be very nervous until you start doing some of the B-list interviews. And then, all of a sudden, things will start to click and you'll start seeing patterns. A scary looking graph question is a simple matter of applying BFS (which you can write up blindfolded now), linked list questions will be a joke, you will be a master of recursion... etc. 
  13. Soft Questions --- You will probably get "soft" questions and these should be part of your training regimen. You should have well thought out, convincing, canned answers for some of the following: ["Describe the current project you're working on", "Describe a time you had a disagreement with a colleague and how you handled it", "What's your biggest weakness", "Why do you want to work here"]. Some of these questions are valid (always know why you want to work at a place you're interviewing). Some are bullshit since if you're caught off guard, you can give a terrible answer that ends up inadvertently hurting your chances.
  14. Puzzle\Riddle Questions --- are pure BS in my opinion, and generally acknowledged to not be a very good indicator of job performance, but you will see them. The key to these is being very methodical, asking smart questions and hoping the problem doesn't have an impossible trick. I wouldn't spend too much time studying these, but you should look at a couple.
  15. Study human relations --- Not, like, the whole field :) But read How to win friends and influence people by Dale Carnegie.  Many points brought up in this book are directly applicable to the "soft" side of the interview process. Seriously, consider this mandatory reading.
  16. Remove Fear --- If you're lucky enough to have an offer from another company before going in to interview, you will do amazing. There will be no fear to hold you back, your self confidence will be sky high and you'll simply do your best without worry. If your lead generation is able to yield enough interviews, this might happen, and you'll be golden.
During the interview
So you've been training hard for a couple of weeks and your lead generation pays off. You land an onsite interview and you want to do well. You'll always be nervous beforehand, but the trick is to A) let your training kick in and B) apply a deep understanding of human relations.
  1. Communication --- ABC. Always be communicating. Candidates that get a problem and write code for 45 minutes without saying a word will not get hired. Communication abilities are as important as coding abilities in a software development environment. Ask questions. If you get stuck, spell out your exact thought process and what you're trying to do next. Even if you don't solve a problem, being able to explain what's going on in your head counts for a lot.
  2. Getting stuck --- You're asked to solve a problem, and you pull a complete blank. You force yourself to solve the problem in a way you're not sure will work. After 20 minutes, you coding in circles. This is a very common pattern and results in a poor interview. In order to recover, communicate as much as possible you thought pattern. Spell out all assumptions you've made up until this point and question them in a conversational way with the interviewer. In the end, interviewers will usually give hints if they see that you're too stuck.
  3. Build Rapport --- If someone likes you, they are more likely to give a "hire". This doesn't happen all the time and interviewers might not realize that it happens, but it does play a role. Two things to try in every interview are 1) try to get the interviewer to laugh and 2) try to get them to tell you something personal about themselves. Doing this at the beginning of the interview is best, and it only works if it feels natural (as with all things).
  4. Hand Writing --- Write neat code. This sounds silly, but you will get dinged if your code is illegible and hard to understand.
  5. Solve what's asked --- Don't try to solve problems that aren't asked. It's very easy to start solving a problem, and suggest going down a very complex route. Make sure you're only solving what's being asked, otherwise you can hurt yourself. Sometimes interviewers will let you go down a winding path if they haven't prepared for the interview. Which leads to my next point ...
  6. Simplify --- When interviewers propose a problem, you can ask a clarifying question that steers the problem in an easier direction by calling out simplifying assumptions. The opportunity to do this comes up more often than you'd think and is easier the more you study. Ex: Instead of coding a sort method from scratch, assume you can use the inbuilt sort method. Boom, you saved 20 minutes.
  7. Never Argue --- Never argue with the interviewer, even if they're wrong. You should politely point out if you think things are obviously incorrect, but if they insist they're right, don't press the issue. The interviewer's pride is not to be trifled with, and doing so will always backfire. Agree that you're wrong and move on; the interviewer usually realizes things on their own after.
  8. Don't eat too much --- So you're interviewing at Google and lunch time comes around. Food is free so you eat way too much, especially carbs. Your post-lunch interview is a disaster since you have trouble focusing due to lethargy. True story.
  9. Keep notes --- Bring a notepad with you and write the names of each of the interviewers you talk to during the day. Writing their name down at the beginning of the interview looks professional and will help you remember their name during the interview. Once the interview is done, write what question they asked you and how you think you did for each question. Be self-critical and drill into areas you think you were weak in future studies.
  10. Get cut short --- If you're scheduled for 6 interviews and you do 3, this usually means you got cut short. That is, your performance was so bad, someone felt it was a waste to have 3 more people interview you. This sometimes happens for the wrong reasons, so don't feel too bad. Keep calm, keep training.
Conclusion
In summary, the real hack to the coding interview is that if I have a big pipeline of companies all using this interview technique then if I screen at Company A on Tuesday and bomb out on a question, I may well get the same question on Thursday from Company B. Company A evaluates me to be low skill and Company B evaluates me to be high skill. Sooner or later, someone will ask me questions I know and I'll be evaluated as high skill.

We should presuppose this happens, and focus on building "pattern recognition" before even entering the first interview. The faster the interviewee gets to "peak pattern" (a level that varies by individual) the more offers and leverage they have.

The fact that I can write this, and it's true, is the saddening fact I'm trying to change.

Next Steps
I'll probably add to this over the coming days if I can think of more. I'd like to get feedback and dissect some of what's going on here. A lot of what I'm suggesting to do is pretty extreme. A lot of the skills here are not something you learn by doing a standard software engineering job (or get coming out of college). It's especially hard for more senior engineers to do technical interviews since most have limited time due to familial obligations and haven't taken CS 101 for quite some time. 

I think there is a better way, and I hope to find it. 

32 comments:

  1. More discussion about this on the interwebs.

    Hacker News:
    https://news.ycombinator.com/item?id=6317959

    reddit/r/programming:
    http://www.reddit.com/r/programming/comments/1lm085/hacking_the_coding_interview/

    ReplyDelete
  2. Wow, great article and resources. I'm going to start coming back to this for my own personal development.

    Thanks for this.

    As for rendion's comment, I think it's arbitrary and fatuous enough to deserve removal.

    ReplyDelete
  3. Great post! I have followed the approach of using "B list" companies as practice runs. Funny thing is that some of the offers I've received from such places have been quite compelling! So be disciplined to stick to your A list companies and make sure to reject politely and professionally so as to ensure that they don't come away thinking you wasted their time.

    ReplyDelete
  4. @ANithian I completely agree! I responded to this same point on hacker news, but I'll repost here:

    >I guess the advantage of interviewing at companies that at first glance you wouldn't want to work at, means that sometimes you get convinced by talking to the great people there. I've joined at least one company that wasn't initially my first choice for this exact reason.

    ReplyDelete
  5. I agree with everything except:

    "Never Argue --- Never argue with the interviewer, even if they're wrong. The interviewer's pride is not to be trifled with, and doing so will always backfire. Agree that you're wrong and move on; the interviewer usually realizes things on their own after."

    I agree that you should not be "arguing" with the interviewer but I have, in the past, said something intentionally incorrect in a set of instructions to see if the candidate 1) could pick up on it, 2) Was able to address it in an acceptable manner (i.e. NOT arguing), and 3) knew what the proper answer was.

    I would recommend something along the lines of "Sir, I heard you say XYZ in the instructions and I had a question. I read the other day that it isn't XYZ but that the proper letters are LMN. Is that way off base?".

    This way you aren't arguing but you come off as competent.

    If the interviewer is the type of person that reacts poorly to that (i.e. very insecure) then it is a good sign that you don't want to work for them.

    Remember you are interviewing the company as much as they are interviewing you.

    Adam

    ReplyDelete
  6. @Adam yes, I agree with you. I think in my mind I viewed argument in much stronger terms and from the perspective of the interviewer. I've actually had candidates actively argue with me during an interview because they thought they were right. In this case they were very wrong, and the way they acted represented them poorly.

    I've updated that point with the following line:
    "You should politely point out if you think things are obviously incorrect, but if they insist they're right, don't press the issue."

    ReplyDelete
    Replies
    1. @Phil I think that works great.

      Of course you really have to be SURE you are right if you are going to try something like that!

      Really a great article overall though, I enjoyed reading it!

      Delete
  7. This comment has been removed by the author.

    ReplyDelete
  8. Well done, Phil.

    I had the after-lunch lethargy when interviewing with Kyle after eating at Palo Alto Sol. True story.

    ReplyDelete
  9. @Chris Ha! Well, it seems to have worked out so I guess your eyes were bigger than your stomach. Or your brain. Or... whatever.

    ReplyDelete
  10. This comment has been removed by the author.

    ReplyDelete
  11. Hi, I am currently preparing for my first technical interview. I am wondering just what are the more important graph and tree algorithms that I have to take note of? I am a little weak when it comes to graphs and trees and I really want to figure out what are the more important things to take note so that I can maximize my time studying for them.

    ReplyDelete
    Replies
    1. The book Introduction to Algorithms: Thomas H. Cormen, Charles E. Leiserson is very readable and covers everything likely to come up in an algorithms interview.

      Delete
  12. Thanks, it's great article. I hope go into startup/big company in Silicon Valley, so it's really helpful to me. Thanks again to share your intel :)

    ReplyDelete
  13. I've been a hiring manager for 10+ years, and am still deep into the software level itself (I've had options and even been a CTO, but, I prefer the architecture and coding still).

    Many of these interview points are correct. I would cover a lot of these. But, since I've been doing it for so long, I also know that this is the coached technique.

    In my phone screens for Java, I cover primitives, collections, threading and memory management. Most of these are not in the "Cracking" book. Intentionally. That book has become a cheat sheet for cookie-cutter developers who lack critical thinking. I like the book more for as a way for existing developers to have fun and challenge themselves on a few things than as questions I would ask in an interview.

    For in-person interviews, I will go over your job history. I will pick out words like "our team" and counter with "What did you do specifically". When you explain your role, I will keep asking detailed questions around your role. You better know what you were doing for the last year, including SDKs (I may not even know them!), communication channels (You used HTTP? Write on the board a simple HTTP Request/Response), Browser oddities (What are some limitations in JQuery with regards to IE that you ran into?)

    I always then follow up with a problem solving question. Sometimes it's one of those silly "Microsoft" questions (what happens if there's no gravity?). I use those when I feel that the candidate doesn't have a good grasp of directly provided information in order to solve the problem. (The questions I use, all the answers are visible, they just have to work thru the logic). The second half of candidates I use a semi-complex system design such as an Elevator or Traffic Signal. Everyone has experienced them. I work thru entity definition/class design. For Sr levels, I want UML or some form of modeling.

    I keep adding problems until they fail. And I will say this, everyone fails my interview at some point. And that's OK. I've been doing it longer and asking the same questions for so long, I expect you to fail. Also, some of the latest cutting edge things I will fail at during the interview and love to openly admit it. The real question is where and how you fail, what questions you ask along the way, and what your logic operations are. When you fail, I give hints, encouragement, even answers to get you to the next step. Everyone has a point where they get stuck, so I do it to see how you deal with somebody providing possible answers. (I do give false ones)

    I have directly hired many hundreds of engineers over my days (30+ in the last 2 years for example). I personally am looking for free-thinkers and problem solvers. Somebody who when given a problem, will work to break down the problem into questions, which form requirements, which then form structures and then code. The code won't be perfect the first time, the problem isn't solved the first time, but, the problem is well understood.

    I've managed other groups including graphic design, test, operations, etc. The questions are always different, but, the substance holds true. Understand the foundation, apply it to a problem. If you can't do those two things, you have no reason to be in the given profession.

    And this comes back to the Critical Thinking. You have to be able to be independent and solve problems in life. Software, you get a logic problem. Operations, you get a hardware/network problem. Web/UI you have a website/ad campain that some exec drew on a napkin. All of these jobs require forward vision and critical thinking.

    Those who lack these are those who work 5 years and "burn out". It's not that they are too old, often times they just don't have the skills needed to keep up with the pace of industry and when interviewing for jobs, are not able to answer at the same level as those who we expect to have a certain level of experience.




    ReplyDelete
    Replies
    1. I can't stand hiring managers such as yourself. Even if I did get an offer from you I would seriously turn you down. Remember this isn't the 80's, there are a lot of jobs out there for software developers and you don't have the golden leads. A job interview is not one sided, its both people trying to figure out if each is a good fit for the other. You seem to really like to validate yourself and your experience, i guess you really like hearing yourself talk don't you.

      Delete
  14. One key thing is missed. It will add tones of value to describe about projects contributed. I mean these are not regular on job works, something more, perhaps an open source. An useful and meaningful contribution will always gives an edge.

    ReplyDelete
  15. I think the B-List strategy is pretty disrespectful of people's time and energy. Companies spend time (and money) on recruiting - going in and taking up a slot that could be used to review a real candidate just for practice is not very professional.

    This style of interviewing (see recent articles about practices based on data) is going away in more serious companies. We look for candidates that have code portfolios or githubs repositories, or get them to do a small coding sample as part of the process. A person's ability to memorize algorithms and repeat them in their language of choice has little correlation to their ability to be commercial software developers.

    ReplyDelete
    Replies
    1. The idea of B-List and A-List is not a waste of anyone's time. People might find that they actually do like what they see on their B-List and accept an offer from them because it meets all of their criteria. Its also not at all disrespectful IMO.

      Delete
  16. You touched on this just a little, but its important to have questions ready to ask the interviewers! If candidates come in and have nothing to ask me, its a huge ding in the interview. How can you not want to know anything about the company or what we do?

    ReplyDelete
  17. Some of the coding challenges rely on string mutability. It doesn't make sense to implement those in programming languages that do not support it. I think it is a good idea to be fluent in a C or Java, which can be a problem if they are not your programming language of choice.

    ReplyDelete
  18. This comment has been removed by the author.

    ReplyDelete
  19. Thank you! This is great article. I found all answers to my questions that I've posted in our local forum.

    ReplyDelete
  20. Pretty nice article. Very informative. Bookmarking this for the future, since I still got a few months of university education around my neck.

    ReplyDelete
  21. Hmmm. I guess hiring based on open-source project contributions is a different blog post.

    ReplyDelete
  22. Hey Phil, had a great chat with you at the McGill career fair and really liked the tutorial. I absolutely agree with the checklists and using no IDEs. Looks like my google interview won't be so hopeless after all! Good luck with the rest of your recruitment trips!

    ReplyDelete
  23. Excellent article, that "progression" paragraph really gave me a huge boost. I am not sure about how to prepare an A-list and B-list. How do I find the companies that do algorithm coding interviews other than the big ones like Google, MS, Apple, Amazon, FB? I really want to prepare my A and B lists but I am stuck there. Help would be really appreciated. Thanks again for the wonderful article.

    ReplyDelete
  24. I read in one of the other articles on the internet that we can answer the questions using pseudo code and not use any specific language. But, the very first point in "Training your Brain" section, specifies exactly the opposite, which one is true?

    ReplyDelete
  25. One of the best detailed articles for general planning and preparation of job hunting. Many people experience fail at two or three interviews in a row, and then they get discouraged to try more. Consequence - they stay at current workplace generating more negative energy, and as the time passes they get harder to motivate again. However, making good plan before starting job marathon is always half of work. If you stick with the plan long enough and get next good offer, then looking backwards, the whole process will look to you as a training journey, and you will easily forget about the fails.

    Planning and training is opposite of hoping!

    ReplyDelete
  26. Cracking the Coding Interview: 150 Programming Questions and Solutions
    http://www.bestbooksite.in/crack-codes-with-150-programming-question-set-available-here

    ReplyDelete
  27. Cracking Programming Interviews: 500 Questions with Solutions

    http://www.amazon.com/Cracking-Programming-Interviews-Questions-Solutions
    /dp/1495459802/

    ReplyDelete