14 Patterns to Ace Any Coding Interview Question by Fahim ul Haq
Recursive approach: solve f(c, i) with c is the remaining capacity and i is th current item index At each level, we branch with the item at index i (if enough capacity) and without it
public int knapsack(int[] profits, int[] weights, int c) {
return knapsack(profits, weights, c, 0, 0);
}
public int knapsack(int[] profits, int[] weights, int c, int i, int sum) {
if (i == profits.length || c <= 0) {
return sum;
}
// Not
int sum1 = knapsack(profits, weights, c, i + 1, sum);
// With
int sum2 = 0;
if (weights[i] <= c) {
sum2 = knapsack(profits, weights, c - weights[i], i + 1, sum + profits[i]);
}
return Math.max(sum1, sum2);
}
Memoization: store a[c][i] (c is the remaining capacity, i is the current item index)
As we need to store the 0 capacity, we have to init the array this way:
int[][] a = new int[c + 1][n] // n is the number of items
Time and space complexity: O(n * c)
public int knapsack(int[] profits, int[] weights, int capacity) {
// Capacity from 1 to n
Integer[][] a = new Integer[capacity][profits.length];
return knapsack(profits, weights, capacity, 0, 0, a);
}
public int knapsack(int[] profits, int[] weights, int capacity, int i, int sum, Integer[][] a) {
if (i == profits.length || capacity == 0) {
return sum;
}
// If value already exists, return
if (a[capacity - 1][i] != null) {
return a[capacity][i];
}
// With
int sum1 = knapsack(profits, weights, capacity, i + 1, sum, a);
// Without
int sum2 = 0;
if (weights[i] <= capacity) {
sum2 = knapsack(profits, weights, capacity - weights[i], i + 1, sum + profits[i], a);
}
a[capacity - 1][i] = Math.max(sum1, sum2);
return a[capacity - 1][i];
}
Two dimensional array: a[n + 1][c + 1] // n the number of items and c the max capacity
First row and first column are set to 0
a[row][col] represent the max profit with items 1..row at capacity col
remainingWeight = col - itemWeight // col: current max capacity
a[row][col] = max(a[row - 1][col], itemValue + a[row - 1][remainingWeight]) // max between item not selected and item selected + max remaining weight
If remainingWeight < 0, we can’t chose the item so a[row][col] = a[row - 1][col]
Return last element of the array
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
int[][] a = new int[profits.length + 1][capacity + 1];
for (int row = 1; row < profits.length + 1; row++) {
int value = profits[row - 1];
int weight = weights[row - 1];
for (int col = 1; col < capacity + 1; col++) {
int remainingWeight = col - weight;
if (remainingWeight < 0) {
a[row][col] = a[row - 1][col];
} else {
a[row][col] = Math.max(
a[row - 1][col],
value + a[row - 1][remainingWeight]
);
}
}
}
return a[profits.length][capacity];
}
If we need to compute a result like “determine if a subset exists” that return a boolean, the array type is boolean[][]
As we are only interested in the previous row, we can also use an int[2][n] array
Solution for solving a problem recursively
Loop:
Iterate over each number of an array and swap it to its correct position
At the end, we may iterate on the array to check which number is not at its correct position
If numbers are not within the 1 to n range, we can simply drop them
Alternative: marker technique (mark a result by setting a[i] to negative for example)
Identify an optimal subproblem or substructure in the problem and determine how to reach it
Focus on what you have now (don’t think about what comes next)
We may want to apply the traversal technique to have a global context for the identification part (a map of letters/positions etc.)
Given K sorted array, technique to perform a sorted traversal of all the elements of all arrays
We need to keep track of which structure the min element come from (tracking the array index or taking the next node if it’s a linked list)
Iterate over the linked list with two pointers simultaneously either with:
This technique can also be applied on other problems where we need to find a cycle (f(slow) and f(f(fast)) may converge)
Simplify the problem. If solvable, generalize to the initial problem.
Example: sort the array first
Range of elements in a specific window size
Two pointers left and right:
Technique to find all the possible permutations or combinations
Start with an empty set, for each element of the input, add them to all the existing subsets to create new subsets
Example:
For each level, we iterate from 0 to size // size is the fixed size of the list
List<List<Integer>> findSubsets(int[] a) {
List<List<Integer>> subsets = new ArrayList<>();
// Add subset []
subsets.add(new ArrayList<>());
for (int n : a) {
// Fix the current size
int size = subsets.size();
for (int i = 0; i < size; i++) {
// Copy subset
ArrayList<Integer> newSubset = new ArrayList<>(subsets.get(i));
// Add element
newSubset.add(n);
subsets.add(newSubset);
}
}
return subsets;
}
Runner technique
Subsets technique or recursion + backtracking
Binary search
Sliding window technique
Example:
Sliding window technique
Example:
Two heaps technique
Runner technique
Two pointers technique
Example:
Cyclic sort technique
Traversal technique
Iterate with two pointers, one over the starts, another one over the ends
Handle the element with the lowest value first and generate an event
Example: how many rooms for n meetings => meeting started, meeting started, meeting ended etc.
Top K elements technique
Greedy technique
K-way merge technique
Topological sort technique
Heap data structure
Possibly two heaps technique
Finding the K biggest elements:
Finding the k smallest elements:
If there is an edge from U to V, then U <= V
Possible only if the graph is a DAG
Algo:
To check if there is a cycle, we must compare the size of the produced array to the number of vertices
List<Integer> sort(int vertices, int[][] edges) {
if (vertices == 0) {
return Collections.EMPTY_LIST;
}
List<Integer> sorted = new ArrayList<>(vertices);
// Adjacency list graph
Map<Integer, List<Integer>> graph = new HashMap<>();
// Count of incoming edges for each vertex
Map<Integer, Integer> inDegree = new HashMap<>();
for (int i = 0; i < vertices; i++) {
inDegree.put(i, 0);
graph.put(i, new LinkedList<>());
}
// Init graph and inDegree
for (int[] edge : edges) {
int parent = edge[0];
int child = edge[1];
graph.get(parent).add(child);
inDegree.put(child, inDegree.get(child) + 1);
}
// Create a source queue and add each source (a vertex whose inDegree count is 0)
Queue<Integer> sources = new LinkedList<>();
for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
if (entry.getValue() == 0) {
sources.add(entry.getKey());
}
}
while (!sources.isEmpty()) {
int vertex = sources.poll();
sorted.add(vertex);
// For each vertex, we will decrease the inDegree count of its children
List<Integer> children = graph.get(vertex);
for (int child : children) {
inDegree.put(child, inDegree.get(child) - 1);
if (inDegree.get(child) == 0) {
sources.add(child);
}
}
}
// Topological sort is not possible as the graph has a cycle
if (sorted.size() != vertices) {
return new ArrayList<>();
}
return sorted;
}
Traverse the input and generate another data structure or optional events
Start the problem from this new state
Keep two heaps:
May be required to balance them to have at most a difference in terms of size of 1
Two pointers iterating through the data structure in tandem until one or both pointers hit a certain condition
Often useful when structure is sorted. If not sorted, we may want to sort it first.
Most of the times (not always): first pointer is at the start, the second pointer is at the end
The two pointers can also be on two different ds, still iterating in tandem (e.g. comparing strings containing backspaces)
Time complexity is linear
Reverse the liked list (or a subpart only), implement the algo then reverse it again to the initial state