Elements of Programming Interviews - Computer Science

1 ElementsofProgrammingInterviewsThe Insiders GuideAdnan AzizTsung-Hsien LeeAmit PrakashThis document is a sampling of our book, Elements ofProgramming Interviews (EPI). Its purpose is to provideexamples of EPI s organization, content, style, topics, andquality. The sampler focuses solely on problems; in par-ticular, it does not include three chapters on the nontech-nical aspects of interviewing. We d love to hear fromyou we re especially interested in your suggestions asto where the exposition can be improved, as well as anyinsights into interviewing trends you may can buy EPI with Azizis a professor at the Department of Electrical and Computer Engineeringat The University of Texas at Austin, where he conducts research and teaches classesin applied algorithms.

2 He received his from The University of California atBerkeley; his undergraduate degree is from Indian Institutes of Technology has worked at Google, Qualcomm, IBM, and several software startups. Whennot designing algorithms, he plays with his children, Laila, Imran, and Leeis a Software Engineer at Google. Previously, he worked as aSoftware Engineer Intern at Facebook. He received both his and undergraduatedegrees from National Tsing Hua University. He has a passion for designing andimplementing algorithms.

3 He likes to apply algorithms to every aspect of his takes special pride in helping to organize Google Code Jam Prakashis a co-founder and CTO of ThoughtSpot, a Silicon Valley , he was a Member of the Technical Staffat Google, where he worked pri-marily on machine learning problems that arise in the context of online that he worked at Microsoft in the web search team. He received his The University of Texas at Austin; his undergraduate degree is from IndianInstitutes of Technology Kanpur. When he is not improving business intelligence, heindulges in his passion for puzzles, movies, travel, and adventures with Nidhi of Programming Interviews : The Insiders Guideby Adnan Aziz, Tsung-Hsien Lee, and Amit PrakashCopyright 2014 Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

4 All part of this publication may be reproduced, stored in a retrieval system, ortransmitted, in any form, or by any means, electronic, mechanical, photocopying,recording, or otherwise, without the prior consent of the views and opinions expressed in this work are those of the authors and do notnecessarily reflect the official policy or position of their typeset this book using LATEX and the Memoir class. We used TikZ to draw Ytac created the cover, based on a design brief we companion website for the book includes contact information and a list of knownerrors for each version of the book.

5 If you come across an error or an improvement,please let us : under the Attribution-NonCommercial-NoDerivs LicenseTable of ContentsI Problems11 Primitive base ..22 the max difference ..33 strings and integers .. all the words in a sentence ..44 Linked for cyclicity ..65 Stacks and a stack with max API .. a binary tree in order of increasing depth ..86 Binary if a binary tree is balanced ..117 sorted files ..128 a sorted array for first occurrence ofk..159 Hash if an anonymous letter is constructible.

6 1710 the intersection of two sorted arrays ..1911 Binary Search if a binary tree satisfies the BST property ..2012 the power set ..2213 Dynamic the number of ways to traverse a 2D array ..2614 Greedy Algorithms and 3-sum problem ..2715 a Boolean matrix ..3116 Parallel a Timer class ..3317 Design a system for detecting copyright infringement ..36II Hints37 III Solutions39IV Notation and Index65 Index of Terms68 Part IProblemsChapter1 Primitive TypesRepresentation is the essence of Programming .

7 The Mythical Man Month, F. P. Brooks, 1975A program updates variables in memory according to its instructions. The variablesare classified according to their type a type is a classification of data that spells outpossible values for that type and the operations that can be performed on can be primitive, , provided by the language, or defined by the program-mer. The set of primitive types depends on the language. For example, the primitivetypes in C++arebool,char,short,int,long,float, anddouble; integer types andchars have unsigned versions too.

8 The primitive types in Java areboolean,char,byte,short,int,long,floa t, anddouble. A programmer can define a complexnumber type as a pair of doubles, one for the real and one for the imaginary width of a primitive-type variable is the number of bits of storage it takes inmemory. For example, most implementations of C++use 32 or 64 bits for anint. InJava anintis always 32 involving manipulation of bit-level data are often asked in is easy to introduce errors in code that manipulates bit-level data when you playwith bits, expect to get Convert baseIn the decimal system, the position of a digit is used to signify the power of 10 thatdigit is to be multiplied with.

9 For example, 314 denotes the number 3 100+1 10+4 1.(Note that zero, which is not needed in other systems, is essential in the decimalsystem, since a zero can be used to skip a power.) The basebnumber systemgeneralizes the decimal number system: the string ak 1ak , where 0 ai<b,denotes in base-bthe integera0 b0+a1 b1+a2 b2+ +ak 1 bk : Write a function that performs base conversion. Specifically, the inputis an integer baseb1, a strings, representing an integerxin baseb1, and anotherinteger baseb2; the output is the string representing the integerxin baseb2.

10 Assume2 b1,b2 16. Use A to represent 10, B for 11,.., and F for 402 Chapter2 ArraysThe machine can alter the scanned symbol and its behavioris in part determined by that symbol, but the symbols on thetape elsewhere do not affect the behavior of the machine. Intelligent Machinery, A. M. Turing, 1948 The simplest data structure is thearray, which is a contiguous block of an arrayAwhich holdsnobjects,A[i] denotes the (i+1)-th object stored in thearray. Retrieving and updatingA[i] takesO(1) time.