# 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):
return 0

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
result = 0

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]

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,