Programming Problems in Java: A Primer for The Technical Interview (2014)

Preface

This book is based on Programming Problems, by BradleyGreen. I was extremely interested and excited when he approached me about writing theJavaversion of the book.Java’s popularity and similarity withC/C++make it ideal for learning and reviewing algorithms.

Even though I had studied computer science in undergrad, I spent my summers in a research lab rather than interning at different companies. I didn’t have any experience with the technical job interview until the year before graduating. As such, I needed to spend more time than most of my peers preparing for job interviews. The interview process was grueling at first, but I got the hang of it over time. Fortunately, I obtained several offers for both software engineering and consulting positions, and I decided to start my tech career in consulting where I obtained a breadth of software experience. I also enjoyed witnessing and participating in both the engineering and business parts of the industry.

Later on I wanted to work on larger scale engineering problems, and so I decided to look for a new opportunity. Having already been through the interview process before, preparing for interviews the second time went faster. After interviewing at a few companies, I decided to go to Facebook for my next adventure.

This book is my attempt at producing the study guide which would have greatly benefited my friends, colleagues, and I when preparing for interviews. It is intended not only for new employees but also seasoned engineers who want a refresher for the technical interview.

Like any profession, interview skills are extremely important. This most definitely applies to the software field as well. Oftentimes I have seen capable candidates who underperform on their interview loop because of their lack of preparation. The algorithms, knowledge, and other skills I learned while preparing for interviews have also been applicable to my job. For example, the process of starting with test cases, brainstorming ideas, and iterating on a solution is a common way of approaching day-to-day work. Having gone through the process of preparing for interviews and having been through multiple interview loops myself, I am also able to do a better job of interviewing other engineers.

Like the original, this book is intended to be a refresher for experienced engineers and a handbook for college students and new candidates. In future editions, the references in this book will be compiled into a bibliography. For the moment, I beg your forgiveness for not knowing where many of the techniques used here were first discovered. I have done my best to ensure the code runs withJava 1.7and passes some basic test cases. While the latest stable version ofJavaisJava 1.8which was released recently, I specifically chose not to write this book inJava 1.8to better illustrate concepts.

.1 Structure of the book

There are three main areas that I hope to cover in this work: data structures, searching and sorting, and advanced algorithms. The latter section of the text is broken up into algorithms on strings, numbers, and sequences. As the scope of this work grew, it became clear that the work should be divided into two volumes. The first volume provides a discussion of programming problems covering elementary data structures, abstract data types, searching and sorting. The second volume covers advanced programming problems such as spatial partitioning, substring searching, parsing, and sampling.

The chapter structure is the same within both volumes. Each chapter is a mostly self-contained study guide on a specific topic. Where necessary, I’ve consumed basic algorithms from prior chapters. I attempted to frame it so that complexity increases throughout the chapter. The introductory material should be simply refresher for anyone in the industry; middle sections contain interesting problems and revisions, and the finale an interesting and complex problem. I hope that these problems give the reader some pleasure in thinking about before continuing on to the discussion of the answer.

.2 Programming inJava

Though not as ubiquitous asCorC++,Javais relatively common in industry. It is not uncommon these days to find undergraduate and graduate school computer science courses taught primarily inJava.Javais an object-oriented language whose syntax is quite similar to that ofCandC++. While not the emphasis of this book, some object-oriented concepts will be sprinkled throughout this book - as they are useful concepts every software engineer should be aware of. Given this, I feel this book will be useful even for developers not familiar with or looking to work in aJavaenvironment.

In some places, I have not written well-optimizedJava, instead favoring constructs that better portray the concept at hand and are hopefully easier to understand. Where it helps make code cleaner, I have encapsulated broader concepts and data structures within classes and/or helper functions. In general, I have tried to keep the code as readable as possible. I also useJavastandard utility functions and classes including arrays, collections, lists, maps, and hashes freely.