c0de_gr1nd

the pursuit of ameloriation as a programmer

Introduction

• This repository features my solutions and explanations to the problems presented in
  Elements of Programming Interviews in Python
• The book solutions and test framework are from EPI Judge

Usage

• Click the Title of the problem to view the problem description, example, solution, explanation, and code dissection
• Click the Solution of the problem to view the program that runs against the test cases in the EPI Judge

Sections

• Primitive Types
• Arrays
• Strings
• Linked Lists
• Stacks and Queues
• Binary Trees
• Heaps
• Searching
• Hash Tables
• Sorting
• Binary Search Trees
• Recursion
• Dynamic Programming
• Greedy Algorithms and Invariants
• Graphs
• Useful References

Primitive Types

#	Title	Solution	Time	Space
4.1	Computing the Parity of a Word	Python	O(1)	O(1)
4.2	Swap Bits	Python	O(1)	O(1)
4.3	Reverse Bits	Python	O(1)	O(1)
4.4	Find a Closest Integer with the Same Weight	Python	O(1)	O(1)
4.5	Compute x × y Without Arithmetical Operators	Python	O(logn)	O(1)
4.6	Compute x ∕ y	Python	O(logn)	O(1)
4.7	Compute x y	Python	O(logn)	O(1)
4.8	Reverse Digits	Python	O(logn)	O(1)
4.9	Check If a Decimal Integer Is a Palindrome	Python	O(logn)	O(1)
4.10	Generate Uniform Random Numbers	Python	O(logn)	O(1)
4.11	Rectangle Intersection	Python	O(1)	O(1)

Arrays

#	Title	Solution	Time	Space
5.1	The Dutch National Flag Problem	Python	O(n)	O(1)
5.2	Increment an Arbitrary-Precision Integer	Python	O(n)	O(1)
5.3	Multiply Two Arbitrary-Precision Integers	Python	O(mn)	O(m+n)
5.4	Advancing Through an Array	Python	O(n)	O(1)
5.5	Delete Duplicates from a Sorted Array	Python	O(n)	O(1)
5.6	Buy and Sell a Stock Once	Python	O(n)	O(1)
5.7	Buy and Sell a Stock Twice	Python	O(n)	O(n)
5.8	Computing an Alternation	Python	O(n)	O(1)
5.9	Enumerate All Primes to n	Python	O(nloglogn)	O(n)
5.10	Permute the Elements of an Array	Python	O(n)	O(n)
5.11	Compute the Next Permutation	Python	O(n)	O(1)
5.12	Sample Offline Data	Python	O(k)	O(1)
5.13	Sample Online Data	Python	O(n)	O(k)
5.14	Compute a Random Permutation	Python	O(n)	O(1)
5.15	Compute a Random Subset	Python	O(k)	O(k)
5.16	Generate Nonuniform Random Numbers	Python	O(n)	O(n)
5.17	The Sudoku Checker Problem	Python	O(n2)	O(n)
5.18	Compute the Spiral Ordering of a 2D Array	Python	O(n2)	O(n)
5.19	Rotate a 2D Array	Python	O(n2)	O(1)
5.20	Compute Rows in Pascal's Triangle	Python	O(n2)	O(n2)

Strings

#	Title	Solution	Time	Space
6.1	Interconvert Strings and Integers	Python	O(n)	O(n)
6.2	Base Conversion	Python	O(nlogn)	O(n)
6.3	Compute the Spreadsheet Column Encoding	Python	O(n)	O(1)
6.4	Replace and Remove	Python	O(n)	O(1)
6.5	Test Palindromicity	Python	O(n)	O(1)
6.6	Reverse All the Words in a Sentence	Python	O(n)	O(1)
6.7	Compute All Mnemonics for a Phone Number	Python	O(4nn)	O(n)
6.8	The Look-and-Say Problem	Python	O(n2n)	O(2n)
6.9	Convert from Roman to Decimal	Python	O(n)	O(1)
6.10	Compute All Valid IP Addresses	Python	O(1)	O(1)
6.11	Write a String Sinusoidally	Python	O(n)	O(1)
6.12	Implement Run-Length Encoding	Python	O(n)	O(n)
6.13	Find the First Occurrence of a Substring	Python	O(m+n)	O(1)

