Salesforce: Flatten Nested Objects and Lists into Full Leaf Paths

Flatten Nested Objects and Lists into Full Leaf Paths

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Flatten a nested object into rows containing the full path to each string leaf and its value. Every parent key must appear in the path. Extend the traversal to handle lists as well as nested objects. ### Function Signature `flatten_paths(data: dict) -> list[list[str]]` ### Input and Path Rules - The root is an object. Each value is a string leaf, another object, or a list of values of these same kinds. - Object keys contain only lowercase ASCII letters and underscores and are nonempty. - Join nested object keys with a dot: key `b` under key `a` has path `a.b`. - Represent a list index with brackets appended to the current path: index zero under `a` is `a[0]`. - A key inside an object at a list position follows a dot, such as `a[0].b`. - Empty objects and empty lists produce no output rows. An empty string is a leaf and must be output. These path and empty-container rules are explicit exercise conventions. Use an iterative traversal with a stack rather than recursive function calls. ### Output Return one `[path, value]` row for every string leaf, sorted by the path in ascending ASCII lexicographic order. Sorting is lexicographic, so an index text `[10]` sorts before `[2]` when their preceding path is identical. ### Constraints - There are at most 100000 total object entries and list elements. - Nesting depth is at most 200. - Keys have at most 40 characters and string values at most 1000 characters. - Total input text and total output text are each at most 1000000 characters. - Objects have no duplicate keys; strings are the only scalar values. ### Examples Input: `data = {"a":{"b":"value"},"tags":["red",{"name":"blue"}],"empty":[]}` Output: `[["a.b","value"],["tags[0]","red"],["tags[1].name","blue"]]` Input: `data = {"a":[[],["x"]],"b":""}` Output: `[["a[1][0]","x"],["b",""]]` Input: `data = {}` Output: `[]`

Overview: Traverse nested maps and lists with a stack, include every parent key and list index, and return deterministically ordered paths to string leaves.

Flatten a nested object into rows containing the full path to each string leaf and its value. Every parent key must appear in the path. Extend the traversal to handle lists as well as nested objects.

Function Signature

flatten_paths(data: dict) -> list[list[str]]

Input and Path Rules

The root is an object. Each value is a string leaf, another object, or a list of values of these same kinds.
Object keys contain only lowercase ASCII letters and underscores and are nonempty.
Join nested object keys with a dot: key b under key a has path a.b .
Represent a list index with brackets appended to the current path: index zero under a is a[0] .
A key inside an object at a list position follows a dot, such as a[0].b .
Empty objects and empty lists produce no output rows. An empty string is a leaf and must be output.

These path and empty-container rules are explicit exercise conventions. Use an iterative traversal with a stack rather than recursive function calls.

Output

Return one [path, value] row for every string leaf, sorted by the path in ascending ASCII lexicographic order. Sorting is lexicographic, so an index text [10] sorts before [2] when their preceding path is identical.

Constraints

There are at most 100000 total object entries and list elements.
Nesting depth is at most 200.
Keys have at most 40 characters and string values at most 1000 characters.
Total input text and total output text are each at most 1000000 characters.
Objects have no duplicate keys; strings are the only scalar values.

Examples

Input: data = {"a":{"b":"value"},"tags":["red",{"name":"blue"}],"empty":[]}

Output: [["a.b","value"],["tags[0]","red"],["tags[1].name","blue"]]

Input: data = {"a":[[],["x"]],"b":""}

Output: [["a[1][0]","x"],["b",""]]

Input: data = {}

Output: []