Depth of a Binary Tree
class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def __repr__(self):
return self.val
def deepest(node):
if not node:
return 0
return 1 + max(deepest(node.left), deepest(node.right))
def deepest2(node, depth=0):
if not node:
return depth + 0
if not node.left and not node.right:
return depth + 1
if not node.left:
return deepest2(node.right, depth + 1)
if not node.right:
return deepest2(node.left, depth + 1)
return max(deepest2(node.left, depth + 1),
deepest2(node.right, depth + 1))
# a
# / \
# b c
# /
# d
# \
# e
root = Node('a')
root.left = Node('b')
root.left.left = Node('d')
root.left.left.right = Node('e')
root.right = Node('c')
print(deepest2(root))
# 4
Intersection of Two Linked Lists
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
def length(head):
if not head:
return 0
return 1 + length(head.next)
lenA, lenB = length(headA), length(headB)
currA, currB = headA, headB
if lenA > lenB:
for _ in range(lenA-lenB):
currA = currA.next
else:
for _ in range(lenB - lenA):
currB = currB.next
while currA != currB:
currA = currA.next
currB = currB.next
return currA
First Missing Positive Integer
class Solution(object):
def first_missing_position(self, nums):
hash = {}
for n in nums:
hash[n] = 1
for i in range(1, len(nums)):
if i not in hash:
return i
return -1
print(Solution().first_missing_position([3, 4, -1, 1]))
# 2
Meeting Rooms
class Solution:
def minMeetingRooms(self, intervals):
start = []
end = []
for i in intervals:
start.append(i[0])
end.append(i[1])
start.sort()
end.sort()
s = 0
e = 0
numRooms = 0
available = 0
while s < len(start):
if start[s] < end[e]:
if available:
available -= 1
else:
numRooms += 1
s += 1
else:
available += 1
e += 1
return numRooms
Sort Colors
class Solution:
def sortColors(self, nums):
p0 = 0
p1 = 0
p2 = len(nums) - 1
while p1 <= p2:
if nums[p1] == 0:
nums[p0], nums[p1] = nums[p1], nums[p0]
p0 += 1
p1 += 1
elif nums[p1] == 1:
p1 += 1
else:
nums[p1], nums[p2] = nums[p2], nums[p1]
p2 -= 1
colors = [0, 1, 2, 2, 1, 0]
Solution().sortColors(colors)
print(colors)
# [0, 0, 1, 1, 2, 2]
Number of Islands
class Solution:
def numIslands(self, grid):
def sinkIsland(grid, r, c):
if grid[r][c] == '1':
grid[r][c] = '0'
else:
return
if r + 1 < len(grid):
sinkIsland(grid, r + 1, c)
if r - 1 >= 0:
sinkIsland(grid, r - 1, c)
if c + 1 < len(grid[0]):
sinkIsland(grid, r, c + 1)
if c - 1 >= 0:
sinkIsland(grid, r, c - 1)
counter = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
counter += 1
sinkIsland(grid, i, j)
return counter
Great J
Get all Values at a Certain Height in a Binary Tree
class Node():
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def valuesAtLevel(node, depth):
if not node:
return []
if depth == 1:
return [node.value]
return valuesAtLevel(node.left, depth - 1) + valuesAtLevel(node.right, depth - 1)
# 1
# / \
# 2 3
# / \ \
# 4 5 7
node = Node(1)
node.left = Node(2)
node.right = Node(3)
node.right.right = Node(7)
node.left.left = Node(4)
node.left.right = Node(5)
print(valuesAtLevel(node, 3))
# [ 4, 5, 7]
Balanced Binary Tree
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isBalanced(self, root):
def isBalancedHelper(root):
if root == None:
return (True, 0)
leftB, leftH = isBalancedHelper(root.left)
rightB, rightH = isBalancedHelper(root.right)
return (leftB and rightB and abs(leftH - rightH) <= 1, max(leftH, rightH) + 1)
return isBalancedHelper(root)[0]
Count Number of Unival Subtrees
class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_unival_subtrees(node):
count, is_unival = count_unival_subtrees_helper(node)
return count
# total_count, is_unival
def count_unival_subtrees_helper(node):
if not node:
return 0, True
left_count, is_left_unival = count_unival_subtrees_helper(node.left)
right_count, is_right_unival = count_unival_subtrees_helper(node.right)
if (is_left_unival and is_right_unival and
(not node.left or node.val == node.left.val) and
(not node.right or node.val == node.right.val)):
return left_count + right_count + 1, True
return left_count + right_count, False
# 0
# / \
# 1 0
# / \
# 1 0
# / \
# 1 1
a = Node(0)
a.left = Node(1)
a.right = Node(0)
a.right.left = Node(1)
a.right.right = Node(0)
a.right.left.left = Node(1)
a.right.left.right = Node(1)
print(count_unival_subtrees(a))
# 5
Maximum Depth of a Tree
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxDepth(self, root):
stack = []
if root is not None:
stack.append((1, root))
depth = 0
while stack != []:
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return depth
Group Words that are Anagrams
import collections
def hashkey(str):
return "".join(sorted(str))
def hashkey2(str):
arr = [0] * 26
for c in str:
arr[ord(c) - ord('a')] = 1
return tuple(arr)
def groupAnagramWords(strs):
groups = collections.defaultdict(list)
for s in strs:
groups[hashkey2(s)].append(s)
return tuple(groups.values())
print(groupAnagramWords(['abc', 'bcd', 'cba', 'cbd', 'efg']))
# (['abc', 'cba'], ['bcd', 'cbd'], ['efg'])
Minimum Subarray Length
class Solution(object):
def minSubArrayLen(self, s, nums):
res = float('inf')
sum = 0
left = 0
right = 0
while right < len(nums):
sum += nums[right]
while sum >= s:
res = min(res, right - left + 1)
sum -= nums[left]
left += 1
right += 1
if res == float('inf'):
return 0
else:
return res
print(Solution().minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))
# 2
Merge List Of Number Into Ranges
def makerange(low, high):
return str(low) + '-' + str(high)
def findRanges(nums):
if not nums:
return []
ranges = []
low = nums[0]
high = nums[0]
for n in nums:
if high + 1 < n:
ranges.append(makerange(low, high))
low = n
high = n
ranges.append(makerange(low, high))
return ranges
print(findRanges([0, 1, 2, 5, 7, 8, 9, 9, 10, 11, 15]))
# ['0-2', '5-5', '7-11', '15-15']
Maximum Subarray
class Solution:
def maxSubArray(self, nums):
if len(nums) == 0:
return 0
res = nums[0]
currMax = 0
for n in nums:
if currMax + n < 0:
currMax = 0
res = max(n, res)
else:
currMax += n
res = max(currMax, res)
return res
print(Solution().maxSubArray([-1, -4, 3, 8, 1]))
# 12
Array Intersection
class Solution:
def intersection(self, nums1, nums2):
results = {}
for num in nums1:
if num in nums2 and num not in results:
results[num] = 1
return list(results.keys())
def intersection2(self, nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
return [x for x in set1 if x in set2]
def intersection3(self, nums1, nums2):
hash = {}
duplicates = {}
for i in nums1:
hash[i] = 1
for i in nums2:
if i in hash:
duplicates[i] = 1
return tuple(duplicates.keys())
print(Solution().intersection3([4, 9, 5], [9, 4, 9, 8, 4]))
# (9, 4)
Invert a Binary Tree
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def invertTree(self, root):
if root == None:
return root
else:
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.right = left
root.left = right
return root
Angles of a Clock
def calcAngle(h, m):
hour_angle = (360 / (12 * 60.0)) * (h * 60 + m)
min_angle = 360 / 60.0 * m
angle = abs(hour_angle - min_angle)
return min(angle, 360 - angle)
print(calcAngle(3, 15))
# 7.50
print(calcAngle(3, 00))
# 90
Climbing Stairs
class Solution:
def climbStairs(self, n):
if n == 0:
return 1
if n == 1:
return 1
first = 1
second = 2
for i in range(3, n + 1):
third = second + first
first = second
second = third
return second
print(Solution().climbStairs(8))
# 34
Tree Serialization
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __str__(self):
result = ''
result += str(self.val)
if self.left:
result += str(self.left)
if self.right:
result += str(self.right)
return result
def serialize(node):
if node == None:
return '#'
return str(node.val) + ' ' + serialize(node.left) + ' ' + serialize(node.right)
def deserialize(str):
def deserialize_helper(values):
value = next(values)
if value == '#':
return None
node = Node(int(value))
node.left = deserialize_helper(values)
node.right = deserialize_helper(values)
return node
values = iter(str.split())
return deserialize_helper(values)
# 1
# / \
# 3 4
# / \ \
# 2 5 7
tree = Node(1)
tree.left = Node(3)
tree.right = Node(4)
tree.left.left = Node(2)
tree.left.right = Node(5)
tree.right.right = Node(7)
string = serialize(tree)
print(deserialize(string))
# 132547
Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s):
letters = {}
tail = -1
head = 0
result = 0
while head < len(s):
if s[head] in letters:
tail = max(tail, letters[s[head]])
letters[s[head]] = head
result = max(result, head-tail)
head += 1
return result
print(Solution().lengthOfLongestSubstring('abcdbbbeacc'))
# 4
Circle of Chained Words
import collections
def is_cycle_dfs(symbol, current_word, start_word, length, visited):
if length == 1:
return start_word[0] == current_word[-1]
visited.add(current_word)
for neighbor in symbol[current_word[-1]]:
if neighbor not in visited:
return is_cycle_dfs(symbol, neighbor, start_word, length - 1, visited)
visited.remove(current_word)
return False
def chainedWords(words):
symbol = collections.defaultdict(list)
for word in words:
symbol[word[0]].append(word)
return is_cycle_dfs(symbol, words[0], words[0], len(words), set())
print(chainedWords(['apple', 'eggs', 'snack', 'karat', 'tuna']))
# True
print(chainedWords(['apple', 'eggs', 'snack', 'karat', 'tunax']))
# False
Merge Intervals
class Solution:
def merge(self, intervals):
def takeFirst(elem):
return elem[0]
intervals.sort(key=takeFirst)
res = []
for interval in intervals:
if not res or res[-1][1] < interval[0]:
res.append(interval)
else:
res[-1][1] = max(res[-1][1], interval[1])
return res
print(Solution().merge([[1, 5], [2, 8], [10, 12]]))
# [[1, 8], [10, 12]]
Best Time to Buy And Sell Stock
class Solution(object):
def maxProfit(self, prices):
if prices == []:
return 0
res = 0
min = prices[0]
for p in prices:
if min > p:
min = p
res = max(res, p-min)
return res
print(Solution().maxProfit([7, 1, 5, 3, 6, 4]))
# 5
Phone Numbers
lettersMaps = {
1: [],
2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r', 's'],
8: ['t', 'u', 'v'],
9: ['w', 'x', 'y', 'z'],
0: []
}
validWords = ['dog', 'fish', 'cat', 'fog']
def makeWords_helper(digits, letters):
if not digits:
word = ''.join(letters)
if word in validWords:
return [word]
return []
results = []
chars = lettersMaps[digits[0]]
for char in chars:
results += makeWords_helper(digits[1:], letters + [char])
return results
def makeWords(phone):
digits = []
for digit in phone:
digits.append(int(digit))
return makeWords_helper(digits, [])
print(makeWords('364'))
Quickselect (iterative)
import heapq
def findKthLargest(arr, k):
for i in range(0, k):
(max_value, max_index) = (arr[0], 0)
for j in range(0, len(arr)):
if max_value < arr[j]:
(max_value, max_index) = arr[j], j
arr = arr[:max_index] + arr[max_index + 1:]
for j in range(0, len(arr)):
if max_value < arr[j]:
(max_value, max_index) = arr[j], j
return max_value
def findKthLargest2(arr, k):
return sorted(arr)[-k]
def findKthLargest2(arr, k):
arr = list(map(lambda x: -x, arr))
heapq.heapify(arr)
for i in range(0, k - 1):
heapq.heappop(arr)
return -arr[0]
def partition(arr, low, high):
pivot = arr[high]
i = low
for j in range(low, high):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quickselect(arr, k):
k = len(arr) - k
left = 0
right = len(arr) - 1
while left <= right:
pivotIndex = partition(arr, left, right)
if pivotIndex == k:
return arr[pivotIndex]
elif pivotIndex > k:
right = pivotIndex - 1
else:
left = pivotIndex + 1
return -1
print(quickselect([8, 7, 2, 3, 4, 1, 5, 6, 9, 0], 3))
Clone Trees
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def __str__(self):
return str(self.val)
def findNode(a, b, node):
if a == node:
return b
if a.left and b.left:
found = findNode(a.left, b.left, node)
if found:
return found
if a.right and b.right:
found = findNode(a.right, b.right, node)
if found:
return found
return None
def findNode2(a, b, node):
stack = [(a, b)]
while len(stack):
(a,b) = stack.pop()
if a == node:
return b
if a.left and b.left:
stack.append((a.left, b.left))
if b.right and b.right:
stack.append((a.right, b.right))
return None
# 1
# / \
#2 3
# / \
# 4* 5
a = Node(1)
a.left = Node(2)
a.right = Node(3)
a.right.left = Node(4)
a.right.right = Node(5)
b = Node(1)
b.left = Node(2)
b.right = Node(3)
b.right.left = Node(4)
b.right.right = Node(5)
print(findNode2(a, b, a.right.left))
# 4
Level by Level Trees
from collections import deque
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
def levelPrint(node):
q = deque([node])
result = ''
while len(q):
num = len(q)
while num > 0:
node = q.popleft()
result += str(node.val)
for child in node.children:
q.append(child)
num -= 1
result += "\n"
return result
tree = Node('a', [])
tree.children = [Node('b', []), Node('c', [])]
tree.children[0].children = [Node('g', [])]
tree.children[1].children = [Node('d', []), Node('e', []), Node('f', [])]
print(levelPrint(tree))
Max Connected Colors in a Grid
class Grid:
def __init__(self, grid):
self.grid = grid
def max_connected_colors(self):
max_n = 0
for y in range(len(self.grid)):
for x in range(len(self.grid[y])):
# max_n = max(max_n, self.dfs(x, y, {}))
max_n = max(max_n, self.dfsIterative(x, y, {}))
return max_n
def colorAt(self, x, y):
if x >= 0 and x < len(self.grid[0]) and y >= 0 and y < len(self.grid):
return self.grid[y][x]
return -1
def neighbors(self, x, y):
POSITIONS = [[-1, 0], [0, -1], [0, 1], [1, 0]]
n = []
for pos in POSITIONS:
if self.colorAt(x + pos[0], y + pos[1]) == self.colorAt(x, y):
n.append((x + pos[0], y + pos[1]))
return n
def dfs(self, x, y, visited):
key = str(x) + ','+str(y)
if key in visited:
return 0
visited[key] = True
result = 1
for neighbor in self.neighbors(x, y):
result += self.dfs(neighbor[0], neighbor[1], visited)
return result
def dfsIterative(self, x, y, visited):
stack = [(x, y)]
result = 0
while len(stack) > 0:
(x, y) = stack.pop()
key = str(x) + ', ' + str(y)
if key in visited:
continue
visited[key] = True
result += 1
for neighbor in self.neighbors(x, y):
stack.append(neighbor)
return result
grid = [[1, 0, 0, 1],
[1, 1, 1, 1],
[0, 1, 0, 0]]
print(Grid(grid).max_connected_colors())
# 7
Closest Points to the Origin
import heapq
def calcDistance(p):
return p[0]*p[0] + p[1]*p[1]
def findClosestPoints2(points, k):
points = sorted(points, key = lambda x: calcDistance(x))
return points[:k]
def findClosestPoints2(points, k):
# ( distance, object )
data = []
for p in points:
data.append((calcDistance(p), p))
heapq.heapify(data)
result = []
for i in range(k):
result.append(heapq.heappop(data)[1])
return result
print (findClosestPoints2([[1, 1], [3, 3], [2, 2], [4, 4], [-1, -1]], 3))
Autocompletion
class Node:
def __init__(self, isWord, children):
self.isWord = isWord
# {'a': Node, 'b': Node, ...}
self.children = children
class Solution:
def build(self, words):
trie = Node(False, {})
for word in words:
current = trie
for char in word:
if not char in current.children:
current.children[char] = Node(False, {})
current = current.children[char]
current.isWord = True
self.trie = trie
def autocomplete(self, word):
current = self.trie
for char in word:
if not char in current.children:
return []
current = current.children[char]
words = []
self.dfs(current, word, words)
return words
def dfs(self, node, prefix, words):
if node.isWord:
words.append(prefix)
for char in node.children:
self.dfs(node.children[char], prefix + char, words)
s = Solution()
s.build(['dog', 'dark', 'cat', 'door', 'dodge'])
print(s.autocomplete('do'))
# ['dog', 'door', 'dodge']
Fibonacci Number
def fib(n):
a = 0
b = 1
if n == 0:
return a
if n == 1:
return b
for _ in range(2, n+1):
value = a + b
a = b
b = value
return value
print(fib(10))
# 55
Wrapping Up
We hope you enjoyed the series and found it helpful!
While we’ve focused on coding and algorithms in AlgoPro, please also keep in mind that there is so much more to the interview process . We’ve seen plenty of interview candidates come in and completely ace the whiteboard sessions, yet still get rejected. Other candidates find themselves rejected before even having the opportunity to prove themselves at the on-sites for lackluster resumes or other reasons.
If you want to learn more about the rest of the interview process, please join us over at Tech Interview Pro ( discounted for AlgoPro members ) where we continue helping people land their dream jobs in tech daily.
If you do happen to land a job, let us know at contact@techseries.dev! We love hearing success stories.
For comments and feedback, also please drop us a line. We’re always looking to improve the quality of our program.
Either way, we wish you all the best in your journey. See you in the field,
Patrick Shyu (“TechLead”)
Jonathan Ma (“Joma”)