Question:
Use the master theorem to find the asymptotic solution to the recurrence
$T(n)=2T\left(\frac{n}{2}\right)+n^2$
Determine the bound for $T(n)$.
Here, we have $a=2$, $b=2$, and $f(n)=n^2$. We compute the critical exponent:
$n^{\log_b a} = n^{\log_2 2} = n$
Since $f(n)$ grows faster than $n$ (i.e. $f(n)=\Omega(n^{1+\epsilon})$ for $\epsilon = 1$) and the regularity condition holds, by case 3 of the master theorem:
$T(n)=\Theta(n^2)$
Question:
Give a concrete example to where the stableness of a sorting algorithm is desirable. Name a stable sorting algorithm.
E.g., sorting a collection of student records (already sorted by student ID) by their letter grades, while still making sure students in the same letter grade group is sorted by student ID.
An example of a stable sorting algorithm is merge sort.
Question:
Prove that
$S(n)=1^2+2^2+\cdots+n^2=\Theta(n^3)$
Either using the formula: $S(n)=\frac{n(n + 1)(2n + 1)}{6}$,
Or obviously $S(n) \leq \sum_{i=1}^{n} n^2 = O(n^3)$. To show the lower bound, we cut the sum into two halves.
$S(n) = \underbrace{\sum_{i=1}^{\frac{n}{2}} i^2}_{A} + \underbrace{\sum_{\frac{n}{2}}^{n} i^2}_{B}$
$\geq B = \Omega(n^3)$
Question:
Given a rotated sorted array of distinct integers, implement an algorithm to find the minimum element in $O(\log n)$ time.
Use a modified binary search. Compare the middle element with the rightmost element to adjust the search boundaries until the minimum element is found.
class Quest:
def findMin(self, nums):
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] > nums[high]:
low = mid + 1
else:
high = mid
return nums[low]
# Example test:
solver = Quest()
print(solver.findMin([4, 5, 6, 7, 0, 1, 2]))
# Expected output: 0Question:
Given a string representing an absolute Unix file path (e.g., /a/./b/../../c/), simplify it. Use a stack to process the directories and produce the canonical path.
Push valid directory names onto the stack while processing components. Skip empty components or ".". When encountering "..", pop from the stack if not empty. Finally, join the stack components to form the simplified path.
def simplifyPath(path: str) -> str:
stack = []
# Split the path by "/" and process each component
for part in path.split("/"):
if part == "" or part == ".":
continue
elif part == "..":
if stack:
stack.pop()
else:
stack.append(part)
return "/" + "/".join(stack)
# Example test:
print(simplifyPath("/a/./b/../../c/"))
# Expected output: "/c"
print(simplifyPath("/../"))
# Expected output: "/"Question:
Given an array of $n$ integers and a window size $k$, compute the maximum value in each of the $n$ sliding window in $O(n)$ time.
Maintain a deque that stores indices of array elements in decreasing order. For each new element, remove indices that are out of the current window or whose values are less than the current value. The element at the front of the deque is the maximum for that window.
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
# Custom double-ended queue implementation using doubly linked list
class CustomDeque:
def __init__(self):
self.head = None # Head of the list (left end)
self.tail = None # Tail of the list (right end)
self.size = 0
def append(self, item):
new_node = Node(item)
if self.size == 0:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.size += 1
def pop(self):
if self.size == 0:
raise IndexError("pop from an empty deque")
value = self.tail.value
if self.size == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.size -= 1
return value
def popleft(self):
if self.size == 0:
raise IndexError("pop from an empty deque")
value = self.head.value
if self.size == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
self.size -= 1
return value
def __len__(self):
return self.size
def __bool__(self):
return self.size > 0
def __getitem__(self, index):
# Handle negative indices
if index < 0:
index = self.size + index
if index < 0 or index >= self.size:
raise IndexError("Index out of range")
if index == 0:
return self.head.value
if index == self.size - 1:
return self.tail.value
# Choose traversal direction based on whether the index is closer to head or tail
if index <= self.size // 2:
current = self.head
for _ in range(index):
current = current.next
else:
current = self.tail
for _ in range(self.size - 1 - index):
current = current.prev
return current.value
def slidingWindowMaximum(nums, k):
if not nums or k <= 0:
return []
dq = CustomDeque() # Stores indices of potential max elements
result = []
for i in range(len(nums)):
# Remove indices that are out of this window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove indices whose corresponding values are less than nums[i]
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Append the maximum for this window when the first full window is reached
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Example test:
print(slidingWindowMaximum([1,3,-1,-3,5,3,6,7], 3)) # Expected output: [3,3,5,5,6,7]Question:
Given $k$ sorted integer arrays, merge them into one sorted array. Use a min-priority queue (heap) to efficiently perform the merge.
Use a min-heap where each entry is a tuple containing the element value, its originating array index, and the element's index within that array. Extract the smallest element from the heap and push the next element from the same array if available.
class Heapq:
def __init__(self):
self.heap = []
def heappush(self, heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
self._siftup(heap, len(heap) - 1)
def heappop(self, heap):
"""Pop and return the smallest item from the heap."""
if not heap:
raise IndexError("pop from empty heap")
last_item = heap.pop()
if heap:
return_item = heap[0]
heap[0] = last_item
self._siftdown(heap, 0)
return return_item
return last_item
def _siftup(self, heap, index):
"""Move the element at index up to maintain heap property."""
item = heap[index]
while index > 0:
parent = (index - 1) // 2
if heap[parent] <= item:
break
heap[index] = heap[parent]
index = parent
heap[index] = item
def _siftdown(self, heap, index):
"""Move the element at index down to maintain heap property."""
item = heap[index]
n = len(heap)
while True:
left = 2 * index + 1
right = 2 * index + 2
smallest = index
if left < n and heap[left] < heap[smallest]:
smallest = left
if right < n and heap[right] < heap[smallest]:
smallest = right
if smallest == index:
break
heap[index] = heap[smallest]
index = smallest
heap[index] = item
def mergeKSortedArrays(arrays):
heapq = Heapq()
min_heap = []
result = []
# Initialize heap with the first element of each array along with array and element indices
for i, arr in enumerate(arrays):
if arr: # Ensure the array is not empty
heapq.heappush(min_heap, (arr[0], i, 0))
while min_heap:
val, arr_idx, elem_idx = heapq.heappop(min_heap)
result.append(val)
if elem_idx + 1 < len(arrays[arr_idx]):
next_val = arrays[arr_idx][elem_idx + 1]
heapq.heappush(min_heap, (next_val, arr_idx, elem_idx + 1))
return result
# Example test:
arrays = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
print(mergeKSortedArrays(arrays)) # Expected output: [1,2,3,4,5,6,7,8,9]Question:
Given a binary tree, perform a level order traversal (breadth-first search) and return the list of values at each level. Use a queue to facilitate the traversal.
Use a queue to process nodes level by level. For each level, dequeue all nodes in the current level and enqueue their children, accumulating the node values in a list.
# Custom Node class for linked list implementation
class Node:
def __init__(self, value):
self.value = value
self.next = None
# Custom queue implementation using singly linked list
class CustomQueue:
def __init__(self):
self.head = None # Head of queue (dequeue from here)
self.tail = None # Tail of queue (enqueue here)
self.size = 0
def append(self, item):
new_node = Node(item)
if self.size == 0:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.size += 1
def popleft(self):
if self.size == 0:
raise IndexError("pop from an empty queue")
value = self.head.value
self.head = self.head.next
if self.head is None:
self.tail = None
self.size -= 1
return value
def __len__(self):
return self.size
def __bool__(self):
return self.size > 0
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: TreeNode) -> list:
if not root:
return []
result = []
queue = CustomQueue()
queue.append(root)
while queue:
level_size = len(queue)
level_vals = []
for _ in range(level_size):
node = queue.popleft()
level_vals.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_vals)
return result
# Example test:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(levelOrder(root)) # Expected output: [[1], [2, 3], [4, 5]]Question:
Write a recursive function longestRootToLeafPath(root) that returns the longest path from the root to any leaf in a binary tree. The path should be returned as a list of node values. If multiple paths have the same length, you can return any one of them.
For instance, consider the following tree:
The function could return [1, 3, 5, 6] as the longest root-to-leaf path.
We can solve this problem recursively by defining the following approach:
None, return an empty list (i.e., no path).Below is the corresponding Python implementation:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def longestRootToLeafPath(root: TreeNode) -> list:
# Base case: if the node is None, return an empty path.
if root is None:
return []
# Base case: if the node is a leaf, return a list with its value.
if root.left is None and root.right is None:
return [root.val]
# Recursively get longest paths from left and right subtrees
left_path = longestRootToLeafPath(root.left)
right_path = longestRootToLeafPath(root.right)
# Select the longer of two paths
if len(left_path) > len(right_path):
longer_path = left_path
else:
longer_path = right_path
# Include the current node's value at the start of the longer path and return.
return [root.val] + longer_path
# Example test:
# Constructing the binary tree:
# 1
# / \
# 2 3
# / \
# 4 5
# \
# 6
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4))
root.right = TreeNode(3, None, TreeNode(5, None, TreeNode(6)))
path = longestRootToLeafPath(root)
print("Longest root-to-leaf path:", path)
# Expected output: Longest root-to-leaf path: [1, 3, 5, 6]