Katkat
Back

Find root IDs and paths

ZipHQSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.