How should I practice Read-Optimized Duplicate Windows?

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

Is Read-Optimized Duplicate Windows associated with Google?

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

Read-Optimized Duplicate Windows

Google● MediumFULLTIMEPHONE SCREENONSITE INTERVIEW

Problem statement

You are given an integer array nums and a fixed window length k. Maintain an index that answers whether any requested contiguous window of length k contains equal values at two different positions.

Process operations in order. Every row contains three integers:

[0, index, value] replaces nums[index] with value.
[1, start, ignored] queries the window from start through start + k - 1, inclusive. Append 1 if that window contains a duplicate value, or 0 otherwise. The third integer is ignored.

Return the query results in encounter order. Updates produce no output. Every query sees all preceding updates and no later ones. The array length and k never change.

Optimize for a read-heavy workload: target O(1) work per query, O(n) work per update, and O(n) index space, where n = nums.length. Hash-table counting gives expected linear update time. Output storage is separate from index space.

Function

duplicateWindowQueries(nums: int[], k: int, operations: int[][]) → int[]

Examples

Example 1

nums = [1,2,1,3]k = 3operations = [[1,0,0],[1,1,0],[0,2,2],[1,0,0],[1,1,0],[0,1,4],[1,0,0]]return = [1,0,1,1,0]

Initially [1,2,1] contains a duplicate, but [2,1,3] does not. Replacing index 2 with 2 makes both windows contain duplicate twos. Replacing index 1 with 4 makes the first window [1,4,2], which is distinct.

Example 2

nums = [4,5,6]k = 3operations = [[1,0,9],[0,2,4],[1,0,-8],[0,0,9],[1,0,7]]return = [0,1,0]

There is one full-array window. Its values change from [4,5,6] to [4,5,4] and then [9,5,4]. The third field of each query has no effect.

Constraints

1 <= nums.length <= 1000
1 <= k <= nums.length
0 <= operations.length <= 300, and each row has exactly three integers.
Initial and replacement values are between -1000000 and 1000000.
Update indices satisfy 0 <= index < n; query starts satisfy 0 <= start <= n-k.
The ignored query field is any integer between -1000000 and 1000000.