Epic Skills Assessment Algorithmic Problem Solving 5

Question 1

Which technique is used to detect a cycle in a linked list using O(1) extra space?

Accepted Answer

Floyd's tortoise and hare algorithm

Answer

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?

Accepted Answer

The subproblem has never been computed before

Answer

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?

Accepted Answer

O(log n)

Answer

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?

Accepted Answer

Kruskal's or Prim's

Answer

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?

Accepted Answer

A recursive call that is the very last operation in a function; the current frame can be reused

Answer

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.

Epic Skills Assessment Practice Test