Algorithms Case Studies & Practical Application 3 — Questions and Answers
Question 1: A streaming service buffers video chunks and always serves the most urgent (lowest remaining playback time) chunk first. Which data structure supports this efficiently?
- Stack
- Min-heap (priority queue) (Correct answer)
- Doubly linked list
- Hash table
Correct answer: Min-heap (priority queue)
A min-heap allows O(log n) insertion and O(1) extraction of the minimum-priority element, perfect for urgency-based scheduling.
Question 2: A warehouse robot must visit a set of pick locations and return to its start, minimizing total travel distance. This is an instance of which NP-hard problem?
- Minimum Spanning Tree
- Traveling Salesman Problem (TSP) (Correct answer)
- Longest Common Subsequence
- Maximum Flow
Correct answer: Traveling Salesman Problem (TSP)
Visiting all nodes exactly once and returning to the start while minimizing cost is the definition of TSP.
Question 3: A version control system (like Git) uses which data structure to efficiently store and compare file trees across commits?
- Adjacency list graph
- Merkle tree (hash tree) (Correct answer)
- Red-black BST
- Circular buffer
Correct answer: Merkle tree (hash tree)
Merkle trees hash subtrees so that any change in a file propagates up, allowing O(log n) change detection between two versions.
Question 4: An autocomplete feature suggests words after a user types a prefix. Which data structure gives the best prefix-lookup performance?
- Hash map
- Trie (prefix tree) (Correct answer)
- Sorted array with binary search
- Max-heap
Correct answer: Trie (prefix tree)
A trie stores characters at each node, enabling O(m) prefix lookup where m is the prefix length, regardless of dictionary size.
Question 5: A load balancer must distribute requests across servers so no server is overwhelmed. Consistent hashing is preferred over simple modular hashing because:
- It is always faster for hash computation
- Adding or removing a server only remaps a fraction of keys instead of all keys (Correct answer)
- It guarantees perfect load balance at all times
- It eliminates hash collisions entirely
Correct answer: Adding or removing a server only remaps a fraction of keys instead of all keys
Consistent hashing minimizes remapping when nodes join or leave, making it robust for dynamic server pools.
Question 6: A genomics tool aligns a short DNA read against a reference genome of 3 billion bases. Which algorithmic technique makes this feasible?
- Naive string search O(nm)
- BWT/FM-index allowing near O(m) lookup (Correct answer)
- Bubble sort then binary search
- DFS over the genome graph
Correct answer: BWT/FM-index allowing near O(m) lookup
The Burrows-Wheeler Transform with an FM-index compresses the genome and allows extremely fast pattern matching, used in tools like BWA.
Question 7: A ride-sharing app must match riders to nearby drivers in real time. Which spatial data structure best supports 'find all drivers within 1 km'?
- Trie
- k-d tree or R-tree (Correct answer)
- Min-heap
- Topological sort output
Correct answer: k-d tree or R-tree
k-d trees and R-trees partition 2D space to answer range queries and nearest-neighbor queries in O(log n) average time.
Algorithms Case Studies & Practical Application 3
A streaming service buffers video chunks and always serves the most urgent (lowest remaining playback time) chunk first.
Which data structure supports this efficiently?