Epic Skills Assessment Algorithmic Problem Solving 4 — Questions and Answers
Question 1: Which algorithm finds the shortest path in a weighted graph with non-negative edge weights?
- BFS
- DFS
- Dijkstra's algorithm (Correct answer)
- Bellman-Ford
Correct answer: Dijkstra's algorithm
Dijkstra's algorithm greedily processes the nearest unvisited vertex and is correct for graphs with non-negative weights.
Question 2: What is the defining property of a hash function used in a hash table?
- It must be reversible
- It maps keys to fixed-size indices with ideally uniform distribution (Correct answer)
- It must produce unique values for every key
- It must run in O(log n)
Correct answer: It maps keys to fixed-size indices with ideally uniform distribution
A good hash function maps arbitrary keys to array indices uniformly, minimizing collisions without needing to be bijective.
Question 3: In a sliding window algorithm, what problem does the technique primarily solve?
- Finding cycles in graphs
- Efficiently processing contiguous subarrays or substrings without recomputing from scratch (Correct answer)
- Sorting elements in-place
- Detecting duplicate elements
Correct answer: Efficiently processing contiguous subarrays or substrings without recomputing from scratch
A sliding window maintains a range and updates it incrementally, reducing many O(n²) subarray problems to O(n).
Question 4: Which of the following is an example of a divide-and-conquer algorithm?
- Dijkstra's shortest path
- Kruskal's MST
- Merge sort (Correct answer)
- Topological sort
Correct answer: Merge sort
Merge sort splits the array in half, recursively sorts each half, and merges them—the classic divide-and-conquer pattern.
Question 5: What does it mean for a problem to be NP-complete?
- It has no known solution
- It can be solved in polynomial time
- It is in NP and every NP problem reduces to it in polynomial time (Correct answer)
- It requires exponential space to solve
Correct answer: It is in NP and every NP problem reduces to it in polynomial time
NP-complete problems are the hardest problems in NP: if any one can be solved in polynomial time, all NP problems can be.
Question 6: Which data structure gives O(1) average-case lookup by key?
- Binary search tree
- Hash table (Correct answer)
- Sorted array
- Linked list
Correct answer: Hash table
Hash tables map keys to indices via a hash function, achieving O(1) average lookup (O(n) worst case with many collisions).
Question 7: What is the key difference between BFS and DFS graph traversal?
- BFS uses a stack; DFS uses a queue
- BFS explores nodes level by level; DFS explores as deep as possible before backtracking (Correct answer)
- BFS only works on trees; DFS works on general graphs
- BFS visits each node exactly twice; DFS visits each once
Correct answer: BFS explores nodes level by level; DFS explores as deep as possible before backtracking
BFS uses a queue to explore neighbors level by level, while DFS uses a stack (or recursion) to go as deep as possible before backtracking.
Epic Skills Assessment Algorithmic Problem Solving 4
Which algorithm finds the shortest path in a weighted graph with non-negative edge weights?