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.

Table of Contents

• 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

Primitive types

1. Computing the parity of a word: How would you compute the parity of a very large number of 64-bit words?
2. Swap bits: Implement code that takes as input a 64-bit integer and swaps the bits at indices i and j.
3. Reverse bits:
4. Find a closest integer with the same weights:
5. Compute x * y without arithmetical operations:
6. Compute x/y:
7. Compute x^y:
8. Reverse digits:
9. Check if a decimal number is a palindrome:
10. Generate uniform random numbers:
11. Rectangle intersection:

Arrays

1. 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.
2. 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.
3. 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]

Strings

Linked Lists

Stacks and queues

Binary trees

1. Test if a binary tree is height balanced
2. Test if a binary tree is symmetric
3. Compute the lowest common ancestor (LCA) in a binary tree
4. Compute the LCA when nodes have parent pointers
5. Sum the root-to-leaf paths in a binary tree
6. Find a root-to-leaf path with a specified sum
7. Implement an iorder traversal without recursion
8. Implement a preorder traversal without recursion
9. Compute the kth node in an inorder traversal
10. Compute the successor (Assume nodes have a parent field)
11. Implement an inorder traversal with O(1) space (Assume nodes have a parent field)
12. Reconstruct a binary tree from traversal data
13. Reconstruct a binary tree from preorder traversal with markers
14. Form a linked list from the leaves of a binary tree
15. Compute the exterior of a binary tree
16. Compute the right sibling tree
17. Check if two binary trees are identical
18. Level order traversal of a binary tree
19. Convert binary tree to doubly linked list
20. Serialize/Deserialize a binary tree
21. Connect all siblings in a binary tree
22. Mirror binary tree nodes
23. Delete zero sum sub-trees
24. N-ary tree to binary tree and back

Heaps

Searching

Hash tables

Sorting

Binary search trees

Recursion

Dynamic Programming

1. Count the number of score combinations

Greedy Algorithms and Invariants

Graphs

Parallel Computing