README.md

epi

This is a work-in-progress, solutions for Elements of Programming Interviews problems written in Golang.

Solutions

Primitive Types

Problem	Test	Solved
Computing the parity of a word	tests	✓
Swap bits	tests	✓
Reverse bits	tests	✓
Find a closest integer with the same weight	tests	✓
Compute x × y without arithmetical operators	tests
Compute x/y	tests
Compute x^y	tests
Reverse digits	tests	✓
Check if a decimal integer is a palindrome	tests
Generate uniform random numbers	tests
Rectangle intersection	tests

Arrays

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

Strings

Problem	Test	Solved
Interconvert strings and integers	tests	✓
Base conversion	tests
Compute the spreadsheet column encoding	tests
Replace and remove	tests
Test palindromicity	tests
Reverse all the words in a sentence	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 a string sinusoidally	tests
Implement run-length encoding	tests	✓
Implement the UNIX tail command	tests
Find the first occurrence of a substring	tests	✓

Linked List

Problem	Test	Solved
Merge two sorted lists	tests	✓
Reverse a singly linked list	tests
Reverse a single sublist	tests
Test for cyclicity	tests	✓
Test for overlapping lists—lists are cycle-free	tests
Test for overlapping lists—lists may have cycles	tests
Delete a node from a singly linked list	tests
Remove the kth last element from a list	tests
Remove duplicates from a sorted list	tests
Implement cyclic right shift for singly linked lists	tests
Implement even-odd merge	tests
Test whether a singly linked list is palindromic	tests
Implement list pivoting	tests
Add list-based integers	tests

Stacks and Queues

Stacks

Problem	Test	Solved
Implement a stack with max API	tests	✓
Evaluate RPN expressions	tests	✓
Test a string over “{,},(,),[,]” for well-formedness	tests	✓
Normalize pathnames	tests
BST keys in sort order	tests
Search a postings list	tests
Compute buildings with a sunset view	tests
Sort a stack	tests

Queues

Problem	Test	Solved
Compute binary tree nodes in order of increasing depth	tests	✓
Implement a circular queue	tests	✓
Implement a queue using stacks	tests	✓
Implement a queue with max API	tests

Binary Trees

Problem	Test	Solved
Test if a binary tree is balanced	tests	✓
Test if a binary tree is symmetric	tests	✓
Compute the lowest common ancestor in a binary tree	tests	✓
Compute the LCA when nodes have parent pointers	tests
Sum the root-to-leaf paths in a binary tree	tests
Find a root to leaf path with specified sum	tests
Compute the kth node in an inorder traversal	tests
Compute the successor	tests
Implement an inorder traversal with O(1) space	tests	✓
Reconstruct a binary tree from traversal data	tests
Reconstruct a binary tree from a preorder traversal with markers	tests
Form a linked list 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

Heaps

Problem	Test	Solved
Merge sorted files	tests	✓
Sort an increasing-decreasing array	tests	✓
Sort an almost-sorted array	tests
Compute the k closest stars	tests
Compute the median of online data	tests	✓
Compute the k largest elements in a max-heap	tests
Implement a stack API using a heap	tests

Searching

Binary Search

Problem	Test	Solved
Search a sorted array for first occurrence of k	tests	✓
Search a sorted array for the first element greater than k	tests	✓
Search a sorted array for entry equal to its index	tests	✓
Search a cyclically sorted array	tests
Compute the integer square root	tests
Compute the real square root	tests	✓

Generalized Search

Problem	Test	Solved
Search in a 2D sorted array	tests	✓
Find the min and max simultaneously	tests	✓
Find the kth largest element	tests	✓
Compute the optimum mailbox placement	tests
Find the missing IP address	tests
Find the duplicate and missing elements	tests

Hash Tables

Problem	Test	Solved
Partition into anagrams	tests	✓
Test for palindromic permutations	tests	✓
Is an anonymous letter constructible?	tests	✓
Implement an ISBN cache	tests
Compute the LCA, optimizing for close ancestors	tests	✓
Compute the k most frequent queries	tests
Find the nearest repeated entries in an array	tests
Find the smallest subarray covering all values	tests	✓
Find smallest subarray sequentially covering all values	tests
Find the longest subarray with distinct entries	tests
Find the length of a longest contained range	tests
Compute the average of the top three scores	tests
Compute all string decompositions	tests
Find a highest affinity pair	tests
Test the Collatz conjecture	tests
Implement a hash function for chess	tests

Sorting

Problem	Test	Solved
Compute the intersection of two sorted arrays	tests	✓
Implement mergesort in-place	tests	✓
Count the frequencies of characters in a sentence	tests	✓
Find unique elements	tests
Render a calendar	tests
Sets of disjoint intervals	tests
Compute the union of intervals	tests	✓
Partitioning and sorting an array with many repeated entries	tests
Team photo day—1	tests
Implement a fast sorting algorithm for lists	tests	✓
Compute a salary threshold	tests

Binary Search Trees

Problem	Test	Solved
Test if a binary tree satisfies the BST property	tests	✓
Find the first occurrence of a key in a BST	tests	✓
Find the first key larger than a given value in a BST	tests	✓
Find the k largest elements in a BST	tests
Compute the LCA in a BST	tests
Reconstruct a BST from traversal data	tests
Find the closest entries in three sorted arrays	tests
Enumerate numbers of the form a + b√2	tests
The most visited pages problem	tests
Build a minimum height BST from a sorted array	tests
Insertion and deletion in a BST	tests
Test if three BST nodes are totally ordered	tests
The range lookup problem	tests
Add credits	tests
Count the number of entries in an interval	tests

