Algorithms Case Studies & Practical Application 3

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?

Accepted Answer

Min-heap (priority queue)

Answer

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?

Accepted Answer

Traveling Salesman Problem (TSP)

Answer

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?

Accepted Answer

Merkle tree (hash tree)

Answer

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?

Accepted Answer

Trie (prefix tree)

Answer

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:

Accepted Answer

Adding or removing a server only remaps a fraction of keys instead of all keys

Answer

Consistent hashing minimizes remapping when nodes join or leave, making it robust for dynamic server pools.

Algorithms Practice Test

Algorithms Practice Test

Algorithms Case Studies & Practical Application 3