PracHub
QuestionsCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Google

Determine Whether a Word Exists in a Graph

Last updated: May 12, 2026

Quick Overview

This question evaluates proficiency in graph algorithms and backtracking techniques, including traversal strategies, cycle avoidance, and state management for matching a target sequence within a graph.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Determine Whether a Word Exists in a Graph

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a graph as a list of node objects. Each node contains a character and a list of neighboring nodes that can be visited next. Design and implement a function: `boolean existsPath(List<Node> nodes, String target)` Return `true` if there exists a path whose node characters, in order, exactly form `target`. The path may start from any node. During one attempted match, the same node cannot be reused. The graph may contain cycles and repeated characters. Example node shape: `Node { char value; List<Node> neighbors; }` Discuss edge cases and the time and space complexity. Possible follow-ups include handling very large graphs, pruning repeated searches, and adapting the solution if nodes may be reused.

Quick Answer: This question evaluates proficiency in graph algorithms and backtracking techniques, including traversal strategies, cycle avoidance, and state management for matching a target sequence within a graph.

Related Interview Questions

  • Find A Threshold-Limited Path With Minimum Required Safety - Google (medium)
  • Build Prefix Lookup with a Trie - Google (medium)
  • Deterministic Task Execution Order - Google (easy)
  • Busiest Rental Car - Google (easy)
  • Find Common Free Time Slots Across Calendars - Google (easy)
|Home/Coding & Algorithms/Google

Determine Whether a Word Exists in a Graph

Google logo
Google
May 2, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
3
0
Practice Read
Loading...

You are given a graph as a list of node objects. Each node contains a character and a list of neighboring nodes that can be visited next.

Design and implement a function:

boolean existsPath(List<Node> nodes, String target)

Return true if there exists a path whose node characters, in order, exactly form target. The path may start from any node. During one attempted match, the same node cannot be reused. The graph may contain cycles and repeated characters.

Example node shape:

Node { char value; List<Node> neighbors; }

Discuss edge cases and the time and space complexity. Possible follow-ups include handling very large graphs, pruning repeated searches, and adapting the solution if nodes may be reused.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Google•More Software Engineer•Google Software Engineer•Google Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.