How should I practice Top-Scoring Items in a Time Window?

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

Is Top-Scoring Items in a Time Window associated with Pinterest?

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

Top-Scoring Items in a Time Window

Pinterest● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Maintain scored items that a user has viewed within a configurable time window. Process a finite ordered batch of operations and return one item ID for each TOP operation.

ADD time id score adds a newly viewed item with a fixed integer score.
EXPIRE time removes expired items and produces no output.
TOP time returns the active item with greatest score, or the empty string if none exists. Equal scores choose the item inserted earliest in the operation sequence.

Times are nondecreasing across all operations. Before every operation, remove items viewed at a time less than or equal to time - window; active items are those in (time - window, time]. Thus TOP expires items automatically. Item IDs are globally unique in the batch, and scores do not change after insertion. Operations at equal times still follow input order.

For this practice contract, the configurable time range takes precedence over an illustrative recent-item count. Discuss the complexity of adding an item, expiring items, and retrieving the top item.

Function

trackTopItems(window: int, operations: String[]) → String[]

Examples

Example 1

window = 10operations = ["ADD 0 a 5","ADD 3 b 9","TOP 3","ADD 5 c 9","TOP 5","EXPIRE 13","TOP 13","TOP 15"]return = ["b","b","c",""]

Equal scores prefer the earlier insertion b. At time 13, b expires exactly at the boundary, leaving c. At time 15 all entries are expired.

Example 2

window = 604800operations = ["ADD 0 981292206280418755 50","ADD 0 981292206280418756 35","ADD 0 981292206280418757 91","ADD 0 981292206280418758 92","ADD 0 981292206280418759 3","ADD 0 981292206280418760 88","ADD 0 981292206280418761 34","ADD 0 981292206280418762 9","ADD 0 981292206280418763 77","ADD 0 981292206280418764 55","TOP 0"]return = ["981292206280418758"]

All ten scored items are active at time zero; the original scored-item example selects the item with score 92.

Example 3

window = 5operations = ["TOP 0","ADD 0 x 7","TOP 4","TOP 5"]return = ["","x",""]

TOP expires entries automatically; an entry at time 0 is absent when now is 5.

Constraints

1 <= window <= 10^9.
0 <= operations.length <= 20000.
0 <= time <= 10^9; times are nondecreasing.
-10^9 <= score <= 10^9.
IDs contain 1 to 32 ASCII letters or digits, have no spaces, and are unique across ADD operations.
Operations have exactly the stated format with single spaces and valid fields.