While preparing for the CS algorithms part of Machine Learning interviews, I came across many interesting problems. I have tried to list the ones that I have found to reappear quite a lot.
- Primitive types
- Arrays
- Strings
- Linked Lists
- Stacks and queues
- Binary trees
- Heaps
- Searching
- Hash tables
- Sorting
- Binary search trees
- Recursion
- Dynamic Programming
- Greedy Algorithms and Invariants
- Computing the parity of a word: How would you compute the parity of a very large number of 64-bit words?
- Swap bits: Implement code that takes as input a 64-bit integer and swaps the bits at indices i and j.
- Reverse bits:
- Find a closest integer with the same weights:
- Compute x * y without arithmetical operations:
- Compute x/y:
- Compute xy:
- Reverse digits:
- Check if a decimal number is a palindrome:
- Generate uniform random numbers:
- Rectangle intersection:
- The Dutch National Flag problem: Write a program that takes an array A and an index i into A, and rearranges the elements such that all elements less than A[i](the "pivot") appear first, followed by elements equal to the pivot, followed by elements greater than the pivot.
- Incerement an arbitrary-precision integer: Write a program which takes as input an array of digits encoding a nonngetaive decimal integer D and updates the array to represent the integer D+1. The algorithm should work even if implemented in a language that has finite-precision arithmetic.
- Multiply two arbitrary-precision integers: Write a program that takes two arrays representing integers, and returns an integer representing their product. For example, since 193 x -761 = -146873, if the inputs are [1, 9, 3] and [-7, 6, 1], the function should return [-1, 4, 6, 8, 7, 3]
- Test if a binary tree is height balanced
- Test if a binary tree is symmetric
- Compute the lowest common ancestor (LCA) in a binary tree
- Compute the LCA when nodes have parent pointers
- Sum the root-to-leaf paths in a binary tree
- Find a root-to-leaf path with a specified sum
- Implement an iorder traversal without recursion
- Implement a preorder traversal without recursion
- Compute the kth node in an inorder traversal
- Compute the successor (Assume nodes have a parent field)
- Implement an inorder traversal with O(1) space (Assume nodes have a parent field)
- Reconstruct a binary tree from traversal data
- Reconstruct a binary tree from preorder traversal with markers
- Form a linked list from the leaves of a binary tree
- Compute the exterior of a binary tree
- Compute the right sibling tree
- Check if two binary trees are identical
- Level order traversal of a binary tree
- Convert binary tree to doubly linked list
- Serialize/Deserialize a binary tree
- Connect all siblings in a binary tree
- Mirror binary tree nodes
- Delete zero sum sub-trees
- N-ary tree to binary tree and back
- Count the number of score combinations