Elements of Programming Interviews in Python: The Insiders’ Guide

Cover
Title page
Table of Contents
Introduction
I The Interview
	1 Getting Ready
	2 Strategies For A Great Interview
	3 Conducting An Interview
II Data Structures and Algorithms
	4 Primitive Types
		4.1 Computing the parity of a word
		4.2 Swap bits
		4.3 Reverse bits
		4.4 Find a closest integer with the same weight
		4.5 Compute x*y without arithmetical operators
		4.6 Compute x/y
		4.7 Compute x^y
		4.8 Reverse digits
		4.9 Check if a decimal integer is a palindrome
		4.10 Generate uniform random numbers
		4.11 Rectangle intersection
	5 Arrays
		5.1 The Dutch national flag problem
		5.2 Increment an arbitrary-precision integer
		5.3 Multiply two arbitrary-precision integers
		5.4 Advancing through an array
		5.5 Delete duplicates from a sorted array
		5.6 Buy and sell a stock once
		5.7 Buy and sell a stock twice
		5.8 Computing an alternation
		5.9 Enumerate all primes to n
		5.10 Permute the elements of an array
		5.11 Compute the next permutation
		5.12 Sample offline data
		5.13 Sample online data
		5.14 Compute a random permutation
		5.15 Compute a random subset
		5.16 Generate nonuniform random numbers
		5.17 The Sudoku checker problem
		5.18 Compute the spiral ordering of a 2D array
		5.19 Rotate a 2D array
		5.20 Compute rows in Pascal’s Triangle
	6 Strings
		6.1 Interconvert strings and integers
		6.2 Base conversion
		6.3 Compute the spreadsheet column encoding
		6.4 Replace and remove
		6.5 Test palindromicity
		6.6 Reverse all the words in a sentence
		6.7 Compute all mnemonics for a phone number
		6.8 The look-and-say problem
		6.9 Convert from Roman to decimal
		6.10 Compute all valid IP addresses
		6.11 Write a string sinusoidally
		6.12 Implement run-length encoding
		6.13 Find the first occurrence of a substring
	7 Linked Lists
		7.1 Merge two sorted lists
		7.2 Reverse a single sublist
		7.3 Test for cyclicity
		7.4 Test for overlapping lists—lists are cycle-free
		7.5 Test for overlapping lists—lists may have cycles
		7.6 Delete a node from a singly linked list
		7.7 Remove the fcth last element from a list
		7.8 Remove duplicates from a sorted list
		7.9 Implement cyclic right shift for singly linked lists
		7.10 Implement even-odd merge
		7.11 Test whether a singly linked list is palindromic
		7.12 Implement list pivoting
		7.13 Add list-based integers
	8 Stacks and Queues
		8.1 Implement a stack with max API
		8.2 Evaluate RPN expressions
		8.3 Test a string over \"{,},(,),[,]\" for well-formedness
		8.4 Normalize pathnames
		8.5 Compute buildings with a sunset view
		8.6 Compute binary tree nodes in order of increasing depth
		8.7 Implement a circular queue
		8.8 Implement a queue using stacks
		8.9 Implement a queue with max API
	9 Binary Trees
		9.1 Test if a binary tree is height-balanced
		9.2 Test if a binary tree is symmetric
		9.3 Compute the lowest common ancestor in a binary tree
		9.4 Compute the LCA when nodes have parent pointers
		9.5 Sum the root-to-leaf paths in a binary tree
		9.6 Find a root to leaf path with specified sum
		9.7 Implement an inorder traversal without recursion
		9.8 Implement a preorder traversal without recursion
		9.9 Compute the k-th node in an inorder traversal
		9.10 Compute the successor
		9.11 Implement an inorder traversal with O(1) space
		9.12 Reconstruct a binary tree from traversal data
		9.13 Reconstruct a binary tree from a preorder traversal with markers
		9.14 Form a linked list from the leaves of a binary tree
		9.15 Compute the exterior of a binary tree
		9.16 Compute the right sibling tree
	10 Heaps
		10.1 Merge sorted files
		10.2 Sort an increasing-decreasing array
		10.3 Sort an almost-sorted array
		10.4 Compute the k closest stars
		10.5 Compute the median of online data
		10.6 Compute the k largest elements in a max-heap
	11 Searching
		11.1 Search a sorted array for first occurrence of k
		11.2 Search a sorted array for entry equal to its index
		11.3 Search a cyclically sorted array
		11.4 Compute the integer square root
		11.5 Compute the real square root
		11.6 Search in a 2D sorted array
		11.7 Find the min and max simultaneously
		11.8 Find the k-th largest element
		11.9 Find the missing IP address
		11.10 Find the duplicate and missing elements
	12 Hash Tables
		12.1 Test for palindromic permutations
		12.2 Is an anonymous letter constructive?
		12.3 Implement an ISBN cache
		12.4 Compute the LCA, optimizing for close ancestors
		12.5 Find the nearest repeated entries in an array
		12.6 Find the smallest subarray covering all values
		12.7 Find smallest subarray sequentially covering all values
		12.8 Find the longest subarray with distinct entries
		12.9 Find the length of a longest contained interval
		12.10 Compute all string decompositions
		12.11 Test the Collatz conjecture
		12.12 Implement a hash function for chess
	13 Sorting
		13.1 Compute the intersection of two sorted arrays
		13.2 Merge two sorted arrays
		13.3 Remove first-name duplicates
		13.4 Smallest nonconstructible value
		13.5 Render a calendar
		13.6 Merging intervals
		13.7 Compute the union of intervals
		13.8 Partitioning and sorting an array with many repeated entries
		13.9 Team photo day—1
		13.10 Implement a fast sorting algorithm for lists
		13.11 Compute a salary threshold
	14 Binary Search Trees
		14.1 Test if a binary tree satisfies the BST property
		14.2 Find the first key greater than a given value in a BST
		14.3 Find the k largest elements in a BST
		14.4 Compute the LCA in a BST
		14.5 Reconstruct a BST from traversal data
		14.6 Find the closest entries in three sorted arrays
		14.7 Enumerate numbers of the form a+b√2
		14.8 Build a minimum height BST from a sorted array
		14.9 Test if three BST nodes are totally ordered
		14.10 The range lookup problem
		14.11 Add credits
	15 Recursion
		15.1 The Towers of Hanoi problem
		15.2 Generate all nonattacking placements of n-Queens
		15.3 Generate permutations
		15.4 Generate the power set
		15.5 Generate all subsets of size k
		15.6 Generate strings of matched parens
		15.7 Generate palindromic decompositions
		15.8 Generate binary trees
		15.9 Implement a Sudoku solver
		15.10 Compute a Gray code
	16 Dynamic Programming
		16.1 Count the number of score combinations
		16.2 Compute the Levenshtein distance
		16.3 Count the number of ways to traverse a 2D array
		16.4 Compute the binomial coefficients
		16.5 Search for a sequence in a 2D array
		16.6 The knapsack problem
		16.7 The bedbathandbeyond.com problem
		16.8 Find the minimum weight path in a triangle
		16.9 Pick up coins for maximum gain
		16.10 Count the number of moves to climb stairs
		16.11 The pretty printing problem
		16.12 Find the longest nondecreasing subsequence
	17 Greedy Algorithms and Invariants
		17.1 Compute an optimum assignment of tasks
		17.2 Schedule to minimize waiting time
		17.3 The interval covering problem
		17.4 The 3-sum problem
		17.5 Find the majority element
		17.6 The gasup problem
		17.7 Compute the maximum water trapped by a pair of vertical lines
		17.8 Compute the largest rectangle under the skyline
	18 Graphs
		18.1 Search a maze
		18.2 Paint a Boolean matrix
		18.3 Compute enclosed regions
		18.4 Deadlock detection
		18.5 Clone a graph
		18.6 Making wired connections
		18.7 Transform one string to another
		18.8 Team photo day—2
	19 Parallel Computing
		19.1 Implement caching for a multithreaded dictionary
		19.2 Analyze two unsynchronized interleaved threads
		19.3 Implement synchronization for two interleaving threads
		19.4 Implement a thread pool
		19.5 Deadlock
		19.6 The readers-writers problem
		19.7 The readers-writers problem with write preference
		19.8 Implement a Timer class
		19.9 Test the Collatz conjecture in parallel
