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 algorithm finds the shortest path in a weighted graph with non-negative edge weights?
Answer: Dijkstra's algorithm
Dijkstra's algorithm greedily processes the nearest unvisited vertex and is correct for graphs with non-negative weights.
What is the defining property of a hash function used in a hash table?
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.
In a sliding window algorithm, what problem does the technique primarily solve?
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).
Which of the following is an example of a divide-and-conquer algorithm?
Answer: Merge sort
Merge sort splits the array in half, recursively sorts each half, and merges them—the classic divide-and-conquer pattern.
What does it mean for a problem to be NP-complete?
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.
Which data structure gives O(1) average-case lookup by key?
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).
What is the key difference between BFS and DFS graph traversal?
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.