Adnan Aziz - Elements of Programming Interviews: The Insiders Guide

This document is a sampling of our book, Elements of ProgrammingInterviews in Python (EPI). Its purpose is to provide examples ofEPIs organization, content, style, topics, and quality. The samplerfocuses solely on problems; in particular, it does not include threechapters on the nontechnical aspects of interviewing. Wed love tohear from youwere especially interested in your suggestions asto where the exposition can be improved, as well as any insightsinto interviewing trends you may have.

You can buy EPI Python at Amazon.com (paperback). http://ElementsOfProgrammingInterviews.com

Adnan Aziz is a Research Scientist at Facebook. Previously, he was a professor at the Departmentof Electrical and Computer Engineering at The University of Texas at Austin, where he conductedresearch and taught classes in applied algorithms. He received his Ph.D. from The University ofCalifornia 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 designingalgorithms, he plays with his children, Laila, Imran, and Omar.

Tsung-Hsien Lee is a Senior Software Engineer at Uber.Previously, he worked as a SoftwareEngineer at Google and as Software Engineer Intern at Facebook. He received both his M.S. andundergraduate degrees from National Tsing Hua University. He has a passion for designing andimplementing algorithms. He likes to apply algorithms to every aspect of his life. He takes specialpride in helping to organize Google Code Jam 2014 and 2015.

Amit Prakashis a co-founder and CTO of ThoughtSpot, a Silicon Valley startup. Previously, he was aMember of the Technical Staff at Google, where he worked primarily on machine learning problemsthat arise in the context of online advertising. Before that he worked at Microsoft in the web searchteam. He received his Ph.D. from The University of Texas at Austin; his undergraduate degree isfrom Indian Institutes of Technology Kanpur. When he is not improving business intelligence, heindulges in his passion for puzzles, movies, travel, and adventures with Nidhi and Aanya.

Elements of Programming Interviews: The Insiders Guideby Adnan Aziz, Tsung-Hsien Lee, and Amit PrakashCopyright 2017 Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. All rights reserved.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in anyform, or by any means, electronic, mechanical, photocopying, recording, or otherwise, without theprior consent of the authors.

The views and opinions expressed in this work are those of the authors and do not necessarilyreflect the official policy or position of their employers.We typeset this book using LATEX and the Memoir class. We used TikZ to draw figures. Allan Ytaccreated the cover, based on a design brief we provided.The companion website for the book includes contact information and a list of known errors foreach version of the book. If you come across an error or an improvement, please let us know.Website: http://elementsofprogramminginterviews.comDistributed under the Attribution-NonCommercial-NoDerivs 3.0 License
i 11.1Test if a binary tree satisfies the BST property .....................56

Chapter Representation is the essence of programming.
The Mythical Man Month,F. P. Brooks, 1975

A program updates variables in memory according to its instructions. Variables come in typesatype is a classification of data that spells out possible values for that type and the operations thatcan be performed on it. A type can be provided by the language or defined by the programmer. InPython everything is an objectthis includes Booleans, integers, characters, etc.

Primitive types boot camp

Writing a program to count the number of bits that are set to 1 in an integer is a good way to getup to speed with primitive types. The following program tests bits one-at-a-time starting with theleast-significant bit. It illustrates shifting and masking; it also shows how to avoid hard-coding thesize of the integer word.

def count_bits(x):
num_bits = 0
while x:

num_bits += x & 1
x >>= 1
return num_bits

Since we performO(1) computation per bit, the time complexity isO(n), where n is the number ofbits needed to represent the integer, e.g., 4 bits are needed to represent 12, which is (1100)2 in binary.The techniques in Solution 1.1 on the facing page , which is concerned with counting the number ofbits modulo 2, i.e., the parity, can be used to improve the performance of the program given above.

Know your primitive typesPython has a number of build-in types: numerics (e.g., integer), sequences (e.g., list), mappings(e.g., dict), as well as classes, instances and exceptions. All instances of these types are objects.

Integers in Python3 are unboundedthe maximum integer representable is a function of theavailable memory. The constantsys.maxsize can be used to find the word-size; specifically, itsthe maximum value integer that can be stored in the word, e.g.,2**63 - 1 on a 64-bit machine.Bounds on floats are specified insys.float_info.

Be very familiar with the bit-wise operators such as6&4,1|2,8>>1,-16>>>2,1<<10,0,15x.Negative numbers are treated as their 2s complement value.(There is no concept of anunsigned shift in Python, since integers have infinite precision.)

Be very comfortable with the bitwise operators, particularly XOR.Understand how to use masks and create them in an machine independent way.Know fast ways to clear the lowermost set bit (and by extension, set the lowermost 0, get itsindex, etc.)Understand signedness and its implications to shifting.Consider using a cache to accelerate operations by using it to brute-force small inputs.Be aware that commutativity and associativity can be used to perform operations in paralleland reorder operations. Table 1.1: Top Tips for Primitive Types

The key methods for numeric types areabs(-34.5),math.ceil(2.17),math.floor(3.14),min(x,-4),max(3.14, y),pow(2.71, 3.14)(alternately,2.71 ** 3.14),andmath.sqrt(225).
Know how to interconvert integers and strings, e.g.,str(42), int(42), floats and strings,e.g.,str(3.14), float(3.14).
Unlike integers, floats are not infinite precision, and its convenient to refer to infinity asfloat(inf) andfloat(-inf). These values are comparable to integers, and can be usedto create psuedo max-int and pseudo min-int.
When comparing floating point values consider using math.isclose()it is robust, e.g.,when comparing very large values, and can handle both absolute and relative differences.
Thekeymethodsin randomare random.randrange(28), random.randint(8,16),random.random(),random.shuffle(A), andrandom.choice(A).

1.1Computing the parity of a word

The parity of a binary word is 1 if the number of 1s in the word is odd; otherwise, it is 0.Forexample, the parity of 1011 is 1, and the parity of 10001000 is 0. Parity checks are used to detectsingle bit errors in data storage and communication. It is fairly straightforward to write code thatcomputes the parity of a single 64-bit word.

How would you compute the parity of a very large number of 64-bit words?
Hint: Use a lookup table, but dont use 264 entries!

Solution: The brute-force algorithm iteratively tests the value of each bit while tracking the numberof 1s seen so far. Since we only care if the number of 1s is even or odd, we can store the numbermodulo 2.

def parity(x):