Solutions for Elements of Programming Interviews problems written in Golang (work-in-progress)
Switch branches/tags
Nothing to show
Clone or download
Latest commit 7dccd96 Jul 23, 2016
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
arrays Polish the source code Jul 23, 2016
bsearch Polish the source code Jul 23, 2016
bstrees Integrate auxiliary function as function literal May 13, 2016
btrees Remove unnecessary variable passing to function literal May 13, 2016
dp Remove pcomputing and designproblems packages, add dynamicprog package May 13, 2016
graphs Remove unnecessary variable passing to function literal May 13, 2016
greedy Remove unnecessary casting to rune May 13, 2016
heaps Polish the source code Jul 23, 2016
honorsclass Speedup benchmark for honorclass.MedianOfSorted function May 13, 2016
htables Change map value from empty sturct into bool in order to improve read… May 13, 2016
internal/epiutil Switch to Go 1.5 Aug 20, 2015
invariants Polish the source code Jul 23, 2016
lists Fix the benchmark for lists.MergeSorted May 13, 2016
ptypes Change the way how reverse table is initialized into more readable way May 13, 2016
queues Polish the source code Jul 23, 2016
recursion Polish the source code Jul 23, 2016
search Polish the source code Jul 23, 2016
sorting Simplify code May 13, 2016
stacks Cleanup stacks.IntStackMax benchmark May 13, 2016
strings Rename variables in order to improve readability May 13, 2016
.gitattributes Initial commit Jul 12, 2015
.gitignore Polish the source code Jul 23, 2016
.travis.yml Upgrade travis builds to Go 1.5.2 Dec 7, 2015
AUTHORS.txt Add link to the LICENSE.txt in README.md Jul 12, 2015
LICENSE.txt Add link to the LICENSE.txt in README.md Jul 12, 2015
README.md Solve the "Generate all subsets of size k" problem May 13, 2016
in_progress.md Mark implemented problems Oct 3, 2015
test_coverage.sh Mark implemented problems Oct 3, 2015

README.md

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

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