epi
epi copied to clipboard
mrekucci
Solutions for Elements of Programming Interviews problems written in Golang (work-in-progress)
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 |
mrekucci