Bradley Green - Programming Problems: A Primer for the Technical Interview

_______________________________________________________
Programming Problems
A Primer for The Technical Interview
__________________
Volume I: Fundamentals in C++11

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

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

In tech, nothing stays very stable for long. Projectschange and company wide reorganizations happen without notice. Itsnot a well kept secret, but at Microsoft, internal transfersrequire a full technical interview. Now and again there areexceptions, for instance if you are well known in the area or ifyou are re-organized into a different division. But for the mostpart you have a full interview, including external resumesubmission, pre-interview screening, and the grueling day oftesting.

So soon into the new millennium, I began interviewingfor my second position. Since that time Ive interviewed many moretimes at Microsoft, Google, Facebook, and a host of other high techcompanies. Im lucky to have always passed the interviews, and havespent time at a number of great companies.

During all this Ive conducted over a hundredinterviews and discussed many more in interview loops and hiringcommittees. Some years ago I began saving notes for when I prepareto give interviews. These became organized into a large collectionof programming problems. At some point a friend mentioned that itwould be worthwhile to write these down, and from that suggestionhas come this book.

This book is meant as a refresher for seasonedengineers and a handbook for first candidates; it is not a textbookor a scientific volume. I considered adding sections with problemsat the end of each chapter, but I believe that without completeanswers this text loses its focus as a handbook. In furthereditions the references made in the text will be properly compiledinto a bibliography, but for the moment I beg your forgiveness fornot knowing where many of the techniques used herein were firstdiscovered. And finally, although Ive done my best to guaranteethe code presented compiles with gcc4.7 andworks on basic test cases, there are not many references ormathematical proofs in the first edition of this book.

There are three main areas that I hope to cover inthis work: data structures, searching and sorting, and advancedalgorithms. The later section of the text is broken up intoalgorithms on strings, numbers, and sequences. As the scope of thiswork grew, it became clear that the work should be divided into twovolumes. The first volume provides a discussion of programmingproblems covering elementary data structures, abstract data types,searching and sorting. The second volume covers advancedprogramming problems such as spatial partitioning, substringsearching, parsing, and sampling.

The chapter structure is the same within bothvolumes. Each chapter is a self-contained study guide on a specifictopic. I attempted to frame it so that complexity increasesthroughout the chapter. The introductory material should be simplyrefresher for anyone in the industry; middle sections containinteresting problems and revisions, and the finale an interestingand complex problem. I hope that these problems give the readersome pleasure in thinking about before continuing on to thediscussion of the answer.

C/C++ has long been thestandard for advanced programming. If you want to work alongsidethe best in our field you should take the time to familiarizeyourself with this language at least to the level of readingcomprehension. And to be clear, if you want to work at a companysuch as Apple, Facebook, Google, or Microsoft you are handicappingyourself and your future if you do not know C/C++ .

C/C++ is the lingua franca ofinterviewing; nearly all interviewers know it and nearly allcandidates are expected to be able to read it. But there are manyreasons aside from just the fact that most of the interviewers atthose companies are familiar with C/C++ .For one, C/C++ hides very little. Whilethis makes writing code more verbose, it allows everyone to knowwhat you are trying to demonstrate. And being able to clearlydemonstrate what you know is what an interview is all about.

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

I attempt to stay close to the C roots of the C++ language atthe expense of class definitions, templates and generic solutions.This is done so as to demonstrate the algorithms as clearly aspossible. The benefits of templates and container classes are notlost to me, and I use them in everyday coding. But they addcomplexity 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 almosteverywhere they are used that a template version of the function ora proper data structure container could be substituted.

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

Near the end of writing the first draft, I decided toincorporate C++11 . The revision vastlyimproves readability and conciseness. The use of auto allows the reader to focus on the variable use andnot the variable declaration. I call elements of type std::function functionals. The use of functionals keepsalgorithms self-contained instead of spread out amongst manyfunctions. I hope this change benefits the reader as much as it didthe writer.

I want to thank L.A.G. for her support and endearinglove, 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, andto my parents R.G. and K.G., for without them I would have nevergotten this far.

I also want to thank J. Melvin for a thoroughreading, and his helpful comments. The editors of Wikipedia maderesearch extremely efficient, and there is not enough that I can doto thank them for their contribution. And finally, I am grateful toto E.M.H. for suggesting this book and her reminder that it shouldhave been completed long ago.

In further editions, I hope to make this resemble aproper scientific text. That will require thorough references andproper arguments instead of oblique mentions and assertions offact. To that end, I am happy to receive your corrections,references, and suggestions regarding any of the material in hereat algorithmist@hotmail.com .

For both sides of an interview there is an art. Theart is at its best when, at the end of an hour, both parties leavethe interview feeling they have spent a productive hour. For theinterviewer, it is asking a challenging but tractable question andworking with the candidate to find an optimal solution. It ismaking the candidate feel welcome, valued, and excited to beoffered an opportunity to work alongside others who have a passionfor technology. And it is being comfortable in the decision to givethe candidate a hire or no hire decision.