Algorithms Case Studies & Practical Application 4

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?

Accepted Answer

Hash map from term to posting list

Answer

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:

Accepted Answer

Trie (Patricia trie) on binary IP prefixes

Answer

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?

Accepted Answer

Serializable transaction ordering via locking or MVCC

Answer

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?

Accepted Answer

Edit distance (Levenshtein distance) via dynamic programming

Answer

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?

Accepted Answer

Weighted least-connections or real-time latency-based routing

Answer

Dynamic latency-based routing continuously re-weights server selection based on measured response times, minimizing perceived user latency.

Algorithms Practice Test

Algorithms Practice Test

Algorithms Case Studies & Practical Application 4