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

3.3. Analyzing Your Solution

Once you've answered 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 memory or space usage, especially when recursion is involved.

A good understanding of big-O analysis is critical to making a good impression with the interviewer. Big-O analysis is a form of run-time 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.

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

3.3.1. Analyzing Two Examples

Let's start with an example of big-O analysis in action. Consider a simple function that returns the maximum value stored in an array of non-negative numbers. 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 this:

/* Returns the largest integer in the array */ int CompareToMax(int array[], int n) { int curMax, i; /* Make sure that there ...