The
Pragmatic Bookshelf
PragPub The Second Iteration
IN THIS ISSUE
* Jay Wengrow on how to conduct an algorithms interview
Issue #98 August 2017
PragPub • August 2017
Contents FEATURES
How to Conduct an Algorithms Interview
..................................................... 2
by Jay Wengrow Jay authored a book on algorithms but he’d fail many algorithm-based whiteboard interviews. Because they’re bad. Here’s how to fix them.
DEPARTMENTS
From the Editor
........................................................................................................ 1
by Michael Swaine About this free article.
Except where otherwise indicated, entire contents copyright © 2017 The Pragmatic Programmers. You may not sell this magazine or its content, nor extract and use more than a paragraph of content in some other publication without our permission. Published monthly in PDF, mobi, and epub formats by The Pragmatic Programmers, LLC, Dallas, TX, and Raleigh, NC. E-Mail
[email protected]. The editor is Michael Swaine (
[email protected]). Visit us at http://pragprog.com for the lowdown on our books, screencasts, training, forums, and more. ISSN: 1948-3562
—i—
From the Editor by Michael Swaine
About this free article.
Most people tasked with hiring programmers would probably agree that asking an interviewee to write a Quicksort on the whiteboard while you watch is dumb. And most would also agree that the ability to understand algorithms is something you want to test for. Is there a better way to do algorithms interviews than the way we’ve been doing it? Jay Wengrow thinks there is, and shares it with us this month. Feel free to share this article with your friends. If you’d like to read the whole July issue of PragPub or to subscribe, you can do that here [U1].
PragPub
August 2017
1
How to Conduct an Algorithms Interview A Template for Success by Jay Wengrow
Jay authored a book on algorithms but he’d fail many algorithm-based whiteboard interviews. Because they’re bad. Here’s how to fix them.
By the time you read this article, my book A Common-Sense Guide To Data Structures and Algorithms [U1] will either be in print or be going to print shortly. While the book aims to demonstrate the power these concepts can provide in everyday programming, I suspect that a fair percentage of people who buy the book will do so to help prepare for technical programming interviews. (I even list that as one of the book’s benefits in the introduction.) Yet, there’s an irony here that simply cannot be ignored: I just authored a book on algorithms, yet I’m certain I’d fail plenty of whiteboarding and algorithm-based interviews. How can this be? If someone understands data structures and algorithms, how could such a person fail an interview that quizzes that person on these topics? This reveals the big flaw with our interviewing system: There is not one, but two distinct skillsets at play here. The first skillset is the ability to reason about algorithms. The second skillset is the ability to succeed at an algorithm interview. And while these two skillsets may have a little overlap, they are actually very different skillsets. The ability to reason about algorithms is the ability to understand an algorithm’s efficiency in terms of time and space — that is, how fast does it run and how much memory does it consume. The ability to succeed at algorithm interviews, however, involves many other things, including prior knowledge of certain algorithms and data structures that may have no practical application other than on technical interviews. I recently showed someone the various books on the market that have titles along the lines of, “How To Succeed At Programming Interviews,” and his response was on the mark. He said, “Shouldn’t the book be called, ‘How To Program?’ From the fact that there are specific books on how to succeed at programming interviews, that clearly reveals that interviewing to become a programmer has little correlation to what programmers actually do.” There’s been a lot of debate on this topic over the years. Proponents of algorithm-based interviews believe that such interviews can reveal much about the candidate’s thought process, as well as reveal their aptitude for writing efficient code. I can appreciate that, but I believe that such an interview has to be conducted correctly to properly achieve those results. I think many people understand the problems with the current system, but we’ve kept the status quo simply because no one has proposed an alternative solution. I’d like to begin that conversation here.
PragPub
August 2017
2
If we put thought into it, we can develop interviewing templates that are both fair and effective — including algorithm-based interviewing templates. To do so, let’s begin by analyzing what doesn’t work. The first flaw in our current process is that many algorithm-based interviews assume that the candidate is armed with knowledge of all sorts of algorithm trivia — the kind of knowledge that is hardly (if ever) used in real-life programming. If you search the web for popular programming interview questions, you’ll come across gems like these: “What is the time-complexity of Heapsort?” “What are the Dijkstra and Prim algorithms, and how are they implemented? How does the Fibonacci heap relate to them?” “Find the Kth smallest element in an unsorted array.” Questions like these demand ready knowledge of HeapSort, Dijkstra’s, Prim’s, and Quickselect algorithms, all of which will not ever be implemented by the vast majority of programmers. I propose that our new interviewing template omits trivia questions like these. So this brings us to Rule #1: No trivia. Our questions should not require knowledge of any data structure or algorithm that isn’t one that the candidate would have used on an everyday basis. So, a question about an array is fair, but a question about a Red-Black tree is not. You can ask about loops and recursion, but mergesort should be off limits. (Yes, mergesort is a “classic” sort, and even used by computer languages under the hood. But has the interviewer ever implemented mergesort for a real project? Exactly.) Another pitfall with algorithm-based interviews is the fact that they test the candidate on just one particular skill. This is not inherently a problem, but it can become a problem if you view their ability to optimize code as a proxy for their general abilities as a programmer. Being a programmer is a lot more than the ability to develop algorithms on the spot, so even if you do want to test for that skill, it’s critical to include such a test as part of a larger interviewing framework that tests for all the skills that a good programmer needs. For example, if a developer can create brilliant algorithms but cannot write readable code, they still may not be effective at their job. This gives us Rule #2: Don’t judge a candidate solely based on an algorithm interview. This isn’t the place for developing a complete interview process, but recognize that an algorithms interview is just one piece of a larger interview. I think one of the strangest aspects of algorithm-based interviewing is that the interviewer is often staring at the candidate while the candidate is thinking and writing code. This creates artificial pressure that doesn’t resemble any real workplace pressure. Put simply: It’s hard to think when someone is staring at you! So I’d like to propose Rule #3: Don’t stare at the candidate as they’re working through the problem. If you’ll complain that the whole point of the algorithm-based interview is that you can use it see the candidate’s thought process, let me propose a better way: Have them work through the initial problem on their own, and once they’re ready, they can explain their solution PragPub
August 2017
3
to you. If you want them to optimize it further, give them space again and let them do it on their own. When they’re ready to present their optimization, you can join them again, and by their explaining it to you, you’ll gain insight into their thought process. To recap, we have three rules of algorithm-based interviewing: •
Rule #1: No trivia.
•
Rule #2: Don’t judge a candidate solely based on an algorithm interview.
•
Rule #3: Don’t stare at the candidate as they’re working through the problem.
The truth is that these three rules boil down to one Golden Rule: The interview should test the candidate on their ability to do the job they’re interviewing for. Anything extraneous to that should be eliminated from the interview. We’ve talked quite a bit about what not to do. Now, let’s walk through an example of what may — under certain circumstances — be an effective algorithms interview. Let’s say that we’re interviewing a candidate — Jesse — for a role as a Senior Developer who will be working on the server-side code for one of our large web apps that gets a lot of traffic. For this role, we can make the case that a Senior Developer needs to be aware of the impact that various algorithms can have on the efficiency of the code that powers the website. In this situation, inefficient code or even a single slow database query can truly bring the website down, so we’d want our Senior Developer to be very cognizant of the effects of the algorithmic choices they make. Now, we don’t need the Senior Developer to know famous algorithms, but we do want them to be able to analyze the efficiency of the algorithms that they themselves develop. So, we might begin with this question: “Write a function that checks whether an unsorted array of numbers contains any duplicate values.” After making sure that Jesse understands our question, we’d leave the room to give space and privacy so that Jesse can properly concentrate on the problem. Let’s say we return, and Jesse provided this solution: function hasDuplicateValue(array) { for(var i = 0; i < array.length; i++) { for(var j = 0; j < array.length; j++) { if(i !== j && array[i] == array[j]) { return true; } } return false; }
We’d then ask Jesse to describe the efficiency of that solution. Jesse may say, “Well, we’ve got a nested loop going on here. That is, for each element of the array, we check all the elements again. So, that’s O(n^2).” “Great!” we’d say. “I’d like to give you some time to see if you can develop a faster solution.”
PragPub
August 2017
4
After giving Jesse the time and space to develop another solution, we may return and see this: function hasDuplicateValue(array) { var existingNumbers = []; for(var i = 0; i < array.length; i++) { if(existingNumbers[array[i]] === undefined) { existingNumbers[array[i]] = 1; } else { return true; } } return false; }
“Excellent!” we’d say. “What is the efficiency of this new algorithm?” “Well,” Jesse replies, “we are now just iterating over the array just once, and using another array to keep track of whether we’d encountered that number before. So it’s O(n).” “Are there any disadvantages of this second algorithm over the first algorithm you developed?” Jesse replies, “The first algorithm didn’t need to take up any auxiliary space, so its space complexity is just O(1), but the second algorithm uses a new array to keep track of data, so has a space complexity of O(n).” “And what if we changed the problem so that the initial array could contain strings instead of just numbers? We wouldn’t be able to use the array’s index anymore. Can you develop another algorithm that has a time complexity of O(n)?” After giving Jesse more time, we’d return to find this: function hasDuplicateValue(array) { var existingValues = {}; for(var i = 0; i < array.length; i++) { if(existingValues[array[i]] === undefined) { existingValues[array[i]] = 1; } else { return true; } } return false; }
Jesse explains, “I’m now using a hash table to keep track of which values we’ve encountered previously, since the hash keys can be strings. We can now handle all sorts of keys, while keeping the time down to O(n), although the hash table does take up O(n) space.” Such an interview can be effective, because we can see that Jesse has a solid grasp on understanding the effects that various algorithms have. Note that we didn’t require Jesse to develop brilliant algorithms in record time, and we didn’t require Jesse to have prior knowledge of brilliant algorithms discovered by famous computer scientists from the 1970’s. But we didn’t need to. We have enough data here to know that Jesse can identify the advantages and disadvantages of competing algorithms.
PragPub
August 2017
5
So here’s one potential interviewing template for testing the candidate on algorithms: •
Step #1: Ask the candidate to develop an algorithm for a problem that can be solved with more than one solution. None of the solutions should require prior knowledge of particular algorithms. Give the candidate the space to solve the problem.
•
Step #2: Ask the candidate to analyze the efficiency of their approach.
•
Step #3: Ask the candidate to develop an alternative solution for the same problem, or propose another solution yourself.
•
Step #4: Ask the candidate to compare the advantages and disadvantages of the two solutions.
This is certainly not the only interviewing template that one could use, but this conversation is an attempt to get us to begin developing effective templates that truly test a candidate for the job they’re being hired for. Let’s stop doing the status quo just because it’s the status quo, and make it so that no more books on preparing for programming interviews need to be written. About the Author Jay Wengrow is the founder and CEO of Actualize [U2], and the author of A Common-Sense Guide to Data Structures and Algorithms [U3].
External resources referenced in this article: [U1]
https://pragprog.com/book/jwdsal/a-common-sense-guide-to-data-structures-and-algorithms
[U2]
http://actualize.co/
[U3]
https://pragprog.com/book/jwdsal/a-common-sense-guide-to-data-structures-and-algorithms
PragPub
August 2017
6