Linked Lists

#	Title	Solution	Time	Space
7.1	Merge Two Sorted Lists	Python	O(m+n)	O(1)
7.2	Reverse a Single Sublist	Python	O(n)	O(1)
7.3	Test for Cyclicity	Python	O(n)	O(1)
7.4	Test for Overlapping Lists—Lists Are Cycle-Free	Python	O(n)	O(1)
7.5	Test for Overlapping Lists—Lists May Have Cycles	Python	O(n)	O(1)
7.6	Delete a Node from a Singly Linked List	Python	O(1)	O(1)
7.7	Remove the kth Last Element from a List	Python	O(n)	O(1)
7.8	Remove Duplicates from a Sorted List	Python	O(n)	O(1)
7.9	Implement Cyclic Right Shift for Singly Linked Lists	Python	O(n)	O(1)
7.10	Implement Even-Odd Merge	Python	O(n)	O(1)
7.11	Test Whether a Singly Linked List Is Palindromic	Python	O(n)	O(1)
7.12	Implement List Pivoting	Python	O(n)	O(1)
7.13	Add List-Based Integers	Python	O(m+n)	O(m+n)

Stacks and Queues

#	Title	Solution	Time	Space
8.1	Implement a Stack with Max API	Python	O(1)	O(n)
8.2	Evaluate RPN Expressions	Python	O(n)	O(n)
8.3	Test a String over "{,},(,),[,]" for Well-Formedness	Python	O(n)	O(n)
8.4	Normalize Pathnames	Python	O(n)	O(n)
8.5	Compute Buildings with a Sunset View	Python	O(n)	O(n)
8.6	Compute Binary Tree Nodes in Order of Increasing Depth	Python	O(n)	O(n)
8.7	Implement a Circular Queue	Python	O(1)	O(n)
8.8	Implement a Queue Using Stacks	Python	O(1)	O(n)
8.9	Implement a Queue with Max API	Python	O(1)	O(n)

Binary Trees

#	Title	Solution	Time	Space
9.1	Test If a Binary Tree Is Height-Balanced	Python	O(n)	O(h)
9.2	Test If a Binary Tree Is Symmetric	Python	O(n)	O(h)
9.3	Compute the Lowest Common Ancestor in a Binary Tree	Python	O(n)	O(h)
9.4	Compute the LCA When Nodes Have Parent Pointers	Python	O(h)	O(1)
9.5	Sum the Root-To-Leaf Paths in a Binary Tree	Python	O(n)	O(h)
9.6	Find a Root to Leaf Path with Specified Sum	Python	O(n)	O(h)
9.7	Implement an Inorder Traversal Without Recursion	Python	O(n)	O(h)
9.8	Implement a Preorder Traversal Without Recursion	Python	O(n)	O(h)
9.9	Compute the kth Node in an Inorder Traversal	Python	O(h)	O(1)
9.10	Compute the Successor	Python	O(h)	O(1)
9.11	Implement an Inorder Traversal with O(1) Space	Python	O(n)	O(1)
9.12	Reconstruct a Binary Tree from Traversal Data	Python	O(n)	O(n)
9.13	Reconstruct a Binary Tree from a Preorder Traversal with Markers	Python	O(n)	O(h)
9.14	Form a Linked List from the Leaves of a Binary Tree	Python	O(n)	O(n)
9.15	Compute the Exterior of a Binary Tree	Python	O(n)	O(h)
9.16	Compute the Right Sibling Tree	Python	O(n)	O(1)

Heaps

#	Title	Solution	Time	Space
10.1	Merge Sorted Files	Python	O(nlogk)	O(k)
10.2	Sort an Increasing-Decreasing Array	Python	O(nlogk)	O(k)
10.3	Sort an Almost-Sorted Array	Python	O(nlogk)	O(k)
10.4	Compute the k Closest Stars	Python	O(nlogk)	O(k)
10.5	Compute the Median of Online Data	Python	O(logn)	O(n)
10.6	Compute the k Largest Elements in a Max-Heap	Python	O(klogk)	O(k)

Searching

