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.

Solve graph and linked list tasks | Google Coding Question

Quick Overview

This question evaluates competencies in dependency graph modeling and reachability, shortest-path computation in weighted directed graphs, and space-efficient linked-list traversal, testing understanding of graph theory, pathfinding algorithms, and pointer-based data structure techniques.

Solve graph and linked list tasks

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given three independent coding tasks. ## 1) Determine which items can be produced (dependency graph) You have: - `recipes`: a list of `n` item names. - `ingredients[i]`: a list of names required to produce `recipes[i]`. - `supplies`: a list of names you already have available in unlimited quantity. Any ingredient name may refer either to a basic supply or to another recipe. You may produce a recipe only if **all** of its required ingredients are currently available (either from the initial `supplies` or from recipes you have already produced). **Task:** Return all recipes that can eventually be produced. **Notes/constraints:** - Recipe/ingredient names are strings. - Cycles may exist (e.g., A depends on B and B depends on A). - `n` can be large; assume the total number of ingredient references across all recipes can be up to ~2e5. ## 2) Signal propagation time in a weighted directed graph You are given a directed graph with positive edge weights: - `n` nodes labeled `1..n` - `edges`: a list of triples `(u, v, w)` meaning an edge from `u` to `v` with travel time `w > 0` - a starting node `k` A signal starts at node `k` at time `0` and travels along directed edges, accumulating time. **Task:** Compute the time when **all** nodes have received the signal (i.e., the maximum of the shortest-path times from `k` to every node). If some node is unreachable, return `-1`. **Notes/constraints:** - `n` up to ~1e5, `|edges|` up to ~2e5. - Weights are positive integers. ## 3) Check whether a singly linked list has odd or even length You are given the head of a singly linked list. **Task:** Determine whether the list length is **odd** or **even** using `O(1)` extra space and without explicitly computing the length with a counter. **Output:** Return something like `"odd"` / `"even"` (or a boolean), as long as the meaning is clear. **Notes/constraints:** - Empty list should be handled (define it as even length `0`).

Quick Answer: This question evaluates competencies in dependency graph modeling and reachability, shortest-path computation in weighted directed graphs, and space-efficient linked-list traversal, testing understanding of graph theory, pathfinding algorithms, and pointer-based data structure techniques.

Part 1: Find All Recipes That Can Be Produced

You are given a list of recipe names, the ingredient list for each recipe, and a list of supplies that are already available. An ingredient can be either a basic supply or another recipe. A recipe becomes available only when all of its required ingredient names are available. Once a recipe is produced, it can be used as an ingredient for other recipes. Return every recipe that can eventually be produced. To make the result deterministic, return them in the same order as they appear in recipes. Cycles may exist, so some recipes may never become available.

Constraints

0 <= len(recipes) == len(ingredients) <= 10^5
Recipes are distinct strings.
0 <= total number of ingredient references across all recipes <= 2 * 10^5
0 <= len(supplies) <= 10^5
Ingredient names and recipe names are strings.
Cycles may exist in the dependency graph.

Examples

Input: (['bread', 'sandwich', 'burger'], [['yeast', 'flour'], ['bread', 'meat'], ['sandwich', 'bread']], ['yeast', 'flour', 'meat'])

Expected Output: ['bread', 'sandwich', 'burger']

Explanation: bread can be made first, then sandwich using bread and meat, then burger using sandwich and bread.

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

Expected Output: []

Explanation: A and B form a cycle, so neither can be produced.

Input: (['tea', 'milktea', 'juice'], [[], ['tea', 'milk'], ['fruit']], ['milk'])

Expected Output: ['tea', 'milktea']

Explanation: tea needs no ingredients, so it is immediately producible. Then milktea can be made from tea and milk. juice cannot be made.

Input: (['omelet'], [['egg', 'pan']], ['egg'])

Expected Output: []

Explanation: pan is never available, so omelet cannot be produced.

Input: ([], [], ['salt'])

Expected Output: []

Explanation: There are no recipes to produce.

Hints

Think of each available name as unlocking the recipes that depend on it.
Track how many required names are still missing for each recipe. When that count becomes 0, the recipe itself becomes available.

Part 2: Signal Propagation Time in a Directed Weighted Graph

You are given a directed graph with positive edge weights. A signal starts from node k at time 0 and travels along outgoing edges. The time to traverse an edge is its weight. Compute the earliest time by which all nodes have received the signal. This is the maximum among the shortest-path times from k to every node. If at least one node is unreachable, return -1.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
1 <= u, v <= n for every edge (u, v, w)
1 <= w <= 10^9
All edge weights are positive integers.
Multiple edges between the same pair of nodes may exist.

Examples

Input: (4, [(2, 1, 1), (2, 3, 1), (3, 4, 1)], 2)

Expected Output: 2

Explanation: From node 2, the shortest times are 1 to node 1, 1 to node 3, and 2 to node 4, so the last node receives the signal at time 2.

Input: (2, [(1, 2, 1)], 2)

Expected Output: -1

Explanation: Starting from node 2, node 1 is unreachable.

Input: (1, [], 1)

Expected Output: 0

Explanation: The only node is the start node, so all nodes have the signal at time 0.

Input: (3, [(1, 2, 10), (1, 2, 3), (2, 3, 4), (1, 3, 20)], 1)

Expected Output: 7

Explanation: The best path to node 2 uses weight 3, and then node 3 is reached in 3 + 4 = 7.

Hints

Because all weights are positive, use a shortest-path algorithm that works well with a priority queue.
Once you know the shortest distance to every node from k, the answer is the largest of those distances, unless some distance was never updated.

Part 3: Determine Whether a Singly Linked List Has Odd or Even Length

Given the head of a singly linked list, determine whether the list length is odd or even. You must use O(1) extra space and should not explicitly compute the length with a counter. For testing in this problem, the linked list is represented as nested Python dictionaries of the form {'val': value, 'next': next_node}, or None for an empty list. Return 'odd' for odd length and 'even' for even length. By definition, the empty list has even length 0.

Constraints

The list may be empty.
The list may contain up to 10^5 nodes.
Use O(1) extra space.
Do not compute the full length with a counter.

Examples

Input: (None,)

Expected Output: 'even'

Explanation: An empty list has length 0, which is even.

Input: ({'val': 7, 'next': None},)

Expected Output: 'odd'

Explanation: A single-node list has odd length.

Input: ({'val': 1, 'next': {'val': 2, 'next': None}},)

Expected Output: 'even'

Explanation: Two nodes give an even length.

Input: ({'val': 1, 'next': {'val': 2, 'next': {'val': 3, 'next': {'val': 4, 'next': {'val': 5, 'next': None}}}}},)

Expected Output: 'odd'

Explanation: This list has 5 nodes, so its length is odd.

Hints

Try advancing through the list two nodes at a time instead of one.
If that pointer falls off the list exactly, the length is even. If it stops on the last node, the length is odd.

Quick Overview