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

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

Chapter 6: Arrays

Remaining: 0

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

Chapter 7: Strings

Remaining: 1

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

Chapter 8: Linked Lists

Remaining: 0

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

Chapter 9: Stacks and Queues

Remaining: 2

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

Chapter 10: Binary Trees

Remaining: 1

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

Chapter 11: Heaps

Remaining: 0

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

Chapter 12: Searching

Remaining: 5

• 12.1: Search a sorted array for the first occurrence of k
• 12.2: Search a sorted array for the first element greater than k
• 12.3: Search a sorted array for entry equal to its index
• 12.4: Search a cyclically sorted array
• 12.5: Compute the integer square root
• 12.6: Compute the real square root
• 12.7: Search in a 2D sorted array
• 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

• 13.1: Partition into anagrams
• 13.2: Test for palindromic permutations
• 13.3: Is an anonymous letter constructable?
• 13.4: Implement an ISBN cache
• 13.5: Compute the LCA, optimizing for close ancestors
• 13.6: Compute the k most frequent queries
• 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
• 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

• 14.1: Compute the intersection of two arrays
• 14.2: Implement mergesort in-place
• 14.3: Count the frequencies of characters in a sentence
• 14.4: Remove first-name duplicates
• 14.5: Render a calendar
• 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

• 15.1: Test if a binary tree satisfies the BST property
• 15.2: Find the first occurrence of a key in a BST
• 15.3: Find the first key larger than a given value in a BST
• 15.4: Find the k largest elements in a ST
• 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
• 16.3: Generate permutations
• 16.4: Generate the power set
• 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

• 17.1: Count the number of score combinations
• 17.2: Compute the Levenshtein distance
• 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
• 17.6: The knapsack problem
• 17.7: The bedbathandbeyond problem
• 17.8: Find the minimum weight path in a triangle
• 17.9: Pick up coins for maximum gain
• 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
• 18.5: The 3-Sum problem
• 18.6: Find the majority element
• 18.7: The gasup problem
• 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

• 19.1: Search a maze
• 19.2: Paint a Boolean matrix
• 19.3: Compute enclosed regions
• 19.4: Degrees of connectedness - 1
• 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

• 22.1: Compute the greatest common divisor
• 22.2: Find the first missing positive entry
• 22.3: Buy and sell a stock k times
• 22.4: Compute the maximum product of all entries but one
• 22.5: Compute the longest contiguous increasing subarray
• 22.6: Rotate an array
• 22.7: Identify positions attacked by rooks
• 22.8: Justify text
• 22.9: Reverse sublists k at a time
• 22.10: Implement list zipping
• 22.11: Copy a postings list
• 22.12: Compute the median of a sorted circular list
• 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