# CodePath Mock Interview Question Bank

**Strings / Arrays**
[Closest in Age](#Closest-In-Age) (Easy / Medium)
[Camelcase Matching](#Camelcase-Matching) (Easy / Medium)
[My Calendar](#My-Calendar) (Easy / Medium)
[Longest Peak](#Longest-Peak) (Medium / Hard)
[Basic Calculator](#Basic-Calculator) (Medium / Hard)

**Binary Trees**
[Branch Sums](#Branch-Sums) (Easy)
[Are Cousins](#Are-Cousins) (Easy / Medium)
[All Nodes Distance K](#All-Nodes-Distance-K) (Medium)

**Graphs**
[Network Delay Time](#Network-Delay-Time) (Medium)
[River Sizes](#River-Size) (Medium)

### Closest In Age
**Problem**:

We are given the ages of people from two different families. We want to find the ages of the two people from the two families who are closest in age.

For example:

Given:
family1 = {50, 15, 20, 55}
family2 = {5, 2, 10, 22}

Return:
{20, 22}

**Clarifying Questions**
- Are the two families always going to have the same number of people?
- No
- What if there are multiple age pairs that have the same difference?
- Return any of the pair

**Hints**

Hint 1: Can we look at all possible differences in ages?

Hint 2: Implementing the solution in Hint 1 is very inefficient. Can we somehow avoid looking at ages that we know are not close to each other?

Hint 3: Would it help if we sorted the ages in the two arrays?

Hint 4: Now that the ages are sorted, can we use two pointers for each of the arrays to only match the ages that are closest to each other?

**General Approach**

1. Sort both arrays
2. Keep two pointers for the two arrays and start each pointer at the beginning of the array
3. Evaluate the difference between the numbers at the two pointers
a. If it's 0, return the numbers at the two pointers
b. Otherwise, increment the pointer that's pointing to the smaller number
c. Keep tracking of the 'smallest difference' we've seen so far
7. Return the 'smallest difference' value we've been keeping track off after we've looked through all of one array

**Potential Follow-up Questions**
- What if we want to return all the pairs with the same minimum difference?
- What if we can't sort the ages?
- What if we want to return the closest aged person for every person?
- For example, given: `family1 = {10, 20, 30}` and `family2 = {11, 25}`, return: `{{10, 11}, {20, 25}, {30, 25}`

#### Leetcode Reference
[Mininum Absolute Difference](https://leetcode.com/problems/minimum-absolute-difference/)

### Camelcase Matching

**Problem**
A query word matches a given pattern if we can insert lowercase letters to the pattern word so that it equals the query.

Given a list of queries, and a pattern, return an answer list of booleans, where `answer[i]` is true if and only if `queries[i]` matches the pattern.

Example:

Input: 
queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
pattern = "FB"

Output: [true,false,true,true,false]

"FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

**Clarifying Questions**
1. Is the pattern always going to be only uppercase letters?
a. Yes

**Hints**
1. Given a single pattern and word, how can we solve it?
2. Would it help if we had two pointers, one for the word and one for the pattern?

**General Approach**
For each string, match it with the pattern and pass the result.

The match process uses `i` for query pointer and `j` for pattern pointer, each iteration:

- If current char query[i] matches pattern[j], increase pattern pointer
- If does not match and query[i] is lowercase, keep going
- If does not match and query[i] is captalized, return false

#### Leetcode Reference
[Camelcase Matching](https://leetcode.com/problems/camelcase-matching/)

### My Calendar

**Problem**

Implement a `MyCalendar` class to store events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, `boolean book(int start, int end)`. Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

For each call to the method `MyCalendar.book`, return `true` if the event can be added to the calendar successfully without causing a double booking. Otherwise, return `false` and do not add the event to the calendar.

Your class will be called like this:

MyCalendar cal = new MyCalendar();
cal.book(start, end);

**Clarifying Questions**
- How is time represented?
- Do we need to worry about times not on the hour, ie 4:30?
- Do we only need to worry about the hours in one day? Or do we also need to consider times in different days? (IE: 3pm Monday vs 3pm Tuesday)

**Hints**
1. It could be helpful to create a helper method `isOverlapping()`
2. How should we store the events to best be able to see whether there will be a time conflict?
3. Sort the events by start/end time, and in sorted order so we can easily find if there will be a conflict.

**General Approach**
1. Maintain a list of interval events.
2. Two events overlap if start1 < end2 && start2 < end1

**Follow-up Questions**
1. Can we do better than an n^2 runtime?
- Hint: If we maintained our events in sorted order, we could check whether an event could be booked in O(log N)O(logN) time (where NN is the number of events already booked) by binary searching for where the event should be placed
2. [Calendar, Part II, Allow Double Bookings But Not Triple Bookings](https://leetcode.com/problems/my-calendar-ii/)

#### Leetcode Reference
[My Calendar](https://leetcode.com/problems/my-calendar-i/)

### Longest Peak

**Problem**

Given an array of integers, return the length of the longest peak in the array.

A ‘peak’ is a sequence of continuous integers that are strictly increasing and then strictly decreasing.

Example:

Input: [1, 2, 2, 2, 0, 1, 2, 3, 2]
Output: 5 // 0, 1, 2, 3, 2

**Clarifying Questions**

- Is there a minimum number of integers that are needed to form a peak?
- Yes, at least 3 continuous integers.
- 1 2 3 2 -> is a peak
- 1 2 -> not a peak
- 5 2 3 -> not a peak
- 5 -> not a peak
- Can there be negative numbers in the input?
- Yes
- Are we guaranteed a peak from the input?
- No. If there is no peak, return 0

**Hints**

1. There are different ways to solve this problem, but the least error-prone way will be to iterate through the array, and start by assuming every number is the 'tip' of a peak.
2. When you find a peak, use the two pointer approach to expand the length of the peak from left and right.

**General Approach**
- keep track of longestPeakLength, initialized at 0
- iterate through array
- determine if the current element is a peak
- if it’s not, ignore it and continue
- if it is a peak
- initialize leftPointer = i - 2
- while leftPointer is decreasing, keep expanding it
- initialize rightPointer = i + 2
- while rightPointer is increasing, keep expanding it
- update longPeakLength if this peak’s length is longer than the last longest peak length we found

#### Common Missed Use Cases
- `[10 9 8 7 6]`
- `[1 1 1 1 1]`
- `[1, 2, 1, 2, 1, 2]`

#### Leetcode Reference
[Longest Mountain in Array](https://leetcode.com/problems/longest-mountain-in-array/)

### Basic Calculator

**Problem**

Implement a basic calculator to evaluate a simple expression string.

For example:

Given: "3+2*2"
Return: 7

Given: "3+5/2 "
Return: 5

**Clarifying Questions**
- Do we have to worry about negative integers?
- Yes
- Do we have to worry about decimal points when doing division?
- Integer division should truncate to 0. For example, Given: ` 3 / 2 `, Return: `1`
- Can we use the built-in `eval` function?
- No
- Is the string input always going to be valid?
- No, there could be strings like:
- "3+"
- "++-/"
- "3+/2"
- Are numbers always single digit?
- No, a valid string could be: "12+342"

**Hints**
1. How does the order of operations matter when we're evaluating `+` and `-` versus `/` and `*`?
2. Can we use a stack to help us keep track of the operations that need to be done in a specific order?

**General Approach**

1. Keep track of the most recently processed operator `op`
2. Keep track of our current number `num`
3. Parse the string one character at a time
a. If the character is a digit, add it to `num`
b. If the character is `+`, push `num` to the stack
c. If the character is a `-`, push `-num` to the stack
d. If the character is a `*` or `/`, pop from the stack, perform the operation on the number, and push it back to the stack
4. Sum up all the numbers in the stack

**Potential Follow-up Questions**
[Calculator with Parentheses Expressions](https://leetcode.com/problems/basic-calculator-iii/)

#### Leetcode Reference
[Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/)

### Branch Sums

**Problem**

Given a binary tree, return a list of its branch sums from leftmost branch sum to rightmost branch sum.

A branch sum is the sum of all values in a tree branch. A branch is a path of nodes that starts at the root and ends at a leaf node.

Example:

Input:
      1
    /   \
   2     3
 
 Output:
 [3, 4]

Sample Node Class:
Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Java:

public class Node {
    int val;
    Node left;
    Node right;
    Node() {}
    Node(int val) { this.val = val; }
    Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
  }
}

**Clarifying Questions**

- Is it always a complete binary tree?
- No

**Hints**
1. Can we use depth first search to help us?
2. Would it help if we used recursion and passed in the value of the current sum of visited nodes in that branch so far?

**General Approach**

Visit each node with DFS while keeping track of the sum of the nodes visited in the branch so far

Pseudocode:

getBranchSums(node)
   sums               # initial list of branch sums
   helper(root, 0, sums)
   return sums
   
helper(node, currentSum, sums)
    if node == null, return         # base case
    currentSum += node.value 
    if (node.isLeaf())
        sums.add(currentSum)
    
    helper(node.left, currentSum, sums)
    helper(node.right, currentSum, sums)

**Potential Follow-up Questions**
- How can we modify our solution if we were no longer guaranteed that each node has a maximum of 2 children? For example, what if some nodes had 3 children and others had 5?

### Are Cousins

**Problem**

Given a binary tree and two node values, return whether the two nodes are cousins.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

Example:

Given:
     1
   /   \
  2     3
 /
4

n1 = 3, n2 = 4

Return: false

Given:
     1
   /   \
  2     3
 /       \
4         5

n1 = 4, n2 =5

Return: true

Sample Node Class:
Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Java:

public class Node {
    int val;
    Node left;
    Node right;
    Node() {}
    Node(int val) { this.val = val; }
    Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
  }
}

**Clarifying Questions**

- Are node values guaranteed to be unique:
- Yes

**Hints**

**General Approaches**

Breadth First Search Approach

1. Perform a level order traversal using a queue.
2. For every node that is popped off the queue, check if it's Node `x` or Node `y`. If it is, then for the first time, set both siblings and cousins flags as true to mark the possibility of siblings or cousins.
3. To distinguish siblings from cousins, insert markers in the queue.
- After inserting the children for each node, also insert a null marker. This marker defines a boundary for each set of siblings and helps differentiate a pair of siblings from cousins.
4. Whenever we encounter the null marker, set the siblings flag to false. (Since the marker means that's the end of a group of siblings.)
5. The second time we encounter Node `x` or Node `y`, we know whether they are siblings or cousins.

Example Java Implementation:

public boolean isCousins(TreeNode root, int x, int y) {

        // BFS Queue
        Queue <TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            boolean siblings = false;
            boolean cousins = false;

            int nodesAtDepth = queue.size();

            for (int i = 0; i < nodesAtDepth; i++) {
                TreeNode node = queue.remove();

                // If we see a null marker, we know siblings should be set to false now.
                if (node == null) {
                    siblings = false;
                } else {
                    if (node.val == x || node.val == y) {
                        // Set both the siblings and cousins flag to true
                        // for a potential first sibling/cousin found.
                        if (!cousins) {
                            siblings = cousins = true;
                        } else {
                            // If the siblings flag is still true this means we are still
                            // within the siblings boundary and hence the nodes are not cousins.
                            return !siblings;
                        }
                    }

                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                    // Add null marker for the siblings
                    queue.add(null);
                }
            }
            
            // After the end of a level if `cousins` is set to true
            // This means we found only one node at this level
            if (cousins) return false;
        }
        return false;
    }

#### Leetcode Reference
[Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/)

### All Nodes Distance K

**Problem**
We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node.

Example:

Input: 
root = [3,5,1,6,2,0,8,null,null,7,4]
target = 5
K = 2

        3
      /   \   
     5     1
    / \   / \
   6  2  0  8
     / \
    7  4
    
Output: [7,4,1]

Sample Node Class:
Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Java:

public class Node {
    int val;
    Node left;
    Node right;
    Node() {}
    Node(int val) { this.val = val; }
    Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
  }
}

**Clarifying Questions**
- Do we have to return the values in any specific order?
- No
- Is the target node guaranteed to be found in the tree?
- Yes
- Are nodes unique in value?
- Yes

**Hints**
1. We could do a BFS to find all nodes `k` nodes away from the `target` node. However, because tree nodes only know about their children, we can't traverse backwards. How can we solve this?
a. Traverse the tree and store the `parent` node of each node in a Hashmap
b. Convert the tree to a graph

**General Approaches**

1. Do a DFS to store information about each node's parent
2. Then do a BFS to find all nodes distance `k` away

Example Java solution:

Map<TreeNode, Integer> map = new HashMap<>();
        
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> res = new LinkedList<>();
        find(root, target);
        dfs(root, target, K, map.get(root), res);
        return res;
    }
    
    // find target node first and store the distance in that path that we could use it later directly
    private int find(TreeNode root, TreeNode target) {
        if (root == null) return -1;
        if (root == target) {
            map.put(root, 0);
            return 0;
        }
        int left = find(root.left, target);
        if (left >= 0) {
            map.put(root, left + 1);
            return left + 1;
        }
		int right = find(root.right, target);
		if (right >= 0) {
            map.put(root, right + 1);
            return right + 1;
        }
        return -1;
    }
    
    private void dfs(TreeNode root, TreeNode target, int K, int length, List<Integer> res) {
        if (root == null) return;
        if (map.containsKey(root)) length = map.get(root);
        if (length == K) res.add(root.val);
        dfs(root.left, target, K, length + 1, res);
        dfs(root.right, target, K, length + 1, res);
    }

**Potential Follow-up Questions**
1. Can we solve this problem without modifying the tree nodes structure or creating a hashmap?

#### Leetcode Reference
[All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/)

### Network Delay Time

**Problem**

There are N network nodes, labelled 1 to N.

We are given a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example:

Input: 
times = [[2,1,1],[2,3,1],[3,4,1]]
N = 4
K = 2

Output: 2

**Hints**
1. This looks like a graph problem, so how what type of traversals can we consider to look at the nodes in the graph?

**General Approach**
- maintain dist[node], the earliest that we arrived at each node.
- When visiting a node while elapsed time has elapsed, if this is the currently-fastest signal at this node, broadcast signals from this node.

An example Java solution using DFS:

class Solution {
    Map<Integer, Integer> dist;
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> graph = new HashMap();
        for (int[] edge: times) {
            if (!graph.containsKey(edge[0]))
                graph.put(edge[0], new ArrayList<int[]>());
            graph.get(edge[0]).add(new int[]{edge[2], edge[1]});
        }
        for (int node: graph.keySet()) {
            Collections.sort(graph.get(node), (a, b) -> a[0] - b[0]);
        }
        dist = new HashMap();
        for (int node = 1; node <= N; ++node)
            dist.put(node, Integer.MAX_VALUE);

        dfs(graph, K, 0);
        int ans = 0;
        for (int cand: dist.values()) {
            if (cand == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, cand);
        }
        return ans;
    }

    public void dfs(Map<Integer, List<int[]>> graph, int node, int elapsed) {
        if (elapsed >= dist.get(node)) return;
        dist.put(node, elapsed);
        if (graph.containsKey(node))
            for (int[] info: graph.get(node))
                dfs(graph, info[1], elapsed + info[0]);
    }
}

Possible improvement:
- To speed things up, at each visited node we'll consider signals exiting the node that are faster first, by sorting the edges.

**Potential Follow-up Questions**
- Can we come up with an n^2 solution?
- Hint: Use Dijkstra's algorithm to find the shortest path from our source to all targets

#### Leetcode Reference
[Network Delay Time](https://leetcode.com/problems/network-delay-time/)

### River Size

**Problem**
You are given a 2D array containing 0’s and 1’s. 0’s represent land, and 1’s present parts of a river. A river consists of any number of 1’s that are horizontally or vertically adjacent (not diagonally). The number of adjacent 1’s determine the river’s size.

Write a function that returns an array of the sizes of all rivers in a matrix.

Example:

Input:
{
[1, 0, 0],
[1, 0, 1].
[1, 1, 0]
}

Output:
{4, 1}

**Clarifying Questions**
Does the 2D array always have the same width and height?
- No

**Hints**
- Traverse the matrix as if it's a graph, which each element having up to 4 neighboring nodes (left, right, top, bottom)
- Whenever you see a 1 in the matrix, you can use DFS or BFS to traverse find out the length of the river.
- You will need to prevent visiting nodes that have already been visited to avoid an infinite loop. The best way to do this is by creating another 2D array that stores the 'visited' state of each node

**General Approach**

- Keep track of visited nodes in another 2D array
- Also keep track of all the river lengths found so far with `riverSizes` variable
- Use BFS or DFS to traverse through matrix
- When we see a '1', traverse through it's neighbors (top, down, left, right) to get the full length of the river
- When we get the full length of a river, add it to our `riverSizes` list

An example Java solution:

public List<Integer> riverSizes(int[][] matrix) {
        List<Integer> sizes = new ArrayList<>();
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                traverseNode(i, j, matrix, visited, sizes);
            }
        }

        return sizes;
    }

    public void traverseNode(int i, int j, int[][] matrix,
                                    boolean[][] visited, List<Integer> sizes) {
        int curRiverSize = 0;
        Stack<Integer[]> nodesToExplore = new Stack<>();
        nodesToExplore.push(new Integer[] {i, j});
        while (!nodesToExplore.empty()) {
            Integer[] curNode = nodesToExplore.pop();
            i = curNode[0];
            j = curNode[1];
            
            if (visited[i][j]) {
                continue;
            }
            
            visited[i][j] = true;
            if (matrix[i][j] == 0) {
                continue;
            }
            
            curRiverSize++;
            List<Integer[]> unvisitedNeighbors = getUnvisitedNeighbors(i, j, matrix, visited);
            for (Integer[] neighbor : unvisitedNeighbors) {
                nodesToExplore.add(neighbor);
            }
            if (curRiverSize > 0) {
                sizes.add(curRiverSize);
            }
        }
    }
    
    public List<Integer[]> getUnvisitedNeighbors(int i, int j, int[][] matrix,
                                                        boolean[][] visited) {
        // check the top, bottom, left, right cells
        // if cell is not out of bounds, and not marked as visited, then add to list to return
    }

#### Similar leetcode problems:
- [Number of Islands](https://leetcode.com/problems/number-of-islands/)
- [Max Area of Island](https://leetcode.com/problems/max-area-of-island/)