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 medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

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

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.

You are given a directed graph where each node stores a single character and a list of neighboring nodes that can be visited next. Your task is to determine whether there exists a simple path whose characters, in order, exactly form the given target string. For this coding problem, the graph is represented as a list where node i is stored as (value, neighbors): - value: a one-character string - neighbors: a list of indices of nodes reachable from i Implement a function solution(nodes, target) that returns True if such a path exists and False otherwise. Rules: - The path may start from any node. - During one attempted match, the same node cannot be reused. - The graph may contain cycles. - Node values may repeat. - An empty target should return True.

Constraints

0 <= len(nodes) <= 200
0 <= len(target) <= 15
Each node is represented as (value, neighbors), where value is a single-character string
Each neighbor index is a valid index into nodes
The graph is directed and may contain cycles and repeated characters
A node cannot be reused within the same matched path

Examples

Input: ([('C', [1]), ('A', [2]), ('T', [])], 'CAT')

Expected Output: True

Explanation: Starting at node 0 gives the path 0 -> 1 -> 2, which spells C-A-T.

Input: ([('X', [1]), ('A', [2]), ('B', []), ('A', [4]), ('B', [])], 'AB')

Expected Output: True

Explanation: The target can start from any node. For example, node 1 -> node 2 spells A-B.

Input: ([('A', [1]), ('B', [2]), ('A', [0, 3]), ('C', [])], 'ABAC')

Expected Output: True

Explanation: A valid path is 0 -> 1 -> 2 -> 3, which spells A-B-A-C. The graph contains a cycle, but the path does not reuse nodes.

Input: ([('A', [0])], 'AA')

Expected Output: False

Explanation: Even though there is a self-loop, the same node cannot be reused in one attempted match.

Input: ([], '')

Expected Output: True

Explanation: The empty string is considered matched trivially.

Input: ([('A', [1]), ('B', []), ('A', [])], 'BA')

Expected Output: False

Explanation: You can start at node 1 for 'B', but it has no outgoing edge to any 'A' node, so no valid path exists.

Hints

Try starting a DFS/backtracking search from every node whose character matches the first character of the target.
Use a visited set or array for the current path so cycles do not cause infinite loops and the same node is not reused.

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.