I recently interviewed with Graviton Research Capital for the Software Engineer role. The first round consisted of two problem-solving questions focusing on data structures and graph theory. The interview lasted around 60 minutes.

Question 1 – Packet Receiver / Ordered Commit

A sender transmits packets to a receiver.

• Each packet has a serial number.
• Serial numbers are positive and strictly increasing for consecutive packets.
• Packets may arrive out of order.
• The receiver must commit packets strictly in order.
• The first packet starts from 1001.
• Additionally, no more than 10 packets can be missing in a row (i.e., packet P and P + 10 will never be reordered).

You need to design a Receiver class with a function:

receive(packet_number)

that processes arriving packets and commits packets whenever possible.

Approach

1. Track the next expected packet number (next_commit).

2. Maintain a data structure storing received but uncommitted packets (a set or boolean array).

3. When a packet arrives:

   • Mark it as received.
   • If its number equals next_commit, we attempt to commit packets sequentially.

4. Continue committing while the next expected packet exists in the received set.

Because the problem guarantees at most 10 packets can be missing, the buffer size remains small and operations stay efficient.

Time complexity per packet: O(1) amortized.

Question 2 – Connected Components with N Nodes and M Edges

Given:

• N nodes
• M undirected edges
• No self-loops
• No multiple edges

Find:

• Maximum possible number of connected components
• Minimum possible number of connected components

Maximum Connected Components

To maximize components, we should concentrate edges within a small subset of nodes while leaving the rest isolated.

Let X be the number of nodes used to place the edges.

A component of size X can contain at most:

X(X-1)/2 edges

We find the largest X such that

X(X-1)/2 ≤ M

Then:

• One component uses these X nodes
• Remaining nodes remain isolated

Maximum components:

N - X + 1

Minimum Connected Components

To minimize components, we should use edges to connect as many nodes as possible.

Each edge can reduce components by at most 1.

Starting with N isolated nodes:

Minimum components:

max(1, N - M)

Explanation:

• If we have enough edges to connect all nodes → one component.
• Otherwise each edge merges two components.