Interview Format:

• Duration: 45 minutes
• Style: Technical coding round (whiteboard/Google Docs-style interface)
• Language: Python (but language-agnostic questions)

🎯 Problem Statement:

You are given an undirected connected graph that forms exactly one cycle (i.e., a ring). The graph is provided as an adjacency list. Your task is to print all the possible paths that form the complete ring, starting from each node.

Example Input:
graph = {
"A": ["B", "D"],
"B": ["C", "A"],
"C": ["D", "B"],
"D": ["A", "C"]
}

Expected Output:
ABCD
BCDA
CDAB
DABC

Key Constraints ( After verifying with the recuiter):

• Each node has exactly two neighbors.
• Graph forms one and only one ring.
• All node values are unique.
• No extra edges or branches.

Discussion & Exploration:

1. The interviewer first asked the approach to solve it i gave brute force and using DFS.

2. Brute force solution explored all paths and maintained a full visited path to prevent cycles.

3. Optimization was then discussed:

   • Since each node has two neighbors and the graph is a ring, simply avoiding the parent node during traversal is sufficient to prevent loops.
   • This eliminates the need for a full visited set → reduced space complexity.

Complexity Analysis:

Brute Force:

• Time: O(N) per path × N paths = O(N²)
• Space: O(N) for each recursive call and visited path

Optimized:

• Time: Still O(N²) (each path is length N, and there are N such paths)
• Space: O(N) only for output path and parent tracking (no visited set needed)

Interview Highlights:

• The interviewer asked many deep questions:

  • Why use visited set?
  • What happens if we remove neighbor not in path?
  • How can we reduce space complexity?
  • What is the difference in complexity between using set vs list approach?
  • Can we reduce space to O(1)?

• They appreciated reasoning about:

  • How DFS works specifically for rings
  • Importance of pruning with just prev node instead of visited
  • Using bitmask/array as a visited alternative

Final Code (Optimized for Ring Graph):

def find_ring_paths(graph):
    def dfs(node, parent, path):
        path.append(node)
        for neighbor in graph[node]:
            if neighbor != parent:
                dfs(neighbor, node, path)
                break  # only one forward direction to follow in a ring

    for start in graph:
        path = []
        dfs(start, None, path)
        print("".join(path))

Key Take Aways:

• Medium difficulty
• Graph theory + DFS
• Optimization discussion was key
• Strong understanding of data structures and complexity was tested
• Excellent round to demonstrate both coding and system-level thinking