← Akuna Capital Interview Insights

Akuna Capital·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Apr 2026

Summary

Graph problem for a Data Engineer role at Akuna Capital. Pretty straightforward OA setup, one coding question, Java solution submitted. Nothing too wild but the problem had some nuance if you weren't thinking carefully about connected components.

Questions Asked (1)

Q1

Given a set of nodes and an undirected edge list, build an adjacency list and find all connected components using BFS. For each component, compute the difference between the maximum and minimum node IDs, then return the largest such difference across all components.

Algorithms & Data Structures
Author's notes

The BFS part wasn't the hard bit, that's muscle memory at this point.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, build an adjacency list from the edge list, ensuring all nodes (including isolated ones) are represented. Then, perform BFS on each unvisited node to identify connected components, tracking the min and max node IDs within each component. Finally, compute the difference for each component and return the maximum difference found.

Pro tip: Clarify whether node IDs are guaranteed to be contiguous or if there can be gaps; handling isolated nodes and sparse IDs correctly shows attention to edge cases. Also, mention that you can compute min/max during BFS to avoid a second pass.

1. Build Adjacency List

Initialize a dictionary or list to map each node to its neighbors. Iterate through the edge list, adding each edge to both endpoints' lists. Ensure all nodes from the set are included, even if they have no edges.

2. Initialize BFS Structures

Create a visited set to track explored nodes. Prepare a queue for BFS and a variable to store the maximum difference found so far.

3. Traverse Components with BFS

For each unvisited node, start a BFS: mark it visited, enqueue it, and initialize min and max IDs to its value. While the queue is not empty, dequeue a node, update min/max, and enqueue all unvisited neighbors.

4. Compute and Track Differences

After BFS completes for a component, compute the difference between its max and min node IDs. Update the global maximum difference if this component's difference is larger.

5. Return Result

After all nodes are visited, return the maximum difference. If there are no nodes, return 0 or as specified.

Key Points to Mention

  • Handling isolated nodes (nodes with no edges) as components of size 1, where difference is 0.
  • Time complexity: O(V + E) for BFS, where V is number of nodes and E is number of edges.
  • Space complexity: O(V + E) for adjacency list and visited set.
  • Using a queue (FIFO) for BFS and marking nodes visited when enqueued to avoid duplicates.
  • Tracking min and max during BFS to avoid a second pass over the component.
  • Edge cases: empty graph, single node, all nodes connected, multiple components with same difference.

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