Algorithms Case Studies & Practical Application 4 — Questions and Answers
Question 1: A search engine indexes billions of web pages and must return relevant results in milliseconds. Which core data structure underpins inverted index lookups?
- Stack
- Hash map from term to posting list (Correct answer)
- Max-heap
- Minimum spanning tree
Correct answer: Hash map from term to posting list
An inverted index maps each term to a list of documents containing it; hash maps give O(1) term lookup to retrieve posting lists.
Question 2: A network router must forward packets to their destination as fast as possible. Longest-prefix matching on IP addresses is efficiently implemented using:
- Linear scan of routing table
- Trie (Patricia trie) on binary IP prefixes (Correct answer)
- Bubble sort on destination IPs
- BFS over network topology
Correct answer: Trie (Patricia trie) on binary IP prefixes
Patricia tries store IP prefixes as binary paths, enabling O(32) worst-case lookup for IPv4 regardless of routing table size.
Question 3: A payment processing system must ensure a sequence of transactions is valid (no double-spend) before committing. Which algorithmic property guarantees correctness?
- Greedy ordering by amount
- Serializable transaction ordering via locking or MVCC (Correct answer)
- Topological sort of accounts
- BFS over transaction graph
Correct answer: Serializable transaction ordering via locking or MVCC
Serializability (via two-phase locking or multi-version concurrency control) ensures concurrent transactions produce results as if executed sequentially.
Question 4: A spell checker suggests corrections for a misspelled word by finding dictionary words with the fewest character edits. Which algorithm computes this?
- Longest Common Subsequence
- Edit distance (Levenshtein distance) via dynamic programming (Correct answer)
- KMP string matching
- Kruskal's algorithm
Correct answer: Edit distance (Levenshtein distance) via dynamic programming
Levenshtein distance uses DP to count the minimum insertions, deletions, and substitutions to transform one string into another.
Question 5: A CDN must select the server with the lowest latency for each user request, given continuously updated latency measurements. Which strategy is most adaptive?
- Round-robin (ignore latency)
- Weighted least-connections or real-time latency-based routing (Correct answer)
- Random server selection
- Static assignment by IP range
Correct answer: Weighted least-connections or real-time latency-based routing
Dynamic latency-based routing continuously re-weights server selection based on measured response times, minimizing perceived user latency.
Question 6: A fraud detection system scores millions of transactions per day. The algorithm must have very high recall (catch most fraud) even at the cost of some false positives. This trade-off relates to:
- Time vs. space complexity
- Precision vs. recall on the ROC curve (Correct answer)
- Best-case vs. worst-case time complexity
- Stable vs. unstable sorting
Correct answer: Precision vs. recall on the ROC curve
On the precision-recall curve, tuning the decision threshold lower increases recall (catches more fraud) at the cost of more false positives.
Question 7: A distributed database replicates data across 5 nodes. To tolerate up to 2 simultaneous node failures while still reading consistent data, how many nodes must agree on a read (quorum)?
- 2
- 3 (Correct answer)
- 4
- 5
Correct answer: 3
With 5 nodes, a majority quorum of 3 guarantees overlap between any write quorum and any read quorum, tolerating 2 failures.
Algorithms Case Studies & Practical Application 4
A search engine indexes billions of web pages and must return relevant results in milliseconds.
Which core data structure underpins inverted index lookups?