Programming interviews

From NoskeWiki
Jump to navigation Jump to search

About

To land a programming job nowadays, most programmers have to go through a fairly rigorous set of "Programming/Coding Interviews". On this page I have written up some practical noes on how to prepare for such an interview. More importantly: I link to several pages of handy study notes which I have typed up, including fundamentals like data-structures, sorting algorithms and even a few pages worth of selected coding problems to help practice.

With the help of these notes, landed a job at Google in 2013. Since then I've conducted dozens of interviews from the other end of the table and I'm surprised by how many candidates don't know the basics of what it takes to succeed. By reading this page I hope you'll learn... because it really is frustrating to interview someone who you know is bright, but who decided they didn't need to practice hard, and/or been prepped on the basic strategies you need to impress your interviewer.


Strategy Sheet

The sheet below represents a "programming strategy sheet" which I developed myself and used in my interviews. I had it memorized to write onto the whiteboard during my on-site (whiteboard) interviews, but interviewers were pretty impressed I invented such a sheet and said I could just stick my page to the wall. This sheet helped me answer questions in a more methodical way... it encourages you to: draw up a simple example, list assumptions, ask the right questions about data limits, and consider the use of certain "tricks" and data structures (eg: bit vectors, suffix arrays, modified quick-sorts, etc), test on edge cases and so on. After my onsite interviews, I was offered a job at Google. Since then I've interviewed many candidates (from the other end of the table), and I'm always surprised that they miss the basics... simple things like saying "this approach is O(n)" before you're asked (or even start writing code) gives you great points with the interviewer, and this sheet can help prompt you to remember such things.

  • DEFINE PROBLEM
    • draw example (i/o)
    • assumptions
      • data types / limits / range / edge cases
  • ANALYZE
    • brainstorm:
      • strategies: ...... bitwise, recursive, flip, swap, pointers, two-pointer, dynamic
      • search: ......... binary (low/high), nested loop (look ahead), reverse (look behind)
      • data structs: ... hash, stack/queue, heap, tree, graph, suffix arr, bit vector, list
      • sorts: ........... insertion, merge, m quicksort, heap, bucket
    • time/space (O(n))
  • IMPLEMENT
    • code / explain
  • TEST
    • examples
    • edge cases

I would suggest practicing a couple of real questions using this sheet... and as you get fast you'll only need to spend 10 seconds on most bullet points. For instance:

  • "Okay to DEFINE this you've already drawn a great example for me, but for assumption: can my input number be negative? Decimal? Null? Can I expect my string to be small or could it be millions of characters? Do I have memory limits or can I return a good string?"
  • "Now for ANALYSIS my instinct is to make an array and iterate backward and I think that will be O(n)... and I don't think any of these other data structures will help improve on that. Should I go ahead and IMPLEMENT this in code?"
  • "I think that code is done now, let me TEST it... I'll run through the example you gave... now let me think of edge cases?"

To help me reproduce this sheet from memory I used the acronym: DAIT, and lots of practice. Note that this order is *somewhat* similar to the Waterfall model of software development (analysis, design, implementation, testing, evaluation), but is tailored specifically for solving small problems presented in coding interviews.

Noske's Programming Interview Study Notes

Below are some pages I've typed up to help prepare me for code interviews.

Fundamentals


Selected Code Questions

  • Programming questions - Resources for questions.
  • Algorithm problems - A handful of questions I've found all over the web and are generally *fairly* easy to medium difficulty and should be relatively quick to solve.
  • LeetCode problems - A handful of questions from LeetCode and some solutions.
  • Google Code Jam - I've written out my own solutions to some of the (now deprecated) "Google Code Jam" competition problems (a step up in difficulty).