#	Title	Solution	Time	Space
11.1	Search a Sorted Array for First Occurrence of k	Python	O(logn)	O(1)
11.2	Search a Sorted Array for Entry Equal to Its Index	Python	O(logn)	O(1)
11.3	Search a Cyclically Sorted Array	Python	O(logn)	O(1)
11.4	Compute the Integer Square Root	Python	O(logk)	O(1)
11.5	Compute the Real Square Root	Python	O(logk⁄s)	O(1)
11.6	Search in a 2D Sorted Array	Python	O(m+n)	O(1)
11.7	Find the Min and Max Simultaneously	Python	O(n)	O(1)
11.8	Find the kth Largest Element	Python	O(n)	O(1)
11.9	Find the Missing IP Address	Python	O(nlogn)	O(n)
11.10	Find the Duplicate and Missing Elements	Python	O(n)	O(1)

Hash Tables

#	Title	Solution	Time	Space
12.1	Test for Palindromic Permutations	Python	O(n)	O(n)
12.2	Is an Anonymous Letter Constructible?	Python	O(m+n)	O(n)
12.3	Implement an ISBN Cache	Python	O(1)	O(1)
12.4	Compute the LCA, Optimizing for Close Ancestors	Python	O(h)	O(h)
12.5	Find the Nearest Repeated Entries in an Array	Python	O(n)	O(d)
12.6	Find the Smallest Subarray Covering All Values	Python	O(n)	O(n)
12.7	Find Smallest Subarray Sequentially Covering All Values	Python	O(n)	O(m)
12.8	Find the Longest Subarray with Distinct Entries	Python	O(n)	O(k)
12.9	Find the Length of a Longest Contained Interval	Python	O(n)	O(n)
12.10	Compute All String Decompositions	Python	O(mnk)	O(nk)
12.11	Test the Collatz Conjecture	Python	O(1)	O(1)

Sorting

#	Title	Solution	Time	Space
13.1	Compute the Intersection of Two Sorted Arrays	Python	O(m+n)	O(m+n)
13.2	Merge Two Sorted Arrays	Python	O(nlogn)	O(1)
13.3	Computing the H-Index	Python	O(nlogn)	O(1)
13.4	Remove First-Name Duplicates	Python	O(nlogn)	O(1)
13.5	Smallest Nonconstructible Value	Python	O(nlogn)	O(1)
13.6	Render a Calendar	Python	O(nlogn)	O(n)
13.7	Merging Intervals	Python	O(n)	O(n)
13.8	Compute the Union of Intervals	Python	O(nlogn)	O(n)
13.9	Partitioning and Sorting an Array with Many Repeated Entries	Python	O(nlogn)	O(1)
13.10	Team Photo Day—1	Python	O(nlogn)	O(1)
13.11	Implement a Fast Sorting Algorithm for Lists	Python	O(nlogn)	O(logn)
13.12	Compute a Salary Threshold	Python	O(nlogn)	O(n)

Binary Search Trees

#	Title	Solution	Time	Space
14.1	Test If a Binary Tree Satisfies the BST Property	Python	O(n)	O(h)
14.2	Find the First Key Greater Than a Given Value in a BST	Python	O(h)	O(1)
14.3	Find the k Largest Elements in a BST	Python	O(h+k)	O(k)
14.4	Compute the LCA in a BST	Python	O(h)	O(1)
14.5	Reconstruct a BST from Traversal Data	Python	O(n)	O(h)
14.6	Find the Closest Entries in Three Sorted Arrays	Python	O(nlogk)	O(1)
14.7	Enumerate Numbers of the Form a + b √2	Python	O(klogk)	O(k)
14.8	Build a Minimum Height BST from a Sorted Array	Python	O(n)	O(logn)
14.9	Test If Three BST Nodes Are Totally Ordered	Python	O(h)	O(1)
14.10	The Range Lookup Problem	Python	O(n)	O(m)
14.11	Add Credits	Python	O(logn)	O(n)

Recursion

