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 Chime.

What role is this question designed for?

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

Compute minimum time with task cooldowns

Quick Overview

This question evaluates understanding of constrained task scheduling, frequency-based reasoning, and algorithmic complexity within the Coding & Algorithms domain (task scheduling and combinatorial optimization), emphasizing both conceptual understanding and practical application.

Company: Chime

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a multiset of task types represented by uppercase letters (e.g., A, A, A, B, B, C). Each task takes exactly 1 time unit to execute. Running the same task type requires at least c cooldown time units between two executions of that type. You may reorder tasks and insert idle slots as needed. Compute the minimum total time units to finish all tasks. Describe an algorithm, justify its correctness, analyze time and space complexity, and explain how to construct one optimal schedule.

Quick Answer: This question evaluates understanding of constrained task scheduling, frequency-based reasoning, and algorithmic complexity within the Coding & Algorithms domain (task scheduling and combinatorial optimization), emphasizing both conceptual understanding and practical application.

You are given a multiset of task types represented by uppercase letters. Each task takes exactly 1 time unit to execute. If the same task type is executed more than once, there must be at least c full time units between two executions of that type. You may reorder the tasks in any order and insert idle time slots if needed. Return the minimum total number of time units needed to complete all tasks. For example, with tasks ['A','A','A','B','B','B'] and c = 2, one optimal schedule is A, B, idle, A, B, idle, A, B, which takes 8 time units.

Constraints

0 <= len(tasks) <= 100000
Each task is an uppercase English letter from 'A' to 'Z'
0 <= c <= 100000
Each task takes exactly 1 time unit

Examples

Input: (['A','A','A','B','B','B'], 2)

Expected Output: 8

Explanation: One optimal schedule is A, B, idle, A, B, idle, A, B. The total time is 8.

Input: (['A','A','A','B','B','C'], 2)

Expected Output: 7

Explanation: One optimal schedule is A, B, C, A, B, idle, A. The final A executions are separated by at least 2 time units.

Input: (['A','B','C','D'], 3)

Expected Output: 4

Explanation: There are no repeated task types, so no cooldown restriction forces idle time.

Input: (['A','A','A','A'], 3)

Expected Output: 13

Explanation: The only possible structure is A, idle, idle, idle, A, idle, idle, idle, A, idle, idle, idle, A, taking 13 time units.

Input: ([], 5)

Expected Output: 0

Explanation: There are no tasks to execute.

Input: (['A','A','B','B','C','C'], 1)

Expected Output: 6

Explanation: A schedule such as A, B, C, A, B, C completes all tasks with no idle time.

Input: (['A','A','A','B','C'], 0)

Expected Output: 5

Explanation: With zero cooldown, tasks can be executed back-to-back in any order.

Hints

The task type with the highest frequency determines the minimum number of separated groups you may need.
Think of arranging the most frequent tasks first, then filling the gaps with other tasks before deciding whether idle slots are necessary.

Quick Overview