Home

Awesome

epi

Build Status Coverage Status GitHub license

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

Solutions

Primitive Types

ProblemTestSolved
Computing the parity of a wordtests
Swap bitstests
Reverse bitstests
Find a closest integer with the same weighttests
Compute x × y without arithmetical operatorstests
Compute x/ytests
Compute x^ytests
Reverse digitstests
Check if a decimal integer is a palindrometests
Generate uniform random numberstests
Rectangle intersectiontests

Arrays

ProblemTestSolved
The Dutch national flag problemtests
Increment an arbitrary-precision integertests
Multiply two arbitrary-precision integerstests
Advancing through an arraytests
Delete a key from an arraytests
Delete duplicates from a sorted arraytests
Robot's minimum battery capacitytests
Buy and sell a stock twicetests
Enumerate all primes to ntests
Permute the elements of an arraytests
Compute the next permutationtests
Sample offline datatests
Sample online datatests
Compute a random permutationtests
Compute a random subsettests
Generate nonuniform random numberstests
The Sudoku checker problemtests
Compute the spiral ordering of a 2D arraytests
Rotate a 2D arraytests
Compute rows in Pascal’s Triangletests

Strings

ProblemTestSolved
Interconvert strings and integerstests
Base conversiontests
Compute the spreadsheet column encodingtests
Replace and removetests
Test palindromicitytests
Reverse all the words in a sentencetests
Compute all mnemonics for a phone numbertests
The look-and-say problemtests
Convert from Roman to decimaltests
Compute all valid IP addressestests
Write a string sinusoidallytests
Implement run-length encodingtests
Implement the UNIX tail commandtests
Find the first occurrence of a substringtests

Linked List

ProblemTestSolved
Merge two sorted liststests
Reverse a singly linked listtests
Reverse a single sublisttests
Test for cyclicitytests
Test for overlapping lists—lists are cycle-freetests
Test for overlapping lists—lists may have cyclestests
Delete a node from a singly linked listtests
Remove the kth last element from a listtests
Remove duplicates from a sorted listtests
Implement cyclic right shift for singly linked liststests
Implement even-odd mergetests
Test whether a singly linked list is palindromictests
Implement list pivotingtests
Add list-based integerstests

Stacks and Queues

Stacks

ProblemTestSolved
Implement a stack with max APItests
Evaluate RPN expressionstests
Test a string over “{,},(,),[,]” for well-formednesstests
Normalize pathnamestests
BST keys in sort ordertests
Search a postings listtests
Compute buildings with a sunset viewtests
Sort a stacktests

Queues

ProblemTestSolved
Compute binary tree nodes in order of increasing depthtests
Implement a circular queuetests
Implement a queue using stackstests
Implement a queue with max APItests

Binary Trees

ProblemTestSolved
Test if a binary tree is balancedtests
Test if a binary tree is symmetrictests
Compute the lowest common ancestor in a binary treetests
Compute the LCA when nodes have parent pointerstests
Sum the root-to-leaf paths in a binary treetests
Find a root to leaf path with specified sumtests
Compute the kth node in an inorder traversaltests
Compute the successortests
Implement an inorder traversal with O(1) spacetests
Reconstruct a binary tree from traversal datatests
Reconstruct a binary tree from a preorder traversal with markerstests
Form a linked list from the leaves of a binary treetests
Compute the exterior of a binary treetests
Compute the right sibling treetests
Implement locking in a binary treetests

Heaps

ProblemTestSolved
Merge sorted filestests
Sort an increasing-decreasing arraytests
Sort an almost-sorted arraytests
Compute the k closest starstests
Compute the median of online datatests
Compute the k largest elements in a max-heaptests
Implement a stack API using a heaptests

Searching

Binary Search

ProblemTestSolved
Search a sorted array for first occurrence of ktests
Search a sorted array for the first element greater than ktests
Search a sorted array for entry equal to its indextests
Search a cyclically sorted arraytests
Compute the integer square roottests
Compute the real square roottests

Generalized Search

ProblemTestSolved
Search in a 2D sorted arraytests
Find the min and max simultaneouslytests
Find the kth largest elementtests
Compute the optimum mailbox placementtests
Find the missing IP addresstests
Find the duplicate and missing elementstests

Hash Tables

ProblemTestSolved
Partition into anagramstests
Test for palindromic permutationstests
Is an anonymous letter constructible?tests
Implement an ISBN cachetests
Compute the LCA, optimizing for close ancestorstests
Compute the k most frequent queriestests
Find the nearest repeated entries in an arraytests
Find the smallest subarray covering all valuestests
Find smallest subarray sequentially covering all valuestests
Find the longest subarray with distinct entriestests
Find the length of a longest contained rangetests
Compute the average of the top three scorestests
Compute all string decompositionstests
Find a highest affinity pairtests
Test the Collatz conjecturetests
Implement a hash function for chesstests

Sorting

ProblemTestSolved
Compute the intersection of two sorted arraystests
Implement mergesort in-placetests
Count the frequencies of characters in a sentencetests
Find unique elementstests
Render a calendartests
Sets of disjoint intervalstests
Compute the union of intervalstests
Partitioning and sorting an array with many repeated entriestests
Team photo day—1tests
Implement a fast sorting algorithm for liststests
Compute a salary thresholdtests

