222 Pages·2016·22.04 MB·English

Save to my drive

Quick download

Download

A l g o r i t h m s I n t e r v i e w s ML1 ••' F * s W ;Af<t * r«r t Adnan Aziz Amit Prakash Algorithms For Interviews AProblem SolvingApproach AdrianAziz AmitPrakash algorithmsforinterviews.com AdnanAzizisaprofessorattheDepartmentofElectricalandComputer EngineeringatTheUniversityofTexas atAustin,whereheconductsre search and teaches classes inapplied algorithms. Hereceived hisPhD fromTheUniversityofCaliforniaatBerkeley;hisundergraduatedegree isfromIITKanpur. HehasworkedatGoogle,Qualcomm,IBM,andsev eralsoftwarestartups. Whennotdesigningalgorithms,heplayswithhis children,Laila,Imran,and Omar. Amit Prakash is aMember of the Technical Staff atGoogle, where he works primarilyonmachine learningproblems thatarise inthecontext ofonline advertising. Priortothatheworked atMicrosoft in theweb searchteam. HereceivedhisPhDfromTheUniversityofTexasatAustin; hisundergraduatedegreeisfromIITKanpur. Whenheisnotimproving thequalityofads,heindulgesinhispassionsforpuzzles,movies,travel, andadventureswithhiswife. All rights reserved. No part of this publication may be reproduced, storedinaretrievalsystem,ortransmitted,inanyform,orbyanymeans^ electronic, mechanical, photocopying, recording, orotherwise, without the priorconsentoftheauthors. This book was typeset by the authors using Lesley Lamport's ETEXdocument preparation systemand Peter Wilson's Memoir class. Thecoverdesignwasdone usingInkscape. MacOSaiXwasusedtocre ate the front cover image; itapproximates Shela Nye's portrait ofAlan Turing using acollection ofpublic domain images offamous computer scientists andmathematicians. The graphic onthebackcover wascre atedby NidhiRohatgi. Thecompanionwebsiteforthebookincludesalistofknownerrorsfor each version of the book. If you come across atechnical error, please writeto us and we willcheerfully sendyou $0.42. Please referto the websitefor details. Version1.0.0(September1,2010) Website:http://algorithmsforinterviews.com ISBN: 1453792996 EAN-13: 9781453792995 To myfather, IshratAziz,forgiving me my lifelong love of learning Adrian Aziz To my parents,Manju ShreeandArun Prakash, the most loving parents Ican imagine AmitPrakash Table of Contents Prologue •1 Problem Solving Techniques •5 I Problems 13 1 Searching•14 2 Sorting •23 3 Meta-algorithms •29 4 Algorithms on Graphs•41 5 Algorithmson Strings •52 6 Intractability- 56 7 Parallel Computing-62 8 Design Problems •67 9 Discrete Mathematics •73 10 Probability •80 11 Programming- 88 II The Interview 99 12 Strategies For A Great Interview•100 13 Conducting An Interview •105 VI TABLEOFCONTENTS III Solutions 109 1 Searching•110 2 Sorting. 123 3 Meta-algorithms-130 4 Algorithms on Graphs•144 5 Algorithms onStrings•156 6 Intractability-160 7 Parallel Computing•167 8 Design Problems •174 9 Discrete Mathematics •186 10 Probability-194 11 Programming•206 Index of Problems•212 Prologue Let'sbeginwith the picture onthe front cover. Youmayhave observed thattheportraitofAlanTuringisconstructedfrom anumberofpictures ("tiles") ofgreatcomputerscientistsandmathematicians. Suppose you were asked in an interview to design aprogram that takesanimageandacollectionofsxs-sizedtilesandproduceamosaic from thetiles thatresembles theimage. Agoodwaytobeginmaybeto partition the image into 5xs-sized squares, compute the average color of each such image square, and then find the tile that isclosest toitin the color space. Here distance in color spacecanbe L2-norm over Red- Green-Blue (RGB)intensitiesfor thecolor. Asyoulookmorecarefullyat the problem, you might conclude that itwouldbebetter to match each tile with an image square that has asimilar structure. One way could betoperformacoarsepixelization (2 x2or3x3) ofeachimagesquare andfindingthetilethatis"closest"totheimagesquareunderadistance X £AN WRITE I CAN SORT I INVENTED rtot-ttPucvnoN coj>ethatsays A N6W MOfcfcL CAN BE POKE *H£UOUlORLt>M OFCOtnPUTAT»0N AS A SERIES OP SWft AN> A» OPERATIONS TO MY AU»OS TOUCH £VERY PACKET OH TME INTERNET YOU ARF SOMEWHERE X WRITE OS KtM£iS H£RE POR. BREAKPAST Figure1.Evolutionofacomputerscientist function defined over all pixel colors (for example, L2-norm over RGB values for each pixel). Depending on how you represent the tiles, you endupwiththeproblemoffinding theclosestpointfrom asetofpoints in a/c-dimensionalspace. Ifthere are mtiles and the image is partitioned into nsquares, then abrute-forceapproachwouldhave 0(rri'n) timecomplexity. Youcould improve on this by first indexing the tiles using an appropriate search tree. Amore detailed discussion onthis approach ispresented inProb lem8.1 anditssolution. Ifina45-60minuteinterview,youcanworkthroughtheaboveideas, write some pseudocode for your algorithm, and analyze its complex ity, youwouldhavehad afairly successfulinterview. Inparticular, you would have demonstrated to yourinterviewer thatyoupossess several keyskills: - Theabilitytorigorouslyformulate real-worldproblems. - Theskillstosolveproblemsanddesignalgorithms. - Thetools togofromanalgorithmtoaworkingprogram. - Theanalyticaltechniquesrequiredtodeterminethecomputational complexityofyoursolution. BookOverview Algorithmsfor Interviews (AFI) aims tohelp engineersinterviewingfor software developmentpositions. Theprimaryfocus ofAFIis algorithm design. Theentirebookispresentedthroughproblemsinterspersedwith discussions. The problems cover key concepts and are well-motivated, challenging,and fun tosolve. We do not emphasize platforms and programming languages since they differ across jobs, and can be acquired fairly easily. Interviews at mostlargesoftwarecompaniesfocus moreonalgorithms,problemsolv ing, and design skills than on specific domain knowledge. Also, plat forms andprogramminglanguages canchangequicklyas requirements changebutthequalitiesmentionedabovewillalwaysbefundamentalto anysuccessfulsoftwareendeavor. The questions we present should all be solvable within a one hour interview and inmany cases, take substantially less time. Aquestion maytake more orless time tocomplete, depending ontheamount of codingthatis askedfor. Oursolutionsvaryintermsofdetail—forsomeproblemswepresent detailed implementations in Java/C++/Python; for others, we simply sketch solutions. Some use fairly technical machinery, e.g., max-flow, randomized analysis, etc. Youwillencountersuchproblems onlyifyou PROLOGUE 3 claimspecializedknowledge, e.g., graphalgorithms, complexitytheory, etc. Interviewing is about more than being able to design algorithms quickly. You alsoneed to knowhow to presentyourself, how to askfor helpwhenyouare stuck,howto comeacross asbeingexcitedaboutthe company, and knowingwhatyoucando for them. We discuss thenon technical aspects of interviewing inChapter 12. You can practice with friends orbyyourself; ineithercase,besuretotimeyourself. Interview atas many places as you can without ittaking away from your job or classes. The experience will help you and you may discover you like companiesthatyoudidnotknowmuchabout. Although an interviewer may occasionally ask a question directly from AFI, you should not base your preparation on memorizing solu tions from AFI. We sincerelyhope thatreading thisbookwillbeenjoy able and improveyour algorithmdesignskills. Theend goalis to make youabetterengineeraswellasbetterpreparedfor softwareinterviews. Level and Prerequisites MostofAFIrequiresitsreaderstohavebasicfamiliaritywithalgorithms taught in atypical undergraduate-level algorithms class. The chapters on meta-algorithms, graphs, and intractability use more advanced ma chineryandmayrequireadditionalreview. Eachchapterbeginswithareviewofkeyconcepts. Thisreviewisnot meanttobecomprehensiveandifyouarenotfamiliarwiththematerial, you should first study the correspondingchapterinan algorithms text book. Thereare dozens ofsuchtexts andourpreferenceisto masterone ortwo goodbooksratherthansuperficiallysamplemany. We likeAlgo rithms byDasgupta, Papadimitriou, and Vazirani because itissuccinct andbeautifullywritten;IntroductiontoAlgorithmsbyCormen,Leiserson, Rivest,andSteinismoredetailedandservesasagoodreference. Sinceourfocus isonproblemsthatcanbesolvedinaninterviewrel atively completely, there are many elegant algorithm design problems whichwedonotinclude. Similarly,wedonothaveanystraightforward review-type problems; you may want tobrushuponthese using intro ductoryprogrammingand data-structurestexts. Thefield ofalgorithmsisvastandtherearemanyspecializedtopics, such ascomputational geometry, numerical analysis, logic algorithms, etc. Unlessyouclaimknowledgeofsuchtopics,itishighlyunlikelythat you willbeasked aquestionwhichrequires esoteric knowledge. While aninterviewproblemmayseemspecializedatfirstglance,itisinvariably thecasethatthebasic algorithms described inthisbookaresufficientto solveit. Acknowledgments The problems in this book come from diverse sources—our own expe riences, colleagues, friends, papers,books, Internetbulletinboards, etc. ToparaphrasePaulHalmosfromhiswonderfulbookProblemsforMath ematicians, Youngand Old: "Idonotgivecredits—whodiscoveredwhat? Who was first? Whose solutionis thebest? Itwould notbe fair to give creditinsomecasesandnotinothers.Nooneknowswhodiscoveredthe theoremthatbearsPythagoras'nameanditdoesnotmatter. Thebeauty ofthe subjectspeaks foritselfand sobeit." Onepersonwhosehelpandsupporthasimprovedthequalityofthis book and made itfun to read is our cartoonist, editor, and proofreader, Nidhi Rohatgi. Several of our friends and students gave feedback on thisbook—wewould especiallylike tothankIanVarley, whowrote so lutionstoseveralproblems,andSenthilChellappan,GayatriRamachan- dran,andAlperSenforproofreadingseveralchapters. Webothwanttothankallthepeoplewhohavebeenasourceofen lightenmentandinspirationtousthroughtheyears. I,AdnanAziz, wouldlike tothankteachers, friends, and students from IIT Kanpur, UC Berkeley, and UT Austin. Iwould especially like to thank my friends Vineet Gupta and Vigyan Singhal, and my teach ersRobertSolovay, RobertBrayton,Richard Karp,Raimund Seidel,and Somenath Biswas for introducingme to the joys of algorithms. My co author,AmitPrakash,hasbeenawonderfulcollaborator—thisbookisa testament tohisintellect,creativity,andenthusiasm. I, Amit Prakash, have myco-author and mentor, AdnanAziz, to thankthemostforthisbook. Toagreatextent,myproblemsolvingskills have been shaped by Adnan. Therehave been occasionsin lifewhen Iwould nothave made through without hishelp. Heisalso thebest possiblecollaboratorIcanthinkofforanyintellectualendeavor. Over theyears, Ihave been fortunate tohave great teachers at IIT KanpurandUTAustin. IwouldespeciallyliketothankProfessorsScott Nettles, VijayaRamachandran, and Gustavo de Veciana. I would also like tothank myfriends andcolleagues atGoogle, Microsoft, andUT Austin for all the stimulating conversations and problem solving ses sions. Lastlyandmostimportantly,Iwanttothankmyfamilywhohave beenaconstantsourceofsupport,excitement,andjoyfor allmylifeand especiallyduringtheprocessofwritingthisbook. AdnanAziz adnanOalgorithmsforinterviews.com AmitPrakash amitOalgorithmsforinterviews.com

×