The Technical Interview - Programming Problems in Java: A Primer for The Technical Interview (2014)

Programming Problems in Java: A Primer for The Technical Interview (2014)

Chapter 1. The Technical Interview

For both sides of an interview there is an art. The art is at its best when, at the end of an hour, both parties leave the interview feeling they have spent a productive hour. For the interviewer, it is asking a challenging but tractable question and working with the candidate to find an optimal solution. It is making the candidate feel welcome, valued, and excited to be offered an opportunity to work alongside others who have a passion for technology. And it is being comfortable in the decision to give the candidate a hire or no hire decision.

But of course the candidate has a more complicated role. Even so it is simple to state what must be done; one must be friendly, be straightforward, and know your fundamentals. There is not much else you can do to prepare for an interview.

The main purpose of this book is to provide a refresher for the fundamentals of programming that come up in technical interviews. We do this by presenting interview questions that have been asked in the field, and answering them in as much completeness as will be required by any technical interview. We strive to provide a number of solutions to each question, in order that the reader can understand the difference between a bad and good solution.

1.1 An overview

There is no secret recipe to acing an interview or solving a programming problem. And even if you know your foundations, in the course of a tech career everyone will come across that interviewer who is annoyed at having to interview, suffering from an inferiority complex, or just plain determined to give you a no hire. But there are a number of things you can do to increase your odds of getting a hire.

First, know what you are getting into. If you have never interviewed before, then the section on the technical interview loop is the place to familiarize yourself with what will be happening.

Second, turn the interview into a conversation. Take turns speaking, ask real questions, and overall be honest. Honesty will make the discussion easier and more enjoyable for both sides. Of course in any technical interview you will be required to present a solution to a coding question, but that will only be about half the time. You can gauge your success by how long the interviewer allows the conversation to run over.

Third, approach the technical question systematically and answer it completely. And, this is very important, do it right the first time.

1.2 The process

In tech, the fundamental unit of hiring is the technical interview. In general, the technical interview is a 45-minute to one hour one-on-one session in which an interviewer asks a candidate to solve one or more programming questions

While screenings and introductions may be handled by human resource personnel, software engineers always conduct technical interviews. These engineers may be individual contributors or managers, but they are always active in the field and are active on a project. Interviewing is not a specialty of software engineering, so most of the interviewers any candidate will see are volunteers from different groups or areas within a company. The exception is the hiring manager, if the loop has one. While they are all volunteers, these interviewers are trained to respect hiring law and avoid certain questions that the company has found useless or harmful. But beyond those small exceptions, all have the freedom to ask any technical question they desire.

Every interviewer has a set of technical questions they prefer. These have been gathered from his or her past interviews, come from current or past project, or has been cultivated by lunchroom discussions with fellow employees. The last part is important to the process. While generally there is a central organization training interviewers, every company has an interview culture where questions are shared and analyzed in an open discussion. And this culture does well to keep the questions in check more than any centralized training.

The point of the technical interview is for the interviewer to gather as much signal from the candidate as possible in order to answer the question “Does this candidate meet the bar.” The bar refers to the standard for hiring of the company. Every company has a similar standard with minor variations. They answer the question in relation to the company, the group, or the individual. For Google, they are looking for someone who is at least as good as the average Googler. For Microsoft, they are looking for someone who is smart and at least as good as the average person in the product group. For Facebook, they are looking for someone who is better than the interviewer. Even so, each interviewer’s standards vary as well. But the bottom line is that a candidate will pass the bar if the interviewer wants to work with the candidate. Passing the bar is met with a decision of hire, and the decision of no hire is given otherwise.

Technical interviews have a progression. At one end is the initial screening. The initial screen is done on the phone, video chat, and only rarely in person. The initial screening is always a series of simple, straightforward questions. The programming component may include questions such as writingatoi, binary search, or reversing a linked list. The purpose of the initial screening is to try to not waste employees’ time if the candidate is clearly below the bar. There are three things the interviewer is looking for in the initial screening: can the candidate write a simple program, can the candidate communicate effectively, and is the candidate being slotted for the right job. The last question is usually one of technical versus managerial or back-end versus front-end specialties.

After the initial screen is the on-site loop. The interview loop is a series of four or more technical interviews with the goal to see if a consensus on hiring can be made. The loop is conducted onsite, either at a company’s main campus or remote interviewing session. This daylong gauntlet is generally the final hurdle to a hire or no hire decision by the company.

