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 Technical Screen rounds at ZipHQ.

What role is this question designed for?

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

Find root IDs and paths | ZipHQ Coding Question

Find root IDs and paths

Company: ZipHQ

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a collection of string blocks, each represented as a JSON object with fields {"id": string, "parentId": string | null}. A block is a root if it has no parent (parentId is null or the referenced parent does not appear). 1) Write a function that returns all root ids from the input. 2) Follow-up: given a target id, return the path of ids from its root to that id. Explain your approach, the data structures you use, and analyze time and space complexity.

Quick Answer: This question evaluates understanding of graph/tree relationships, identification of root nodes, and path reconstruction from parent references, assessing algorithmic reasoning and data-structure familiarity.

Find Root IDs

You are given a collection of blocks, each an object with fields `id` (string) and `parentId` (string or null). A block is a **root** if it has no parent — that is, its `parentId` is null, OR the `parentId` references an id that does not appear anywhere in the input. Return the list of all root ids, in the order the blocks are given. **Example** ``` blocks = [ {"id": "a", "parentId": null}, {"id": "b", "parentId": "a"}, {"id": "c", "parentId": "b"} ] => ["a"] ``` `a` has no parent, so it is a root. `b` and `c` both chain up to `a`, so they are not roots. A block whose `parentId` points to an id that is not present (a dangling reference) is also a root.

Constraints

0 <= number of blocks <= 10^5
Each id is a non-empty string and ids are unique.
parentId is either null or a string (which may or may not match an existing id).
Return roots in the order their blocks appear in the input.

Examples

Input: ([{"id": "a", "parentId": None}, {"id": "b", "parentId": "a"}, {"id": "c", "parentId": "b"}],)

Expected Output: ['a']

Explanation: Only 'a' has no parent; 'b' and 'c' chain up to it.

Input: ([{"id": "a", "parentId": None}, {"id": "b", "parentId": None}, {"id": "c", "parentId": "a"}, {"id": "d", "parentId": "b"}],)

Expected Output: ['a', 'b']

Explanation: Two separate trees, so two roots, returned in input order.

Input: ([{"id": "x", "parentId": "missing"}, {"id": "y", "parentId": "x"}],)

Expected Output: ['x']

Explanation: 'x' references a parent 'missing' that does not appear in the input, so 'x' is a root (dangling reference).

Input: ([],)

Expected Output: []

Explanation: Empty input yields no roots.

Input: ([{"id": "solo", "parentId": None}],)

Expected Output: ['solo']

Explanation: A single block with null parent is a root.

Input: ([{"id": "a", "parentId": "ghost"}, {"id": "b", "parentId": None}, {"id": "c", "parentId": "a"}, {"id": "d", "parentId": "zzz"}],)

Expected Output: ['a', 'b', 'd']

Explanation: 'a' (dangling 'ghost'), 'b' (null), and 'd' (dangling 'zzz') are all roots; 'c' chains to 'a'.

Hints

First collect every block's id into a hash set so you can test 'does this parent exist?' in O(1).
A block is a root when parentId is null OR parentId is not in that set — handle the dangling-reference case explicitly.
Preserve input order by iterating the blocks a second time rather than iterating the set.

Path From Root To Target

Using the same block structure — each block has an `id` (string) and a `parentId` (string or null), where a missing/dangling `parentId` means the block is a root — implement the follow-up: Given a `targetId`, return the path of ids from the target's **root** down to the target, inclusive. **Example** ``` blocks = [ {"id": "a", "parentId": null}, {"id": "b", "parentId": "a"}, {"id": "c", "parentId": "b"} ] targetId = "c" => ["a", "b", "c"] ``` Walk upward from the target following `parentId` links until you reach a root (null parent or a dangling parent reference), collecting ids, then reverse so the result reads root → target. If `targetId` is not present in the input, return an empty list.

Constraints

0 <= number of blocks <= 10^5
ids are unique, non-empty strings.
parentId is null or a string; a dangling parentId marks a root.
If targetId is not one of the block ids, return an empty list.
The path is returned root-first, target-last.

Examples

Input: ([{"id": "a", "parentId": None}, {"id": "b", "parentId": "a"}, {"id": "c", "parentId": "b"}], "c")

Expected Output: ['a', 'b', 'c']

Explanation: Walk c -> b -> a, then reverse to root-first order.

Input: ([{"id": "a", "parentId": None}, {"id": "b", "parentId": "a"}, {"id": "c", "parentId": "b"}], "a")

Expected Output: ['a']

Explanation: The target is itself a root, so the path is just [a].

Input: ([{"id": "x", "parentId": "missing"}, {"id": "y", "parentId": "x"}, {"id": "z", "parentId": "y"}], "z")

Expected Output: ['x', 'y', 'z']

Explanation: 'x' has a dangling parent so it is the root; path is x -> y -> z.

Input: ([{"id": "a", "parentId": None}, {"id": "b", "parentId": "a"}], "missing")

Expected Output: []

Explanation: The target id is not present in the input, so return an empty list.

Input: ([{"id": "solo", "parentId": None}], "solo")

Expected Output: ['solo']

Explanation: Single-node tree where the target is the root.

Input: ([{"id": "r", "parentId": None}, {"id": "a", "parentId": "r"}, {"id": "b", "parentId": "a"}, {"id": "c", "parentId": "b"}, {"id": "d", "parentId": "c"}], "d")

Expected Output: ['r', 'a', 'b', 'c', 'd']

Explanation: A deep chain r->a->b->c->d returned root-first.

Hints

Build a map id -> effective parent, normalizing both null and dangling parents to 'no parent' (None).
Walk upward from the target collecting ids until you hit a node with no parent, then reverse the collected list.
Guard against cycles with a visited set so a malformed input can't loop forever; also return [] up front when the target isn't present.

Quick Overview

This question evaluates understanding of graph/tree relationships, identification of root nodes, and path reconstruction from parent references, assessing algorithmic reasoning and data-structure familiarity.