III Domain Specific Problems
	20 Design Problems
		20.1 Design a spell checker
		20.2 Design a solution to the stemming problem
		20.3 Plagiarism detector
		20.4 Pair users by attributes
		20.5 Design a system for detecting copyright infringement
		20.6 Design TeX
		20.7 Design a search engine
		20.8 Implement PageRank
		20.9 Design TeraSort and PetaSort
		20.10 Implement distributed throttling
		20.11 Design a scalable priority system
		20.12 Create photomosaics
		20.13 Implement Mileage Run
		20.14 Implement Connexus
		20.15 Design an online advertising system
		20.16 Design a recommendation system
		20.17 Design an optimized way of distributing large files
		20.18 Design the World Wide Web
		20.19 Estimate the hardware cost of a photo sharing app
	21 Language Questions
		21.1 Garbage Collection
		21.2 Closure
		21.3 Shallow and deep copy
		21.4 Iterators and Generators
		21.5 @decorator
		21.6 List vs tuple
		21.7 *args and *kwargs
		21.8 Python code
		21.9 Exception Handling
		21.10 Scoping
		21.11 Function arguments
	22 Object-Oriented Design
		22.1 Template Method vs. Strategy
		22.2 Observer pattern
		22.3 Push vs. pull observer pattern
		22.4 Singletons and Flyweights
		22.5 Adapters
		22.6 Creational Patterns
		22.7 Libraries and design patterns
	23 Common Tools
		23.1 Merging in a version control system
		23.2 Hooks
		23.3 Is scripting more efficient?
		23.4 Polymorphism with a scripting language
		23.5 Dependency analysis
		23.6 ANT vs. Maven
		23.7 SQLvs.NoSQL
		23.8 Normalization
		23.9 SQL design
		23.10 IP, TCP, and HTTP
		23.11 HTTPS
		23.12 DNS
