Monday, March 04, 2013

Programming interviews: recommendations versus experience

Gayle McDowell gives a presentation 'Cracking the Coding Interview'.

Three years ago, when I was looking for a job after 10 years of working at one company, I really wished there were consultants to help software developers to improve their resumes and prepare for technical interviews. How enormously helpful it would be if someone who was a developer once to guide your preparation! Especially if such a person collected many years' and many companies' worth of technical interview questions.

Such a company now exists, and its founder, former Google engineer Gayle McDowell, visited Austin last year to promote her book "Cracking the Coding Interview". In her presentation, based on the book, she advised software developers what to expect at, and how to prepare for technical interviews. I found myself agreeing with Gayle half of the time, and scratching my head the other half. If my experience did not match her recommendations, the reason may have been that her advice was directed to (a) mostly beginner programmers, and (b) those who want to work at big companies. No wonder her presentation was paired with a hiring pitch by Amazon Web Services.

Let us see, then, how my experience of interviewing for software development jobs stacks up to Gayle McDowell's advice.

What happens when "they" pull your resume out of a giant pile

Gayle's version

  1. Pull resume out of giant stack;
  2. Spot-check: company names, positions, projects, schools;
  3. Skim bullets to see if you've written real code.

My experience

I haven't been on the recruiting side of things, but I was hoping that that's how it is -- that a real hiring manager (i.e. someone who knows what to look for in a developer), would look for that, as opposed to for buzzwords from an HR bingo.

Resume length

Gayle's recommendation:

Your resume should be 1 page only, unless you have more than 10 years of experience. In a 2-page resume, no one will read all the points; they might read 50% at most. The hiring manager will skim your resume and notice only some random job experience points. Some of them won't be your strongest. Wouldn't you want a hiring manager to notice only your strongest experience? If so, cull them and put them on a 1-page resume.

My experience:

I had many seasoned recruiters tell me that my resume needs to be 2 pages. But then, I have more than 10 years of work experience.

Technical questions

Gayle McDowell recomended her company's website, CareerCup.com, for a good list of real interview questions. I checked it and the questions are really good -- they don't test your knowledge of a programming language syntax, but rather test your ability to design, as well as deep understanding of object-orienting programming.

"Don't memorize!"

Gayle's recommendation:

If an interviewer asked you a question you've already heard before in a different interview, don't just spit it out the answer -- tell them first that you've heard it. It's likely that the interviewer will still ask you to answer the question / solve the problem, but you won't come across as dishonest. Plus, they don't want just to hear you spit out the answer -- they want to know your thought process. Seeing that you've memorized some answer tells them nothing about you -- the question was wasted. It didn't give them any extra information about you.

My experience:

Perhaps this is reasonable for college students, but if I am an experienced programmer, I might have faced certain types of problems in my programming practice often enough that I know the answer off the top of my head. Such is the question mentioned later in this text, where the answer turns out to be binary search tree. What if at some of my previous jobs I searched for data in large lists? Then I could spit out the answer "BST" before I even heard the end of the question, and it's not because I heard it in another interview, or memorized the answer off of some online preparation site -- it's because I know it from practice.

Push yourself

Gayle's advice:

  • When studying a code problem, write the solution from the beginning to end. Don't just stop because you think you understand it. When faced with a whiteboard at an interview, you may discover you don't understand it nearly as well as you thought.
  • Write the code with pen on paper -- it's harder than in an IDE, where intellisense helps you. But you won't have IDE and intellisense on a whiteboard.
  • Using pseudocode is OK temporarily, as long as you tell the interviewer you will fill it out with actual code later, and actually do so.

My experience:

Agree completely. To make sure you completely understand a problem, you need to write it on a piece on paper from beginning to end. Otherwise it's easy to stumble when solving it on the whiteboard. You are used to the IDE doing so much for you, that when you are faced with a blank sheet of paper, you might start thinking, do you need a keyword "function" to declare a function in C#? Or was that PHP?

I use lots of pseudocode when writing code on a piece of paper, and I think if the pseudocode is detailed enough, most interviewers would be fine with that. No one necessarily expects you to remember all the 50+ methods of the generic List<> class when you're coding on the whiteboard.

Data structures

Gayle's recommendation:

You have to know how to implement, or when to use, the basic data structures: linked lists, stacks, queues, trees, tries, graphs, vectors, heaps, hashtables. Especially hashtables -- they come up often in interviews.

My experience:

