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

Chapter 4. Linked Lists

The deceptively simple linked list is the basis for a surprising number of problems regarding the handling of dynamic data. Problems about efficient list traversal, list sorting, and the insertion or removal of data from either end of a list are good tests of basic data-structure concepts, which is why we devote an entire chapter to linked lists. Their simplicity appeals to interviewers, who want to present at least two or three problems over the course of an hour-long interview. This means that they have to give you problems that you can be reasonably expected to answer in 20 to 30 minutes. You can write a relatively complete implementation of a linked list in less than 10 minutes, leaving you plenty of time to solve the problem. In contrast, it might take you most of the interview period to implement a more complex data structure such as a hash table. In addition, there is little variation in the way linked lists are implemented, which means that an interviewer can simply say "linked list" and not waste time discussing and clarifying implementation details.

Linked list problems are typically posed for jobs requiring C or C++ experience because they're an easy way to determine whether a candidate understands how pointers work, so most of the examples in this chapter are in C++, but without any use of C++'s object-oriented programming facilities. It's assumed that you're using a C++ compiler so that you can use the C++ new and delete operators in your code. ...