Google Interview Experience – Test Engineer (Onsite Round 1)

Interview Format:

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

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

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