#	Title	Solution	Time	Space
15.1	The Towers of Hanoi Problem	Python	O(2n)	O(2n)
15.2	Generate All Nonattacking Placements of n-Queens	Python	O(n!)	O(n)
15.3	Generate Permutations	Python	O(nn!)	O(nn!)
15.4	Generate the Power Set	Python	O(n2n)	O(n2n)
15.5	Generate All Subsets of Size k	Python	O(C(n, k))	O(C(n, k))
15.6	Generate Strings of Matched Parens	Python	O(C(k))	O(C(k))
15.7	Generate Palindromic Decompositions	Python	O(n2n)	O(n2n)
15.8	Generate Binary Trees	Python	O(C(n))	O(C(n))
15.9	Implement a Sudoku Solver	Python	O(9!9)	O(1)
15.10	Compute a Gray Code	Python	O(2n)	O(2n)

Dynamic Programming

#	Title	Solution	Time	Space
16.1	Count the Number of Score Combinations	Python	O(mn)	O(mn)
16.2	Compute the Levenshtein Distance	Python	O(mn)	O(mn)
16.3	Count the Number of Ways to Traverse a 2D Array	Python	O(mn)	O(n)
16.4	Compute the Binomial Coefficients	Python	O(nk)	O(k)
16.5	Search for a Sequence in a 2D Array	Python	O(mns)	O(s)
16.6	The Knapsack Problem	Python	O(nw)	O(nw)
16.7	The bedbathandbeyond.​com Problem	Python	O(n2w)	O(n2)
16.8	Find the Minimum Weight Path in a Triangle	Python	O(n2)	O(1)
16.9	Pick Up Coins for Maximum Gain	Python	O(n2)	O(n2)
16.10	Count the Number of Moves to Climb Stairs	Python	O(mn)	O(mn)
16.11	The Pretty Printing Problem	Python	O(mn)	O(n)
16.12	Find the Longest Nondecreasing Subsequence	Python	O(n2)	O(n)

Greedy Algorithms and Invariants

#	Title	Solution	Time	Space
17.1	Compute an Optimum Assignment of Tasks	Python	O(nlogn)	O(n)
17.2	Schedule to Minimize Waiting Time	Python	O(nlogn)	O(1)
17.3	The Interval Covering Problem	Python	O(nlogn)	O(1)
17.4	The 3-Sum Problem	Python	O(nlogn)	O(1)
17.5	Find the Majority Element	Python	O(n)	O(1)
17.6	The Gasup Problem	Python	O(n)	O(1)
17.7	Compute the Maximum Water Trapped by a Pair of Vertical Lines	Python	O(n)	O(1)
17.8	Compute the Largest Rectangle Under the Skyline	Python	O(n)	O(n)

Graphs

#	Title	Solution	Time	Space
18.1	Search a Maze	Python	O(|V|+|E|)	O(|V|+|E|)
18.2	Paint a Boolean Matrix	Python	O(|V|+|E|)	O(1)
18.3	Compute Enclosed Regions	Python	O(mn)	O(m+n)
18.4	Deadlock Detection	Python	O(|V|+|E|)	O(|V|)
18.5	Clone a Graph	Python	O(|V|+|E|)	O(|V|+|E|)
18.6	Making Wired Connections	Python	O(|V|+|E|)	O(|V|)
18.7	Transform One String to Another	Python	O(nd)	O(d)
18.8	Team Photo Day—2	Python	O(|V|+|E|)	O(|E|)

Random Code — Not from EPI

Title	Solution	Time	Space
Shiba	ASM	O(w0w)	O(such)
Caesar Cipher	Python	N/A	N/A
FizzBuzz	Python C++ ASM	O(n)	O(1)

Useful References

• Big-O Cheat Sheet
• Python Wiki - Time Complexity
• Python Code Visualizer
• Python Tutorial
• Open Data Structures
• Problem Solving with Algorithms and Data Structures using Python
• Big O Notation and Algorithm Analysis with Python Examples

Acknowledgements

• Adnan Aziz - Author of EPI
• Tsung-Hsien Lee - Author of EPI
• Amit Prakash - Author of EPI
• All contributers to the EPI Judge
• Brandon Hough - Incubate distributed infomediaries
• Cory Walker - Mesh distributed mindshare

License

This project is released under the GNU GPL License - see the LICENSE file for details