Handy Values to Memorize

  • Computer metrics - refresh yourself on the current speed, capacity, and cost of various components in case you are asked any "practical" questions. I never really was asked such a question, but it's still great knowledge to keep!
  • Big O notation - a handy refresher of all the Big O notation names.
  • Handy measurements - some handy measurements (Pi, e, 210, etc) you should measurements.
  • Handy world statistics - various geographic, economic, and population numbers (world's diameter, size, GDP and populations of US, etc) which can help tremendously if asked a "Fermi" estimation questions. Apparently project managers are often asked such questions... but it's very unlikely you'll be asked if you're going for a programming position - which is a pity - because they are fun!


Books To Read

To prepare for a code interview, here are a few books suggested to me by others. If you've never done a code interview before (which described me up until recently!) I highly, highly recommend that the very first book on this like "Programming Interview Exposed" is the best place to start!

  • "Programming Interviews Exposed: Secrets to Landing Your Next Job" by John Mongan, Noah Suojanen, Noah Kindler, Eric Giguère
    • A fantastic place to start and tells you everything you need to know about the process, plus some great little example coding problems.
  • "Programming Pearls" by Jon Louis Bentley
    • This book is a little slow and "old-school" (its 1st edition was 1986), but contains some brilliant solutions and data-structures like "[suffix arrays]" which you never have used before and reduce your [Big O] run time on notch.
  • "Introduction to Algorithms" by Thomas H Cormen et al - a very thick (>1000 pg) book, which you probably won't read cover to cover (I haven't), but list out some very useful problems and strategies like dynamic programming which aren't covered as well in the previous two books.
  • "Are You Smart Enough to Work at Google?" by William Poundstone - a fun little problem solving book full of open ended question and "zen-like riddles" which (apparently) asked of people going for project management role... but I'm pretty sure these trick questions are asked less and less by companies - especially the ones already published in books like this!



Basic Interview Tips

If a friend wants to interview for a programming company, here is the top few pieces of advice I give them:

  • General Advice:
    • Practice, practice, practice. I can't stress this enough... unless you're a champion at code competitions, you get rusty, and there is no Google searching allowed on during these interviews.
    • Read a book or two. If you have time, you really should read a book - it will have a lot more tips than I gave here, and help you understand the process plus what goes on in the interviewers mind and/or some great questions to practice.
    • Practice on a whiteboard. Go to Target, and buy a little whiteboard and marker, and solve questions on it (most questions should be solvable in 30 lines). Limited space will help get you used to writing small variable names, and being neat and concise - messy code can really hurt you for reading your own code and solving the question! Even the best coder can fail at an interview if they haven't practiced on a whiteboard ever, and without practicing how to gracefully leave room, write small, append/erase nicely, use one-letter-code-interview variable-names... your code can suddenly get so messy you can't refactor - and you will go home disappointed that poor white board proficiency may have just cost you a good job!
    • Enthusiastic attitude. We're supposed to show no bias, but when I get a candidate who: (a) has life in his/her eyes, (b) is excited they made it this far, (c) seems eager to learn new skills, (d) is generally personable.... then it's human nature for me give that person more hints and a better review. When I was an interview candidate I convinced myself "I probably won't get it, but by gosh, this is going to be fun", and with that simple attitude I feel all my interviewers loved me. I was genuinely very grateful every-time they said "or you could do it this way" - because I felt I was learning so much from their wisdom. People recognize that enthusiasm to grow. If you are nervous, don't be afraid to admit it... and definitely be friendly during the small chat, but also hint that you are keen to get started (so you have enough time)! Generally the people who interview you are never the people who makes the decision... they just send feedback and a copy of your written code to the hiring committee... and they are the people who make the final decision.
    • Don't panic. You start excited but then bang - you get a question you have no idea how to solve. What helped me calm down in such moments is knowing that companies like Google learn nothing from you if you can solve the problem easily. Maybe you knew the answer already. But if you get stumped, then they see what you are made of. Do you panic and shut down... or do you go back to basics... offer some intelligent insights (each one of those counts!), think about different data-structures, and say "hrmmm... I'm just going to take a minute to think about this if you don't mind" or "I'm not sure I can solve the whole thing, but I know I can solve this part, so maybe I can code that up first". Some problems can be broken into pieces, and worst, worst case scenario... admit that you are not strong at this particular question type, and either need help or maybe there's another question? If you have 5 interviews in one day.... well very few people do well in all 5.... if you've solved all your questions, then I would say the interviewers as a whole have failed a little bit, because they didn't stump you. Be excited about being stumped.
    • Talk out loud. Coding by yourself you don't generally talk out loud... but in onsite and (especially) phone interviews you are expected to talk though your thought process. For some people this comes naturally... if not then practice with a friend.
    • Ask recruiter for help. Good recruiters should have their own advice on books to read, arrive early, etc. If nothing else, ask why type of questions will be asked and maybe the first names (just first names will do) of your onsite interviewers if you make it that far. Why? Well I wrote them all on the board so I'd remember because... well, after 6 interviews you will forget the name of the guy you are talking to.
  • Good Interview Code Style:
    • Use tiny variable names. In regular coding "bool AddTrailingCharactersToDatabase(const char charToUse, const int numberOfChars)" might help readability, but will take up half your interview to write on the whiteboard. Instead: "bool addChars(char c, int n)" ... and then for your for loops always "i" and then "j" (if you need an inner loop). Your candidate already knows the problem, and refactoring becomes way easier when you have short or (better yet) single letters variables! When you see coding champions in work you rarely see a function or variable name more than three letters!
    • Never write header crap. For good jobs they just assume you know how to Google search the right includes... or maybe we even have automated tools for that... so never write "#include", "using std" or even "std::"... that part is assumed!
    • Start with a function that defines problem. The first line of code you write should be a function. You already know the inputs and output you want.... so impress the interviewer by showing that you understood the question: "string removeCharsFromString(string s, vector<char> bad_chars) {". Don't hesitate to write extra functions when then make sense.
    • Learn the style guide. Most languages allow for much naming flexibility, but the people who interview you are used to style guides. I am biased, but I recommend you read the "Google Style Guide" for your language and start applying it too all code you write as good practice. When it comes to your interview, you can then impress the crap out of your interviewer if you say "do you mind if I use Google Style Guide" before you start writing code.


