Brian T. Liao
Aug 28, 2019 • 41 min read

# Interview Cram II

They say teaching is the best way to learn.

# Number of Islands

LeetCode

## Problem

Given a 2d map, ‘1’ is an island space, and ‘0’ is an ocean space. An island is all island spaces connected. Count the number of islands.

## Walkthrough

To get a whole island, we can use DFS to recursively see if spaces adjacent are also part of the same island. Once seen, mark it as ‘s’ so we won’t explore the space again.

We can use two for loops, going through each column and each row. On each new seen island, increase our counter, and DFS the island, updating each space to seen to not be double counted.

### Techniques

Recursion, Search, Union-Find

### Complexity

Time: O(m * n) where m is number of rows and n is number of columns. We have two for loops and run DFS on each space which is O(m * n) as well in the worst case.

`DFS is O(|E|+|V|)?`

Space: O(1) because we use the grid and never change the size.

## Python

``````class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 5 variable for counting islands
count = 0
# 6 go through grid, seen islands are ignore as they are marked 's'
for col in range(len(grid)):
for row in range(len(grid[col])):
if grid[col][row] == '1':
count += 1
self.dfs(grid, row, col)
return count

def dfs(self, grid, row, col) -> int:
# 1 check if block's out of bounds
if col < 0 or col >= len(grid):
return
if row < 0 or row >= len(grid[0]):
return
# block is in bounds
# 2 check if block is island
if grid[col][row] == '1':
# 3 block is seen
grid[col][row] = 's'
# 4 dfs your blocks's north, south, east, west (connected blocks)
self.dfs(grid, row + 1, col)
self.dfs(grid, row - 1, col)
self.dfs(grid, row, col + 1)
self.dfs(grid, row, col - 1)
``````

## Java

``````class Solution {
public int numIslands(char[][] grid) {
// 5. variable to count number of islands
int count = 0;
// 6. go through the grid, run dfs on new islands seen. seen islands are marked 's'
for (int col = 0; col < grid.length; col++) {
for (int row = 0; row < grid[0].length; row++) {
if (grid[col][row] == '1') {
count += 1;
dfs(grid, row, col);
}
}
}
return count;
}

public void dfs(char[][] grid, int row, int col) {
// 1. check spot is in bounds
if (col < 0 || col >= grid.length) {
return;
}
if (row < 0 || row >= grid[0].length) {
return;
}
// 2. check spot is island
if (grid[col][row] != '1') {
return;
}

// 3. set spot to seen
grid[col][row] = 's';

// 4. recursive check left, right, up, and down of spot.
dfs(grid, row - 1, col);
dfs(grid, row + 1, col);
dfs(grid, row, col - 1);
dfs(grid, row, col + 1);
}
}
``````

# Coin Change

LeetCode

## Problem

Given a list of different coin values and a goal value, give the minimum number of coins to make the goal value, or -1 if not possible.

## Walkthrough

We can use dynamic programming, our subproblems is for a value i, arr[i], the min number of coins is min(arr[i], 1 + arr[i - coin]) for all coins. Initialize each value to ‘inf’ and loop from 0 to i and return arr[value] or -1 if not possible (arr[value] will still be ‘inf’).

``````subproblem? want for value i, want min number of coins. arr[i] = min(arr[i], 1 + arr[i - coin]) for all coins
java has an overflow issue
``````

### Techniques

Dynamic Programming and Recursion

### Complexity

Time: O(m * n) where m is number of coins and n is the goal value. We have two for loops, the inner loop on coins solves subproblems, and the outer loop iterates the subproblems we solve.

Space: O(n) need a cache for goal.

## Python

