Elements of Programming Interviews

Valiantly trying to solve every single question in Elements of Programming Interviews

• Completed: 135
• Remaining: 101

Chapter 5: Primitives

Remaining: 0

• [x] 5.1: Computing the parity of a word
• [x] 5.2: Swap bits
• [x] 5.3: Reverse bits
• [x] 5.4: Find a closest integer with the same weight
• [x] 5.5: Compute X x Y without arithmetical operators
• [x] 5.6: Compute X / Y
• [x] 5.7: Compute X ^ Y
• [x] 5.8: Reverse digits
• [x] 5.9: Check if a decimal integer is a palindrome
• [x] 5.10: generate uniform random numbers
• [x] 5.11: Rectangle intersection

Chapter 6: Arrays

Remaining: 0

• [x] 6.1: The Dutch national flag problem
• [x] 6.2: Increment an arbitrary-precision integer
• [x] 6.3: Multiply two arbitrary-precision integers
• [x] 6.4: Advancing through an array
• [x] 6.5: Delete a key from an array
• [x] 6.6: Delete duplicates from a sorted array
• [x] 6.7: Buy and sell a stock once
• [x] 6.8: Buy and sell a stock twice
• [x] 6.9: Enumerate all primes to n
• [x] 6.10: Permute the elements of an array
• [x] 6.11: Compute the next permutation
• [x] 6.12: Sample offline data
• [x] 6.13: Sample online data
• [x] 6.14: Compute a random permutation
• [x] 6.15: Compute a random subset
• [x] 6.16: Generate nonuniform random numbers
• [x] 6.17: The Sudoku checker problem
• [x] 6.18: Compute the spiral ordering of a 2D array
• [x] 6.19: Rotate a 2D array
• [x] 6.20: Compute rows in Pascal's Triangle

Chapter 7: Strings

Remaining: 1

• [x] 7.1: Interconvert strings and integers
• [x] 7.2: Base conversion
• [x] 7.3: Compute the spreadsheet column encoding
• [x] 7.4: Replace and remove
• [x] 7.5: Test palindromicity
• [x] 7.6: Reverse all the words in a sentence
• [x] 7.7: Compute all mnemonics for a phone number
• [x] 7.8: The look-and-say problem
• [x] 7.9: Convert from Roman to decimal
• [x] 7.10: Compute all valid IP addresses
• [x] 7.11: Write a string sinusoidally
• [x] 7.12: Implement run-length encoding
• [x] 7.13: Implement the UNIX tail command
• [ ] 7.14: Find the first occurrence of a substring

Chapter 8: Linked Lists

Remaining: 0

• [x] 8.1: Merge two sorted lists
• [x] 8.2: Reverse a singly linked list
• [x] 8.3: Reverse a single sublist
• [x] 8.4: Test for cyclicity
• [x] 8.5: Test for overlapping lists -- lists are cycle-free
• [x] 8.6: Test for overlapping lists -- lists may have cycles
• [x] 8.7: Delete a node from a singly linked list
• [x] 8.8: Remove the kth last element from a list
• [x] 8.9: Remove duplicates from a sorted list
• [x] 8.10: Implement cyclic right shift for singly linked lists
• [x] 8.11: Implement even-odd merge
• [x] 8.12: Test whether a singly linked list is palindromic
• [x] 8.13: Implement list pivoting
• [x] 8.14: Add list-based integers

Chapter 9: Stacks and Queues

Remaining: 2

• [x] 9.1: Implement a stack with a max API
• [x] 9.2: Evaluate RPN expressions
• [x] 9.3: Test a string of parens for well-formedness
• [x] 9.4: Normalize pathnames
• [x] 9.5: BST keys in sort order
• [x] 9.6: Search a postings list
• [x] 9.7: Compute buildings with a sunset view
• [ ] 9.8: Sort a stack
• [x] 9.9: Compute binary tree nods in order of increasing depth
• [x] 9.10: Implement a circular queue
• [x] 9.11: Implement a queue using stacks
• [x] 9.12: Implement a queue with max API

Chapter 10: Binary Trees

Remaining: 1

• [x] 10.1: Test if a binary tree is balanced
• [x] 10.2: Test if a binary tree is symmetric
• [x] 10.3: Compute the lowest common ancestor in a binary tree
• [x] 10.4: Compute the LCA when nodes have parent pointers
• [x] 10.5: Sum the root-to-leaf paths in a binary tree
• [x] 10.6: Find a root to leaf path with specified sum
• [x] 10.7: Compute the kth node in an inorder traversal
• [x] 10.8: Compute the successor
• [x] 10.9: Implement an inorder traversal with O(1) space
• [x] 10.10: Reconstruct a binary tree from traversal data
• [x] 10.11: Reconstruct a binary tree from a preorder traversal with markers
• [x] 10.12: Form a linked list from the leaves of a binary tree
• [x] 10.13: Compute the exterior of a binary tree
• [x] 10.14: Compute the right sibling tree
• [ ] 10.15: Implement locking in a binary tree

