google logo
Google· Test Engineer

Google Interview Experience – Test Engineer (Onsite Round 1)

Posted
6 May 2025
352 reads

Summary

I experienced a technical coding round at Google for a Test Engineer role, focusing on graph theory and DFS. The interview, which was medium difficulty, heavily emphasized optimizing my solution and discussing complexity, which I felt went well.

How it went

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

Questions asked (1)

  1. 01

    Find All Ring Paths in a Connected Graph

    Data Structures & Algorithms · Medium

    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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!