Outline from Flat Parent Records
Updated
Problem statement
A web app stores a hierarchy, such as folders or teams, as a flat list. Each record is [id, parentId]: an item's id and the id of the item it sits under. A parentId of -1 means the item is at the top level. Records can come in any order, so a child may appear before its parent.
Build the hierarchy and return it as an outline: a list of rows [id, depth]. Top-level items have depth 0, the items under them depth 1, and so on. Each item is followed right away by all the items under it, before the next item at its own level.
Follow these rules:
- Items with the same parent appear in the same order as their records in the input. Top-level items follow the same rule.
- If a
parentIdmatches no record's id, treat that item as top level. - If following parent links up from an item never reaches a top-level item, because the links go around in a loop, leave that item out. This leaves out every item under it as well.
Function
buildOutline(records: int[][]) → int[][]Examples
Example 1
records = [[4,-1],[7,4],[2,4],[9,7],[5,-1],[3,2]]return = [[4,0],[7,1],[9,2],[2,1],[3,2],[5,0]]4 and 5 are top level, in that order. Under 4 come 7 and then 2, in input order. 9 sits under 7 and 3 sits under 2. So the outline is 4, then 7 with 9 under it, then 2 with 3 under it, then 5.
Example 2
records = [[10,30],[20,-1],[30,20],[40,99]]return = [[20,0],[30,1],[10,2],[40,0]]10 appears before its parent 30, which is fine. No record has id 99, so 40 is treated as top level. The top-level items in input order are 20 and 40. The chain is 20, then 30 at depth 1, then 10 at depth 2.
Example 3
records = [[1,-1],[2,3],[3,2],[4,2],[5,1]]return = [[1,0],[5,1]]2 and 3 point to each other, so they never reach a top-level item and are left out. 4 sits under 2, so it is left out too. Only 1 and its child 5 remain.
Constraints
1 <= records.length <= 1000records[i] = [id, parentId]1 <= id <= 10000, and all ids are different.parentId == -1or1 <= parentId <= 10000. AparentIdmay match no record, and may even equal the item's own id.
More Rippling Onsite Interview questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Delivery Cost TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Maximum Currency Conversion Along a Simple PathPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Top K Frequent WordsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Future-Effective Employee SalaryONSITE INTERVIEW · Seen Aug 2026
- Filter and Sort Scheduled TasksONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Merge N-Ary Trees by KeyLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
- Render an Org Chart and Find Skip-Level PairsSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Render a Comment HierarchyAmazon · ONSITE INTERVIEW
- Topmost Accessible NodesFigma · PHONE SCREEN · ONSITE INTERVIEWFigma interview questions
- Top View of a Binary TreeInMobi · ONSITE INTERVIEWInMobi interview questions
- Total Balance of an Account and Its Sub-AccountsCapital One · ONSITE INTERVIEWCapital One interview questions