``````class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 1. create an array for the min amount of coins that make each index amount
# 2. set each value to infinity in case it is not possible to make that amount of coins
# 3. set index 0 to 0 because it takes 0 of each coins to make \$0. Base Case.
minNumCoinsToMakeAmount = [float('inf')] * (amount + 1)
minNumCoinsToMakeAmount[0] = 0
# 4. solve each subproblem in order (including amount)
for curAmount in range(amount + 1):
# 5. solve the subproblem. Min number of coins using each coin.
for coin in coins:
# 6. check the coin value is less than the curAmount. If not, we will get a negative index, out of bounds.
if coin <= curAmount:
# update if using this coin (1 + num coins to make this amount with the coin value subtracted) is less than currently. This removes 'inf' if it is possible to make the coin amount
minNumCoinsToMakeAmount[curAmount] = min(minNumCoinsToMakeAmount[curAmount], 1 + minNumCoinsToMakeAmount[curAmount - coin])
# if the array has a value for amount, it is possible. Else if it's 'inf', it's not possible and return -1.
return minNumCoinsToMakeAmount[amount] if minNumCoinsToMakeAmount[amount] != float('inf') else -1
``````

## Java

``````class Solution {
public int coinChange(int[] coins, int amount) {
// 1. array for dynamic programming to the coin amount
int[] fewestCoinsToAmount = new int[amount + 1];
// 2. get the value of number of coins to each ammount
for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
// 3. Use Integer.MAX_VALUE as a placeholder in case no coin combination
fewestCoinsToAmount[currentAmount] = Integer.MAX_VALUE;
// 4. count number of way using each type of coin
for (int coin : coins) {
// 5. currentAmount must be greated than the coin value and previous coin value has a number of ways
if (currentAmount >= coin && fewestCoinsToAmount[currentAmount - coin] != Integer.MAX_VALUE) {
// 6. update if the number of coins with this coin is less than current number of coins
int numCoinsWithCurrentCoin = 1 + fewestCoinsToAmount[currentAmount - coin];
if (numCoinsWithCurrentCoin < fewestCoinsToAmount[currentAmount]) {
fewestCoinsToAmount[currentAmount] = numCoinsWithCurrentCoin;
}
}
}
}
int numberOfCoins = fewestCoinsToAmount[amount];
// 7. check that there is a way to make the amount with the coins given
if (numberOfCoins == Integer.MAX_VALUE) {
return -1;
}
return numberOfCoins;

}
}
``````

### Notes

Why is the dynamic programming array size amount + 1? What is the dynamic programming array called. “Cache?”

How to solve Dynamic Programming?

1. decide parameters to index on and what they represent
2. find base cases
3. find recurrence relation
4. find a valid iteration order and what to return

# Edit Distance

LeetCode

## Problem

Given word1 and word2, find the minimum number of operations required to convert word1 to word2. Operations are inserting a character, deleting a character, and replacing a character.

## Walkthrough

We can build up a solutiøn by solving subproblems. The cost of moving from a subword1 to a subword2 is first check if the final character is the same. Consider raptor. A subword that are the same are rapt and rapt. Both are the same so there is no operation done from rap and rap. Consider rapt and rapp. Here we need to replace a character. Which is just replace t with p from the subproblem of rap to rap. The alternative is removing a character or adding a character to either word. By creating a editDistance dynamic programming cache, we can solve the subproblems so solve the final solution.

### Techniques

Dynamic Programming and Recursion

### Complexity

Let m be the length of word1 and n be the distance of word2.

Time Complexity: O(m * n) from going through each subproblem of each word1 subword to each word2 subword.

Space Complexity: O(m * n) from the editDistance dynamic programming cache for each subproblem.

## Python

