← Together AI Interview Insights

Together AI·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Mar 2026

Summary

Technical phone screen at together.ai, one coding problem, graph theory flavored. Pretty standard for an infra-adjacent role but the pod/dependency framing threw me off for a second before I realized it was just cycle detection.

Questions Asked (1)

Q1

You have a set of pods where some share dependencies with each other, modeled as an undirected graph. Determine if the graph contains a cycle, and if it does, return any single edge whose removal would break it.

Algorithms & Data Structures
Author's notes

The pod/dependency wrapper made it sound fancier than it was.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use DFS with a parent pointer to detect cycles in the undirected graph, tracking the edge that closes the cycle. Alternatively, use Union-Find to detect the first edge that connects two already-connected components, which is the edge to remove.

Pro tip: Clarify whether the graph is guaranteed to be connected and whether multiple cycles exist; if so, any edge that breaks a cycle is acceptable, but ensure your solution handles disconnected components by iterating over all nodes.

1. Clarify assumptions and edge cases

Confirm if the graph is connected, if self-loops or multiple edges are possible, and if the cycle-breaking edge must be part of a cycle. Discuss handling of empty graph or single node.

2. Choose an algorithm

Select between DFS with parent tracking or Union-Find. DFS is straightforward for cycle detection and returning the back edge; Union-Find efficiently finds the edge that creates a cycle.

3. Implement cycle detection

For DFS: traverse the graph, track visited nodes and parent; when encountering a visited neighbor that is not the parent, a cycle is found and the current edge is the back edge. For Union-Find: iterate edges, union nodes; if an edge connects nodes already in the same set, that edge creates a cycle.

4. Return the cycle-breaking edge

If a cycle is detected, return the edge that closes the cycle (the back edge in DFS or the redundant edge in Union-Find). If no cycle, return null or indicate no cycle.

5. Analyze complexity and discuss trade-offs

State time and space complexity: DFS O(V+E) time, O(V) space; Union-Find O(E α(V)) time, O(V) space. Mention that DFS can also find all cycles but here we only need one edge.

Key Points to Mention

  • Cycle detection in undirected graphs using DFS with parent tracking or Union-Find.
  • Handling disconnected graphs by iterating over all components.
  • Time and space complexity analysis: O(V+E) for DFS, O(E α(V)) for Union-Find.
  • Edge cases: self-loops, multiple edges, empty graph, single node.
  • The returned edge must be part of a cycle; removing it breaks that cycle.
  • Trade-offs between DFS and Union-Find in terms of implementation simplicity and efficiency.

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