How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Meta during technical interviews.

Optimize Oculus Data Streaming with Bandwidth Constraints

Company: Meta

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Scenario Algorithmic screening for Meta VR/AR teams covering Oculus data streaming and geometric optimization. ##### Question Oculus: Given an array frame_sizes and an integer bandwidth_limit, split the array into the fewest contiguous segments so that the sum of each segment ≤ bandwidth_limit. Return that minimum number. Circle: Given n circles on a 1-D line represented by [center, radius], return the minimum number of horizontal arrows needed so that every arrow shot at position p bursts all circles satisfying center-radius ≤ p ≤ center+radius. ##### Hints Both can be solved with greedy + sorting; think about keeping running sums or end-points.

Quick Answer: This question evaluates a candidate's ability in algorithm design and problem decomposition for array segmentation and interval coverage, focusing on reasoning about cumulative constraints for streaming data and geometric interval intersections.

Oculus: Minimum Bandwidth-Constrained Segments

Given an array `frame_sizes` and an integer `bandwidth_limit`, split the array into the fewest contiguous segments so that the sum of each segment is at most `bandwidth_limit`. Return that minimum number of segments. Because the segments must be contiguous (you cannot reorder frames in a stream), a simple greedy pass works: keep a running sum and start a new segment whenever adding the next frame would exceed the limit. If any single frame already exceeds `bandwidth_limit`, it can never fit in any segment — return -1. An empty input requires 0 segments.

Constraints

0 <= len(frame_sizes) <= 10^5
0 <= frame_sizes[i] <= 10^9
1 <= bandwidth_limit <= 10^9
Segments must be contiguous (frames cannot be reordered)
Return -1 if any single frame exceeds bandwidth_limit

Examples

Input: ([2, 3, 5, 1, 4], 5)

Expected Output: 3

Explanation: Segments [2,3]=5, [5]=5, [1,4]=5. Three segments, each exactly at the limit.

Input: ([1, 1, 1, 1], 10)

Expected Output: 1

Explanation: Total sum 4 <= 10, so the whole array fits in a single segment.

Input: ([5, 5, 5], 5)

Expected Output: 3

Explanation: Each frame equals the limit, so no two can share a segment: three segments.

Input: ([], 5)

Expected Output: 0

Explanation: An empty stream needs no segments.

Input: ([3], 5)

Expected Output: 1

Explanation: A single frame within the limit forms one segment.

Input: ([4, 2, 6, 1], 5)

Expected Output: -1

Explanation: The frame of size 6 exceeds bandwidth_limit=5 and can never fit, so the split is impossible.

Input: ([2, 2, 2, 2, 2], 4)

Expected Output: 3

Explanation: Greedy: [2,2]=4, [2,2]=4, [2]=2 -> three segments.

Hints

Frames cannot be reordered, so a single left-to-right greedy pass is optimal: extend the current segment as long as the running sum stays within the limit.
Start a new segment exactly when adding the next frame would push the running sum above bandwidth_limit, and reset the running sum to that frame's size.
Guard the impossible case first: if any individual frame already exceeds bandwidth_limit it can never fit, so return -1.

Circle: Minimum Arrows to Burst All Circles

Given `n` circles on a 1-D line, each represented as `[center, radius]`, return the minimum number of horizontal arrows needed so that every circle is burst. An arrow shot at position `p` bursts a circle if `center - radius <= p <= center + radius`. Each circle [center, radius] is equivalent to the closed interval [center - radius, center + radius], so this is the classic minimum-number-of-points-to-stab-all-intervals (a.k.a. minimum arrows to burst balloons) problem. Sort the intervals by their right endpoint and greedily place an arrow at the current interval's right endpoint, covering as many subsequent intervals as possible. Intervals that merely touch at a single boundary point can be burst by one shared arrow.

Constraints

0 <= n <= 10^5
circles[i] = [center, radius] with radius >= 0
An arrow at p bursts circle i iff center_i - radius_i <= p <= center_i + radius_i
Circles that touch only at a single boundary point can be burst by one shared arrow

Examples

Input: ([[1, 1], [4, 1], [7, 1]],)

Expected Output: 3

Explanation: Intervals [0,2],[3,5],[6,8] are pairwise disjoint, so three separate arrows are required.

Input: ([[2, 2], [3, 1], [10, 1]],)

Expected Output: 2

Explanation: Intervals [0,4],[2,4],[9,11]. One arrow at 4 bursts the first two; another at 11 bursts the last.

Input: ([],)

Expected Output: 0

Explanation: No circles, no arrows.

Input: ([[5, 0]],)

Expected Output: 1

Explanation: A degenerate circle is the point [5,5]; one arrow at 5 bursts it.

Input: ([[0, 3], [2, 1], [6, 2]],)

Expected Output: 2

Explanation: Intervals [-3,3],[1,3],[4,8]. Arrow at 3 bursts the first two; arrow at 8 bursts the last.

Input: ([[1, 5], [2, 5], [3, 5]],)

Expected Output: 1

Explanation: Intervals [-4,6],[-3,7],[-2,8] all overlap around 6; a single arrow at 6 bursts all three.

Input: ([[0, 1], [2, 1], [4, 1]],)

Expected Output: 2

Explanation: Intervals [-1,1],[1,3],[3,5]. The first two touch at 1 (one arrow), and [1,3]/[3,5] touch at 3, so an arrow at 3 also burns the third: two arrows total.

Input: ([[-3, 1], [-1, 1], [-2, 2]],)

Expected Output: 1

Explanation: Intervals [-4,-2],[-2,0],[-4,0] all contain -2; a single arrow at -2 bursts all three.

Hints

Convert each circle [center, radius] into the closed interval [center - radius, center + radius]; the problem becomes the minimum number of points that stab all intervals.
Sort the intervals by their right endpoint. Greedily shoot each arrow at the right endpoint of the earliest-ending interval not yet burst.
An interval is already burst by the last arrow if its start is <= the last arrow position; only when start > last_arrow do you need a new arrow.

Quick Overview

This question evaluates a candidate's ability in algorithm design and problem decomposition for array segmentation and interval coverage, focusing on reasoning about cumulative constraints for streaming data and geometric interval intersections.