دانلود کتاب 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