Compute delivery order via BFS

Q: Compute delivery order via BFS

This is a Coding & Algorithms interview question from Akuna Capital for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

A city road network is an unweighted, undirected graph G(V, E) with a depot node s and D delivery requests located at nodes r1..rD, each with an integer priority p and a unique ID. Produce the service order that sorts deliveries by increasing shortest-hop distance from s, breaking ties by higher priority first, then by smaller ID. Design an algorithm that runs in O(V+E + D log D) by performing a BFS from s to compute distances and then sorting the requests by (distance asc, priority desc, ID asc). Explain correctness, handle unreachable nodes, and provide pseudocode.

Compute delivery order via BFS

Comments (0)