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 J.P. Morgan.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at J.P. Morgan during technical interviews.

Solve scheduling and collision problems | J.P. Morgan Coding Question

Quick Overview

This question evaluates a candidate's understanding of algorithm design and data structures for resource allocation and dynamic interaction problems, specifically interval overlap analysis for scheduling/CPU provisioning and one-dimensional collision simulation.

Solve scheduling and collision problems

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The interview included multiple algorithm questions in the same category: 1. **Minimum concurrent resources for intervals** You are given a list of time intervals, where each interval represents a meeting or a CPU task with a start time and an end time. Return the minimum number of rooms or CPU slots required so that all intervals can run without overlap conflicts. Example: if intervals are `[0, 30]`, `[5, 10]`, and `[15, 20]`, the answer is `2` because at most two intervals overlap at the same time. 2. **Equivalent CPU-capacity variant** Solve the same problem again, but framed as finding the minimum number of CPUs needed to run all jobs whose active windows are given as intervals. 3. **One-dimensional collision simulation** You are given an array of integers representing moving objects on a line. A positive value moves to the right, and a negative value moves to the left. When two objects moving toward each other collide, the one with smaller absolute value disappears. If they have equal absolute value, both disappear. Return the final state after all collisions are resolved. The interview version was described as a simplified variant of the standard stack-based collision simulation problem. Implement efficient solutions and discuss the time and space complexity.

Quick Answer: This question evaluates a candidate's understanding of algorithm design and data structures for resource allocation and dynamic interaction problems, specifically interval overlap analysis for scheduling/CPU provisioning and one-dimensional collision simulation.

Part 1: Minimum Concurrent Resources for Intervals

You are given an unsorted list of time intervals `intervals`, where each interval `[start, end]` represents a meeting or CPU job that uses exactly one resource from time `start` up to but not including `end`. Two intervals do not overlap if one ends exactly when another begins. Return the minimum number of rooms or CPU slots required so that all intervals can be processed without conflict.

Constraints

`0 <= len(intervals) <= 200000`
`0 <= start < end <= 10^9` for every interval
The input list may be unsorted

Examples

Input: [[0, 30], [5, 10], [15, 20]]

Expected Output: 2

Explanation: At most two intervals are active at the same time, so two resources are enough.

Input: [[7, 10], [2, 4]]

Expected Output: 1

Explanation: The intervals do not overlap, so one resource can be reused.

Input: []

Expected Output: 0

Explanation: No intervals means no resources are needed.

Input: [[1, 2]]

Expected Output: 1

Explanation: A single interval always needs exactly one resource.

Input: [[1, 4], [4, 5], [4, 6]]

Expected Output: 2

Explanation: The interval `[1, 4]` frees its resource at time 4, then the other two intervals overlap with each other.

Hints

If you process intervals in increasing order of start time, you only need to know which active interval ends earliest.
A min-heap of end times lets you release finished jobs before assigning the next one.

Part 2: One-Dimensional Collision Simulation

You are given an array of non-zero integers `objects`. Each value represents an object moving on a line: a positive number moves right and a negative number moves left. When two objects moving toward each other collide, the one with smaller absolute value disappears. If both have the same absolute value, both disappear. Objects moving in the same direction never collide. Return the final state after all collisions have been resolved.

Constraints

`0 <= len(objects) <= 100000`
`1 <= abs(objects[i]) <= 10^9`
Each `objects[i]` is non-zero

Examples

Input: [5, 10, -5]

Expected Output: [5, 10]

Explanation: The `-5` collides with `10` and disappears because `10` has larger magnitude.

Input: [8, -8]

Expected Output: []

Explanation: Both objects have equal magnitude, so both disappear.

Input: [10, 2, -5]

Expected Output: [10]

Explanation: The `-5` destroys `2`, then collides with `10` and disappears.

Input: []

Expected Output: []

Explanation: An empty input stays empty.

Input: [-2, -1, 1, 2]

Expected Output: [-2, -1, 1, 2]

Explanation: These objects never move toward each other, so no collisions happen.

Hints

A collision can only happen when a right-moving object is to the left of a left-moving object.
Use a stack to keep survivors seen so far, and resolve collisions while the top of the stack can still meet the current object.

Quick Overview