Chapter 11: Heaps

Remaining: 0

• [x] 11.1: Merge sorted files
• [x] 11.2: Sort an increasing-decreasing array
• [x] 11.3: Sort an almost-sorted array
• [x] 11.4: Compute the k closest stars
• [x] 11.5: Compute the median of online data
• [x] 11.6: Compute the k largest elements in a max-heap
• [x] 11.7: Implement a stack API using a heap

Chapter 12: Searching

Remaining: 5

• [x] 12.1: Search a sorted array for the first occurrence of k
• [x] 12.2: Search a sorted array for the first element greater than k
• [x] 12.3: Search a sorted array for entry equal to its index
• [x] 12.4: Search a cyclically sorted array
• [x] 12.5: Compute the integer square root
• [ ] 12.6: Compute the real square root
• [x] 12.7: Search in a 2D sorted array
• [x] 12.8: Find the min and max simultaneously
• [ ] 12.9: Find the kth largest element
• [ ] 12.10: Compute the optimum mailbox placement
• [ ] 12.11: Find the missing IP address
• [ ] 12.12: Find the duplicate and missing elements

Chapter 13: Hash Tables

Remaining: 11

• [x] 13.1: Partition into anagrams
• [x] 13.2: Test for palindromic permutations
• [ ] 13.3: Is an anonymous letter constructable?
• [x] 13.4: Implement an ISBN cache
• [ ] 13.5: Compute the LCA, optimizing for close ancestors
• [ ] 13.6: Compute the k most frequent queries
• [x] 13.7: Find the nearest repeated entries in an array
• [ ] 13.8: Find the smallest subarray sequentially covering all values
• [ ] 13.9: Find smallest subarray sequentially covering all values
• [x] 13.10: Find the longest subarray with distinct entries
• [ ] 13.11: Find the length of a longest contained interval
• [ ] 13.12: Compute the average of the top three scores
• [ ] 13.13: Compute all string decompositions
• [ ] 13.14: Find a highest affinity pair
• [ ] 13.15: Test the Collatz conjecture
• [ ] 13.16: Implement a hash function for chess

Chapter 14: Sorting

Remaining: 6

• [x] 14.1: Compute the intersection of two arrays
• [x] 14.2: Implement mergesort in-place
• [x] 14.3: Count the frequencies of characters in a sentence
• [x] 14.4: Remove first-name duplicates
• [x] 14.5: Render a calendar
• [x] 14.6: Merging intervals
• [ ] 14.7: Compute the union of intervals
• [ ] 14.8: Partitioning and sorting an array with many repeated entries
• [ ] 14.9: Team photo day-1
• [ ] 14.10: Implement a fast sorting algorithm for lists
• [ ] 14.11: Compute a salary threshold

Chapter 15: Binary Search Trees

Remaining: 10

• [x] 15.1: Test if a binary tree satisfies the BST property
• [x] 15.2: Find the first occurrence of a key in a BST
• [x] 15.3: Find the first key larger than a given value in a BST
• [x] 15.4: Find the k largest elements in a ST
• [x] 15.5: Compute the LCA in a BST
• [ ] 15.6: Reconstruct a BST from traversal data
• [ ] 15.7: Find the closest entries in three sorted arrays
• [ ] 15.8: Enumerate numbers of the form a + b sqrt(2)
• [ ] 15.9: The most visited pages problem
• [ ] 15.10: Build a minimum-height BST from a sorted array
• [ ] 15.11: Insertion and deletion in a BST
• [ ] 15.12: Test if three BST nodes are totally ordered
• [ ] 15.13: The range lookup problem
• [ ] 15.14: Add credits
• [ ] 15.15: Count the number of entries in an interval

Chapter 16: Recursion

Remaining: 8

• [ ] 16.1: The Tower of Hanoi problem
• [ ] 16.2: Generate all nonattacking placements of n-Queens
• [x] 16.3: Generate permutations
• [x] 16.4: Generate the power set
• [x] 16.5: Generate all subsets of k
• [ ] 16.6: Generate strings of matched parens
• [ ] 16.7: Generate palindromic decompositions
• [ ] 16.8: Generate binary trees
• [ ] 16.9: Implement a Sudoku solver
• [ ] 16.10: Compute a Gray code
• [ ] 16.11: Compute the diameter of a tree

Chapter 17: Dynamic Programming