Binary Search Trees

ProblemTestSolved
Test if a binary tree satisfies the BST propertytests
Find the first occurrence of a key in a BSTtests
Find the first key larger than a given value in a BSTtests
Find the k largest elements in a BSTtests
Compute the LCA in a BSTtests
Reconstruct a BST from traversal datatests
Find the closest entries in three sorted arraystests
Enumerate numbers of the form a + b√2tests
The most visited pages problemtests
Build a minimum height BST from a sorted arraytests
Insertion and deletion in a BSTtests
Test if three BST nodes are totally orderedtests
The range lookup problemtests
Add creditstests
Count the number of entries in an intervaltests

Recursion

ProblemTestSolved
The Tower of Hanoi problemtests
Generate all nonattacking placements of n-Queenstests
Generate permutationstests
Generate the power settests
Generate all subsets of size ktests
Generate strings of matched parenstests
Generate palindromic decompositionstests
Generate binary treestests
Implement a Sudoku solvertests
Compute a Gray codetests
Compute the diameter of a treetests

Dynamic Programming

ProblemTestSolved
Count the number of score combinationstests
Compute the Levenshtein distancetests
Count the number of ways to traverse a 2D arraytests
Plan a fishing triptests
Search for a sequence in a 2D arraytests
The knapsack problemtests
Divide the spoils fairlytests
The bedbathandbeyond.com problemtests
Find the minimum weight path in a triangletests
Pick up coins for maximum gaintests
Count the number of moves to climb stairstests
Compute the probability of a Republican majoritytests
The pretty printing problemtests
Find the longest nondecreasing subsequencetests

Greedy Algorithms and Invariants

Greedy Algorithms

ProblemTestSolved
Implement Huffman codingtests
Compute an optimum assignment of taskstests
Implement a schedule which minimizes waiting timetests
The interval covering problemtests

Invariants

ProblemTestSolved
The 3-sum problemtests
Find the majority elementtests
The gasup problemtests
Compute the maximum water trapped by a pair of vertical linestests
Compute the largest rectangle under the skylinetests

Graphs

ProblemTestSolved
Identify the celebritytests
Search a mazetests
Paint a Boolean matrixtests
Compute enclosed regionstests
Degrees of connectedness—1tests
Clone a graphtests
Making wired connectionstests
Transform one string to anothertests
The shortest straight-line program for x^ntests
Team photo day—2tests
Compute a shortest path with fewest edgestests

Parallel Computing

ProblemTestSolved
Implement caching for a multithreaded dictionarytests
Analyze two unsynchronized interleaved threadstests
Implement synchronization for two interleaving threadstests
Implement a thread pooltests
Implement asynchronous callbackstests
Implement a Timer classtests
The readers-writers problemtests
The readers-writers problem with write preferencetests
Test the Collatz conjecture in paralleltests
Design TeraSort and PetaSorttests
Implement distributed throttlingtests

Design Problems

ProblemTestSolved
Design a spell checkertests
Design a solution to the stemming problemtests
Plagiarism detectortests
Pair users by attributestests
Design a system for detecting copyright infringementtests
Design TEXtests
Design a search enginetests
Implement PageRanktests
Design a scalable priority systemtests
Create photomosaicstests
Implement Mileage Runtests
Implement Connexustests
Design an online advertising systemtests
Design a recommendation systemtests
Design an optimized way of distributing large filestests
Design the World Wide Webtests
Estimate the hardware cost of a photo sharing apptests

Honors Class

ProblemTestSolved
Compute the greatest common divisortests
Find the first missing positive entrytests
Buy and sell a stock k timestests
Compute the maximum product of all entries but onetests
Compute the longest contiguous increasing subarraytests
Rotate an arraytests
Identify positions attacked by rookstests
Justify texttests
Reverse sublists k at a timetests
Implement list zippingtests
Copy a postings listtests
Compute the median of a sorted circular linked listtests
Compute the longest substring with matching parenstests
Compute the maximum of a sliding windowtests
Implement preorder and postorder traversals without recursiontests
Compute fair bonusestests
Find k elements closest to the mediantests
Search a sorted array of unknown lengthtests
Search in two sorted arraystests
Find the kth largest element—large n, small ktests
Find an element that appears only oncetests
Find the line through the most pointstests
Find the shortest unique prefixtests
Compute the smallest nonconstructible changetests
Find the most visited pages in a windowtests
Convert a sorted doubly linked list into a BSTtests
Convert a BST to a sorted doubly linked listtests
Merge two BSTstests
Test if a binary tree is an almost BSTtests
The view from abovetests
Searching a min-first BSTtests
Implement regular expression matchingtests
Synthesize an expressiontests
Count inversionstests
Draw the skylinetests
Find the two closest pointstests
Measure with defective jugstests
Compute the maximum subarray sum in a circular arraytests
Determine the critical heighttests
Voltage selection in a logic circuittests
Find the maximum 2D subarraytests
Trapping watertests
Load balancingtests
Search for a pair-sum in an abs-sorted arraytests
The heavy hitter problemtests
Find the longest subarray whose sum ≤ ktests
Degrees of connectedness—2tests
Compute a minimum delay schedule, unlimited resourcestests
Road networktests
Test if arbitrage is possibletests
The readers-writers problem with fairnesstests
Implement a producer-consumer queuetests