Algorithmic Problem Solving Flashcards
7 cards from real Epic Skills Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Algorithmic Problem Solving flashcards as text
Which technique is used to detect a cycle in a linked list using O(1) extra space?
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.
In memoization, what triggers a cache miss?
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.
What is the time complexity of binary search on a sorted array of n elements?
Answer: O(log n)
Binary search eliminates half the remaining elements each step, giving a depth of log₂(n) comparisons.
Which algorithm would you use to find the minimum spanning tree of a graph?
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.
What is 'tail recursion' and why can compilers optimize it?
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.
Which problem-solving approach explores all possibilities and abandons a branch as soon as it violates a constraint?
Answer: Backtracking
Backtracking builds candidates incrementally and prunes branches the moment they cannot lead to a valid solution.
Given an algorithm with recurrence T(n) = 2T(n/2) + O(n), what is its time complexity by the Master Theorem?
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.