``````class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# 1. Have a 2d array where col, row is number of operations to go from word 1 to word 2
# why + 1? Consider 'horse' len -> 5 index 0 to 4. Want "" as 0 so e is 5
edit_distance = [[float('inf') for row in range(len(word1) + 1)] for col in range(len(word2) + 1)]
# 2. empty string to empty string is 0. So col 0 row 0 is 0. 'h' to '' is 1, so col 1, row 0 is 1.
# 'ho' to '' is 2, so col 2, row 0 is 2 and so on. This is our base case.
for col in range(len(edit_distance)):
edit_distance[col][0] = col
# 3. do the same for string 1 to string 2. I reversed col and row for word1 and 2.
for row in range(len(edit_distance[0])):
edit_distance[0][row] = row
# 4. Solve each subproblem for row 1. Then row 2 and so on.
for col in range(1, len(edit_distance)):
for row in range(len(edit_distance[0])):
# 5. subproblem: If letters at the index are equal, edit_distance (ed) is the changes
# up to the previous character. ed[row][col] = ed[row - 1][col - 1]
# else ed is the min of adding a character to col, to row, or changing a character
# ed[col][row] = min([1 + ed[col - 1][row], 1 + ed[col][row - 1], 1 + ed[col - 1][row - 1]])
if row > 0 and word2[col - 1] == word1[row - 1]:
edit_distance[col][row] = edit_distance[col - 1][row - 1]
else:
edit_distance[col][row] = min([1 + edit_distance[col - 1][row],
1 + edit_distance[col][row - 1],
1 + edit_distance[col - 1][row - 1]])
# 6. return edit distance from all characters of word 1 to word 2
return edit_distance[len(word2)][len(word1)]
``````

## Java

``````class Solution {
public int minDistance(String word1, String word2) {
// 1. Have a cost cache of subproblems cost to go from word1 to word2. Add 1 to both for a space for ''
int[][] editDistanceCost = new int[word1.length() + 1][word2.length() + 1];
// 2. set up for both word1 to word2 as '' and word2 to word1 as ''
for (int row = 0; row < word1.length() + 1; row++) {
editDistanceCost[row][0] = row;
}
for (int col = 0; col < word2.length() + 1; col++) {
editDistanceCost[0][col] = col;
}
// 3. solve each subproblem for each subword1 to subword2 in order
for (int row = 1; row < word1.length() + 1; row++) {
for (int col = 1; col < word2.length() + 1; col++) {
// 4. If both subwords are equal, cost is how much cost without the latest added letter
// else it's the min of the cost to add/remove one character from word1, or from word2, or replace a character
if (word1.charAt(row - 1) == word2.charAt(col - 1)) {
editDistanceCost[row][col] = editDistanceCost[row - 1][col - 1];
} else {
int replaceCost = 1 + editDistanceCost[row - 1][col - 1];
int addToWord1Cost = 1 + editDistanceCost[row - 1][col];
int addToWord2Cost = 1 + editDistanceCost[row][col - 1];
int minCost = replaceCost;
} else if (addToWord2Cost < minCost) {
}
editDistanceCost[row][col] = minCost;
}
}
}
// 5. return the general case solution, number of edits from word1 to word2;
return editDistanceCost[word1.length()][word2.length()];
}
}
``````

### Notes

Why do the subproblems work for adding and removing a letter?

# Construct Binary Tree from Preorder and Inorder Traversal

LeetCode

## Problem

Given a list as a preorder traversal of a tree and an inorder traversal of a tree, can you construct the original binary tree?

### Techniques

Recursion Search Trees

### Complexity

Time Complexity: O(n^2) Worst case everything is in a line. Each time we will have to find the index.

``````Possibly
``````

Space Complexity: O(h) The height of the tree as our recrusive stack goes up h times. The array size never exceeds the limit.

## Python

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 1. Preorder always has the top node of the tree first.
# Inorder always has the nodes of left side of tree left of head node and nodes right side of the tree right of the head node.
# Recursively split the tree and the preorder, inorder to solve the problem.
# 2. Base case: empty inorder array
if not inorder:
return None
# 4. split inorder into right of tree and left of tree
left = inorder[:index]
right = inorder[1+index:]
# 5. Create the node to return. Set left and right to recursively building tree.
node.left = self.buildTree(preorder, left)
node.right = self.buildTree(preorder, right)
return node
``````

## Java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder, int preorderIndex, int inorderStartIndex, int inorderEndIndex) {
// 1. Base Case if inorder start and end index are the same (the recursive inorder list is empty)
if (inorderStartIndex > inorderEndIndex) {
return null;
}
// 2. In preorder the head of a tree is always the first element
// 3. find head value in inorder array.
int headValueIndexInorder = 0; // will be replaced
for (int i = inorderStartIndex; i <= inorderEndIndex; i++) {
break;

}
}
// 4. Recursively call left and right trees. In inorder, all nodes left of head are left of headValueIndexInorder and all nodes right of head are right of headValueIndexInorder

}

