Programming Problems in Ruby

_______________________________________________________

Programming Problems in Ruby

A Primer for the Technical Interview

__________________

Jason Brewer and Bradley Green

Copyright 2013 Bradley Green and Jason Brewer

Smashwords Edition

Preface

This book is based on Programming Problems, by Bradley Green. When he approached me about converting it to Ruby, I was very interested - I feel that Ruby’s simplicity and readability make it ideal for reviewing and understanding algorithms.

After graduating college, Microsoft hired me as a Software Developer. This was great for me, because I had very little formal training in software. It was, however, difficult for me to switch jobs - while my team at Microsoft had been willing to take a chance for me, it was still difficult for me to prove myself in software interviews. Eventually, when I finally wanted to change jobs, I had to study extensively - books on algorithms, practiced interviews. I finally went through interviews with Google, Microsoft and Facebook. These covered a lot of ground, much of which I had just learned recently.

This is my attempt at producing the study guide I wish I’d had when preparing for interviews.

I realize now that being able to interview well is a fundamental skill for software developers. The skills I learned practicing for my interviews have made my work more discipline, they’ve lowered my stress level, since now I can switch jobs more easily, and they have helped me do a better job hiring other developers, since I have a better understanding of how important some algorithms and knowledge of them can be.

As with the original, this book is intended as a refresher for seasoned engineers and a handbook for college students and new candidates. In future editions, the references in this book should 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 with Ruby 1.9.2 and passes some basic test cases.

.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 in Ruby

Ruby is not used very widely in much of industry - C/C++ and Java tend to dominate. Despite this, Ruby has earned itself a wide following for being straightforward, easy to use, and powerful. Ruby has the additional advantages of being concise and readable. Given this, I feel it to be a useful language even for developers not looking to work in Ruby, because it reads a lot like pseudocode. One can learn an algorithm quickly, and write it in another language if necessary during the interview.

In some places, I have not written optimally concise Ruby, instead favoring constructs that translate well to other languages and are hopefully easier to understand. Where it helps make code cleaner, I have encapsulated broader concepts and data structures within classes, but many helper functions I have left as plain functions. In general, I have tried to keep the code as readable as possible. I do use Ruby standard library functions and classes including arrays and hashes freely.

.3 Acknowledgements - Bradley Green

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 E.M.H. for suggesting this book and her reminder that it should have been completed long ago.

.4 Acknowledgements - Jason Brewer

I would like to thank my parents, Anne and Glen, for kindling my passion for computers, and teaching me to never stop wondering. I want to thank Jennifer for her support, advice, and her contribution of wonderful cover art.

I also want to thank Bradley Green for mentoring me and giving me the opportunity to work with him writing this book.

.5 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 [email protected].

Chapter 1

The Technical Interview

For both sides of an interview there is an art. The art is at its best when, at the end of an hour, both parties leave the interview feeling they have spent a productive hour. For the interviewer, it is asking a challenging but tractable question and working with the candidate to find an optimal solution. It is making the candidate feel welcome, valued, and excited to be offered an opportunity to work alongside others who have a passion for technology. And it is being comfortable in the decision to give the candidate a hire or no hire decision.

But of course the candidate has a more complicated role. Even so it is simple to state what must be done; one must be friendly, be straightforward, and know your fundamentals. There is not much else you can do to prepare for an interview.

The main purpose of this book is to provide a refresher for the fundamentals of programming that come up in technical interviews. We do this by presenting interview questions that have been asked in the field, and answering them in as much completeness as will be required by any technical interview. We strive to provide a number of solutions to each question, in order that the reader can understand the difference between a bad and good solution.

1.1 An overview

There is no secret recipe to acing an interview or