Java Programming Interviews Exposed

Chapter 7

Implementing Popular Interview Algorithms

This chapter looks at some popular questions used in interviews. Although these questions will probably not come up in the exact form presented here, they serve as a good introduction to the level and approach that interviewers take.

Many of the questions here have been taken from the website Interview Zen, (www.interviewzen.com) where they have been used in real interviews for real developers.

When you are asked in an interview to write or develop an algorithm, you should be focusing on how efficient the algorithm is. Efficiency can take several forms: The running time of an algorithm is usually the main point of focus, but it is also important to consider the space an algorithm uses. Quite often, you will need to strike a balance between these two depending on your requirements.

A common method for describing the efficiency of an algorithm is called Big O Notation. This is used to describe how an algorithm reacts to a change to its input.

An algorithm with O(n) is said to have linear complexity: As the size of the input, n, increases, the performance of the algorithm increases by a proportional amount.

An O(n2) complexity is said to be quadratic: if you tripled the size of the input, the algorithm would take nine times longer to run. As you would expect, quadratic, or worse, exponential (O(nn)) algorithms should be avoided where possible.

Implementing FizzBuzz

Write an algorithm that prints all numbers between 1 and n, replacing ...