How should I practice Detect Duplicate Trace IDs in a Linked List?

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

Is Detect Duplicate Trace IDs in a Linked List associated with Google?

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

Detect Duplicate Trace IDs in a Linked List

Google● MediumINTERNONSITE INTERVIEW

Learn

Problem statement

You are given a finite acyclic singly linked list through three parallel inputs:

traceIds[i] is the case-sensitive trace ID stored at node i.
next[i] is the index of node i's successor, or -1 when i is the tail.
head is the first node index, or -1 for an empty list.

Return true if two different reachable nodes have exactly the same trace ID. Otherwise, return false.

Do not modify traceIds or next. Your final solution must use O(1) auxiliary space; O(n^2) time is acceptable.

Function

hasDuplicateTraceId(traceIds: String[], next: int[], head: int) → boolean

Examples

Example 1

traceIds = ["ingest","index","ingest"]next = [1,2,-1]head = 0return = true

Nodes 0 and 2 both store ingest.

Example 2

traceIds = ["root","api","db"]next = [2,-1,1]head = 0return = false

The traversal order is root -> db -> api, and every trace ID is distinct.

Example 3

traceIds = ["Trace-1","trace-1"]next = [1,-1]head = 0return = false

Trace ID comparison is case-sensitive, so the two values are different.

Constraints

0 <= traceIds.length = next.length <= 2000.
When the arrays are empty, head == -1. Otherwise, 0 <= head < traceIds.length.
Every next[i] is -1 or a valid node index.
Following next from head visits every represented node exactly once and ends at -1.
Each trace ID contains between 1 and 32 case-sensitive printable ASCII characters.
Do not use a map, set, or another auxiliary collection whose size grows with the list.