- 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
- 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
- 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
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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) |
| # | 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|) |
| 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) |
- 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
- 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
This project is released under the GNU GPL License - see the LICENSE file for details