Array Problems

1. Median of Arrays

● Question: Find the median of two sorted arrays.

arr1 = [1, 3, 5]

arr2 = [2, 4, 6]

median(arr1, arr2) = 3.5

2. 0-1 Knapsack
● Question: Given a list of items with values and weights, as well as a max weight, find the
maximum value you can generate from items where the sum of the weights is less than
the max.
● Eg.

items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}

maxWeight = 5

knapsack(items, maxWeight) = 22

1
3. Matrix product
● Question: Given a matrix, find the path from top left to bottom right with the
greatest product by moving only down and right.
● Eg.

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

1 ‑> 4 ‑> 7 ‑> 8 ‑> 9

[‑1, 2, 3]
[4, 5, ‑6]
[7, 8, 9]

‑1 ‑> 4 ‑> 5 ‑> ‑6 ‑> 9

2
4. Find Duplicates
● Question: Given an array of integers where each value 1 <= x <= len(array), write a
function that finds all the duplicates in the array.
● Eg.

dups([1, 2, 3]) = []
dups([1, 2, 2]) = [2]
dups([3, 3, 3]) = [3]
dups([2, 1, 2, 1]) = [1, 2]

5. Consecutive Array
● Question: Given an unsorted array, find the length of the longest sequence of
consecutive numbers in the array.
● eg.

consecutive([4, 2, 1, 6, 5]) = 3, [4, 5, 6]

3
6. Zero Matrix
● Question: Given a boolean matrix, update it so that if any cell is true, all the cells in that
row and column are true.
● Eg.

[true, false, false] [true, true, true ]

7. Square Submatrix
● Question: Given a 2D array of 1s and 0s, find the largest square subarray of all 1s.
● Eg. Given a 2D array of 1s and 0s, find the largest square subarray of all 1s.

4
8. Merge K Arrays
● Question: Given k sorted arrays, merge them into a single sorted array.
● Eg.

merge({{1, 4, 7},{2, 5, 8},{3, 6, 9}}) = {1, 2, 3, 4, 5, 6, 7, 8, 9}

9. Matrix Search
● Question: Given an n x m array where all rows and columns are in sorted order, write a
function to determine whether the array contains an element x.
● Eg.

contains([1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]) = True

5
10. Merge Arrays
● Question: Given 2 sorted arrays, A and B, where A is long enough to hold the contents
of A and B, write a function to copy the contents of B into A without using any buffer or
additional memory.
● Eg.

A = {1,3,5,0,0,0}

B = {2,4,6}
mergeArrays(A, B)
A = {1,2,3,4,5,6}

11. Zero Sum Subarray

zeroSum({1, 2, -5, 1, 2, -1}) = [2, -5, 1, 2]

6
12. Permutations
● Question: Write a function that returns all permutations of a given list.
● Eg.

permutations({1, 2, 3})
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

7
13. N Stacks
● Question: Implement N > 0 stacks using a single array to store all stack data (you may
use auxiliary arrays in your stack object, but all of the objects in all of the stacks must be
in the same array). No stack should be full unless the entire array is full.
● Eg.

N = 3;

capacity = 10;
Stacks stacks = new Stacks(N, capacity);
stacks.put(0, 10);

stacks.put(2, 11);
stacks.pop(0) = 10;

stacks.pop(2) = 11;

8
14. Anagrams
● Question: Given two strings, write a function to determine whether they are
anagrams.
● Eg.

isAnagram("", "") = true

isAnagram("A", "A") = true

9
Graph Problems

15. Build Order

0:

1: 0

2: 0

3: 1, 2

4: 3

output: 0, 1, 2, 3, 4

10
16. Shortest Path

● Question: Given a directed graph, find the shortest path between two nodes if one
exists.
● Eg.

Directed graph:

shortestPath(2, 3) = 2 -> 5 -> 4 -> 3

11
Recursion Problems

17. Random Binary Tree

● Question: Implement a binary tree with a method getRandomNode() that returns a

getRandomNode() = 5

getRandomNode() = 8

getRandomNode() = 1

12
18. Lowest Common Ancestor

● Question: Given two nodes in a binary tree, write a function to find the lowest
common ancestor.
● Eg.

lcs(4, 3) = 1

lcs(6, 7) = 3

13
19. Sum

● Question: Given two integers, write a function to sum the numbers without using any
arithmetic operators.

20. Reverse Stack

● Question: Given a stack, reverse the items without creating any additional data
structures.
● Eg.

reverse(1->2->3) = 3->2->1

14
21. Tree to Doubly Linked List

● Question: Given a tree, write a function to convert it into a circular doubly linked list
from left to right by only modifying the existing pointers.
● Eg.

<- 4 <-> 2 <-> 5 <-> 1 <-> 6 <-> 3 <-> 7 ->

15
22. Longest Consecutive Branch

● Question: Given a tree, write a function to find the length of the longest branch of nodes
in increasing consecutive order.
● Eg.

length = 3

16
23. Print Reversed Linked List

● Question: Given a linked list, write a function that prints the nodes of the list in
reverse order.
● Eg.

printReversedList(1 -> 2 -> 3)

17
24. Balanced Binary Tree

● Question: Given a binary tree, write a function to determine whether the tree is
balanced.
● Eg.

Balanced tree (all branches are same height +- 1):

Balanced tree (all subtrees are balanced):

18
25. Binary Search Tree Verification

● Question: Given a binary tree, write a function to test if the tree is a binary search tree.
● Eg.

Valid:

Invalid:

19