Notes from the Interview Quickstart course
- 2 pointers iterate through an array at the same time
- Useful for searching for pairs in a sorted array
Given an array of integers sorted in non-decreasing order, return an array of the squares of each number (also sorted in non-decreasing order)
[-4, -1, 0, 3, 10] -> [0, 1, 9, 16, 100]
Answer
- Have both pointers start on the absolute lowest number (in this case 0)
- Move 1 pointer to the left, 1 pointer to the right
- Compare both pointed values, appending the smaller squared one to the result
- Move the pointer pointing to the lower value once again in the direction it was going in
- Compare once more
- Repeat 3-5 until finished
* *
[-4, -1, 0, 3, 10] -> []
* *
[-4, -1, 0, 3, 10] -> [1]
* *
[-4, -1, 0, 3, 10] -> [1, 9]
...- Iterate over array once: O(n) time and O(1) space (no extra data structures)
- O(1) insert/get/delete
- Detect duplicates and count occurrences of array elements
- Reduce time complexity
Duplicate, Unique, # Occurences -> Hashmaps
Given an array of integers, return True if there are 2 numbers that add up to a specified target number
[2, 7, 9] -> 16
Answer: Hash Set
- Hash the current element by
target - element - If the hash exists in the set, return True
- Else, move on to the next element
2: is 14 in the hash set? No
{2}
7: is 9 in the hash set? No
{2, 7}
9: is 7 in the hash set? Yes
True- O(n) runtime and O(n) space
- Sliding window is a sub-array that slides over the main array
- Used when looking for a substring with certain properties
- The window always contains a partial solution to the problem
- Consecutive
Given a string, find the length of the longest substring without repeating characters
- We have 2 indexes, a left window and right window index both starting at 0
- Start
right_iat the first element and add the element to a hash set - Increment
right_iby 1 and add the new element to the hash set longest_len = max(longest_len, len(chars_in_window))- Repeat until finding a value that is already in the hash set
- While the repeated value is in still in the hash set, keep removing elements based on the
left_iand incrementleft_iby 1 for each removal
while string[right_i] in chars_in_window:
chars_in_window.remove(string[left_i])
left_i += 1- Brute force takes O(n^3)
- Sliding window is O(n) runtime and O(n) space (hashmap)
- Recursive data structure
If the rest of the linked list is solved, how can I use that on the current node?
Given two sorted linked lists, merge them together and return a new sorted list
# Recursive solution
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
# Base case if one list is null
if l1 is None:
return l2
elif l2 is None:
return l1
# Current node should be whichever is smaller
if l1.val < l2.val:
merged_list = merge_two_lists(l1.next, l2)
else:
merged_list = merge_two_lists(l1, l2.next)
return merged_list
- O(m + n) time & space (new list) where m, n are the number of elements in both sorted linked lists
- Used to detect cycles in linked lists and graphs
- Start from the beginning, move a pointer 1 node at a time (tortoise)
- Also move a pointer 2 nodes at a time (hare)
- If the pointers meet there is a cycle
- Let
$m$ be the number of moves from the head to the cycle start - Let
$L$ be the number of nodes in the cycle - Let
$k$ be the number of nodes from cycle start
- Here,
$t$ is the number of tortoise moves and$h$ is the number of hare moves (the hare is double the speed of the tortoise) - There exists some value
$t$ ,$h$ ,$k$ which makes the above equation true
- O(
$L + m$ ) runtime, O(1) space - Tell interviewer you've seen this before; no way you're figuring out the proof in the middle of an interview
- Recursive data structure
- Iterative solutions often involve stacks/queues
Find the number of nodes along the longest path from the root node to the farthest leaf node
Hint: Assume you have the maximum depth of the left and right subtree
def max_depth(root: Node) -> int:
if root is None:
return 0
left_max_depth = max_depth(root.left)
right_max_depth = max_depth(root.right)
return max(left_max_depth, right_max_depth) + 1- Simply take the maximum of the left/right subtrees and add 1 to account for the root node
- Base case: hitting a leaf node; max depth is 1
return max(0, 0) + 1
- O(n) runtime, visit every node once
- O(d) space, d = max depth of tree
Determine if a binary tree is a valid binary search tree
- We must keep track of additional information and pass them through function calls
def is_valid_bst_h(root: Node, min: int, max: int) -> bool:
if root is None:
return True
# The value of all nodes in the left subtree have to be less than this node's value.
# They also have to be greater than the current minimum from higher up in the tree.
left_valid = is_valid_bst_h(root.left, min, root.val)
# Similarly, the value of all nodes in the right subtree have to be greater than this node's value.
# They also have to be less than the current maximum from higher up in the tree.
right_valid = is_valid_bst_h(root.right, root.val, max)
return min < root.val < max and left_valid and right_valid
def is_valid_bst(root: Node) -> bool:
return is_valid_bst_h(root, -float('inf'), float('inf'))- O(n) runtime, visit every node once
- O(d) space, d = max depth of tree
- Another method is to use in-order traversal and add every node value to an array
- If the array is sorted, the BST is valid
- The most common binary tree algorithm
- Searches from the root to the leaf node, 1 path at a time
- Find values that fit criteria
- Recursion
- For binary trees, DFS is in the form of pre/in/post order traversal
- Level order traversal
- Uses queue/stack
Given a BST + min/max values, return the sum of all tree nodes with values in between min/max (inclusive)
DFS
- Note that we can slightly optimize where we use BST properties to know when to stop searching
- ex. If min = 10, and we have a node of value 9, we do not need to search any nodes on the left as they will all be smaller than 9
def range_sum_bst(root: Node, L: int, R: int) -> int:
if root is None:
return 0
total = 0
if L <= root.val <= R:
total += root.val
if L < root.val:
total += range_sum_bst(root.left, L, R)
if root.val < R:
total += range_sum_bst(root.right, L, R)
return total- O(n) time, O(d) space (d is max depth)
A complete binary tree has every level except the last level completely full. If the last level is not full, all nodes are to the far left.
Key: "level" -> level-order traversal -> BFS
- Once we find a null, we know that the level is not complete
- Start at the root node and place it into a queue
- Pop it off and add its left and right children to the queue
- Pop the next node off the queue (left in this case as it was added first, FIFO) and add its left and right children to the queue
- Pop the next node off the queue (right in this case) and add its left and right children to the queue
- Repeat until null is popped
- Now check if the rest of the elements are null. If there is a non-null element, the binary tree is not complete
- O(n) time and space
- Can be used in almost all graph problems
- Can be used almost interchangeably
- BFS is good for shortest path
- ex. Determine smallest # steps to reach end of maze:
- DFS computes all possible paths
- BFS expands 1 step at a time so the first time we hit the end, it uses the shortest path
- DFS is good for searching all paths in a graph from a node/exhaustive graph search
- ex. Find best chess move,
Given a graph, return True iff it is bipartite
A graph is bipartite if we can split its nodes into 2 independent subsets A and B, such that every edge has one node A and another node B.
- Basically, no 2 neighbours can be of the same letter
- Our BFS algorithm will "colour" neighbours and make sure that they are not the same colour
- Start at a node and colour it (I like yellow)
- Colour the neighbours (I think purple is cool)
- Traverse through the graph and colour more nodes!
- If the neighbour is not coloured, colour it yellow, however if the current node is also yellow we must colour it purple
- If the neighbour colour is the current node colour, we return False
- O(V + E) time where V represents vertices and E represents edges
- O(V) space
Given a graph, return a deep copy of the graph
We want to clone every neighbour and add it recursively to our copy graph.
- We must keep track of which nodes are already cloned - hash maps
- Set the keys as node values and the hash map values as references to the cloned node
- Check through every node in the graph - if it is not in the hash map, add it to the clone and add it to the hash map
- If the node is already in the hash map, add it as a neighbour to the current cloned node
- O(V + E) time where V represents vertices and E represents edges
- O(V) space
- Take a directed graph and line up the nodes in a straight line (all pointers point in the same direction)
- Useful when problems involve resolving dependencies:
- Course dependencies
- Program build dependencies
- Recipe steps
Key: dependencies, prerequisites, ordered steps
- Only applies to directed acyclic graphs (DAGs)
- DAGs can have many unique valid topological orderings
- 2 ways:
- DFS (simpler than BFS)
- BFS (Kahn's algorithm)
Given a directed graph representing courses and prerequisites, return an ordering of courses you can take to finish all the courses while satisfying all the prerequisites
If no ordering exists, return an empty array
-
Pick a node to start the DFS
-
Whenever we have to backtrack from the DFS, we add a node to the beginning of the topological ordering and mark it as part of the topological ordering on the graph
- We do not want to add the same node multiple times in the ordering
-
Whenever we recurse in the DFS we add another prerequisite
-
Hitting the end of a branch is basically saying: "We need to finish all the courses on the way in order to complete the end course"
-
Keep performing DFS until all the nodes have been evaluated in the ordering
-
In this question, if we hit a node that we have already encountered it means that there is a cycle and there are no valid topological orderings
- Use a new hash set for each DFS
- This is different from being marked as part of the topological ordering
-
O(V + E) time
-
O(V) space
- Shortest path from one node to all others (main focus)
- Slower than Dijkstra's but can handle negative edges
- Shortest paths from all nodes to all other nodes
- Less effective for weighted graphs
- They can still be used, but they are slower
A network is represented by a directed graph, where each node is a server, and each weighted edge is how many seconds a request takes to get from that server to its neighbour
Find how long it takes for all servers in the network to receive a request from the given server; Return -1 if this is impossible.
Dijkstra - one node to all other nodes
- We are bounded by the server that takes the longest to receive the request
- Compute shortest path from starting node to all other servers
- Find maximum value for these paths
- Initialize hash map to keep track of shortest distance from start node to all other nodes (so far)
- Also initialize a minimum heap to keep track of the shortest distances from the start node. To start, the start node has a distance of 0 and the other nodes have distances of infinity
- Visit nodes until all are visited or the heap is emptied. Visiting a node is when we pop it off the min heap
- The next unvisited node is the value we get when we pop off the min of the heap. Here, we start off with 0. Add the node value (shortest known distance) to the hash map by mapping it to its respective node
- Check out the neighbours of the node we are visiting: Add the value of the current node (found in hash map) and add the weight of the edge to the neighbour and look it up in the heap
- If this sum is smaller than the value in the heap, replace it
- This sum represents the shortest path from the start node
- Pop off another value from the min heap and continue until we have visited all nodes/min heap is empty
def dijkstras(graph, start_node):
shortest_dists = {}
shortest_path_heap = min_heap()
shortest_path_heap.insert(0, start_node)
# add nodes to heap
for node in graph:
if node != start_node:
shortest_path_heap.insert(inf, node
# end conditions
while (shortest_path_heap and not all_nodes_visited):
val, node = shortest_path_heap.pop()
visit(node, ...)
# success - hash table full and min heap empty
if (len(shortest_dists) == len(graph)):
return max(shortest_dists.values())
# the min heap is empty and the hash table is not full - there is an unreachable node from the start node
return -1
def visit(node, val, graph, shortest_path_heap, shortest_dists):
shortest_dists[node] = val
for edge in graph[node]:
new_dist = val + edge.weight
# The find function would ideally use a hash table to look up the shortest distance for the current node
heap_dist = find(edge.neighbor, shortest_path_heap)
# If we find a new shortest distance, update the min heap of that node
if new_dist < heap_dist:
shortest_path_heap.update(edge.neighbor, new_dist)-
Simplified: O((V + E)logV) time
-
Long answer: O(V + E + VlogV + ElogV) time
- Hash table: we visit each node and perform constant time lookups, but we also visit all of the node's neighbours
- Min heap: We pop off V nodes from the min heap which takes logV time
- Updating heap may occur E times
- Heap bubbling is logV
- Updating heap may occur E times
-
O(V) space - hash map + min heap