Skip to content

Python solutions for Elements of Programming Interviews

License

Notifications You must be signed in to change notification settings

jwl-7/c0de_gr1nd

Repository files navigation

c0de_gr1nd

Introduction

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

# 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 xy 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(logks) 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

Acknowledgements

License

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

About

Python solutions for Elements of Programming Interviews

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published