IV The Honors Class
	24 Honors Class
		24.1 Compute the greatest common divisor *
		24.2 Find the first missing positive entry *
		24.3 Buy and sell a stock k times **
		24.4 Compute the maximum product of all entries but one *
		24.5 Compute the longest contiguous increasing subarray *
		24.6 Rotate an array *
		24.7 Identify positions attacked by rooks *
		24.8 Justify text *
		24.9 Implement list zipping *
		24.10 Copy a postings list *
		24.11 Compute the longest substring with matching parens *
		24.12 Compute the maximum of a sliding window *
		24.13 Implement a postorder traversal without recursion *
		24.14 Compute fair bonuses *
		24.15 Search a sorted array of unknown length *
		24.16 Search in two sorted arrays **
		24.17 Find the k-th largest element—large n, small k **
		24.18 Find an element that appears only once **
		24.19 Find the line through the most points *
		24.20 Convert a sorted doubly linked list into a BST **
		24.21 Convert a BST to a sorted doubly linked list *
		24.22 Merge two BSTs **
		24.23 Implement regular expression matching *
		24.24 Synthesize an expression *
		24.25 Count inversions *
		24.26 Draw the skyline *
		24.27 Measure with defective jugs *
		24.28 Compute the maximum subarray sum in a circular array *
		24.29 Determine the critical height *
		24.30 Find the maximum 2D subarray **
		24.31 Implement Huffman coding *
		24.32 Trapping water *
		24.33 The heavy hitter problem *
		24.34 Find the longest subarray whose sum ≤ k **
		24.35 Road network *
		24.36 Test if arbitrage is possible *
V Notation and Index
Notation
Index of Terms