Programming Problems: A Primer for The Technical Interview

By Bradley Green

A complete primer for the technical programming interview. This book reviews the fundamentals of computer programming through programming problems posed to candidates at Amazon, Apple, Facebook, Google, Microsoft, and others. Complete solutions to every programming problem is provided in clear explanations and easy to read C++11 code.

If you are learning to code then this book provides a great introduction to C++11 and fundamental data structures and algorithms. If you are preparing for an interview or want to challenge yourself, then this book will cover all the fundamentals asked at major companies such as Amazon, Google, and Microsoft.

• Language: English
• Publisher: Bradley Green
• Release date: Apr 23, 2012
• ISBN: 9781476226583

Book preview

_______________________________________________________

Programming Problems

A Primer for The Technical Interview

__________________

Volume I: Fundamentals in C++11

Bradley Green

Copyright 2013 Bradley Green

Smashwords Edition

Preface

This book is the study guide I wish I had when preparing for my first programming interview.

After graduation, I was unprepared for the gauntlet of the technical interview. At that time, in quick succession IBM, Intel, and Microsoft interviewed me. Microsoft was far and away the most difficult interview, spanning 2 days and 14 total interviews. We covered everything; makefiles and build environments, digital circuits, C/C++ language specifications, and algorithms. Luckily, in the end everything worked out fine. I evaluated my offers, and moved to Redmond, Washington to begin my career in high tech. However, I still wish I knew what I was getting myself into before I had my first tech interview.

In tech, nothing stays very stable for long. Projects change and company wide reorganizations happen without notice. Its not a well kept secret, but at Microsoft, internal transfers require a full technical interview. Now and again there are exceptions, for instance if you are well known in the area or if you are re-organized into a different division. But for the most part you have a full interview, including external resume submission, pre-interview screening, and the grueling day of testing.

So soon into the new millennium, I began interviewing for my second position. Since that time I’ve interviewed many more times at Microsoft, Google, Facebook, and a host of other high tech companies. I’m lucky to have always passed the interviews, and have spent time at a number of great companies.

During all this I’ve conducted over a hundred interviews and discussed many more in interview loops and hiring committees. Some years ago I began saving notes for when I prepare to give interviews. These became organized into a large collection of programming problems. At some point a friend mentioned that it would be worthwhile to write these down, and from that suggestion has come this book.

This book is meant as a refresher for seasoned engineers and a handbook for first candidates; it is not a textbook or a scientific volume. I considered adding sections with problems at the end of each chapter, but I believe that without complete answers this text loses its focus as a handbook. In further editions the references made in the text will be properly compiled into a bibliography, but for the moment I beg your forgiveness for not knowing where many of the techniques used herein were first discovered. And finally, although I’ve done my best to guarantee the code presented compiles with gcc4.7 and works on basic test cases, there are not many references or mathematical proofs in the first edition of this book.

.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 later 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 self-contained study guide on a specific topic. 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 in C/C++

C/C++ has long been the standard for advanced programming. If you want to work alongside the best in our field you should take the time to familiarize yourself with this language at least to the level of reading comprehension. And to be clear, if you want to work at a company such as Apple, Facebook, Google, or Microsoft you are handicapping yourself and your future if you do not know C/C++.

C/C++ is the lingua franca of interviewing; nearly all interviewers know it and nearly all candidates are expected to be able to read it. But there are many reasons aside from just the fact that most of the interviewers at those companies are familiar with C/C++. For one, C/C++ hides very little. While this makes writing code more verbose, it allows everyone to know what you are trying to demonstrate. And being able to clearly demonstrate what you know is what an interview is all about.

The coding style used here loosely follows the style guidelines published by Google. I find the format they have come to agree upon and evangelize to favor readability over conciseness. In the listings most coding will be verbose in many areas, aside from some pointer arithmetic and parameter variable reuse.

I attempt to stay close to the C roots of the C++ language at the expense of class definitions, templates and generic solutions. This is done so as to demonstrate the algorithms as clearly as possible. The benefits of templates and container classes are not lost to me, and I use them in everyday coding. But they add complexity to the code listings that does not justify their weight. For that reason nearly all the value data types will simply be int. It should be clear that for almost everywhere they are used that a template version of the function or a proper data structure container could be substituted.

I did not want to write this text in ANSI C, so to avoid many lines of text due to memory management I will use the STL containers queue, stack, and vector, freely. But there will be some pointer arithmetic and in fact an entire section on bit twiddling in the second volume.

Near the end of writing the first draft, I decided to incorporate C++11. The revision vastly improves readability and conciseness. The use of auto allows the reader to focus on the variable use and not the variable declaration. I call elements of type std::function functionals. The use of functionals keeps algorithms self-contained instead of spread out amongst many functions. I hope this change benefits the reader as much as it did the writer.

.3 Acknowledgements

I want to thank L.A.G. for her support and endearing love, and always being there by my side. I also want to thank T.G. for always being there to offer a short diversion to writing, and to my parents R.G. and K.G., for without them I would have never gotten this far.

I also want to thank J. Melvin for a thorough reading, and his helpful comments. The editors of Wikipedia made research extremely efficient, and there is not enough that I can do to thank them for their contribution. And finally, I am grateful to to E.M.H. for suggesting this book and her reminder that it should have been completed long ago.

.4 A last word

In further editions,

Reviews for Programming Problems

[Kumar Sabyasachi Padhi · Rating: 4 out of 5 stars]

Its a awesome book for programmers and software developer interviews