Solutions for EPI

Chapter 5 - Arrays

Problem	Test	Solved
The Dutch national flag problem	Tests	✓
Increment an arbitrary-precision integer	Tests	✓
Multiply two arbitrary-precision integers		x
Advancing through an array	Tests	✓
Delete duplicates from a sorted array	Tests	✓
Buy and sell a stock once	Tests	✓
Buy and sell a stock twice		x
Computing an alternation	Tests	✓
Enumerate all primes to n	Tests	✓
Permute the elements of an array	Tests	✓
Compute the next permutation		x
Sample offline data	Tests	✓
Sample online data		x
Compute a random permutation		x
Compute a random subset		x
Generate nonuniform random numbers		x
The Sudoku checker problem		x
Compute the spiral ordering of a 2D array	Tests	✓
Rotate a 2D array	Tests	✓
Compute rows in Pascal’s Triangle		x

Chapter 6 - Strings

Problem	Test	Solved
Interconvert strings and intergers	Tests	✓
Base Conversion	Tests	✓
Compute the spreadsheet column encoding	Tests	✓
Replace and remove	Tests	✓
Test palindromcity	Tests	✓
Reverse all the words in a sentece	Tests	✓
Compute all mnemonics for a phone number	Tests	✓
The Look and say problem	Tests	✓
Convert from Roman to Decimal	Tests	✓
Compute all valid IP addresses	Tests	✓
Write string sinusoidally	Tests	✓
Implement RUN-LENGTH Encoding	Tests	✓
Find the first occurrence of a substring	Tests	✓

Chapter 7 - Linked Lists

Problem	Test	Solved
Merge Two sorted lists	Tests	✓
Reverse a single sublist	Tests	✓
Cycle detection	Tests	✓
Test if Overlap	Tests	✓
Test if Overlap (may have cycles)	Tests	x
Delete a node from a SLL	Tests	✓
Delete kth last node	Tests	✓
Remove duplicates	Tests	✓
Cyclic right shift	Tests	✓
Even odd merge	Tests	✓
Is palindrome	Tests	✓
List pivoting	Tests	x
Add list-based intergers	Tests	x

Chapter 8 - Stacks and Queues

Problem	Test	Solved
Implement stack with Max API	Tests	✓
Evaluate RPN expression	Tests	✓
String is Well Formed	Tests	✓
Normalize Pathnames	Tests	✓
Compute posting list	Tests	x
Compute building with a sunset view	Tests	✓
Binary tree level order	Tests	✓
Implement a circular queue	Tests	✓
Implement a queue using stacks	Tests	✓
Implement a queue with Max API	Tests	x

Chapter 9 - Binary Trees

Problem	Test	Solved
Test if a binary tree is height-balanced	Tests	✓
Test if a binary tree is symetric	Tests	✓
Compute LCA without parent node	Tests	✓
Compute LCA with parent node	Tests	x
Sum the root-to-leaf paths	Tests	✓
Find a root to leaf path with specified sum	Tests	✓
Inorder traversal without recursion	Tests	✓
Preorder traversal without recursion	Tests	✓
Compute the kth node in an inorder traversal	Tests	✓
Compute successor	Tests	✓
Implement inorder traversal with O(1) space	Tests	x
Reconstruct a binary tree from preorder/inorder traversals	Tests	✓
Reconstruct a binary tree from preorder with markers	Tests	✓
Form a Linked lists from the leaves of a binary tree	Tests	✓
Compute the exterior of a binary tree	Tests	✓
Compute the right sibling tree	Tests	✓
Implement locking in a binary tree	Tests	✓

Chapter 10 - Heaps

Problem	Test	Solved
Merge sorted files	Tests	✓
Sort an increasing-decresing array	Tests	✓
Sort an almost sorted array	Tests	✓