FastPrepUnique Active Pins by Time Segment

Unique Active Pins by Time Segment

Pinterest logoPinterest● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

You are given interaction logs in an integer matrix logs. Each row [pinId, startTime, endTime] means that one user interaction keeps pinId active throughout the half-open interval [startTime, endTime).

Return the number of distinct active pins for every event-defined time segment. Let t0 < t1 < ... < tm be all distinct start and end timestamps. For every adjacent pair, return one row [ti, ti+1, count], where count is the number of distinct pin IDs active throughout [ti, ti+1).

  • Include segments whose count is zero.
  • Do not merge adjacent segments, even when their counts are equal.
  • Several logs for the same pin may overlap. That pin contributes only one to the distinct count while at least one of its intervals is active.

Function

uniqueActivePinTimeline(logs: int[][]) → int[][]

Examples

Example 1

logs = [[1,0,3],[2,1,2]]return = [[0,1,1],[1,2,2],[2,3,1]]

Pin 1 is active for the entire range. Pin 2 raises the distinct count only on [1,2).

Example 2

logs = [[7,0,4],[7,2,6],[8,3,5]]return = [[0,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,1]]

The two overlapping interactions for pin 7 still count as one distinct pin. Pin 8 makes the count two on [3,5).

Example 3

logs = [[1,0,1],[2,3,4]]return = [[0,1,1],[1,3,0],[3,4,1]]

No pin is active in the event-defined gap [1,3), so that segment is retained with count 0.

Constraints

  • 1 <= logs.length <= 200000.
  • Each row contains exactly three integers [pinId, startTime, endTime].
  • 1 <= pinId <= 10^9.
  • -10^9 <= startTime < endTime <= 10^9.

More Pinterest problems

See Pinterest hiring insights
public int[][] uniqueActivePinTimeline(int[][] logs) {
    // write your code here
}
logs[[1,0,3],[2,1,2]]
expected[[0,1,1],[1,2,2],[2,3,1]]
Checking account…