Leetcode: Basic Algorithms Flashcards
Reverse a binary tree
# recursively
def invertTree1(self, root):
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
# BFS
def invertTree2(self, root):
queue = collections.deque([(root)])
while queue:
node = queue.popleft()
if node:
node.left, node.right = node.right, node.left
queue.append(node.left)
queue.append(node.right)
return root
# DFS
def invertTree(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.extend([node.right, node.left])
return root
Inorder traversal binary tree
DFS
left, root, right
- —def inorder(self, node):
- ——-if node:
- ———–self.in_order(node.left)
- ———–print(node.value, end=””)
- ———–self.in_order(node.right)
- —def inorder_iterative(self, node):
- ——-stack = []
- ——-current = node
- ——-while True:
- ———–if current:
- —————stack.append(current)
- —————current = current.left
- ———–elif stack:
- —————current = stack.pop()
- —————print(current.value, end=””)
- —————current = current.right
- ———–else:
- —————break
Preorder binary tree
DFS
root, left, right
- —def preorder(self, node):
- ——-if node:
- ———–print(node.value, end=””)
- ———–self.preorder(node.left)
- ———–self.preorder(node.right)
- —def preorder_iterative(self, node):
- ——-stack=[]
- ——-stack.append(node)
- ——-while stack:
- ———–current = stack.pop()
- ———–if current:
- —————print(current.value)
- —————stack.append(current.right)
- —————stack.append(current.left)
Postorder binary tree
DFS
left, right, root
- —def postorder(self, node):
- ——-if node:
- ———–self.post_order(node.left)
- ———–self.post_order(node.right)
- ———–print(node.value, end=””)
- —def postorder_iterative(self, node):
- ——-if not Node:
- ———–return
- ——-s1 = []
- ——-s2 = []
- ——-s1.append(node)
- ——-while s1:
- ———–current = s1.pop()
- ———–s2.append(current)
- ———–# print(current.value, end=””)
- ———–if current.left: s1.append(current.left)
- ———–if current.right: s1.append(current.right)
- ——-while s2:
- ———–node2 = s2.pop()
- ———–print(node2.value, end=””)
What are collisions in a hash map
This scenario can occur because according to the equals and hashCode contract, two unequal objects in Java can have the same hash code.
It can also happen because of the finite size of the underlying array, that is, before resizing. The smaller this array, the higher the chances of collision.
That said, it’s worth mentioning that Java implements a hash code collision resolution technique which we will see using an example.
Keep in mind that it’s the hash value of the key that determines the bucket the object will be stored in. And so, if the hash codes of any two keys collide, their entries will still be stored in the same bucket.
And by default, the implementation uses a linked list as the bucket implementation.
The initially constant time O(1) put and get operations will occur in linear time O(n) in the case of a collision. This is because after finding the bucket location with the final hash value, each of the keys at this location will be compared with the provided key object using the equals API.
To simulate this collision resolution technique, let’s modify our earlier key object a little:
level order traversal of a binary tree
BFS
- utilize stack
- append root node to stack
- while stack, pop, print out values from left to right
- pop(0) to pop the first index instead of last
- —def tree_level(self, node):
- ——-stack = []
- ——-stack.append(node)
- ——-while stack:
- ———–node = stack.pop(0)
- ———–if node:
- —————print(node.value)
- —————stack.append(node.left)
- —————stack.append(node.right)
bubble_sort
- —# O(n*2), constant space
- —# https://www.youtube.com/watch?v=xli_FI7CuzA
- —def bubble_sort(self, arr):
- ——-n = len(arr)
- ——-for i in range(n):
- ———–for j in range(n-i-1):
- —————if arr[j] > arr[j+1]:
- ——————-arr[j], arr[j+1] = arr[j+1], arr[j]
- ——-return arr
insertion sort
O n^2, constant space
- —def insertion_sort(self, arr):
- ——-for i in range(1, len(arr)):
- ———–key = arr[i]
- ———–j = i-1
- ———–while j>=0 and arr[j]>key:
- —————arr[j+1] = arr[j]
- —————j -= 1
- ———–arr[j+1] = key
- ——-return arr
selection sort
O n^2, constant space
- —def selection_sort(self, arr):
- ——-n = len(arr)
- ——-for i in range(n):
- ———–min_index = i
- ———–for j in range(i+1, n):
- —————if arr[min_index]>arr[j]:
- ——————-min_index = j
- ———–arr[i], arr[min_index] = arr[min_index], arr[i]
- ——-return arr
merge sort
time: o(n*log(n))
space: O(N), if we have 16 objects in arr, we go 16 -> 8 -> 4 -> 2 -> 1, 2 needs both 1’s to solve, 4 needs both 2s, until we get up to 16 which needs both 8s, so it evaluates to N space, it would be NLogN if we evaluated all the branches at the same time. https://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity
def merge_sort(self, arr):
- ——-if len(arr)[greater than]1:
- ———–mid = len(arr)//2
- ———–left = arr[:mid]
- ———–right = arr[mid:]
- ———–self.merge_sort(left)
- ———–self.merge_sort(right)
- ———–i=j=k=0
- ———–while i[less than]len(left) and j[less than]len(right):
- —————if left[i][less than]right[j]:
- ——————-arr[k]=left[i]
- ——————-i+=1
- —————else:
- ——————-arr[k]=right[j]
- ——————-j+=1
- —————k+=1
- ———–while i[less than]len(left):
- —————arr[k]=left[i]
- —————k+=1
- —————i+=1
- ———–while j[less than]len(right):
- —————arr[k]=right[j]
- —————j+=1
- —————k+=1
- ——-return arr
heap sort
time: o(n*log(n)), worst O n^2
space: constant space since we only re-arrange the initial list (or heap)
- —def heap_sort(self, arr):
- ——-n = len(arr)
- ——-for i in range(n//2-1, -1, -1):
- ———–self.__heapify(arr, n, i)
- ——-for i in range(n-1, 0, -1):
- ———–arr[i], arr[0] = arr[0], arr[i] # swap
- ———–self.__heapify(arr, i, 0)
- ——-return arr
- —def __heapify(self, arr, n, i):
- ——-largest = i
- ——-left = 2*i+1
- ——-right = 2*i+2
- ——-if left < n and arr[largest] < arr[left]:
- ———–largest = left
- ——-if right < n and arr[largest] < arr[right]:
- ———–largest = right
- ——-if largest != i:
- ———–arr[i], arr[largest] = arr[largest], arr[i]
- ———–self.__heapify(arr, n, largest)
quick sort
time: O n*log(n)
space = log(n)
def quick_sort(self, arr, low, high):
- ——-if high[greater than]=low:
- ———–pi = self.__partition(arr, low, high)
- ———–self.quick_sort(arr, low, pi-1)
- ———–self.quick_sort(arr, pi+1, high)
- ——-return arr
- —def __partition(self, arr, low, high):
- ——-pivot = arr[high]
- ——-for j in range(low, high):
- ———–if arr[j][less than]= pivot:
- —————arr[low], arr[j] = arr[j], arr[low]
- —————low+=1
- ——-arr[low], arr[high] = arr[high], arr[low]
- ——-return low
reverse a linked list
def reverse_iterative(self):
- -current = self.head
- -node = None
- -while current:
- —nxt = current.next
- —current.next = node
- —node = current
- —current = nxt
- -self.head = node
add, insert after a node, delete, find a node in a linked list
class Node(object):
- —def __init__(self, val, next=None) -[greater than] None:
- ——-self.val = val
- ——-self.next = next
def find(target, node):
- —if not node:
- ——-return False
- —if node.val is target or find(target, node.next):
- ——-return True
- —else:
- ——-return False
def insert_after(after, new_node, node):
- —if not node:
- ——-return
- —if node.val is after:
- ——-hold = node.next
- ——-node.next = Node(new_node)
- ——-node.next.next = hold
- —else:
- ——-insert_after(after, new_node, node.next)
class LL:
- —def __init__(self, node):
- ——-self.head = node
need a reference to head to delete a node, since we could delete the first node!
- —def delete_node(self, target):
- ——-current = self.head
- ——-if not current:
- ———–return None
- ——-if current.val is target:
- ———–self.head = current.next
- ———–current = None
- ———–return None
- ——-return self.delete_helper(target, current.next, current)
- —def delete_helper(self, target, current, prev):
- ——-if not current:
- ———–return None
- ——-if current.val is target:
- ———–prev.next = current.next
- ———–current = None
- ———–return True
- ——-else:
- ———–return self.delete_helper(target, current.next, current)
add, insert after a node, delete, find a node in a doubly-linked list
- make sure to have helper head/tail nodes, it becomes very difficult without them
- don’t forget indexing for get/delete is different from adding. If we have 5 elements, we can add on the 5th index, it just goes on the end
class ListNode:
- —def __init__(self, x, next = None, prev = None):
- ——-self.val = x
- ——-self.next = next
- ——-self.prev = prev
class MyLinkedList:
- —def __init__(self):
- ——-self.size = 0
- ——-self.head, self.tail = ListNode(0), ListNode(0)
- ——-self.head.next = self.tail
- ——-self.tail.prev = self.head
- —def get(self, index: int) -> int:
- ——-if index > self.size - 1:
- ———–return -1
- ——-if index > self.size // 2:
- ———–cur = self.tail
- ———–for _ in range(self.size - index):
- —————cur = cur.prev
- ———–return cur.val
- ——-else:
- ———–cur = self.head.next
- ———–for _ in range(index):
- —————cur = cur.next
- ———–return cur.val
- —def addAtHead(self, val: int) -> None:
- ——-self.addAtIndex(0, val)
- —def addAtTail(self, val: int) -> None:
- ——-self.addAtIndex(self.size, val)
- —def addAtIndex(self, index: int, val: int) -> None:—-
- ——-if index > self.size:
- ———–return
- ——-if index > self.size // 2:
- ———–cur = self.tail
- ———–for _ in range(self.size - index):
- —————cur = cur.prev
- ——-else:
- ———–cur = self.head.next
- ———–for _ in range(index):
- —————cur = cur.next
- ——-prev = cur.prev
- ——-new = ListNode(val)
- ——-prev.next = new
- ——-new.prev = prev
- ——-new.next = cur
- ——-cur.prev = new
- ——-self.size += 1
- —def deleteAtIndex(self, index: int) -> None:
- ——-if index > self.size - 1:
- ———–return
- ——-if index > self.size // 2:
- ———–cur = self.tail
- ———–for _ in range(self.size - index):
- —————cur = cur.prev
- ——-else:
- ———–cur = self.head.next
- ———–for _ in range(index):
- —————cur = cur.next
- ——-cur.prev.next = cur.next
- ——-cur.next.prev = cur.prev
- ——-self.size -= 1
