Akuna Capital·Data Scientist·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Interviewed for a Data Scientist role at Akuna Capital and got a graph algorithm problem that felt more like a software engineering screen than anything data science related. The question was well-defined but required you to actually know your BFS and sorting complexity, not just wave your hands at it.

Questions Asked (1)

Given an unweighted undirected city road network modeled as a graph, with a depot node and a set of delivery requests each having a priority and unique ID, design an algorithm to produce a service order sorted by shortest-hop distance from the depot, breaking ties by higher priority first and then by smaller ID. The solution should run in O(V+E + D log D). Explain correctness, handle unreachable nodes, and write pseudocode.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one took me a second to parse because there's a lot of text dressing up what is basically BFS plus a sort.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: we need to compute shortest-hop distances from the depot to all nodes, then sort the delivery requests by distance, priority, and ID. Use BFS for distances and a custom comparator for sorting, ensuring O(V+E + D log D) time. Explain how to handle unreachable nodes by assigning them a sentinel distance and placing them at the end of the sorted list.

Pro tip: Mention that BFS is optimal for unweighted graphs and that the sorting step dominates only when D is large; also note that if D is small, a linear scan might be simpler, but the required complexity assumes D log D sorting.

1. Clarify requirements and constraints

Confirm that the graph is unweighted and undirected, that distances are in hops, and that the output is a sorted list of delivery IDs. Ask about edge cases like unreachable nodes and tie-breaking rules.

2. Compute shortest-hop distances

Run BFS from the depot to compute the minimum number of edges to each node. This takes O(V+E) time and handles unreachable nodes by leaving their distance as infinity.

3. Sort delivery requests

Sort the delivery requests using a comparator that orders by distance ascending, then priority descending, then ID ascending. This takes O(D log D) time.

4. Handle unreachable nodes

Assign a sentinel distance (e.g., infinity) to unreachable nodes so they appear at the end of the sorted list. If multiple unreachable nodes, sort them by priority and ID.

5. Analyze complexity and correctness

Argue that BFS correctly computes shortest-hop distances in unweighted graphs, and that the sorting step produces the required order. Total time is O(V+E + D log D), which meets the requirement.

Key Points to Mention

BFS is the optimal algorithm for shortest paths in unweighted graphs, running in O(V+E).
The sorting comparator must handle three keys: distance (ascending), priority (descending), and ID (ascending).
Unreachable nodes should be assigned a distance of infinity (or a large number) and placed at the end of the sorted list.
The overall time complexity is O(V+E + D log D), where D is the number of delivery requests.
Correctness proof: BFS guarantees shortest hop distances; sorting with the comparator ensures the required order.
Edge cases: depot itself may have delivery requests (distance 0), multiple requests with same distance and priority, and disconnected graph components.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.