I agree about the importance of hashtables. Many code problems I've been given in interviews required use of a hashtable for best solution. Linked lists were the second most popular data structure -- for example, I was asked to write code to reverse a linked list. There was a time when I was asked to write a program for searching a binary tree. But I was never asked about a stack, queue, trie (whatever that is?), graph, or heap. (As for vectors, they are essentially arrays, and they are used in every coding problem -- you can't write almost any code without it.)

Algorithm Questions

Gayle's advice:

Study the basics: complex algorithms usually unnecessary.

My experience:

I agree: I have never been given a problem that required more than a simple algorithm. Well, at one point I was shown the code for merge-sort, and asked what was the complexity of that code (it's O(n log n)), and the interviewer asked me which lines of the code contained the log n part. That was the most complex algorithm I had to deal with at an interview, and even then I didn't have to write code for it, only analyze it.

Decomposing algorithm problems

Gayle's advice:

To make the problem easier to solve, decompose it in 4 steps:
  • Pattern Matching
  • Simplicity and Generalization
  • Base Case and Build
  • Data Structure Brainstorm

My experience:

Overall I agree, however, I think we think about decomposition differently.

Example of decomposition

Design an algorithm to print subsets of a set: {a, b, c} -> {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

Gayle's decomposition:

You start with empty set:

S({}) -> {}

Find a solution for a one-element set

S({a}) -> {}, {a}

For a two-element set, the solution is still obvious:

S({a, b}) -> {}, {a}, {b}, {a, b}

S({a, b, c}) -> ?

You'll notice that there is a pattern: build S(n) -- a subset for an n-element set -- by cloning S(n-1) and adding n to the cloned sets.

My comment:

This is an example of a problem that can be solved inductively, but there are many problems where induction wouldn't help. Such is, for example, a problem that I was asked at a past interview -- determine if two words are anagrams of one another. It's easy, yes, it's just not inductive. Probably because we are not required to find all anagrams of each word (in which case it would be closely related to the subset problem), only to determine whether one word can be an anagram of the other, i.e. if both words have the exact same set of letters. You don't gain knowledge on how to do it for a 3-letter word if you know how to do it for a 2-letter word, because it's an exact same problem.

Pattern matching as a step decomposing algorithm questions

Reverse the order of words in a sentence

Write code to reverse the order of words in a sentence, e.g. "dogs are cute" to "cute are dogs".

Gayle's way:

This problem is similar to reversing the characters in a string: "dogs are cute" -> "etuc era sgod".

The answer: reverse full string, then reverse each word.

My comment:

This solution sounds straight from a joke about mathematicians. How does a mathematician make tea? He/She pours water into a kettle, puts the kettle on the stove, turns on the stove, waits until the water boils, then ours the boiling water over the tea leaves. Now suppose the kettle is already boiling. How do you make the tea then? Mathematicians's answer: turn off the stove, dump the water, and now you've reduced this problem to the one you already know how to solve.

I think a simpler way to reverse the word order in the string would be to split the string at spaces, put the resulting words in an array of strings, and reverse that array (many programming languages have built-in functions to reverse arrays. The ones that don't, like C, don't have functions to reverse strings either).

A ransom note from a magazine

Design algorithm to figure out if you can build a ransom note (array of strings) from a magazine (array of strings)

Gayle's way:

What if we used characters instead of strings, and built an array of character frequencies? And generalized to word frequencies?

My comment:

The suggested approach doesn't seem to simplify much. I don't think it's essentially simpler to do that than to build an array of word frequencies. The key to it in any case is hashtable. Familiarity with the hashtable data structure is pretty much the only thing you need to know to keep track of how many times each word occurs, and therefore if there are enough words to put together the note you want.

Unconventional, but intuitive advice

Gayle McDowell gives a presentation 'Cracking the Coding Interview'.

Some of Gayle's general interviewing advice was not what career advisors typically give, but consistent with my experience. Such as: there is no need to write thank-you cards, because no candidate for an engineering position was ever rejected for not writing a thank-you card. People make a decision whether to hire you pretty soon after the interview - perhaps within a day or so -- and that's much sooner than your thank-you card could reach them. From over a hundred of candidates that she had interviewed at Google, she got only 1 thank-you card, and it did not sway her decision towards that person in any way.

Finally, do not despair if you think you did poorly. Gayle says that you really, truly can't know how well or poorly you did. Seriously, you think you do, but you don't. Candidates are evaluated on the scale of comparison with other candidates, so sometimes you might think you did really poorly, but in the interviewer's eyes you were the best candidate interviewed for this position.