together.ai·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Interviewed at together.ai and got a graph problem that I've seen before but still managed to overthink in the moment. Pretty standard technical screen, nothing too surprising about the format.

Questions Asked (1)

Given a set of pods with shared dependencies modeled as an undirected graph, detect whether a cycle exists and return any single edge whose removal would eliminate it.

Algorithms & Data Structures

Author's notes

Classic redundant connection problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use depth-first search (DFS) with a parent pointer to detect back edges in the undirected graph. When a back edge is found, return that edge as the one whose removal breaks the cycle. Alternatively, use union-find to detect the first edge that connects two already-connected components.

Pro tip: Clarify whether the graph is guaranteed connected and whether multiple cycles exist; if so, returning any edge from a cycle is sufficient, but mention that removing it may not eliminate all cycles. Also, discuss handling self-loops and parallel edges as immediate cycles.

1. Clarify assumptions and edge cases

Confirm if the graph is connected, if multiple cycles can exist, and how to handle self-loops or parallel edges. State that any edge in a cycle is acceptable.

2. Choose an algorithm

Select DFS with parent tracking for cycle detection and edge identification, or union-find for a simpler implementation. Explain the trade-offs.

3. Implement cycle detection

For DFS: traverse the graph, track visited nodes and parent; when encountering a visited node that is not the parent, a cycle is found. For union-find: process edges, union endpoints; if an edge connects nodes already in the same set, it's a cycle edge.

4. Return the edge

Return the back edge (DFS) or the edge that caused the union-find conflict. Ensure it's a valid edge in the graph.

5. Analyze complexity and discuss alternatives

State time and space complexity: O(V+E) for DFS, O(E α(V)) for union-find. Mention that removing the edge may not eliminate all cycles if multiple exist.

Key Points to Mention

Cycle detection in undirected graphs using DFS with parent tracking
Union-Find (Disjoint Set Union) for cycle detection
Handling of self-loops and parallel edges as immediate cycles
Time and space complexity analysis (O(V+E) for DFS, near O(E) for union-find)
The returned edge is part of at least one cycle; removal breaks that cycle but may not break all cycles
Edge cases: empty graph, single node, disconnected components

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