Programming Interviews Exposed: Secrets to Landing Your Next Job by John Mongan, Eric Giguere, Noah Suojanen

From Barnes & Noble

The Barnes & Noble Review
Interviewing doesn't comes naturally to every programmer. But a programming interview typically involves even more than the "typical" job interview: You must demonstrate your creativity in solving technical problems under pressure. Thankfully, there's a start-to-finish guide to doing just that. If you're pursuing a career in software development, Programming Interviews Exposed, Second Edition could be the most valuable book you ever read.

The authors first help you make it past the screeners (including "sanitizing" your online footprint, so you're not weeded out for reasons unrelated to technical competence). Next, you'll take a closer look at the interviewing process, from preliminary interviews to half-day or full-day on-site interviews. Then, the authors turn to the meat of the on-site interview: the coding questions that are carefully designed to make or break you. What does the interviewer want to see? What thought processes should you follow, and how do you make your thinking "visible"?

Then, they turn to the programming problems themselves. This is the material that made the first edition of Programming Interviews Exposed an underground classic, and it's been thoroughly revised in this new edition. You'll find "brain teasers," solutions, and thought processes for a wide variety of programming tasks, from linked lists to arrays, recursion to concurrency, objects to databases. You'll find counting and spatial puzzles, knowledge-based questions, and a full chapter of non-technical questions, too. What side insights or elegant "special case" solutions will make you look especially knowledgeable? Where are the interviewers looking for you to trip up? You won't find this information anywhere else. Can you afford to interview without it? Bill Camarda, from the June 2007 Read Only

From the Publisher

Programming Interviews Exposed
2nd Edition

The pressure is on during the interview process but with the right preparation, you can walk away with your dream job. This classic book uncovers what interviews are really like at America's top software and computer companies and provides you with the tools to succeed in any situation. The authors take you step-by-step through new problems and complex brainteasers they were asked during recent technical interviews.

50 interview scenarios are presented along with in-depth analysis of the possible solutions. The problem-solving process is clearly illustrated so you'll be able to easily apply what you've learned during crunch time. You'll also find expert tips on what questions to ask, how to approach a problem, and how to recover if you become stuck. All of this will help you ace the interview and get the job you want.

What you will learn from this book

* Tips for effectively completing the job application
*

Ways to prepare for the entire programming interview process
*

How to find the kind of programming job that fits you best
*

Strategies for choosing a solution and what your approach says about you
*

How to improve your interviewing skills so that you can respond to any question or situation
*

Techniques for solving knowledge-based problems, logic puzzles, and programming problems

Who this book is for

This book is for programmers and developers applying for jobs in the software industry or in IT departments of major corporations.

Wrox Beginning guides are crafted to make learning programming languages andtechnologies easier than you think, providing a structured, tutorial format that will guide you through all the techniques involved.

Product Details

• Table of Contents
• Read a Sample Chapter

Table of Contents

Read a Sample Chapter

Note: The Figures and/or Tables mentioned in this sample chapter do not appear on the Web.

Coding questions are generally the meat of an interview. They are your chance to demonstrate that you can do the job. These questions are a large component of the process that most computer and software companies use to decide who to hire and who not to hire. Many companies make offers to less than 10 percent of the people who interview with them. The questions are generally rather difficult. If everyone (or even most people) were able to answer a particular question quickly, the company would stop asking it because it wouldn't tell anything about the applicants. Many of the questions are designed to take up to an hour, so don't get frustrated if you don't see the answer right away. Almost no one does.

LESSON: These problems are hard! Some of the questions are designed to see how you handle a problem when you don't immediately see the solution.

The Process

In these questions, you will usually be working one on one with your interviewer. He will give you a marker and a whiteboard (or pen and paper) and ask you to write some code. The interviewer will probably want you to talk through the question before you start writing. Generally, you will be asked to code a function, but sometimes you will need to write a class definition or a series of functions. In any case, you will be writing code.

If you are applying for a job as a programmer in a specific language, you should know that language and expect to use it to solve any problems you are given. If you are applying for a general programming or development position, a thorough knowledge of C and some familiarity with C++ will be enough to get by. Your interviewer may permit you to use other mainstream languages, such as Java or Perl. If you are given a choice, select the language you know best, but expect that you will be required to solve some problems in C or C++. Interviewers are less likely to be amenable to you using less mainstream languages like Lisp, Python, Tcl, Prolog, Cobol, or Fortran, but if you are particularly expert in one of these, there's no harm in asking. Before you go to your interview, you should make sure you are completely comfortable with the use and syntax of any language you plan to use. One final note about language selection: Whether rightly or wrongly, many people consider Visual Basic and JavaScript to be lesser languages. Unless you are applying for a job where you will be using these languages it's probably best to avoid them in your interviews. The solutions in this book are all in C, C++, Perl, or Java with an emphasis on C because it's still the most common language in interviews.

The code you write in the interview is probably the only example of your code that your interviewer will see. If you write ugly code, your interviewer will assume you always write ugly code. This is your chance to shine and show your best code. Take the time to make your code solid and pretty.

LESSON: Brush up on the languages you expect to use, and write your best code.

Programming questions are designed to see both how well you can code and how you solve problems. If all the interviewer wanted to do was measure your coding ability, he could give you a piece of paper with problems and come back an hour later to evaluate how you did. However, the interviewer wants to see your thought process throughout the interview. The problem-solving process is interactive, and if you're having difficulty, the interviewer will generally guide you to the correct answer via a series of hints. Of course, the less help you need to solve the problem, the better you look, but showing an intelligent thought process and responding well to the hints you are given is also very important. If you know any additional information that pertains to the problem you may want to mention it to show your general knowledge of computers, even if it's not directly applicable to the problem at hand. In answering these problems, show that you're not just a propeller-head coder. Demonstrate that you have a logical thought process, are generally knowledgeable about computers, and can communicate well.

LESSON: Keep talking! Always explain what you are doing.

Questions are generally asked in ascending order of difficulty. This is not a hard and fast rule, but you can expect the questions to get more difficult as you answer more of them correctly. Often, different interviewers will communicate with each other about what they asked you, what you could answer, and what you couldn't answer. If you answer all the questions in your early interviews but find yourself stumped by harder questions later on, this may indicate that earlier interviewers were impressed with your responses.

About the Questions

These questions have very specific requirements. They have to be short enough that they can be explained and solved reasonably quickly, yet complex enough that not everyone can solve them. Therefore, it's unlikely that you'll be asked any real-world problems. Almost any worthy real-world problem would take at least three hours to explain, a day to examine the existing code, and a week to solve. That isn't an option in an interview. Instead, many of these problems require using tricks or uncommonly used features of a language.

The problems often prohibit you from using the most common way to do something or from using the ideal data structure. For example, you might be given a problem like this: "Write a function that determines if two integers are equal without using any comparative operators." 1 This is an outright silly and contrived problem. Almost every language that ever existed has some way to compare two integers. However, you're not off the hook if you respond, "This is a stupid question; I'd always use the equality operator. I'd never have this problem." In fact, you flunked if you answer this way. Sometimes, it may be worthwhile to comment on a better way to solve the problem, even if it has been disallowed, but you need to solve the questions as they're asked. For example, if you were asked to solve a certain problem with a hashtable, you might say, "This would be easy with a binary search tree because it's much easier to extract the largest element. But let's see how I can solve this with a hashtable ..."

LESSON: Many questions involve ridiculous restrictions, use obscure features of languages, and seem silly and contrived. Play within the rules.

Solving the Questions

You can't solve the problem correctly if you don't understand it. Often, there are hidden assumptions in the problem, or the interviewer's explanation may be very brief or difficult to follow. You can't demonstrate your skills if you don't understand the problem. Don't hesitate to ask your interviewer questions about the problem, and don't start solving it until you understand it.

Once you understand the question, you should almost always try an example. This example may lead to insights on how to solve the problem or bring to light any remaining misunderstandings that you have. Starting with an example also demonstrates a methodical, logical thought process. Examples are especially useful if you don't see the solution right away.

LESSON: Make sure you understand the problem before you start solving it, then start with an example to solidify your understanding.

After your example, focus on the algorithm you will use to solve the problem. Often, this will take a long time and require additional examples. This is to be expected. If you stand quietly staring at the whiteboard, the interviewer has no way of knowing whether you're making productive headway or simply clueless. Therefore, talk to your interviewer and tell him what you are doing. For example, you might say something like "I'm wondering if I can store the values in an array and then sort them, but I don't think that this will work because I can't quickly look up elements in an array by value..." This demonstrates your skill, which is the point of the interview, and may also lead to hints from the interviewer. He might respond, "You're very close to the solution. Do you really need to look up elements by value, or could you ..."

It may take you a long time to solve the problem. You may be tempted to begin coding before you figure out exactly how to solve the problem. Resist this temptation. Consider who you would rather work with: someone who thinks about a problem for a long time and then codes it correctly the first time or someone who hastily jumps into a problem, makes several errors while coding, and doesn't have any idea where he is going. Not a difficult decision, is it?

After you've figured out your algorithm and how you will implement it, explain your solution to your interviewer. This gives him an opportunity to evaluate your solution before you begin coding. Your interviewer may say, "Sounds great, go ahead and code it," or he may say something like "That's not quite right because you can't look up elements in a hashtable that way . . ." In either case, you gain valuable information.

While you code, it's important that you explain what you're doing. For example, you might say, "Here, I'm initializing the array to all 0's ..." This narrative allows the interviewer to follow your code more easily.

LESSON: Explain what you are doing to your interviewer before and while coding the solution. Keep talking!

You generally won't be penalized for asking factual questions that you might otherwise look up in a reference. You obviously can't ask a question like "How do I solve this problem?" but it is acceptable to ask a question like "I can't remember-- what format string do I use to get printf to print out octal numbers?" While it's better to know how to do this without asking, it's OK to ask this sort of question.

After you've written the code for a problem, immediately verify that the code is correct by tracing through it with an example. This step demonstrates very clearly that your code works in at least one case. It also illustrates a logical thought process and your desire to check your work and search for bugs. The example may also help you flush out minor bugs in your solution.

Finally, you should make sure you check your code for all error and special cases. Many error and special cases go overlooked in programming; forgetting these cases in an interview indicates you may forget them in a job. For example, if you allocate dynamic memory, make sure you check that the allocation did not fail. Also, check that you won't dereference any NULL pointers and that you can handle empty data structures. It's important to cover these cases to truly impress your interviewer and correctly solve the problem.

LESSON: Try an example, and check all error and special cases.

Once you try an example and feel comfortable that your code is correct, the interviewer may ask you questions about what you wrote. Commonly, these questions focus on running time, alternative implementations, and complexity. If your interviewer does not ask you these questions, you should volunteer the information to show that you are cognizant of these issues. For example, you could say, "This implementation has linear running time, which is the best possible because I have to check all the input values. The dynamic memory allocation will slow it down a little, as will the overhead of using recursion..."

When You Get Stuck

Often, you will get stuck on a problem. This is expected and is an important part of the interviewing process. Interviewers want to see how you respond when you don't recognize the answer to a question immediately. The worst thing to do is give up or get frustrated. Instead, show interest in the problem and keep trying to solve it. When all else fails, go back to an example. Try performing the task and analyzing what you are doing. Try extending from your specific example to the general case. You may have to use very detailed examples. This is OK.

LESSON: When all else fails, return to a specific example. Try to move from the specific example to the general case and from there to the solution.

Another fallback option is to try a different data structure. Perhaps a linked list, array, hashtable, or binary search tree will help solve the problem. If you're given an unusual data structure, look for similarities between it and more familiar data structures. Using the right data structure often makes a problem much easier.

You should also consider the less commonly used or more advanced aspects of a language when you have trouble with a problem. These can include bit operators, union types, complex pointer casting, and advanced keywords. Sometimes, the key to a problem involves one of these features.

LESSON: Sometimes a different data structure or advanced language feature is key to the solution.

Even when you don't feel stuck, you may be having problems. You may be missing an elegant or obvious way to implement something and writing too much code. One of the shared traits of almost all interview coding questions is that the correct solutions are short. You rarely need to write more than 15 lines of code and almost never more than 30. If you start writing lots of code, it should be a warning that you may be heading in the wrong direction.

One final note on writing code: You often need to compare a value to NULL or 0. In this case (at least in C or C++), you could write either:

if (elem != NULL) {
if (elem) {

These two statements are equivalent to the compiler. There's something of an argument between programmers as to which alternative is visually cleaner. Some programmers argue the former implementation is easier to read and worth writing out. Other programmers argue that this is such a common situation that the latter implementation is perfectly acceptable. From an interviewer's standpoint, both implementations are technically correct. In the former definition, however, the interviewer may wonder if you know that comparing to NULL is unnecessary; in the latter case, the interviewer wonders nothing and sees you as a coding veteran. Thus, it is probably preferable to choose the latter implementation in an interview and mention that it's the same as comparing to NULL or 0.

Analysis of the Solution

The interviewer will usually ask about the efficiency of your implementation. Often, you will have to compare trade-offs between your implementation and another possibility and identify the conditions that make each choice more favorable. Common questions focus on the use of dynamic memory and recursion.

The most important part of measuring efficiency is run-time analysis. The most commonly used form of this is called big-O analysis. This method provides a concrete means of comparing two algorithms. The formal definition of big-O analysis is quite mathematical; this explanation deals with it on a more practical and intuitive level. If you're familiar with big-O analysis, this explanation will serve as a review. Otherwise, it should bring you up to speed on basic run-time analysis.

Big-O analysis deals specifically with the time an algorithm takes to run as a function of the size of the input. Let's start with an example of Big-O analysis in action. Consider a simple function that returns the maximum value in an array of numbers. The size of the array is n. There are at least two easy ways to implement the function. First, you can keep track of the current largest number as the function iterates through the array and return that value when you are done iterating. This implementation, called CompareToMax, looks like this:

/* Returns the largest integer in the array */
int CompareToMax( unsigned int array[], int n)
{
unsigned int curMax, i;

/* Make sure that there is at least one element in the array. */
if (n <= 0)
return -1;

/* Set the largest number so far to the first array value. */
curMax = array[ 0];

/* Compare every number with the largest number so far. */
for (i = 1; i < n; i++) {
if (array[ i] > curMax) {
curMax = array[ i];
}
}
return curMax;
}

Alternatively, you could implement this function by comparing each value to all the other values. If all other values are less than or equal to a certain value, that value must be the maximum value. This implementation, called CompareToAll, looks like this:

/* Returns the largest integer in the array */
int CompareToAll( unsigned int array[], int n)
{
int i, j, isMax;
/* Make sure that there is at least one element in the array. */
if (n <= 0)
return -1;

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {

isMax = 1;
/* See if any value is greater. */
if (array[ j] > array[ i])
isMax = 0; /* array[ i] is not the largest value. */
}
/* If isMax == 1, no larger value exists; array[ i] is max. */
if (isMax)
return array[ i];
}
}

Both of these functions correctly return the maximum value. Which one is more efficient? The most accurate way to compare CompareToMax and CompareToAll is to benchmark them. In most development efforts, though, it's impractical to implement and benchmark every possible alternative. You need to be able to predict an algorithm's performance without having to implement it. Big-O analysis allows you to do exactly that: compare the predicted relative performance of different algorithms.

In Big-O analysis, input size is assumed to be n. In this case, n simply represents the number of elements in an array. In other analyses, n may represent the number of nodes in a linked list, the number of bits in a data-type, or the number of entries in a hashtable. After figuring out what n means in terms of the input, you have to determine how many times the n input items are examined in terms of n. "Examined" is a fuzzy word because algorithms differ greatly. Commonly, an examination might be something like adding an input value to a constant, creating a new input item, or deleting an input value. In big-O analysis, these operations are all considered equivalent. In both CompareToMax and CompareToAll, "examine" means comparing an array value to another value.

In CompareToMax, each array element was compared once to a maximum value. Thus, the n input items are each examined once, resulting in n examinations. This is considered O( n). O( n) is often called linear time. Y check to make sure that the array is not empty and a step that initializes the curMax variable. Thus, it may seem more accurate to call this an O( n + 2) function. Big-O analysis, however, yields the asymptotic running time, the limit of the running time as n gets very large. As n approaches infinity, the difference between n and n + ² is insignificant, so the constant term can be ignored. Similarly, for an algorithm running in n + n ² time, the difference between n2 and n + n² is negligible for very large n. Thus, in big-O analysis, you eliminate all but the highest-order term, the term that is largest as n gets very large. In this case, n is the highest-order term. Therefore, the CompareToMax function is O( n).

The analysis of CompareToAll is a little more difficult. First, you have to make an assumption about where the largest number occurs in the array. For now, assume that the maximum element is at the end of the array. In this case, this function may compare each of n elements to n other elements. Thus, there are n n examinations, and this is an O( n ² ) algorithm. The analysis so far has shown that CompareToMax is O( n) and CompareToAll is O( n² ). This means that as the array grows, the number of comparisons in CompareToAll will become much larger than in CompareToMax. Consider an array with 30,000 elements. CompareToMax will compare on the order of 30,000 elements while CompareToAll will compare on the order of 900,000,000 elements. You would expect CompareToMax to be much faster because it examines 30,000 times fewer elements. In fact, one benchmark timed CompareToMax at less than .01 seconds while CompareToAll took 23.99 seconds.

You may think this comparison was stacked against CompareToAll because the maximum value was at the end. This is true, and it raises the important issues of best-case, average-case, and worst-case running times. The analysis of CompareToAll was a worst-case scenario, where the maximum value was at the end of the array. Consider the average case, where the largest value is in the middle. You have to check only half the values n times because the maximum value is in the middle. This results in checking n( n/2) = n 2/2 times. This would appear to be an O( n2/2) running time. Consider, though, what the 1/2 factor means. The actual time to check each value is highly dependent on the machine instructions that the code translates to and then on the speed in which the CPU can execute the instructions. Therefore, the 1/2 doesn't mean very much. You could even come up with an O( n² ) algorithm that was faster than an O( n 2/2) algorithm. In big-O analysis, you drop all constant factors, so the average case for CompareToAll is no better than the worst case. It is still O( n2 ).

The best case running time for CompareToAll is better than O( n ² ). In this case, the maximum value is at the beginning of the array. The maximum value is compared to all other values only once, so the result is an O( n) running time.

Note that in CompareToMax, the best-case, average-case, and worst-case running times are identical. Regardless of the arrangement of the values in the array, the algorithm is always O( n).

The general procedure for big-O run-time analysis is as follows:

1. Figure out what the input is and what n represents.

2. Express the number of operations the algorithm performs in terms of n.

3. Eliminate all but the highest-order terms.

4. Remove all constant factors.

Here's a common case to be aware of. You could make the following optimization to CompareToAll. Instead of comparing each number to every other number, compare each number to only the numbers occurring after it. In essence, every number before the current number has already been compared to the current number. Thus, the algorithm is still correct if you compare only to numbers occurring after the current number. What's the worst-case running time for this implementation? The first number is compared to n numbers, the second number to n D 1 numbers, the third number to n - 2, resulting in a number of comparisons equal to n + (n - 1) + (n - 2) + (n - 3) + É + 1. This is a very common result; the sum of this series is

n 2 is the highest-order term, so this is still an O( n 2 ) running time. The fastest possible running time is O( 1). This is commonly referred to as constant running time. This means the function always takes the same amount of time to execute, regardless of the input size. There may even be no input to the function. Most coding problem solutions in this book include a run-time analysis. You may find these examples helpful in solidifying your understanding.