 Brian T. Liao
Aug 18, 2019 • 24 min read

# Interview Cram

## Number of Islands

Given a 2-D Array, count the number of islands in it, where land is connected in the NSEW direction

Recursion, Search, Union-Find

## Number of Islands (Sol)

https://leetcode.com/problems/number-of-islands/

``````class Solution:
def numIslands(self, grid):
if not grid:
return 0

count = 0
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == '1':
self.dfs(grid, i, j)
count += 1
return count

def dfs(self, grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid) or grid[i][j] != '1':
return
grid[i][j] = '#'
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
``````

## Coin Change Problem

Given a target of N cents and a collection of coins, how many ways can you form N cents?

Dynamic Programming, Recursion

## Coin Change Problem (Sol)

https://leetcode.com/problems/coin-change/

``````class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
A = [float('inf')] * (amount + 1)
A = 0
for i in range(amount + 1):
for coin in coins:
if coin <= i:
A[i] = min(A[i], 1 + A[i - coin])
return A[amount] if A[amount] != float('inf') else -1
``````

## Minimum Window Substring

Given a string and a collection of characters, find the shortest substring that contains all the characters

Sliding Window

## Minimum Window Substring (Sol)

https://leetcode.com/problems/minimum-window-substring/

``````class Solution(object):
def minWindow(self, s, t):
dicT = collections.Counter(t)
dicS = {}
rec = set()
j = 0
res = float('inf')
for i, c in enumerate(s):
if c not in dicS:
dicS[c] = 1
else:
dicS[c] += 1
if c in dicT and dicT[c] <= dicS[c]:
while len(rec) == len(dicT):
dicS[s[j]] -= 1
if s[j] in dicT and dicT[s[j]] > dicS[s[j]]:
rec.remove(s[j])
if res > i-j+1:
start = j
end = i
res = i-j+1
j += 1
if res == float('inf'):
return ""
return s[start:end+1]
``````

## Buying and Selling Stock

Given a list of starting and ending days for a stock, maximize your profit

Greedy

## Buying and Selling Stock (Sol)

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_, temp = 0, 0
for i in range(1, len(prices)):
temp += prices[i] - prices[i - 1]
temp = max(0, temp)
max_ = max(max_, temp)
return max_
``````

## Range Sum Query

Efficiently compute the sum of the numbers between two indexes of an array

Dynamic Programming

## Range Sum Query (Sol)

https://leetcode.com/problems/range-sum-query-immutable/

``````class NumArray(object):

def __init__(self, nums):
"""
:type nums: List[int]
"""
self.table = nums[:]
for i in range(1, len(nums)):
self.table[i] += self.table[i - 1]

def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
if i == 0:
return self.table[j]
return self.table[j] - self.table[i - 1]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
``````

## Merge Intervals

Given a list of intervals with a start and end value, merge the intervals

Sorting

## Merge Intervals (Sol)

https://leetcode.com/problems/merge-intervals/

``````class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
if len(intervals) < 2:
return intervals
intervals.sort(key=lambda x: x)
i = 0
while i < len(intervals) - 1:
first = intervals[i]
print(first)
second = intervals[i + 1]
if first >= second:
intervals.pop(i)
second = first
second = max(first, second)
else:
i += 1
return intervals
``````

## Maximum Subarray

Given an array, find the subarray with the maximum sum

Sliding Window

## Maximum Subarray (Sol)

https://leetcode.com/problems/maximum-subarray

``````class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1]
return max(nums)
``````

## Range Sum Query Mutable

Given a mutable array of integers, find the sum of elements between i and j

Recursion, Trees

## Range Sum Query Mutable (Sol)

https://leetcode.com/problems/range-sum-query-mutable

``````class Node:
def __init__(self, low, high):
self.l = low
self.h = high
self.tot = 0
self.left = None
self.right = None

def u(self, i, val):
if self.l == self.h:
self.tot = val
return
m = self.l + (self.h - self.l) // 2
if i <= m:
self.left.u(i, val)
elif i > m:
self.right.u(i, val)
self.tot = self.left.tot + self.right.tot

def r(self, l, h):
if self.l == l and self.h == h:
return self.tot
m = self.l + (self.h - self.l) // 2
if h <= m:
return self.left.r(l, h)
elif l > m:
return self.right.r(l, h)
else:
return self.left.r(l, m) + self.right.r(m + 1, h)

class NumArray:

def __init__(self, nums: List[int]):
self.head = self._cst(nums, 0, len(nums) - 1)

def update(self, i: int, val: int) -> None:

def sumRange(self, i: int, j: int) -> int:
def _cst(self, nums, l, h):
if l > h:
return None
if l == h:
n = Node(l, l)
n.tot = nums[l]
return n
n = Node(l, h)
m = l + (h - l) // 2
n.left = self._cst(nums, l, m)
n.right = self._cst(nums, m + 1, h)
n.tot = n.right.tot + n.left.tot
return n

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)
``````

