Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

Discover millions of ebooks, audiobooks, and so much more with a free trial

From $11.99/month after trial. Cancel anytime.

Programming Problems: Advanced Algorithms
Programming Problems: Advanced Algorithms
Programming Problems: Advanced Algorithms
Ebook228 pages2 hours

Programming Problems: Advanced Algorithms

Rating: 3.5 out of 5 stars

3.5/5

()

Read preview

About this ebook

Self contained with problems completely worked out in clear, readable C++11, Volume II covers a wide swatch of advanced programming techniques. The sections range from specialized procedures for bit manipulation, numerical analysis, subsequence problems, and random algorithms. Each chapter gives an in excellent coverage of the topics by providing a wide array of problems and solutions. For both beginning programmers and senior engineers, this book is sure to provide you with more valuable insights and enjoyable challenges.

LanguageEnglish
PublisherBradley Green
Release dateMay 20, 2013
ISBN9781301643998
Programming Problems: Advanced Algorithms

Read more from Bradley Green

Related to Programming Problems

Related ebooks

Computers For You

View More

Related articles

Reviews for Programming Problems

Rating: 3.7142857142857144 out of 5 stars
3.5/5

7 ratings1 review

What did you think?

Tap to rate

Review must be at least 10 words

  • Rating: 4 out of 5 stars
    4/5
    good

Book preview

Programming Problems - Bradley Green

_______________________________________________________

Programming Problems

A Primer for The Technical Interview

__________________

Volume II: Advanced Algorithms 

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, I hope to make this resemble a proper scientific text. That will require thorough references and proper arguments instead of oblique mentions and assertions of fact. To that end, I am happy to receive your corrections, references, and suggestions regarding any of the material in here at algorithmist@hotmail.com.

Preface To The Second Volume

The second volume of Programming Problems has taken me longer to complete than originally promised. The date of late 2012 was a date I believed could be accomplished. However with the growth of my family and transitions at work, time moved faster than I ever thought it could.

I want to thank the many readers of the first volume for your comments and recommendations. I really enjoyed hearing from you, and hope I can continue my side of the dialog going forward.

To Ada, on her first birthday.

Chapter 1

Advanced Algorithms

A digest of advanced algorithms is hard to qualify. Topics that were advanced in the field many years ago may be taught at an elementary level today. What is advanced for the novice may be obvious to the expert. Across domains, an advanced technique in one specialization may be a simple application of the tools of another. The specification of being advanced is hence somewhat arbitrary, but we will try to be consistent in its application.

1.1 What comes next

In the first volume, we explored elementary abstract data structures and simple algorithmic applications of them to programming problems. We visited elementary algorithms that employed these data structures, such as searching, selection, and sorting. These were elementary not because they were simple but because of the generality of their application. We now shift our focus to specialized data structures used to solve specialized problem. It is not specialization that makes an algorithm advanced, but instead is the amount of information required to develop and understand the algorithm. And that information requirement makes advanced algorithms interesting.

There is a difference between elementary algorithms and naive algorithms. An elementary algorithm such as binary search or merge sort can be employed in almost universally. A naive algorithm may solve a specialized problem, but it is a solution to that uses the first workable approach without regard to time or space. In doing so it employs elementary algorithms mechanically. However with

Enjoying the preview?
Page 1 of 1