How should I practice JSON Path Lookup with Implicit Array Wildcards?

Start by reading the full statement, solve the visible examples, then compare the pattern against related MongoDB onsite interview problems in FastPrep.

Is JSON Path Lookup with Implicit Array Wildcards associated with MongoDB?

FastPrep tags this as a MongoDB onsite interview coding practice problem when the problem catalog has that company and stage context.

JSON Path Lookup with Implicit Array Wildcards

MongoDB● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Source note: The interviewer gave a JSON syntax tree and a path and asked for the value at that path. The author wrote: "One case is special: at an array, if there is no index, it defaults to *, and then every match after it is returned." The path was already a vector of strings, and key order inside an object did not matter. The interviewer also asked for tests on hard-coded trees, with no parser.

The report does not say how the tree is passed in, what an index looks like, or what to return. Here, the tree is a list of tagged nodes, a step is a key or an index, an index at an object or past the end of an array matches nothing, and you return the ids of the matching nodes in array order. The report is vague about what happens to the step after a missing index. Here, that step is kept and used on every element of the array, including elements that are arrays themselves. The follow-ups are described but not judged.

The judged task matches the report at about 80%.

A JSON document is stored as a tree of tagged nodes. Node i is described by nodes[i], and node 0 is the root.

["object", key1, child1, key2, child2, ...] is a JSON object. Each key is followed by the id of the node it maps to. An object can be empty.
["array", child1, child2, ...] is a JSON array. Its elements are the listed nodes, in order. An array can be empty.
["value", text] is a plain value, such as a string or a number.

Child ids are written as decimal strings.

You are also given a path, which is a list of steps. Start at the root and follow the steps in order. At each node, the next step works like this:

At an object, move to the node for the key named by the step. If the object has no such key, this route matches nothing.
At an array, if the step is an index, move to the element at that index. An index past the end matches nothing.
At an array, if the step is a key, the path gave no index for this array, so the array stands for all of its elements. Use the same step on every element, in order. An element that is itself an array is handled the same way.
At a value, the route stops and matches nothing.

Every node reached after the last step is a match, even an object or an array. Return the ids of all matches. When the routes split at an array, list every match reached through an earlier element before any match reached through a later element.

Interviewer Follow-ups

The candidate stored a node as a tagged struct. Asked whether there were other ways to model it, the candidate named a union or a class hierarchy with virtual methods.
Write tests on trees built by hand in code, with no JSON parser, including a check that compares a simple string result.

These follow-ups are for discussion. The tests check only the returned ids.

Function

findPathMatches(nodes: String[][], path: String[]) → int[]

Examples

Example 1

nodes = [["object","users","1","count","9"],["array","2","7"],["object","name","3","tags","4"],["value","ada"],["array","5","6"],["value","x"],["value","y"],["object","name","8"],["value","lin"],["value","2"]]path = ["users","name"]return = [3,8]

Node 0 is the root object. Its key users leads to the array at node 1. The step name is not an index, so it is used on every element of that array: node 2 gives node 3 (ada) and node 7 gives node 8 (lin).

Example 2

nodes = [["object","users","1","count","9"],["array","2","7"],["object","name","3","tags","4"],["value","ada"],["array","5","6"],["value","x"],["value","y"],["object","name","8"],["value","lin"],["value","2"]]path = ["users","1","name"]return = [8]

This time the array is followed by the index 1, so only its second element, node 7, is used. Its key name leads to node 8.

Example 3

nodes = [["object","users","1","count","9"],["array","2","7"],["object","name","3","tags","4"],["value","ada"],["array","5","6"],["value","x"],["value","y"],["object","name","8"],["value","lin"],["value","2"]]path = ["users","tags"]return = [4]

Only the first user has tags, so the only match is node 4. The path ends there, so the whole array is returned as one match. Its elements, nodes 5 and 6, are not returned on their own.

Constraints

1 <= nodes.length <= 1000
1 <= path.length <= 20
The rows form one tree with node 0 as the root. Every other node is the child of exactly one node, and a child's id is always larger than its parent's id.
Keys are 1 to 10 lowercase English letters, and the keys inside one object are all different. Value text is 1 to 10 lowercase letters or digits.
Every path step is either a key, made of 1 to 10 lowercase English letters, or an index, a whole number from 0 to 999 with no leading zeros.