Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Analyzing Your Solution

After you answer the problem, you may be asked about the efficiency of your implementation. Often, you have to compare trade-offs between your implementation and another possible solution and identify the conditions that make each option more favorable. Common questions focus on run time and memory usage.

A good understanding of Big-O analysis is critical to make a good impression with the interviewer. Big-O analysis is a form of runtime analysis that measures the efficiency of an algorithm in terms of the time it takes for the algorithm to run as a function of the input size. It’s not a formal benchmark, just a simple way to classify algorithms by relative efficiency when dealing with very large input sizes.

Most coding problem solutions in this book include a runtime analysis to help you solidify your understanding of the algorithms.

Big-O Analysis In Action

Consider a simple function that returns the maximum value stored in an array of non-negative integers. The size of the array is n. There are at least two easy ways to implement the function.

In the first alternative, you 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:

/* Returns the largest value in an array of non-negative integers */ int CompareToMax(int array[], int n) { int curMax, i; /* Make sure that there is at least one element in the array. */ if (n <= ...