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[0])):
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[0]) 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] = 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]
``````

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

Greedy

``````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[0])
i = 0
while i < len(intervals) - 1:
first = intervals[i]
print(first)
second = intervals[i + 1]
if first[1] >= second[0]:
intervals.pop(i)
second[0] = first[0]
second[1] = max(first[1], second[1])
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[26];
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[0].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[0].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

``````from heapq import *

class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
maxFreq = 0
max_count = 0
dic = {}
else:
max_count = 1
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[0])  # sort on start time
currEnd, cnt = intervals[0][1], 0
for x in intervals[1:]:
if x[0] < currEnd:  # find overlapping interval
cnt += 1
currEnd = min(currEnd, x[1])  # erase the one with larger end time
else:
currEnd = x[1]   # 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[0]
hare = nums[0]
while True:
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare:
break
ptr1 = nums[0]
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 = [0] * (len(s) + 1)
w[0] = 1
if 0 < int(s[0]) <= 9:
w[1] = 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 = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):
table[i][0] = i
for j in range(n + 1):
table[0][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