Remaining: 6

• [x] 17.1: Count the number of score combinations
• [x] 17.2: Compute the Levenshtein distance
• [x] 17.3: Count the number of ways to traverse a 2D array
• [ ] 17.4: Compute the binomial coefficients
• [ ] 17.5: Search for a sequence in a 2D array
• [x] 17.6: The knapsack problem
• [x] 17.7: The bedbathandbeyond problem
• [ ] 17.8: Find the minimum weight path in a triangle
• [ ] 17.9: Pick up coins for maximum gain
• [x] 17.10: Count the number of moves to climb stairs
• [ ] 17.11: The pretty printing problem
• [ ] 17.12: Find the longest nondecreasing subsequence

Chapter 18: Greedy Algorithms and Invariants

Remaining: 5

• [ ] 18.1: Implement Huffman coding
• [ ] 18.2: Compute an optimum assignment of tasks
• [ ] 18.3: Schedule to minimize waiting time
• [ ] 18.4: The interval covering problem
• [x] 18.5: The 3-Sum problem
• [x] 18.6: Find the majority element
• [x] 18.7: The gasup problem
• [x] 18.8: Compute the maximum water trapped by a pair of vertical lines
• [ ] 18.9: Compute the largest rectangle under the skyline

Chapter 19: Graphs

Remaining: 5

• [x] 19.1: Search a maze
• [x] 19.2: Paint a Boolean matrix
• [x] 19.3: Compute enclosed regions
• [x] 19.4: Degrees of connectedness - 1
• [x] 19.5: Clone a graph
• [ ] 19.6: Making wired connections
• [ ] 19.7: Transform one string to another
• [ ] 19.8: Addition chain exponentiation
• [ ] 19.9: Team photo day - 2
• [ ] 19.10: Compute a shortest path with fewest edges

Chapter 22: Honors Class

Remaining: 41

• [x] 22.1: Compute the greatest common divisor
• [x] 22.2: Find the first missing positive entry
• [x] 22.3: Buy and sell a stock k times
• [x] 22.4: Compute the maximum product of all entries but one
• [x] 22.5: Compute the longest contiguous increasing subarray
• [ ] 22.6: Rotate an array
• [x] 22.7: Identify positions attacked by rooks
• [x] 22.8: Justify text
• [ ] 22.9: Reverse sublists k at a time
• [x] 22.10: Implement list zipping
• [ ] 22.11: Copy a postings list
• [x] 22.12: Compute the median of a sorted circular list
• [x] 22.13: Compute the longest substring with matching parens
• [ ] 22.14: Compute the maximum of a sliding window
• [ ] 22.15: Implement preorder and postorder traversals without recursion
• [ ] 22.16: Compute fair bonuses
• [ ] 22.17: Find k elements closest to the median
• [ ] 22.18: Search a sorted array of unknown length
• [ ] 22.19: Search in two sorted arrays
• [ ] 22.20: Find the kth largest element - large n, small k
• [ ] 22.21: Find an element that only appears once
• [ ] 22.22: Find the line through the most points
• [ ] 22.23: Find the shortest unique prefix
• [ ] 22.24: Compute the smallest nonconstructible change
• [ ] 22.25: Find the most visited pages in a window
• [ ] 22.26: Convert a sorted doubly linked list into a BST
• [ ] 22.27: Convert a BST to a sorted doubly linked list
• [ ] 22.28: Merge two BSTs
• [ ] 22.29: Test if a binary tree is an almost BST
• [ ] 22.30: The view from above
• [ ] 22.31: Searching a min-first BST
• [ ] 22.32: Implement regular expression matching
• [ ] 22.22: Synthesize and expression
• [ ] 22.34: Count inversions
• [ ] 22.35: Draw the skyline
• [ ] 22.36: Find the two closest points
• [ ] 22.37: Measure with defective jugs
• [ ] 22.38: Compute the maximum sum in a circular array
• [ ] 22.39: Determine the critical height
• [ ] 22.40: Voltage selection in a logic circuit
• [ ] 22.41: Find the maximum 2D subarray
• [ ] 22.42: Trapping water
• [ ] 22.43: Load balancing
• [ ] 22.44: Search for a pair-sum in an abs-sorted array
• [ ] 22.45: The heavy hitter problem
• [ ] 22.46: Find the longest subarray whose sum <= k
• [ ] 22.47: Degrees of connectedness - 2
• [ ] 22.48: Compute a minimum delay schedule, unlimited resources
• [ ] 22.49: Road network
• [ ] 22.50: Test if arbitrage is possible
• [ ] 22.51: The readers-writers problem with fairness
• [ ] 22.52: Implement a producer-consumer queue