public TreeNode buildTree(int[] preorder, int[] inorder) {
// . call the Helper function with the index set to the sizes of the arrays
return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
}
}
``````

### Notes

Java bounds checking was ‘>’. Java had to have index pointers and can’t just create new arrays. Can do postorder, just creat the tree right to left.

# Find the Duplicate Number

LeetCode

## Problem

Given an array with n + 1 integers between 1 to n inclusive, find the duplicate.

Search

### Complexity

Time: O(N) Never have to traverse the “linked list more than once”

Space: O(1) Only use the given array.

## Python

``````class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# 1. This problem can be seen as a linked list. At index 0, it points to index 1.
# At index 1, it points to index 3. Therefore we are actually trying to find a cycle
# in the linked list. We can solve this two pointers a fast rabbit pointer that jumps two
# "nodes" and a slow turtle pointer that jumps one node. They will eventually land on
# the same node. Refer to https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work/32190575#32190575

rabbit_pointer = nums[0]
turtle_pointer = nums[0]
# 2. if we put the rabbit == turtle check here, it will break initially
# Let x be the distance to the start of the cycle. Let Y be the distance to the meeting point.
# Let Z be the remaining distance to the head of the cycle. The fast rabbit pointer
# traveled (x + y + z) one full cycle + y reaching the turtle. This is x + 2y + z.
# The slow turtle pointer traveled x + y to the meeting point.
while True:
rabbit_pointer = nums[nums[rabbit_pointer]]
turtle_pointer = nums[turtle_pointer]
if rabbit_pointer == turtle_pointer:
break
# Since the rabbit is twice as fast as the turtle, it's distance is twice as much.
# Therefore 2 * (x + y) = x + 2y + z => 2x + 2y = x + 2y + z => x = z.
# Therefore to reach the head, have two pointers travel, one from the start and
# one from the meeting point to get to the head.
turtle_pointer = nums[turtle_pointer]
``````

## Java

``````class Solution {
public int findDuplicate(int[] nums) {
// 1. Since we have all number 1 to n inclusive, this can be seen as a linked list.
// nums[0] points to index 1. nums[1] points to index 3, etc.
// Therefore we can solve this as rabbit turtle cycle head detection.
// A cycle meeting point will be found with a rabbit moving two steps and a
// turtle moving one step as they will overlap.
int rabbit = nums[0];
int turtle = nums[0];
while (true) {
rabbit = nums[nums[rabbit]];
turtle = nums[turtle];
if (rabbit == turtle) {
break;
}
}
// 2. Let x be the distance to the head of the cycle, the duplicate number.
// Let y be the distance to the meeting point of the rabbit and turtle.
// Let z be the remainder of the cycle from end of y to the head of the cycle.
// The rabbit moved a full cycle x + y + z and to the meeting point again + y for total of x + 2y + z.
// The turtle moved to the meeting point x + y.
// The rabbit is twice as fast so 2(x + y) = x + 2y + z => 2x + 2y = x + 2y + z => x = z.
// Therefore to get the head and the duplicate number have a pointer at the start node,
// and increment it and the turtle node till they match.
turtle = nums[turtle];
}
}
}
``````

### Notes

The second node traversal should be head != turtle instead of while True, and break if equal. This is for the edge case the first node is the duplicate.

# Decode Ways

LeetCode

## Problem

Given a mapping ‘1’ -> ‘A’ to ‘26’ -> ‘Z’, and a string of numbers, find the number of ways to build characters.

### Techniques

Dynamic Programming Recursion

### Complexity

Time: O(N) go through each character in s Space: O(N) create an Dynamic Programming Cache

## Python

