APPENDIX
C
Sample Phone Screen Transcript
[Dial number: 1-800-DRUIDIA1]
Patrick: Hello, this is Patrick calling from ExampleCompany for Roxanne.
Roxanne: Yes, this is Roxanne. Pleased to meet you!
Comment Make sure you’re talking to the right person.
Patrick: Wonderful. You were expecting my call today?
Roxanne: Yes, at this time.
Patrick: I am a software development manager at ExampleCompany and I’m calling to do a technical phone screen for a software development engineer position. Is that what you were expecting?
Roxanne: Yes, that and the Spanish Inquisition. You never know.
Comment This introduces you and sets up the context for the call. If you get a “no” in response, find out what you can, apologize for the confusion, and get off the phone. Then tell someone about the problem.
Patrick: Let me start by telling you something about ExampleCompany. We rock. We’re hiring a bunch of rocket scientist software engineers so we rock harder. We’re building out and building up!
Roxanne: Yes, that’s what I expected.
Patrick: Great. This is going to take up to forty-five minutes. Still a good time to talk? We can reschedule if it’s not.
Roxanne: Sure, I have this time set aside, I can go up to an hour today.
Comment Candidates sometimes complain later that they were under some sort of duress—worrying about a personal or work issue, ill, or something like that. This may be a legitimate concern, but they should also feel free to ask for a reschedule. I would rather reschedule a few times than misread a candidate. It’s hard enough to evaluate them as it is, and candidates will appreciate the flexibility.
Patrick: Okay! So here’s how we’ll do this. I’m going to ask you several technical questions to gauge your overall proficiency, including a couple of coding problems, and spend a few minutes answering any general questions you have toward the end. Ready?
Roxanne: I was born ready.
Patrick: You won’t need to use a computer or access the Internet for this interview. Do you have something to write with?
Roxanne: I shall improvise with this 1975 lead “goblin archer” figurine and some fast-food receipts.
Comment They may need to find something to write with. Now they know they are going to need to write something.
Patrick: Good. We’ll start with a coding question. There’s no set way to do this and no strict time limit; you can listen to the question, do it quietly and tell me the answer, or talk out loud as you go, whatever you’re comfortable with. Also, don’t hesitate to ask for clarification or help. None of my questions are meant to be tricks. What I’m looking to get, at the end, is for you to read me essentially working code.
Comment Coding on the phone is unnatural enough. This preface seems to disarm most of the nervousness candidates bring in to the interview.
Patrick: Write a method in C, C++, C#, or Java that takes four separate integer parameters and returns the value of the largest one.
Comment This is the Trivial Coding Question. Its purpose is to warm up good candidates and weed out bad ones. Yes, not everyone with ten years of development experience can solve this. Yes, I know that’s really sad.
Roxanne: That’s not so difficult. I’ll assume you pass the integers in as an array.
Comment Candidates make this assumption all the time, no matter how clearly you pronounce “separate integer parameters.” Chalk it up to phone entropy.
[Two minutes pass]
Alright, here’s my solution.
public int max(int ints[]]
{
int max = −1;
foreach(int i in ints)
if (i > max)
i = max;
return max;
}
Comment There are several ways to write the function correctly. Here’s how to evaluate the answer you get: it must work. It must not use collections. It must not use an array. It’s no problem if the candidate reaches for an ArrayList or something, throws in the parameters, calls .Sort() and returns the last one. Just say, “That works, but pretend you don’t have access to collections,” and make them solve it like civilized people.
If the candidate does not solve this problem in less than six minutes, get off the phone. Say something like this: “This position is going to require substantial fluency with coding. At this point I don’t think you have that fluency, so I’m going to save us some time and end our conversation here. I have enjoyed speaking with you, however, and very much appreciate your time.” Then draw a big X through the résumé.
Patrick: I believe I see a problem in your code. Would you find and fix it for me?
[In a moment]
Roxanne: Yes, sorry, my assignment statement had i and max reversed.
Patrick: All right, that’s logically correct. There is a small problem, though. I expect to pass the integer arguments in as separate parameters, not in an array.
Roxanne: Okay. Then what I’ll do is create an array up front, ints, and populate the array with the parameters.
Patrick: Yes, that will work. However, it does just sort of patch the original solution rather than rethink it, and there’s a fair amount of unnecessary work going on. Can you refactor this method for efficiency?
[One minute passes]
Roxanne: Very well. I don’t know if this is the most efficient possible solution, but it’s straightforward.
public int max(int a, int b, int c, int d)
{
int max = a;
if (b > max)
max = b;
if (c > max)
max = c;
if (d > max)
max = d;
return max;
}
Patrick: Sounds good. Okay, let’s move to a slightly more complex coding problem. I’d like you to write a method that computes a discrete Fourier transform over an arbitrary sequence.
Roxanne: What??
Patrick: Just kidding. Write a method that finds the maximum depth of a binary tree, given a root node. The signature is int getDepth(Node node) where Node is a data structure that contains a Node left and a Node right, either or both of which could be null. If this is not a perfectly straightforward question, I am happy to clarify and explain what I mean.
Comment This is the Moderate Difficulty question. Its purpose is to test the candidate’s ability to reason with data structures and build algorithms using recursion. You can solve this with iteration. If the candidate gives you an iterative solution in less than ten minutes, call me!
Roxanne: Is this a binary search tree? Is it balanced?
Patrick: Maybe and maybe.
Roxanne: Can I assume the existence of a massless elephant?
Patrick: If it helps you solve the problem.
Roxanne: I’ve always wanted to assume that. Tree problems often lend themselves to recursion, so I’ll look at that first. Let’s see . . . each node only knows that it exists, that it has children, and whatever its children tell it. If we start with the opening method signature, then the children report the maximal depth at their own level. Hmm. I’m going to draw a tree to help me think.
Comment In reality this question frequently trips up candidates, particularly very senior ones, who haven’t thought about trees in a long time. They may spend a little more time on this problem, but they still need to solve it. If the candidate doesn’t make progress, offer a couple of hints such as these:
Suggest drawing an example tree.
Suggest a recursive approach.
Suggest looking at the stopping condition of the recursion: what the last function will return.
Suggest not using a static variable. It’s really not needed and it’s just tripping you up.
[Time passes]
Roxanne: I have a working approach. A method is called with the root node. If there is no root node, there is no tree, it has no depth, and it returns 0. If the root node has no children, its depth is 1 and it returns that. However, if it has children, what we care about is the maximal depth—whichever child reports greater depth. The node then includes itself and passes that maximum value + 1 upwards. Here, let me express it in code.
public int depth(Node node)
{
if (node == null)
Return 0;
Return max(depth(node.left), depth(node.right)) + 1;
}
Comment Usually candidates give a messier answer, with temporary variables and what not. Sometimes a candidate will make a helper function that takes a second parameter such as “int maxlevel.” It’s possible to make that work.
Here’s how to evaluate their answer: it must work.
Patrick: Okay, I think that algorithm will work. I’d like you to reason about the time and space complexity of your algorithm. Let’s start with time complexity, in Big O notation.
Roxanne: Well, it’s clearly in the complexity class “quasi-polynomial time,” at O(log 2 n).
Comment This question is used to probe the candidate’s understanding of the algorithm they just used as well as the ability to reason about the efficiency of the code they write.
Sometimes candidates already know the answer to the maxDepth question (or any other question you just asked), and this follow-up question sometimes reveals that prior knowledge; a total failure to answer means their answer to the previous question is, unfortunately, useless.
Patrick: What??
Roxanne: Just kidding. We need to examine each node of the tree exactly once; so we’re going to run in O(n) time.
Comment A common failure path is to say it’s O(log n) time. This is because they are stuck thinking of a binary tree as a binary search tree even though you just told them it isn’t. It’s okay. Take a deep breath. Your brain malfunctions under stress, too. Ask them to explain why and you will have the opportunity to correct that assumption.
Patrick: That sounds like good reasoning. How about space complexity? It’s not a common concept, shall I elaborate?
Roxanne: Lay on, MacDuff.2
Comment This tests the candidate’s application of familiar concepts in novel situations. She will also need to understand stack and memory allocation, of course.
Patrick: I shall. Space complexity is like time complexity. With time, we want to know about the worst-case scenario of time consumed by the algorithm in relation to the size of the input n. With space, we want to know the worst-case scenario of space consumed (maximally, at any time) by the algorithm in relation to input size n.
Roxanne: Um . . . we only allocate space during our recursion, so what we really need to understand is how deep our recursion can get based on the size of the tree. A tree can degenerate to one node per level, so, in the worst case, we recurse n times. Space complexity is O(n) just like time.
Also, I’m going to go ahead and take the opportunity to word-drop “tail recursion” because it makes me sound sophisticated.
Patrick: You are correct, sir.
Roxanne: Madam.
Patrick: Er, sorry.
Roxanne: No problem. Please go on.
Comment Politeness goes a long way. There’s a power imbalance between interviewer and interviewee; there is no need to further exaggerate the effect on the interview.
Patrick: So what is tail recursion?
Roxanne: I’m sorry, it’s actually beyond my experience. Something to do with not accumulating stack frames for some kinds of recursions, in languages that support it.
Patrick: I see. It’s time to ask you a design question. Please design the API for a spell checker. It will be a shared component for two products, including a word processor and a spreadsheet program. As much fun as it is to design the implementation for a spell checker, what I need from you is just an API. The engineers who will use it expect an object-oriented interface, so in the end what I need from you is the classes and methods that you’ll present to them.
Roxanne: Let me make sure I understand. This is a spell checker that will be a library or part of a library that both products will include—it’s not a service? And should I assume a particular language for the API, or IDL, or . . . ?
Patrick: Pick an object-oriented language you’re familiar with, as you did with the previous questions. Yes, assume a statically linked component, or the equivalent for the language.
Roxanne: Huh. Well, let me think about spell checkers I have known and loved. . . . They have come a long way. These days they tend to detect errors immediately, automatically correct common mistakes, and suggest corrections when it’s not totally obvious what word is meant. And, speaking of meaning, sometimes they worry about grammar, too. Which of these are in scope for this spell checker?
Patrick: Glad you asked. You’ve probably noticed that there’s a distinct shortage of grammar checking in the world, but for this question, consider both suggestions and grammar out of scope.
Roxanne: Right. Let me draw on my paper for a minute.
[Time passes]
Roxanne: Wait, you said there were two different products using this API. Do they have different requirements? Different usage patterns?
Patrick: They certainly do! The spreadsheet team expects to have lots of small nonwords, like you find on Twitter, and the word processing team wants to check large documents at load time, say 50,000 words at once. Both of them do want to check for errors “as they go.”
Roxanne: Ah, interesting. And now that I think about it, there’s more than one language. I’m going to assume that the callers will want to specify which language to check against. Stop me if I’m wrong about that. So, here’s my preliminary sketch of a design. Callers send in either one or many words and the library says yes or no to all of them. There should be a batch interface to support many words without round-trip method calls. I’ll keep it really simple and make it just as complex as I need.
Class Spellcheck
{
Spellcheck(Language l);
Bool checkword(String word);
Bool[] checkwords(String[] words);
}
The single word check is obvious, but let me explain the batch interface. First, the caller has to decide what words to send. Who knows what internal representation they use for their documents? So I’m going to ask for a string, which is a simple, baseline data structure to represent each word. The service returns an array of yes/no Boolean answers for each word: yes, it’s spelled correctly; or no, it’s not. As an aside, I’ll go philosophical—or call it linguistic—and say that the spell checker doesn’t really check spelling. It doesn’t even know if you’re giving it words or just garbage characters. It just checks to see whether it recognizes the string as one in a dictionary specific to the language.
Patrick: A sensible distinction, though the caller probably doesn’t care about that. You mentioned a dictionary but not how that’s related, and you referenced a class or structure called “Language.” Tell me more about those.
Roxanne: I guess I really mean “culture” more than language, because that’s not specific enough. What counts as a word depends on where you live and who you talk to, right? So that should be a “culture” object passed into the constructor, and I’m going to lean on a standard native library to provide that infrastructure rather than creating my own. I don’t want callers to have to worry about making or loading dictionaries, so I’ll make that an implementation detail internal to the library.
Patrick: Some library users might care. One other question about this: Do you expect callers to keep one of these Spellcheck objects “on file,” or build new ones when they need to check words?
Roxanne: On file. It could take time to load dictionaries, and this is an implementation detail, but I’d want to cache results so it was more efficient over time for callers like word processors. It would work either way, but keeping one around would work better for callers. I’m not sure how I could indicate that in my API, though.
Patrick: Perhaps through a factory pattern of some sort. Anyway, those were all the questions I had for you today, so thanks for putting up with the barrage. Do you have any questions about the job, the company, the team, me, the weather? I’ll answer whatever we have time for and that is not actually confidential.
Comment Never write a check . . .
Roxanne: Why is it so cold?
Patrick: Arctic air from the central continent is entering the region through the Columbia River Valley and the Fraser Gap.
Comment . . . that you can’t cash.
Roxanne: Why should I work for your company? Google and other great employers are hiring!
Patrick: We have substantial engineering challenges, solid funding, brilliant coworkers, and free ice cream.
Comment If you have time, gush! If the candidate throws you a doozy (“what do you like least about your job?”) then improvise but be honest. People know when you’re not. Especially your mom. You may want to call her up and apologize.
Patrick: I enjoyed our conversation today! I know your time is not free, so thank you for spending some of it with us. I’ll share my notes with our recruiters and you should expect to hear back from us shortly. I hope you have a great rest of your day!
Roxanne: All righty!
Comment End the call on a positive note even if—especially if—it did not go well. The candidate is a customer, a fellow professional, and a human being. Be even more awesome than you would hope for if you were on the other end.
Your goal: The candidate hangs up smiling and feeling good about you and about us. Even if we don’t move forward, the candidate refers her friends.
Sample Feedback for This Interview
Coding mixed. The candidate stumbled through the warm-up method. Didn’t ask for clarification and had trivial initial bug. Patched it inefficiently rather than refactoring it. When prompted, she refactored quickly and effectively; the final solution was fine. Produced an elegant solution to the more complex method pretty quickly. Perhaps she anticipated the question beforehand and studied it explicitly?
The design was average to above average. Thought through the requirements, produced a simple solution that met major needs. The answer she gave was in the uppermost quartile.
[Copies of the candidate’s code included in the feedback.]
1Spaceballs (dir. Mel Brooks; MGM, 1987), act I, ccene iv.
2 Hamlet, act V, scene viii.