How should I practice Linked Perception History?

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

Is Linked Perception History associated with Waymo?

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

Linked Perception History

Waymo● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Two perception systems, L and R, use different identifiers for the same tracked object. Process a finite sequence of operations and answer history queries across both systems.

Each operation is a pipe-delimited string in one of these forms:

LINK|leftId|rightId permanently links one L identifier with one R identifier.
OBSERVE|L|id|timestamp|payload or OBSERVE|R|id|timestamp|payload appends an observation to that identifier's history.
QUERY|L|id or QUERY|R|id requests the complete history for the linked object.

For each query, combine observations recorded under both linked identifiers and sort them by increasing timestamp. Preserve operation order between observations with the same timestamp. Encode each observation as timestamp,system,id,payload and join consecutive observations with a semicolon. Return one encoded string per query in query order; return the empty string for a linked object with no observations.

Function

linkedPerceptionHistory(operations: String[]) → String[]

Examples

Example 1

operations = ["LINK|camera-1|lidar-9","OBSERVE|L|camera-1|20|far","OBSERVE|R|lidar-9|10|near","QUERY|L|camera-1","OBSERVE|L|camera-1|15|mid","QUERY|R|lidar-9"]return = ["10,R,lidar-9,near;20,L,camera-1,far","10,R,lidar-9,near;15,L,camera-1,mid;20,L,camera-1,far"]

Both identifier forms resolve to the same linked object. The first query sees two observations; the second also includes the later-added observation with timestamp 15.

Example 2

operations = ["LINK|a|b","OBSERVE|L|a|5|first","OBSERVE|R|b|5|second","QUERY|R|b"]return = ["5,L,a,first;5,R,b,second"]

The timestamps tie, so the observations remain in their original operation order.

Example 3

operations = ["OBSERVE|R|b|2|rb","LINK|a|b","LINK|c|d","OBSERVE|L|c|1|lc","QUERY|L|a","QUERY|R|d"]return = ["2,R,b,rb","1,L,c,lc"]

An observation may precede its link operation, and histories from different linked objects remain isolated.

Constraints

1 <= operations.length <= 100000.
Every identifier belongs to at most one permanent cross-system link, and every query names an identifier in a linked pair.
An observation names an identifier that appears in exactly one link, although it may occur before or after that LINK operation in the input sequence.
0 <= timestamp <= 10^9.
Identifiers and payloads contain only lowercase English letters, digits, hyphens, and underscores, and are non-empty.