Typical Interview Process

So what's a typical interview process for a big company like Amazon or Google?

  • Application submitted. If you're lucky you know someone at the company, they refer you with an excellent recommendation, and you "get the email" they are interested in weeks. If you have to submit a resume... well good luck - there is often a long waiting line, and often resume are rejected because... we'll there's a lot of competition and amazing talent out there!
  • weeks to years waiting
  • Initial chat with recruiter. Your designated "recruiter" calls you for a quick chat about where you might be a good fit. She's also wants schedule you for a phone interview.
  • days to weeks waiting
  • Phone interview (~40 minutes). Unless you are amazing (a distinguished researcher or leadership in another company), you'll have to do at least 1, but often 2 "phone screens". Here you are called on the phone or (if you prefer) you can use video chat, and the interviewer and you both look at the same empty document as you type code. Please don't cheat! Interviewers can generally tell if you have a friend nearby trying to help you, or if you are trying to Google search the answer. Even if you got away with it, you are screwing yourself over, because you can't sneak those people into an offsite. A 2nd interview may mean the 1st interviewer was on the fence, although at some places 2 is standard before they pay money for you to visit the company!
  • days to weeks waiting
  • Onsite interviews (5 * 45 minutes) If you passed your screen your recruiter will coordinate for you to come to the company campus in person. Be prepared for a long day... get a good night sleep. Typically you have about five programming interviews back-to-back... except for a 1 hour "lunch interview" in the middle, where you can relax, because usually this person doesn't give feedback - they are just taking you for a friendly meal. Hopefully you'll have a great day, and it won't take too long for all your interviewer to submit feedback so that the hiring committee can decide, and the recruiter to finally call back.
  • usually days to weeks waiting (unless you were a superstar)
  • Offer / no offer. If you did really, really well... you'll get an offer. Don't feel bad if you don't - there's a lot of false negatives, and most companies will let you interview again in a year... by which time you'll have more experience (hopefully) and be better prepared! If you do get an offer... you've beat the odds! I don't even want to tell you the fraction of people who don't get an offer, because it's a little discouraging. The encouraging part is that no matter what the outcome - you've learned a lot from the process.


Links

  • hackerrank.com - really fun problems which you can solve in any language and just fill in a function and hit run. :)
  • topcoder.com - lets you register and then access and/or compete for money on a large number of code challenges you wouldn't normally see.
  • BestCode.com Interview Questions - lists a few basic interview questions.



Acknowledgements: Emily Dunn and William Mathews from Google for suggesting some of the above resources.
Retrieved from "http://andrewnoske.com/w/index.php?title=Programming_interviews&oldid=6797"