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 hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

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

Minimize time for two handlers | Amazon Coding Question

Minimize time for two handlers

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given a sequence of jobs that must be processed in the given order. There are exactly two handlers, and each job must be assigned to one of them. Each job has a **type**. Let `workList[i]` be the type of the `i`-th job. For each job type `t`, you are also given: - `longPrepTime[t]`: the cost for a handler to process type `t` if this is the first job that handler has ever processed, or if the handler's most recent job type is different from `t` - `shortPrepTime[t]`: the cost for a handler to process type `t` if the handler's most recent job type is also `t` Initially, both handlers have processed nothing. Your task is to assign every job in `workList` to one of the two handlers so that the **total preparation time** is minimized. Example: - `workList = [1, 2, 2]` - `longPrepTime = [4, 5]` - `shortPrepTime = [2, 3]` Assume job types are 1-indexed, so: - type `1` has `longPrepTime = 4`, `shortPrepTime = 2` - type `2` has `longPrepTime = 5`, `shortPrepTime = 3` One optimal assignment is: - handler A processes job type `1` with cost `4` - handler B processes job type `2` with cost `5` - handler B processes job type `2` again with cost `3` So the minimum total time is `12`. Return the minimum total preparation time.

Quick Answer: This question evaluates algorithmic optimization skills and stateful scheduling reasoning, focusing on task assignment trade-offs and cumulative cost minimization for two handlers.

Part 1: Minimum Preparation Time for Two Handlers

You are given a list of jobs in the exact order they must be assigned. Each value in workList is a work type ID from 1 to m. There are exactly two handlers, and each job must be assigned to one of them. When a handler processes a job of type x: - If it is the first job ever assigned to that handler, or the handler's previous job type is different from x, the cost is longPrepTime[x - 1]. - If the handler's previous job type is also x, the cost is shortPrepTime[x - 1]. Return the minimum total preparation time needed to assign all jobs.

Constraints

0 <= len(workList) <= 200
0 <= len(longPrepTime) == len(shortPrepTime) <= 50
If workList is non-empty, every work type x satisfies 1 <= x <= len(longPrepTime)
0 <= longPrepTime[i], shortPrepTime[i] <= 10^4

Examples

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

Expected Output:

Explanation: Assign work 1 to handler A for 4, work 2 to handler B for 5, and the last work 2 again to handler B for 3. Total = 12.

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

Expected Output:

Explanation: No jobs means no preparation cost.

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

Expected Output:

Explanation: Best is to keep all three jobs on the same handler: 7 + 2 + 2 = 11.

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

Expected Output:

Explanation: Let one handler keep type 1 and the other keep type 2: 5 + 6 + 1 + 1 = 13.

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

Expected Output:

Explanation: All three jobs are effectively long preparations because no handler can repeat the same type here. Total = 3 + 4 + 5 = 12.

Hints

The full assignment history does not matter. For each handler, only its last job type affects the next cost.
Use dynamic programming over the prefix of workList and the pair of last job types for the two handlers.

Part 2: Replacement Problem - Balance Jobs Between Two Handlers

The original source referenced a second Reddit problem but did not include its text. To avoid inventing a false reconstruction, this is a clearly labeled replacement problem in the same two-handler scheduling theme. You are given a list of job durations. Each job must be assigned to exactly one of two handlers. Jobs assigned to the same handler are processed sequentially, while the two handlers work in parallel. Return the minimum possible finishing time after all jobs are assigned. In other words, split the jobs into two groups so that the larger group sum is as small as possible.

Constraints

0 <= len(jobs) <= 200
1 <= jobs[i] <= 1000 for each job
sum(jobs) <= 20000

Examples

Input: [3, 1, 4, 2, 2]

Expected Output:

Explanation: One optimal split is {4, 2} and {3, 2, 1}, both summing to 6.

Input: []

Expected Output:

Explanation: No jobs means the finishing time is 0.

Input: [7]

Expected Output:

Explanation: A single job must be handled by one handler, so the makespan is 7.

Input: [1, 2, 3, 9]

Expected Output:

Explanation: Best split is {9} and {1, 2, 3}. The larger side is 9.

Input: [5, 5, 5, 5]

Expected Output:

Explanation: Split into two pairs: 10 and 10.

Hints

If one handler gets total time s, the other gets total time sum(jobs) - s. You want these two sums as close as possible.
A subset-sum dynamic programming approach up to half of the total duration is enough.

Quick Overview

This question evaluates algorithmic optimization skills and stateful scheduling reasoning, focusing on task assignment trade-offs and cumulative cost minimization for two handlers.