The loop is designed to ask a sequence of moderately difficult questions to measure a candidate’s competency, creativity, and cultural fit. A normal mix of questions involves two programming questions, a design question, and an algorithms question. Programming questions are the heart of the technical interview, and a candidate will generally see more of these than less.

The implementation of the loop differs only slightly from company to company.

At Microsoft, interviewers shuffle a candidate between their offices. During this transition they will share initial feedback immediately in order to shift focus during the day. For instance if a candidate has shown great mastery in algorithms, an interviewer may suggest focusing on design. If a candidate fumbles a question in design, an interviewer may suggest that a follow-up is made.

The process is different at Google and new companies. Since these companies do not provide their employees offices, a candidate is assigned to a meeting room and interviewers come to him or her throughout the day. Also at Google and new companies, interviewers have little to no contact with each other throughout the entire process other than to avoid question duplication. At Google, questions are written down on a sheet of paper that is shuffled between interviewers. While this may give the candidate a feeling of disjointed disorganization, it is done to attempt to eliminate bias from other interviewers’ decisions.

At the end of the technical interview, feedback is collated into a hiring packet and a decision is made. At Microsoft, the hiring manager often makes the decision the same day and a candidate can expect a phone call with an offer within a week. At Google and Facebook, the feedback is made by a local hiring committee and forwarded to a final hiring committee. The committee is a sanity check on the interviewer’s consensus aimed at maintaining a high hiring bar. The cost of this process is that it may be many weeks after the loop before a candidate gets an offer or no hire decision.

Keep in mind that a single no hire during a loop is usually not enough to stop the process. However, a sequence of no hires and very weak hires, or a continued failure to answer basic questions definitely is enough. What the hiring manager or hiring committee is looking for is confidence from the interviewers in their decisions, a breadth of knowledge demonstrated by the candidate, good communication skills, and an answer to the question “Does the candidate meet our bar?”

1.3 The approach

A good interview question has many right answers but always at least one optimal in time or space. Getting to the optimal solution will take mastery of the fundamentals: data structure, memory management, iteration style, and search techniques.

It is important that you know how to approach technical questions. Every candidate should learn to take his time in order to consider all these angles. Take your time. After all if an interviewer asks you to code up lowest common ancestor in a binary search tree and you approach it for an unstructured binary tree you have made an error that will cost you a hire.

There is a simple, natural approach to problem solving that I see all well-prepared candidates take. The steps are restating the question, understanding what is required, sketching a solution, coding, and testing. Let’s go through each of these steps in turn.

First restate the problem. You should look for ambiguity, and if found continue by either proposing changes or asking for clarification. Ambiguity comes in many forms, so be on the lookout for undefined behavior and corner cases.

Second, make sure you understand the corner cases and you’ve defined away as much ambiguity as possible. Do a few test cases with the interviewer. Write down the input and expected output, and leave these on the board to refer back to later. These cases will be useful during sketching and testing.

Third, sketch the program on the board. Do not take the whole board, because you will need to write the code next. But you want to have something to refer back to while you present your solution. Your sketch should be enough to show what you’ll need to write for your main processing path and what helper functions you’ll need to write. Your sketch should also be complete enough to gauge the asymptotic run time of your algorithm.

Fourth, write the program correctly. It cannot be said enough - you are best off to do it right the first time. Many candidates ask if they can skip error checking, boundary conditions, or helper functions that they believe are not core to the problem at hand. Do not do this. To see why simply compare two candidates, one in which after writing the prototype the candidate automatically begins checking fornulland buffer length, and another in which the candidate waves his hand and says that he will do normal error and bounds checking later. All else being equal, the first candidate is the better interview. And that is because he showed he could do it right the first time.

Fifth and lastly, run your test cases from the second step through the code you wrote on the board. This gives you a chance to show the interviewer how you test, and also lets you see you own writing with fresh eyes. Perhaps you changed a variable name, missed a boundary case, or improperly changed a helper function prototype. By stepping through your test cases these problems will be avoided. And that is it. Restate the problem, write down some test cases, sketch you approach, write the program, and test it. This should sound familiar, because it’s no coincidence that interviewing and every day programming have the same workflow.

Working through programming problems is much more enjoyable than talking about strategies on how to approach them, so let’s begin. First up is a review of the fundamentals of programming.