``````class Solution:
def numDecodings(self, s: str) -> int:
# 1. Can use dynamic programming solve the subproblems
# of number of ways up to the subword of using n characters
# need to go backwards for case of 0 (10)
# 55 -> 2 0 1
# 0 1
subwordNumWays = [0 for _ in range(len(s) + 1)]
subwordNumWays[len(s)] = 1
idx = len(s) - 1
# 2. Handle for case 10 and 20
if int(s[idx]) == 0:
subwordNumWays[idx] = 0
else:
subwordNumWays[idx] = 1
idx -= 1
# 3. go through subproblems until all characters
while idx >= 0:
if int(s[idx]) == 0:
# 4. Handle the case for 10 and 20
idx -= 1
else:
# 5. if a number is 1 to 9 or 2[and something] add all ways up to it
subwordNumWays[idx] += subwordNumWays[idx + 1]
if int(s[idx:idx + 2]) <= 26:
# 6. add up ways for number 21 to 26
subwordNumWays[idx] += subwordNumWays[idx + 2]
idx -= 1
# 6. return num ways using all characters
return subwordNumWays[0]
``````

## Java

``````class Solution {
public int numDecodings(String s) {
// 1. Create a dynamic programming cache working backwards to account for 0
// for 10 or 20. All numbers up to i. Add + 1 for extra case of a two digit number base case
int[] subNumDecodings = new int[s.length() + 1];
// 2. 2 digit number base case
subNumDecodings[s.length()] = 1;
// 3. If the last digit is '0', the only base case is the two digit base case
// Else another number 1 to 9 fits the 1 digit base case
if (s.charAt(s.length() - 1) == '0') {
subNumDecodings[s.length() - 1] = 0;
} else {
subNumDecodings[s.length() - 1] = 1;
}

// 4. Go backwards solve the subproblems of using all elements up to index
for (int idx = s.length() - 2; idx >= 0; idx--) {
// 5. if it is a 0, let the two digit case handle it in the next subproblem
if (s.charAt(idx) == '0') {
continue;
}
// 6. We know the number is not 0 so both can be two digit and just one digit have the
// one digit case.
subNumDecodings[idx] = subNumDecodings[idx + 1];
// 7. Add the two digit subproblem case.
if (Integer.parseInt(s.substring(idx, idx + 2)) <= 26) {
subNumDecodings[idx] += subNumDecodings[idx + 2];
}
}
// 8. Return master problem of using all digits
return subNumDecodings[0];
}
}
``````

### Notes

Have to go backward for ‘0’ case. Skip the case and let the next subproblem with two digits solve it.

# Word Search II

LeetCode

## Problem

Given a 2d array of words and a list of words, return a list of every word in the array up down left right.

### Techniques

Recursion Search Trees

### Complexity

Time: O(m * n)

Space: (w) Longest word?

## Python

``````class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# 1. Build a trie to efficiently see if a word is used
trie = self.build_trie(words)
# 3. Have a 2d for loop to traverse the board
found = []
for row in range(len(board)):
for col in range(len(board[0])):
# 4. from this row, col search to see if has a word.
found.extend(self.trie_search(trie, board, row, col))
# 5. return all found words remove duplicates
return list(set(found))

def build_trie(self, words):
trie = {}
# 2. Go through each word, and create a new dictionary for each leter
# At the end, have the null char '\0' so we know word is done
for word in words:
level = trie
for char in word:
if char not in level:
level[char] = {}
level = level[char]
# level is at the end
level['\0'] = word
return trie

def trie_search(self, level, board, row, col):
# 5. check search is still in board
if row < 0 or row >= len(board):
return []
if col < 0 or col >= len(board[0]):
return []
# 6. see in the character is in the level
char = board[row][col]
if char in level:
# 7. see in the word is in the tire
level = level[char]
found = []
if '\0' in level:
found.append(level['\0'])
# search left, right, up, down remove char and put back to not reuse in search
board[row][col] = '#'
found.extend(self.trie_search(level, board, row - 1, col))
found.extend(self.trie_search(level, board, row + 1, col))
found.extend(self.trie_search(level, board, row, col - 1))
found.extend(self.trie_search(level, board, row, col + 1))
board[row][col] = char
return found
else:
return []
``````