## Word Search II

Given a 2-D array of characters and a list of valid words, find the number of words on the board

Recursion, Search, Trees

## Word Search II (Sol)

https://leetcode.com/problems/word-search-ii

``````class TrieNode {
TrieNode[] next = new TrieNode;
String word;
}

class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
dfs (board, i, j, root, res);
}
}
return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) {
p.word = null;
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j, p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board.length - 1) dfs(board, i, j + 1, p, res);
board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}
}
``````

Given an array of tasks an a cooldown period, given an efficient ordering

Greedy, Priority Queue

## Task Scheduler (Sol)

``````from heapq import *

class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
maxFreq = 0
max_count = 0
dic = {}
if task in dic:
else:
if dic[task] > maxFreq:
max_count = 1
elif dic[task] == maxFreq:
max_count += 1

return max((maxFreq-1) * (n+1) + max_count, len(tasks))
``````

## Non-overlapping Intervals

Given a collection of intervals, find the number of intervals you need to remove to make the rest of the intervals non-overlapping

Greedy, Sorting

## Non-overlapping Intervals (Sol)

https://leetcode.com/problems/non-overlapping-intervals

``````class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals: return 0
intervals.sort(key=lambda x: x)  # sort on start time
currEnd, cnt = intervals, 0
for x in intervals[1:]:
if x < currEnd:  # find overlapping interval
cnt += 1
currEnd = min(currEnd, x)  # erase the one with larger end time
else:
currEnd = x   # update end time
return cnt
``````

## Preorder Serialization Verification of a Binary Tree

Given a particular kind of preorder serialization of a binary tree, verify that it’s valid

Recursion, Trees

## Preorder Serialization Verification of a Binary Tree (Sol)

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree

``````class Solution:
def isValidSerialization(self, preorder: str) -> bool:
# remember how many empty slots we have
# non-null nodes occupy one slot but create two new slots
# null nodes occupy one slot

p = preorder.split(',')

#initially we have one empty slot to put the root in it
slot = 1
for node in p:

# no empty slot to put the current node
if slot == 0:
return False

# a null node?
if node == '#':
# ocuppy slot
slot -= 1
else:
# create new slot
slot += 1

#we don't allow empty slots at the end
return slot==0
``````

## Find the Duplicate Number

Find the duplicate number in an array AND use O(1) space

Search

## Find the Duplicate Number (Sol)

https://leetcode.com/problems/find-the-duplicate-number/

``````class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
tortoise = nums
hare = nums
while True:
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare:
break
ptr1 = nums
ptr2 = tortoise
while ptr1 != ptr2:
ptr1 = nums[ptr1]
ptr2 = nums[ptr2]
return ptr1
``````

## Construct a Binary Tree from Preorder and Inorder Serialization

Given the preorder and inorder serialization of a binary tree, construct a tree data structure

Recursion, Search, Trees

## Construct a Binary Tree from Preorder and Inorder Serialization (Sol)

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

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

class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[:ind])
root.right = self.buildTree(preorder, inorder[ind + 1:])
return root
``````

## Decode Ways

Given an encoding from letters to numbers, count the number of ways to decode a string of numbers

Dynamic Programming, Recursion

## Decode Ways (Sol)

https://leetcode.com/problems/decode-ways/description/

``````class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""

# cars
# [0, 0, 0, 0]
# 0, 1, 2, 3
w =  * (len(s) + 1)
w = 1
if 0 < int(s) <= 9:
w = 1

print(w)
for i in range(2, len(s) + 1):
if 0 < int(s[i - 1]) <= 9:
w[i] += w[i - 1]
if int(s[i - 2]) != 0 and int(s[i - 2:i]) <= 26:
w[i] += w[i - 2]
print(w)
return w[len(s)]
``````

## Jump Game II

Given a non-negative integer array where each index represents the maxmimum you can iterate forward, minimize the number of jumps to reach the end of the array

Greedy

## Jump Game II (Sol)

https://leetcode.com/problems/jump-game-ii/description/

``````class Solution:
def jump(self, nums: List[int]) -> int:
j, ce, cf = 0, 0, 0
for i in range(len(nums) - 1):
cf = max(cf, i + nums[i])
if i == ce:
j += 1
ce = cf
return j
``````

## Find the Edit Distance Between Two Words

Given two words, find the minimum number of edits to mutate one word into the other

Dynamic Programming, Recursion

## Find the Edit Distance Between Two Words (Sol)

https://leetcode.com/problems/edit-distance/description/

``````class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m = len(word1)
n = len(word2)
table = [ * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):
table[i] = i
for j in range(n + 1):
table[j] = j

for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
table[i][j] = table[i - 1][j - 1]
else:
table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])
return table[m][n]
``````
Post by: Brian T. Liao