Epic Skills Assessment Algorithmic Problem Solving 5 — Questions and Answers
Question 1: Which technique is used to detect a cycle in a linked list using O(1) extra space?
- Storing visited nodes in a hash set
- Floyd's tortoise and hare algorithm (Correct answer)
- Reversing the list and comparing
- Using a counter variable
Correct answer: Floyd's tortoise and hare algorithm
Floyd's algorithm uses two pointers moving at different speeds; if they meet, a cycle exists, using only O(1) extra space.
Question 2: In memoization, what triggers a cache miss?
- The subproblem result is incorrect
- The subproblem has never been computed before (Correct answer)
- The cache is full
- The recursion depth exceeds a threshold
Correct answer: The subproblem has never been computed before
A cache miss occurs when the function is called with arguments it hasn't processed yet, requiring actual computation.
Question 3: What is the time complexity of binary search on a sorted array of n elements?
- O(n)
- O(n²)
- O(log n) (Correct answer)
- O(1)
Correct answer: O(log n)
Binary search eliminates half the remaining elements each step, giving a depth of log₂(n) comparisons.
Question 4: Which algorithm would you use to find the minimum spanning tree of a graph?
- Dijkstra's
- Bellman-Ford
- Kruskal's or Prim's (Correct answer)
- Floyd-Warshall
Correct answer: Kruskal's or Prim's
Kruskal's and Prim's are the standard MST algorithms; Dijkstra's and Bellman-Ford find shortest paths, not spanning trees.
Question 5: What is 'tail recursion' and why can compilers optimize it?
- Recursion with no base case; it avoids stack frames
- A recursive call that is the very last operation in a function; the current frame can be reused (Correct answer)
- Recursion that processes the tail end of a list first
- Any recursion that runs in O(log n) time
Correct answer: A recursive call that is the very last operation in a function; the current frame can be reused
When a recursive call is the final action, the compiler can replace the current stack frame instead of adding a new one, avoiding stack growth.
Question 6: Which problem-solving approach explores all possibilities and abandons a branch as soon as it violates a constraint?
- Dynamic programming
- Greedy
- Backtracking (Correct answer)
- Divide and conquer
Correct answer: Backtracking
Backtracking builds candidates incrementally and prunes branches the moment they cannot lead to a valid solution.
Question 7: Given an algorithm with recurrence T(n) = 2T(n/2) + O(n), what is its time complexity by the Master Theorem?
- O(n)
- O(n log n) (Correct answer)
- O(n²)
- O(log n)
Correct answer: O(n log n)
This matches Master Theorem Case 2 (a=2, b=2, f(n)=n, log_b(a)=1), yielding T(n) = O(n log n)—the complexity of merge sort.
Epic Skills Assessment Algorithmic Problem Solving 5
Which technique is used to detect a cycle in a linked list using O(1) extra space?