Epic Skills Assessment Algorithmic Problem Solving 3 ā Questions and Answers
Question 1: Which algorithm strategy makes the locally optimal choice at each step without reconsidering past decisions?
- Dynamic programming
- Greedy (Correct answer)
- Brute force
- Branch and bound
Correct answer: Greedy
Greedy algorithms commit to the best immediate option at each step, which works when local optima lead to a global optimum.
Question 2: What is a 'sentinel value' used for in algorithms?
- A placeholder that simplifies boundary condition checks (Correct answer)
- A flag that signals an error state
- A value that marks the maximum of a dataset
- A pointer to the last processed node
Correct answer: A placeholder that simplifies boundary condition checks
A sentinel is a special value (e.g., āā or null) placed at array boundaries so the main loop never needs to check for edge cases explicitly.
Question 3: In the context of recursion, what causes a stack overflow?
- Using too many variables
- Infinite or excessively deep recursive calls that exhaust call stack memory (Correct answer)
- Returning incorrect base case values
- Calling non-recursive functions from within recursion
Correct answer: Infinite or excessively deep recursive calls that exhaust call stack memory
Each recursive call pushes a frame onto the call stack; without a reachable base case or with very deep recursion, memory is exhausted.
Question 4: Which traversal visits a binary tree's nodes in ascending order when the tree is a BST?
- Pre-order
- Post-order
- In-order (Correct answer)
- Level-order
Correct answer: In-order
In-order traversal (left ā root ā right) visits BST nodes in sorted ascending order.
Question 5: What is the purpose of a 'two-pointer' technique in array problems?
- To traverse two arrays simultaneously
- To reduce time complexity by maintaining two indices that move toward each other (Correct answer)
- To detect cycles in a linked list
- To implement merge sort
Correct answer: To reduce time complexity by maintaining two indices that move toward each other
Two pointers placed at opposite ends (or at specific offsets) allow many array problems to be solved in O(n) instead of O(nĀ²).
Question 6: Which of the following is NOT a valid reason to choose an iterative solution over a recursive one?
- Avoiding stack overflow on deep inputs
- Reducing function call overhead
- The iterative version always has better time complexity (Correct answer)
- Explicit control over the stack allows optimization
Correct answer: The iterative version always has better time complexity
Iteration and recursion can express the same algorithms; iterative versions don't automatically have better time complexity.
Question 7: What does 'amortized O(1)' mean for a dynamic array's append operation?
- Every single append takes O(1) time
- The average cost per append across all operations is O(1), even though occasional resizes cost more (Correct answer)
- Appending never triggers a resize
- Only the first append costs O(1)
Correct answer: The average cost per append across all operations is O(1), even though occasional resizes cost more
Occasional O(n) resizes are rare enough that the total cost spread over n appends averages to O(1) per operation.
Epic Skills Assessment Algorithmic Problem Solving 3
Which algorithm strategy makes the locally optimal choice at each step without reconsidering past decisions?