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 Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute servers needed for daily recurring jobs

Q: Compute servers needed for daily recurring jobs

This question evaluates understanding of interval-based resource allocation and job grouping by identifier, testing competency in managing overlapping time intervals, capacity planning, and handling day-boundary truncation.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You operate a cluster of identical servers that run recurring **daily** jobs. For a single day, you are given a list of job execution intervals. Each interval has: - `job_id` (string or integer), - `start_time` (timestamp within that day), - `end_time` (timestamp within that day), with `start_time < end_time`. Interpret each interval as a half-open time range `[start_time, end_time)` during which that job must be running on some server **on that day**. Rules and constraints: - Each physical server can execute at most **one job at a time**. - However, if multiple intervals in the input correspond to the **same `job_id`**, they may overlap in time **on the same server** (they are considered parts or retries of the same job and do not consume extra capacity). - If a job's true execution would extend past midnight into the next day, it is conceptually **truncated at the end of the current day** for scheduling purposes; for each day you only see the portion that falls within that day’s 24-hour window. ### Tasks 1. Given all job intervals for a single day (potentially with repeated `job_id`s and overlapping intervals), compute the **minimum number of servers** required to schedule all the jobs under the above rules. 2. Describe the time and space complexity of your algorithm in terms of the number of intervals \(m\). ### Follow-up Some rare jobs are extremely long-running and conceptually span **multiple days** without restart. For such a multi-day job, you decide to reserve a **dedicated server** that is not shared with any other jobs, but which may still handle different intervals of that same `job_id`. Explain how you would extend or adapt your solution to: - Detect which jobs require a dedicated server based on their multi-day duration or configuration. - Account for these dedicated servers when computing the total number of servers needed for the system.

Quick Answer: This question evaluates understanding of interval-based resource allocation and job grouping by identifier, testing competency in managing overlapping time intervals, capacity planning, and handling day-boundary truncation.

Part 1: Minimum Servers for One Day with Overlapping Same-Job Intervals

You are given all job execution intervals for a single day. Each interval is half-open, meaning [start_time, end_time), and represents a time range during which a job must be running. A server can run at most one job at a time. However, if multiple intervals have the same job_id, they are considered parts or retries of the same job, so overlapping intervals with the same job_id consume only one server total during the overlap. Return the minimum number of servers required to run all intervals for the day.

Constraints

0 <= len(intervals) <= 200000
0 <= job_id <= 10^9
0 <= start_time < end_time <= 1440
Intervals are half-open: an interval ending at time t does not overlap an interval starting at time t.
Multiple intervals may have the same job_id.

Examples

Input: ([],)

Expected Output: 0

Explanation: There are no jobs, so no servers are needed.

Input: ([[5, 100, 200], [5, 150, 250], [5, 240, 300]],)

Expected Output: 1

Explanation: All intervals belong to the same job_id. Even though they overlap, they can share one server.

Input: ([[1, 0, 10], [1, 2, 8], [2, 5, 15], [3, 7, 12]],)

Expected Output: 3

Explanation: From time 7 to 10, job_ids 1, 2, and 3 are all active. The duplicate interval for job 1 does not add extra capacity.

Input: ([[1, 0, 60], [2, 60, 120], [3, 120, 180]],)

Expected Output: 1

Explanation: The intervals only touch at endpoints. Because ranges are half-open, they do not overlap.

Input: ([[1, 60, 180], [1, 120, 240], [2, 150, 210], [3, 240, 300], [4, 200, 260]],)

Expected Output: 3

Explanation: Job 1 is active from 60 to 240 after merging. From 200 to 210, job_ids 1, 2, and 4 are active, requiring 3 servers.

Hints

At any moment, one server is needed for each distinct active job_id, not for each active interval.
Try merging all intervals belonging to the same job_id first, then run a sweep-line algorithm over the merged intervals.

Part 2: Total Servers with Dedicated Multi-Day Jobs

You are given true job execution intervals that may span multiple days. Some jobs require dedicated servers. A job is dedicated if its job_id is listed in configured_dedicated, or if any one of its true intervals has duration at least min_dedicated_duration minutes. A dedicated job uses one reserved server for that job_id and does not share that server with other jobs, though multiple intervals of the same dedicated job_id may use the same dedicated server. For a given target_day, compute the total number of servers needed: one server for each dedicated job active during that target day, plus the minimum number of shared servers needed for all non-dedicated jobs active during that day. Non-dedicated intervals should be clipped to the target day's 24-hour window before scheduling.

Constraints

0 <= len(intervals) <= 200000
0 <= job_id <= 10^9
0 <= start_day <= end_day <= 10^9
0 <= start_minute < 1440
0 <= end_minute <= 1440
The absolute start time of every interval is strictly less than its absolute end time.
1 <= min_dedicated_duration <= 10^12
A dedicated server is counted for target_day only if that dedicated job has at least one interval overlapping target_day.

Examples

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

Expected Output: 0

Explanation: No intervals exist, so no servers are needed.

Input: ([[1, 0, 60, 0, 180], [1, 0, 120, 0, 240], [2, 0, 150, 0, 210], [99, 0, 0, 2, 0], [3, 1, 0, 1, 60]], 0, [], 1440)

Expected Output: 3

Explanation: Job 99 runs for 2880 minutes, so it is dedicated and active on day 0, using 1 server. Non-dedicated jobs 1 and 2 overlap, requiring 2 shared servers. Total is 3.

Input: ([[10, 0, 100, 0, 200], [20, 0, 150, 0, 250], [30, 0, 180, 0, 220]], 0, [20], 1440)

Expected Output: 3

Explanation: Job 20 is configured as dedicated and active, so it uses 1 dedicated server. Jobs 10 and 30 overlap from 180 to 200, requiring 2 shared servers.

Input: ([[1, 0, 1000, 2, 100], [2, 1, 0, 1, 60], [3, 1, 60, 1, 120]], 1, [], 1440)

Expected Output: 2

Explanation: Job 1 lasts at least 1440 minutes and overlaps day 1, so it uses 1 dedicated server. Jobs 2 and 3 only touch at time 60 on day 1, so they need just 1 shared server.

Input: ([[1, 0, 0, 2, 0], [2, 2, 10, 2, 20]], 3, [2], 1440)

Expected Output: 0

Explanation: Although job 1 is long-running and job 2 is configured as dedicated, neither overlaps target day 3, so no server is needed for that day.

Hints

Classify dedicated job IDs before clipping intervals to the target day, because dedication depends on true multi-day duration or configuration.
After removing active dedicated jobs, the remaining shared-server calculation is the same as Part 1 on the clipped intervals.

Quick Overview

This question evaluates understanding of interval-based resource allocation and job grouping by identifier, testing competency in managing overlapping time intervals, capacity planning, and handling day-boundary truncation.