Bradley Green - Programming Problems in Ruby

_______________________________________________________
Programming Problems inRuby
A Primer for the TechnicalInterview
__________________

Jason B rewer and Bradley G reen

Copyright 2013 Bradley Green and Jason Brewer

Smashwords Edition

This book is based on ProgrammingProblems, by Bradley Green. When he approached me about convertingit to Ruby , I wasvery interested - I feel that Ruby s simplicity and readability makeit ideal for reviewing and understanding algorithms.

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

This is my attempt at producing the study guide Iwish Id had when preparing for interviews.

I realize now that being able to interview well is afundamental skill for software developers. The skills I learnedpracticing for my interviews have made my work more discipline,theyve lowered my stress level, since now I can switch jobs moreeasily, and they have helped me do a better job hiring otherdevelopers, since I have a better understanding of how importantsome algorithms and knowledge of them can be.

As with the original, this book isintended as a refresher for seasoned engineers and a handbook forcollege students and new candidates. In future editions, thereferences in this book should be compiled into a bibliography. Forthe moment, I beg your forgiveness for not knowing where many ofthe techniques used here were first discovered. I have done my bestto ensure the code runs with Ruby1.9.2 and passes some basic testcases.

There are three main areas that I hope to cover inthis work: data structures, searching and sorting, and advancedalgorithms. The latter 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 mostly self-contained study guide on aspecific topic. Where necessary, Ive consumed basic algorithmsfrom prior chapters. I attempted to frame it so that complexityincreases throughout the chapter. The introductory material shouldbe simply refresher for anyone in the industry; middle sectionscontain interesting problems and revisions, and the finale aninteresting and complex problem. I hope that these problems givethe reader some pleasure in thinking about before continuing on tothe discussion of the answer.

Ruby is notused very widely in much of industry - C/C++ and Java tend to dominate. Despitethis, Ruby hasearned itself a wide following for being straightforward, easy touse, and powerful. Ruby has the additional advantages of beingconcise and readable. Given this, I feel it to be a useful languageeven for developers not looking to work in Ruby , because it reads a lot likepseudocode. One can learn an algorithm quickly, and write it inanother language if necessary during the interview.

In some places, I have not writtenoptimally concise Ruby , instead favoring constructs that translate well to otherlanguages and are hopefully easier to understand. Where it helpsmake code cleaner, I have encapsulated broader concepts and datastructures within classes, but many helper functions I have left asplain functions. In general, I have tried to keep the code asreadable as possible. I do use Ruby standard library functions and classes includingarrays and hashes freely.

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

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

I also want to thank Bradley Green for mentoring meand giving me the opportunity to work with him writing thisbook.

In further editions, I hope to makethis resemble a proper scientific text. That will require thoroughreferences and proper arguments instead of oblique mentions andassertions of fact. To that end, I am happy to receive yourcorrections, references, and suggestions regarding any of thematerial in here at 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.

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

The main purpose of this book is to provide arefresher for the fundamentals of programming that come up intechnical interviews. We do this by presenting interview questionsthat have been asked in the field, and answering them in as muchcompleteness as will be required by any technical interview. Westrive to provide a number of solutions to each question, in orderthat the reader can understand the difference between a bad andgood solution.

There is no secret recipe to acing an interview orsolving a programming problem. And even if you know yourfoundations, in the course of a tech career everyone will comeacross that interviewer who is annoyed at having to interview,suffering from an inferiority complex, and just plain determined togive you a no hire. But there are a number of things you can do toincrease the odds of getting a hire.

First, know what you are getting into. If you havenever interviewed before, then the section on the technicalinterview loop is the place to familiarize yourself with what willbe happening.

Second, turn the interview into a conversation. Taketurns speaking, ask real questions, and overall be honest. Honestywill make the discussion easier and more enjoyable for both sides.Of course in any technical interview you will be required topresent a solution to a coding question, but that will only beabout half the time. You can gauge your success by how long theinterviewer allows the conversation to run over.