Recursion

Problem	Test	Solved
The Tower of Hanoi problem	tests	✓
Generate all nonattacking placements of n-Queens	tests	✓
Generate permutations	tests	✓
Generate the power set	tests	✓
Generate all subsets of size k	tests	✓
Generate strings of matched parens	tests
Generate palindromic decompositions	tests
Generate binary trees	tests
Implement a Sudoku solver	tests	✓
Compute a Gray code	tests
Compute the diameter of a tree	tests

Dynamic Programming

Problem	Test	Solved
Count the number of score combinations	tests
Compute the Levenshtein distance	tests
Count the number of ways to traverse a 2D array	tests
Plan a fishing trip	tests
Search for a sequence in a 2D array	tests
The knapsack problem	tests
Divide the spoils fairly	tests
The bedbathandbeyond.com problem	tests
Find the minimum weight path in a triangle	tests
Pick up coins for maximum gain	tests
Count the number of moves to climb stairs	tests
Compute the probability of a Republican majority	tests
The pretty printing problem	tests
Find the longest nondecreasing subsequence	tests

Greedy Algorithms and Invariants

Greedy Algorithms

Problem	Test	Solved
Implement Huffman coding	tests	✓
Compute an optimum assignment of tasks	tests	✓
Implement a schedule which minimizes waiting time	tests	✓
The interval covering problem	tests

Invariants

Problem	Test	Solved
The 3-sum problem	tests	✓
Find the majority element	tests
The gasup problem	tests
Compute the maximum water trapped by a pair of vertical lines	tests
Compute the largest rectangle under the skyline	tests

Graphs

Problem	Test	Solved
Identify the celebrity	tests	✓
Search a maze	tests	✓
Paint a Boolean matrix	tests	✓
Compute enclosed regions	tests
Degrees of connectedness—1	tests	✓
Clone a graph	tests
Making wired connections	tests
Transform one string to another	tests
The shortest straight-line program for x^n	tests
Team photo day—2	tests
Compute a shortest path with fewest edges	tests

Parallel Computing

Problem	Test	Solved
Implement caching for a multithreaded dictionary	tests
Analyze two unsynchronized interleaved threads	tests
Implement synchronization for two interleaving threads	tests
Implement a thread pool	tests
Implement asynchronous callbacks	tests
Implement a Timer class	tests
The readers-writers problem	tests
The readers-writers problem with write preference	tests
Test the Collatz conjecture in parallel	tests
Design TeraSort and PetaSort	tests
Implement distributed throttling	tests

Design Problems

Problem	Test	Solved
Design a spell checker	tests
Design a solution to the stemming problem	tests
Plagiarism detector	tests
Pair users by attributes	tests
Design a system for detecting copyright infringement	tests
Design TEX	tests
Design a search engine	tests
Implement PageRank	tests
Design a scalable priority system	tests
Create photomosaics	tests
Implement Mileage Run	tests
Implement Connexus	tests
Design an online advertising system	tests
Design a recommendation system	tests
Design an optimized way of distributing large files	tests
Design the World Wide Web	tests
Estimate the hardware cost of a photo sharing app	tests

Honors Class

Problem	Test	Solved
Compute the greatest common divisor	tests
Find the first missing positive entry	tests
Buy and sell a stock k times	tests
Compute the maximum product of all entries but one	tests
Compute the longest contiguous increasing subarray	tests
Rotate an array	tests
Identify positions attacked by rooks	tests
Justify text	tests
Reverse sublists k at a time	tests
Implement list zipping	tests
Copy a postings list	tests
Compute the median of a sorted circular linked list	tests	✓
Compute the longest substring with matching parens	tests
Compute the maximum of a sliding window	tests
Implement preorder and postorder traversals without recursion	tests
Compute fair bonuses	tests
Find k elements closest to the median	tests
Search a sorted array of unknown length	tests
Search in two sorted arrays	tests
Find the kth largest element—large n, small k	tests
Find an element that appears only once	tests
Find the line through the most points	tests
Find the shortest unique prefix	tests
Compute the smallest nonconstructible change	tests
Find the most visited pages in a window	tests
Convert a sorted doubly linked list into a BST	tests
Convert a BST to a sorted doubly linked list	tests
Merge two BSTs	tests
Test if a binary tree is an almost BST	tests
The view from above	tests
Searching a min-first BST	tests
Implement regular expression matching	tests
Synthesize an expression	tests
Count inversions	tests
Draw the skyline	tests
Find the two closest points	tests
Measure with defective jugs	tests
Compute the maximum subarray sum in a circular array	tests
Determine the critical height	tests
Voltage selection in a logic circuit	tests
Find the maximum 2D subarray	tests
Trapping water	tests
Load balancing	tests
Search for a pair-sum in an abs-sorted array	tests
The heavy hitter problem	tests
Find the longest subarray whose sum ≤ k	tests
Degrees of connectedness—2	tests
Compute a minimum delay schedule, unlimited resources	tests
Road network	tests
Test if arbitrage is possible	tests
The readers-writers problem with fairness	tests
Implement a producer-consumer queue	tests