How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a nan difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Together AI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Together AI during technical interviews.

Detect cycles and break them in pod dependencies

Company: Together AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: nan

Interview Round: Technical Screen

You are given dependencies between software pods. Each dependency is a directed edge `u -> v` meaning **pod `u` must be built/installed before pod `v`**. ## Part 1: Detect whether a cycle exists Given: - `n`: number of pods (labeled `0..n-1`) - `edges`: list of directed dependency pairs `(u, v)` Return `true` if the dependency graph contains **any cycle** (i.e., it is impossible to build all pods), otherwise return `false`. ## Part 2: If there is a cycle, output an edge to remove Using the same input format (directed edges), if the graph has a cycle, return **any single directed edge `(u, v)`** such that **removing that edge makes the graph acyclic**. If the graph is already acyclic, return an empty result (e.g., `null` / `(-1, -1)` depending on your language). ### Notes / Assumptions - There may be multiple valid edges to remove; returning any one is acceptable. - You may assume there exists at least one edge whose removal can break all cycles (i.e., one-edge fix is possible). ### Example Input: `n = 3`, `edges = [(0,1),(1,2),(2,1)]` - Part 1 output: `true` - Part 2 output: `(2,1)` (removing it breaks the cycle)

Quick Answer: This question evaluates proficiency with directed graph concepts and dependency resolution, focusing on cycle detection and selecting a single dependency edge whose removal renders the graph acyclic.

Part 1: Detect a Cycle in Pod Dependencies

You are given `n` software pods labeled `0` to `n - 1` and a list of directed dependencies `edges`, where `(u, v)` means pod `u` must be built before pod `v`. Return `True` if the dependency graph contains at least one directed cycle. Return `False` if all pods can be built in some valid order.

Constraints

0 <= n <= 200000
0 <= len(edges) <= 300000
0 <= u, v < n for every edge (u, v)

Examples

Input: (4, [(0, 1), (1, 2), (2, 3)])

Expected Output: False

Explanation: The dependencies form a simple chain, so a valid build order exists: 0, 1, 2, 3.

Input: (3, [(0, 1), (1, 2), (2, 0)])

Expected Output: True

Explanation: Every pod depends on another in the cycle 0 -> 1 -> 2 -> 0, so no valid build order exists.

Input: (0, [])

Expected Output: False

Explanation: An empty graph has no nodes and therefore no cycles.

Input: (2, [(1, 1)])

Expected Output: True

Explanation: Pod 1 depends on itself, which is a directed cycle.

Input: (5, [(0, 1), (2, 3)])

Expected Output: False

Explanation: The graph is disconnected, but neither component contains a cycle.

Solution

def solution(n, edges):
    from collections import deque

    adj = [[] for _ in range(n)]
    indegree = [0] * n

    for u, v in edges:
        adj[u].append(v)
        indegree[v] += 1

    queue = deque(i for i in range(n) if indegree[i] == 0)
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1

        for neighbor in adj[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return processed != n

Time complexity: O(n + m), where m is the number of edges. Space complexity: O(n + m).

Hints

A directed graph has no cycle if you can produce a full topological ordering.
Try repeatedly removing nodes with indegree 0. What does it mean if some nodes are never removed?

Part 2: Remove One Dependency to Break All Cycles

You are given `n` software pods labeled `0` to `n - 1` and a list of directed dependencies `edges`, where `(u, v)` means pod `u` must be built before pod `v`. Return any one directed edge `(u, v)` such that removing that single edge makes the entire graph acyclic. If the graph is already acyclic, return `(-1, -1)`. You may assume that if the graph contains a cycle, there exists at least one single edge whose removal breaks all cycles.

Constraints

0 <= n <= 2000
0 <= len(edges) <= 5000
0 <= u, v < n for every edge (u, v)
If the graph contains cycles, at least one single-edge removal can make the graph acyclic

Examples

Input: (4, [(0, 1), (1, 2), (2, 3)])

Expected Output: True

Explanation: A simple chain has no cycle, so all pods can be built.

Input: (3, [(0, 1), (1, 2), (2, 1)])

Expected Output: False

Explanation: Pods 1 and 2 depend on each other, creating a cycle.

Input: (1, [])

Expected Output: True

Explanation: Edge case: a single pod with no dependencies is always buildable.

Input: (2, [(1, 1)])

Expected Output: False

Explanation: A self-loop is a cycle.

Input: (5, [(0, 1), (2, 3)])

Expected Output: True

Explanation: Disconnected components are fine as long as none contains a cycle.

Solution

def solution(n, edges):
    from collections import deque

    adj = [[] for _ in range(n)]
    indegree = [0] * n

    for u, v in edges:
        adj[u].append(v)
        indegree[v] += 1

    q = deque(i for i in range(n) if indegree[i] == 0)
    built = 0

    while q:
        node = q.popleft()
        built += 1
        for nei in adj[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                q.append(nei)

    return built == n

Time complexity: O(n + m), where m = len(edges). Space complexity: O(n + m).

Hints

Any valid edge to remove must belong to every cycle, so it must be on at least one cycle you detect.
Find one cycle first, then try removing each edge on that cycle and test whether the remaining graph has a topological ordering.

Quick Overview

This question evaluates proficiency with directed graph concepts and dependency resolution, focusing on cycle detection and selecting a single dependency edge whose removal renders the graph acyclic.