← AkunaCapital Interview Insights

AkunaCapital·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Jun 2026

Summary

Graph problem for a Data Engineer role at Akuna Capital. One coding question, submitted in Java, felt more like a pure algorithms screen than anything data-engineering specific.

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. Return the largest such difference across all components.

Algorithms & Data Structures
Author's notes

Took me a minute to realize the answer isn't just a global max minus global min across all nodes.

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 included. Then, run BFS from 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 within a certain range or if they can be arbitrary; this affects whether you can use an array-based adjacency list or need a hash map. Also, mention that you'll handle isolated nodes by initializing the adjacency list with all nodes.

1. Build the adjacency list

Initialize a dictionary or list to store neighbors for each node. Iterate through the edge list and add each edge in both directions. Ensure all nodes from the given set are included, even if they have no edges.

2. Initialize BFS structures

Create a visited set to track nodes that have been processed. Also, prepare a queue for BFS traversal.

3. Traverse each component with BFS

For each unvisited node, start a BFS. While traversing, keep track of the minimum and maximum node IDs encountered in that component.

4. Compute and track the maximum difference

After finishing a component, calculate the difference between its max and min node IDs. Update a global maximum if this difference is larger.

5. Return the result

After processing all nodes, return the largest difference found. If there are no nodes, return 0 or as specified.

Key Points to Mention

  • Handling isolated nodes: ensure they are included as components of size 1 with difference 0.
  • Time and space complexity: O(V + E) time and O(V + E) space for adjacency list and BFS.
  • Using a queue for BFS and a visited set to avoid revisiting nodes.
  • Tracking min and max node IDs during BFS traversal.
  • Edge cases: empty graph, single node, multiple components with same difference.
  • Choice of data structures: adjacency list as dictionary of lists or array of lists depending on node ID range.

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