## Java

Too Complicated :(

# Minimum Window Substring

LeetCode

## Problem

Given a string S and a string T, give the smallest window (continuous substring) of S that has all the characters of T

Sliding Window

### Complexity

Time: O(N) Go through S, at most twice for left and right pointers.

Space: O(N + M) need a dict for both S and T.

## Python

``````class Solution:
def minWindow(self, s: str, t: str) -> str:
# 1. Use a sliding window. Have a counter for number of characters in T.
counterT = {} # or collections.Counter
for char in t:
if char in counterT:
counterT[char] += 1
else:
counterT[char] = 1
# 2. counter for S; all the characters in S used
counterS = {}
# 3. Have a left and right pointer for the start and end of the sliding window.
ptr_left = 0
ptr_right = 0
# 4. Have a  set of characters in both S and T
recorded_chars = set()
# 5. Have a result length of infinity in case there is no solution
result_length = float('inf')
while ptr_right < len(s):
char = s[ptr_right]
# 6. Count char count in S
if char in counterS:
counterS[char] += 1
else:
counterS[char] = 1
# 6. Check that is a required character and we stil need more of that character
if char in counterT and counterT[char] <= counterS[char]:
# 7. while we have all characters we need, shrink sliding window on left
while len(recorded_chars) == len(counterT):
# 8. remove the left most character counted
char_left = s[ptr_left]
counterS[char_left] -= 1
# 9. we used all of the characters of char_left needed
# this is a possible window
if char_left in counterT and counterT[char_left] > counterS[char_left]:
recorded_chars.remove(char_left)
# 10. get the end and start result if this is the best seen so far.
# +1 because we haven't incremented yet
if result_length > ptr_right - ptr_left + 1:
end = ptr_right
start = ptr_left
result_length = ptr_right - ptr_left + 1
ptr_left += 1
ptr_right += 1

# 11. if the result length is still infinity, return '' no solution
if result_length == float('inf'):
return ''
# 12. return the window with the smallest start to end
return s[start:end+1]
``````

## Java

``````class Solution {
public String minWindow(String s, String t) {
// 1. Create a counter for T
Map<Character, Integer> counterT = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char charT = t.charAt(i);
if (!counterT.containsKey(charT)) {
counterT.put(charT, 0);
}
counterT.put(charT, counterT.get(charT) + 1);
}
// 2. Have a counter for S
Map<Character, Integer> counterS = new HashMap<>();
// 3. Have a left and right pointer
int leftPtr = 0;
int rightPtr = 0;
// 4. Have a set for characters used in S and T
Set<Character> recordedChars = new HashSet<>();
// 5. Have resultLength initialized MAX_VALUE for
int resultLength = Integer.MAX_VALUE;
// 6. increment rightPtr, expanding characters used
int start = 0;
int end = 0;
while (rightPtr < s.length()) {
char charS = s.charAt(rightPtr);
if (!counterS.containsKey(charS)) {
counterS.put(charS, 0);
}
counterS.put(charS, counterS.get(charS) + 1);

// 7. check that character is required and we have enough
if (counterT.containsKey(charS) && counterT.get(charS) <= counterS.get(charS)) {
// 8. add it the set of characters used
while (recordedChars.size() == counterT.size()) {
// 9. Remove the left most character
char charLeft = s.charAt(leftPtr);
counterS.put(charLeft, counterS.get(charLeft) - 1);
if (counterT.containsKey(charLeft) && counterT.get(charLeft) > counterS.get(charLeft)) {
recordedChars.remove(charLeft);
if (resultLength > rightPtr - leftPtr + 1) {
end = rightPtr;
start = leftPtr;
resultLength = rightPtr - leftPtr + 1;
}
}
leftPtr += 1;
}
}
rightPtr++;
}
if (resultLength == Integer.MAX_VALUE) {
return "";
}
return s.substring(start, end + 1);
}
}
``````

### Notes

Post by: Brian T. Liao