Java Programming Interviews Exposed

Chapter 4

Writing Core Algorithms

Many of the algorithms you are asked to define or demonstrate in interviews are operations on lists, usually sorting or searching. This chapter examines several ways to assemble a list into an ordered list, and discusses the advantages of each approach. It also looks at a common approach to searching lists for a given value.

The algorithms described here are often covered in a core computer science course, so if you have ever studied computer science you will probably be able to treat this chapter as a refresher.

Looking at Big O Notation

A formal approach to describing the performance or complexity of an algorithm is called Big O Notation. This describes how an algorithm performs as its input changes.

For instance, an algorithm described as having a worst-case performance of O(n2) means that as the size of the input doubles, the algorithm takes four times longer to run. An O(n2) algorithm is often not the most efficient implementation, although this is entirely dependent on the exact goal of the algorithm.

Big O tends to be applicable for larger values of n. When n is small, the running time or space consumption of an algorithm is often negligible. Regardless, for any algorithm you do write, it is always worth considering Big O notation, even for small values of n, as, over time, you may find you are running your algorithm with larger and larger input.

An algorithm often has three values of complexity: best-case, worst-case, and average-case. ...