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.

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.

Hints

  1. First collect every block's id into a hash set so you can test 'does this parent exist?' in O(1).
  2. A block is a root when parentId is null OR parentId is not in that set — handle the dangling-reference case explicitly.
  3. 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].

Hints

  1. Build a map id -> effective parent, normalizing both null and dangling parents to 'no parent' (None).
  2. Walk upward from the target collecting ids until you hit a node with no parent, then reverse the collected list.
  3. 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.

Loading coding console...