How should I practice Streaming Step Progress Hierarchy?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The Allen Institute for AI phone screen problems in FastPrep.

Is Streaming Step Progress Hierarchy associated with The Allen Institute for AI?

FastPrep tags this as a The Allen Institute for AI phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Streaming Step Progress Hierarchy

Learn this problem

● Medium

The Allen Institute for AIFULLTIMEPHONE SCREEN

Problem statement

Process an ordered batch of step-progress event arrivals. Each row in events has five strings:

[timestamp, stepId, parentId, runState, text]

timestamp is a non-negative decimal integer.
stepId identifies the step.
An empty parentId declares a root; otherwise it names the intended parent step.
runState and text are the current values for that step.

Maintain only the latest event for each stepId. A greater timestamp replaces the current event. A smaller timestamp is stale and ignored. At an equal timestamp, the later arrival replaces the earlier arrival.

Return one hierarchy snapshot after every arrival. A step whose non-empty parent is not currently known is a temporary root. As soon as that parent appears, the step attaches beneath it. A newer event may change a step's parent, state, or text.

Snapshot Encoding

Each snapshot is a string array containing every current step exactly once in preorder. Roots and siblings are sorted lexicographically by stepId. Encode a node as:

depth:stepId:parentId:runState:text

depth is 0 for each current root and increases by one down each attached edge. A temporary root keeps its missing parentId in the encoded token even though its depth is 0.

Function

buildProgressSnapshots(events: String[][]) → String[][]

Examples

Example 1

events = [["2","child","root","RUNNING","fetch"],["1","root","","RUNNING","job"],["3","child","root","DONE","fetched"]]return = [["0:child:root:RUNNING:fetch"],["0:root::RUNNING:job","1:child:root:RUNNING:fetch"],["0:root::RUNNING:job","1:child:root:DONE:fetched"]]

The child first appears as a temporary root. When root arrives, the child attaches beneath it without needing another child event. The final event updates the child's state and text.

Example 2

events = [["5","b","","RUNNING","new"],["3","b","","FAILED","stale"],["5","b","","DONE","tie-wins"],["1","a","","DONE","first"]]return = [["0:b::RUNNING:new"],["0:b::RUNNING:new"],["0:b::DONE:tie-wins"],["0:a::DONE:first","0:b::DONE:tie-wins"]]

The timestamp-3 event is ignored as stale. The later arrival at timestamp 5 wins the tie. Once step a arrives, lexicographic root ordering places it before b.

Example 3

events = [["1","a","","RUNNING","A"],["1","b","a","RUNNING","B"],["2","b","missing","DONE","moved"],["1","missing","","RUNNING","M"]]return = [["0:a::RUNNING:A"],["0:a::RUNNING:A","1:b:a:RUNNING:B"],["0:a::RUNNING:A","0:b:missing:DONE:moved"],["0:a::RUNNING:A","0:missing::RUNNING:M","1:b:missing:DONE:moved"]]

Step b first belongs under a, then its newer event reparents it to an absent step, making it a temporary root. When missing arrives, b attaches beneath it.

Constraints

1 <= events.length <= 200.
Every event row contains exactly five strings in the documented order.
Each timestamp is a decimal integer from 0 through 10^15.
1 <= stepId.length <= 40, and each stepId contains only ASCII letters, digits, underscores, or hyphens.
parentId is empty or a valid step identifier distinct from stepId.
1 <= runState.length, text.length <= 80, and these fields contain only ASCII letters, digits, spaces, underscores, periods, or hyphens.
After applying the latest event for every current step, existing parent links never form a cycle.