DSAA2043 Spring 2025 Practice Questions

Table of Contents

Practice Question 1 (Short Answer)

Back to TOC

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)$

Practice Question 2 (Short Answer)

Back to TOC

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.

Practice Question 3 (Short Answer)

Back to TOC

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)$

Practice Question 4 (Coding)

Back to TOC

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: 0

Practice Question 5: Simplify Unix File Path

Back to TOC

Question:

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: "/"

Practice Question 6: Sliding Window Maximum

Back to TOC

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]

Practice Question 7: Merge K Sorted Arrays

Back to TOC

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]

Practice Question 8: Level Order Traversal in a Binary Tree (Using Queue)

Back to TOC

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]]

Practice Question 9: Find the Longest Root-to-Leaf Path in a Binary Tree

Back to TOC

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:

1 / \ 2 3 / \ 4 5 \ 6

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:

  • Base Case: If the node is None, return an empty list (i.e., no path).
  • Leaf Node: If the node has no children, return a list containing only the node's value.
  • Recursive Case: Compute the longest path from the left subtree and from the right subtree. Compare their lengths, and select the longer one. Then prepend the current node's value to that path and return the result.

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]