FastPrepSum Two Piecewise-Constant Time Series

Sum Two Piecewise-Constant Time Series

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Each time series is a sorted array of pairs [time, value]. A pair changes the series to value at time, and that value remains active until the next pair. Before its first event, a series has value 0.

Return the pointwise sum of first and second in the same format. Emit the earliest time from either input, then emit a pair only when the summed value changes. If both inputs change at the same time, apply both changes before emitting that time.

Both inputs use strictly increasing integer times. Either input may be empty.

Function

sumTimeSeries(first: int[][], second: int[][]) → int[][]

Examples

Example 1

first = [[0,0],[2,1],[8,0]]second = [[0,0],[1,3],[5,2]]return = [[0,0],[1,3],[2,4],[5,3],[8,2]]

The union of change times is 0,1,2,5,8; summing the active values gives the shown series.

Example 2

first = [[1,2],[8,10],[15,0]]second = [[3,5],[10,4],[12,0]]return = [[1,2],[3,7],[8,15],[10,14],[12,10],[15,0]]

Each output event occurs when either input changes.

Example 3

first = []second = [[4,7]]return = [[4,7]]

An empty series contributes zero everywhere.

Constraints

  • 0 <= first.length, second.length <= 100000.
  • Each row contains exactly two integers [time,value].
  • Times are strictly increasing within each input and lie in [-10^9,10^9].
  • Values lie in [-10^9,10^9]; every sum fits a signed 32-bit integer.

More Google problems

See Google hiring insights
public int[][] sumTimeSeries(int[][] first, int[][] second) {
    // Write your code here.
}
first[[0,0],[2,1],[8,0]]
second[[0,0],[1,3],[5,2]]
expected[[0,0],[1,3],[2,4],[5,3],[8,2]]
Checking account…