Video Advertisement Frame Ranges
Google● MediumFULLTIMEONSITE INTERVIEWProblem statement
A supplied advertisement-detection model reports rectangular boxes in video frames. Return all continuous frame and timestamp ranges occupied by each reported rectangle.
For this exercise, assume the video has frameCount frames numbered from zero and a constant integer frame rate fps. Each unordered detection row is [frame,x,y,width,height]. Identical (x,y,width,height) values identify one rectangle; repeated copies in one frame count once. Merge only consecutive frames for that exact rectangle. A missing frame splits a range; changing any coordinate or size starts a different rectangle.
Return one row [startFrame,endFrameExclusive,startMs,endMs,x,y,width,height] per maximal run. Timestamps are floor(frameBoundary * 1000 / fps) milliseconds at the respective boundaries. Sort rows lexicographically by start frame, exclusive end frame, x, y, width and height. Different rectangles remain separate even when they overlap spatially.
Function
advertisementRanges(frameCount: int, fps: int, detections: int[][]) → int[][]Examples
Example 1
frameCount = 6fps = 10detections = [[2,0,0,2,3],[0,0,0,2,3],[1,0,0,2,3],[4,0,0,2,3]]return = [[0,3,0,300,0,0,2,3],[4,5,400,500,0,0,2,3]]Frames zero through two form one run; the missing third frame separates frame four.
Example 2
frameCount = 3fps = 30detections = [[0,5,7,1,1],[1,0,0,2,3],[0,0,0,2,3]]return = [[0,1,0,33,5,7,1,1],[0,2,0,66,0,0,2,3]]The shorter run comes first when start frames tie; timestamps use floored boundary times.
Example 3
frameCount = 0fps = 25detections = []return = []No frames and no model detections produce no ranges.
Constraints
0 <= frameCount <= 100000,1 <= fps <= 1000, and0 <= detections.length <= 10000.- Every detection contains five integers and
0 <= frame < frameCount. A zero-frame video has no detections. 0 <= x,y <= 10000and1 <= width,height <= 10000.- All detections are accepted model outputs. There is no confidence threshold, interpolation or identity tracking across moving boxes.