Elements
           of
           Programming
           Interviews in Python
           TheInsiders’ Guide
           AdnanAziz
           Tsung-HsienLee
           AmitPrakash
            Thisdocumentisasamplingofourbook,ElementsofProgramming
            Interviews in Python (EPI). Its purpose is to provide examples of
            EPI’s organization, content, style, topics, and quality. The sampler
            focuses solely on problems; in particular, it does not include three
            chapters on the nontechnical aspects of interviewing. We’d love to
            hear from you—we’re especially interested in your suggestions as
            to where the exposition can be improved, as well as any insights
            into interviewing trends you may have.
              YoucanbuyEPIPythonatAmazon.com(paperback).
           http://ElementsOfProgrammingInterviews.com
       AdnanAzizisaResearchScientist at Facebook. Previously, he was a professor at the Department
       of Electrical and Computer Engineering at The University of Texas at Austin, where he conducted
       research and taught classes in applied algorithms. He received his Ph.D. from The University of
       California at Berkeley; his undergraduate degree is from Indian Institutes of Technology Kanpur.
       He has worked at Google, Qualcomm, IBM, and several software startups. When not designing
       algorithms, he plays with his children, Laila, Imran, and Omar.
       Tsung-Hsien Lee is a Senior Software Engineer at Uber. Previously, he worked as a Software
       Engineer at Google and as Software Engineer Intern at Facebook. He received both his M.S. and
       undergraduate degrees from National Tsing Hua University. He has a passion for designing and
       implementingalgorithms. Helikes to apply algorithms to every aspect of his life. He takes special
       pride in helping to organize Google Code Jam 2014 and 2015.
       AmitPrakashisaco-founderandCTOofThoughtSpot,aSiliconValleystartup. Previously,hewasa
       MemberoftheTechnicalStaffatGoogle,whereheworkedprimarilyonmachinelearningproblems
       that arise in the context of online advertising. Before that he worked at Microsoft in the web search
       team. He received his Ph.D. from The University of Texas at Austin; his undergraduate degree is
       from Indian Institutes of Technology Kanpur. When he is not improving business intelligence, he
       indulges in his passion for puzzles, movies, travel, and adventures with Nidhi and Aanya.
       ElementsofProgrammingInterviews: TheInsiders’Guide
       byAdnanAziz,Tsung-HsienLee,andAmitPrakash
       Copyright©2017AdnanAziz,Tsung-HsienLee,andAmitPrakash. Allrightsreserved.
       Nopartofthispublication may be reproduced, stored in a retrieval system, or transmitted, in any
       form, or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the
       prior consent of the authors.
       The views and opinions expressed in this work are those of the authors and do not necessarily
       reflect the official policy or position of their employers.
                               A
       Wetypesetthis book using LT X and the Memoir class. We used TikZ to draw figures. Allan Ytac
                                E
       created the cover, based on a design brief we provided.
       The companion website for the book includes contact information and a list of known errors for
       eachversionofthebook. Ifyoucomeacrossanerrororanimprovement,pleaseletusknow.
       Website: http://elementsofprogramminginterviews.com
       Distributed under the Attribution-NonCommercial-NoDerivs 3.0 License
                               TableofContents
               I        DataStructuresandAlgorithms                                                                                                                                        1
               1     Primitive Types                                                                                                                                                       2
                     1.1         Computingtheparityofaword . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                       3
               2     Arrays                                                                                                                                                                7
                     2.1         TheDutchnationalflagproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                        9
               3     Strings                                                                                                                                                             13
                     3.1         Interconvert strings and integers . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                               14
                     3.2         Baseconversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                              15
               4     LinkedLists                                                                                                                                                         17
                     4.1         Test for cyclicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                          19
               5     Stacks and Queues                                                                                                                                                   21
                     5.1         ImplementastackwithmaxAPI . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                       22
                     5.2         Computebinarytreenodesinorderofincreasingdepth . . . . . . . . . . . . . . .                                                                            26
               6     BinaryTrees                                                                                                                                                         28
                     6.1         Test if a binary tree is height-balanced . . . . . . . . . . . . . . . . . . . . . . . . .                                                              30
               7     Heaps                                                                                                                                                               33
                     7.1         Mergesortedfiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                               35
               8     Searching                                                                                                                                                           37
                     8.1         Search a sorted array for first occurrence of k . . . . . . . . . . . . . . . . . . . . .                                                                39
               9     HashTables                                                                                                                                                          42
                     9.1         Is an anonymousletter constructible?                                  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . . . .            46
               10 Sorting                                                                                                                                                                48
                     10.1        Computetheintersectionoftwosortedarrays . . . . . . . . . . . . . . . . . . . .                                                                         50
                     10.2        Renderacalendar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                               51
               11 BinarySearchTrees                                                                                                                                                      54
                                                                                                     i
                     11.1        Test if a binary tree satisfies the BST property . . . . . . . . . . . . . . . . . . . . .                                                               56
               12 Recursion                                                                                                                                                              59
                     12.1        Generatethepowerset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                 60
               13 DynamicProgramming                                                                                                                                                     63
                     13.1        Countthenumberofwaystotraversea2Darray . . . . . . . . . . . . . . . . . . .                                                                            65
               14 GreedyAlgorithmsandInvariants                                                                                                                                          69
                     14.1        The3-sumproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                 71
               15 Graphs                                                                                                                                                                 73
                     15.1        Paint a Boolean matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                              76
               16 Parallel Computing                                                                                                                                                     78
                     16.1        ImplementaTimerclass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                  80
               II DomainSpecificProblems                                                                                                                                                  81
               17 DesignProblems                                                                                                                                                         82
                     17.1        Designasystemfordetectingcopyrightinfringement . . . . . . . . . . . . . . . .                                                                          83
               18 LanguageQuestions                                                                                                                                                      85
                     18.1        Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                           85
                     18.2        Shallowanddeepcopy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                  85
               19 Object-Oriented Design                                                                                                                                                 87
                     19.1        Creational Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                             87
               20 CommonTools                                                                                                                                                            89
                     20.1        Merginginaversioncontrolsystem . . . . . . . . . . . . . . . . . . . . . . . . . .                                                                      89
               III The Honors Class                                                                                                                                                      93
               21 HonorsClass                                                                                                                                                            94
                     21.1        Computethegreatestcommondivisor                                             .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .   .  .        95
                     21.2        Computethemaximumproductofallentriesbutone                                                             .  .  .  .  .  .  .  .  .  .  .  .   .  .        96
               IV NotationandIndex                                                                                                                                                       99
               Notation                                                                                                                                                                100
               IndexofTerms                                                                                                                                                            102