PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates task-scheduling and constraint-handling skills, testing algorithmic reasoning about arranging repeated jobs with cooldown constraints along with analysis of schedule optimality and algorithmic complexity.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Rearrange Tasks With Cooldown

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of tasks, where each task is represented by an uppercase letter, and an integer `cooldown`. Rearrange the tasks into an execution order such that the same task type appears at least `cooldown` time slots apart. Each task takes exactly one time slot. You may insert idle slots if necessary. Return one valid schedule as a string, using `'_'` to represent an idle slot. If multiple schedules are valid, return any one of them. The schedule should be as short as possible. Example: ```text tasks = ["A", "A", "A", "B", "B", "C"] cooldown = 2 ``` One valid shortest schedule is: ```text "ABCA_BA" ``` because every repeated task is separated by at least two other time slots. Follow-up questions: 1. How would your approach change if idles are not allowed and you must either return a valid permutation of the tasks or an empty string? 2. How would you prove that your schedule length is minimal? 3. What is the time and space complexity of your solution?

Quick Answer: This question evaluates task-scheduling and constraint-handling skills, testing algorithmic reasoning about arranging repeated jobs with cooldown constraints along with analysis of schedule optimality and algorithmic complexity.

Part 1: Shortest Cooldown Schedule With Idles

You are given a list of task types, where each task is a one-character uppercase string, and an integer `cooldown`. Build the shortest possible execution schedule as a string. The same task type must appear at least `cooldown` time slots apart. You may insert '_' to represent idle slots. To make the answer deterministic, at each time slot first return every task whose cooldown has expired to the available pool, then choose the available task with the largest remaining frequency; if there is a tie, choose the lexicographically smaller task. If no task is available, append '_'. Return the resulting schedule string.

Constraints

  • 0 <= len(tasks) <= 100000
  • 0 <= cooldown <= 100000
  • Each element of `tasks` is a single uppercase English letter from 'A' to 'Z'

Examples

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

Expected Output: 'ABCAB_A'

Explanation: Using the required tie-break, the greedy shortest schedule is ABCAB_A.

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

Expected Output: 'AB_A__A'

Explanation: After using A and B, the scheduler must insert idles until A becomes available again.

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

Expected Output: 'AB_AB'

Explanation: One idle is necessary between the second A and second B.

Input: ([], 3)

Expected Output: ''

Explanation: No tasks means an empty schedule.

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

Expected Output: 'AAB'

Explanation: With cooldown 0, tasks may repeat immediately. The deterministic rule picks A first.

Hints

  1. Keep available tasks in a max-heap keyed by remaining count, and store recently used tasks in a queue with the time when they become available again.
  2. If the heap is empty but some tasks are still cooling down, you must place an idle slot.

Part 2: Cooldown Permutation Without Idles

You are given a list of task types, where each task is a one-character uppercase string, and an integer `cooldown`. Rearrange the tasks into a string that uses every task exactly once and contains no '_' characters. The same task type must appear at least `cooldown` time slots apart. If no such permutation exists, return an empty string. To make the answer deterministic, at each time slot first return every task whose cooldown has expired to the available pool, then choose the available task with the largest remaining frequency; if there is a tie, choose the lexicographically smaller task. If at some step no task is available before all tasks are used, return an empty string.

Constraints

  • 0 <= len(tasks) <= 100000
  • 0 <= cooldown <= 100000
  • Each element of `tasks` is a single uppercase English letter from 'A' to 'Z'

Examples

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

Expected Output: 'ABCABC'

Explanation: The tasks can be perfectly interleaved with distance 2.

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

Expected Output: ''

Explanation: A valid permutation without idles does not exist.

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

Expected Output: 'ABCA'

Explanation: A appears at positions 0 and 3, which satisfies cooldown 2.

Input: ([], 2)

Expected Output: ''

Explanation: The empty input has the empty permutation.

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

Expected Output: 'AAB'

Explanation: With cooldown 0, adjacent equal tasks are allowed.

Hints

  1. This is similar to Part 1, except you are not allowed to insert idle slots when nothing is available.
  2. If the available-task heap becomes empty before you place all tasks, then no valid permutation exists.

Part 3: Validate That a Cooldown Schedule Is Minimal

You are given the original task list, an integer `cooldown`, and a candidate schedule string that may contain task letters and '_' idle slots. Return `True` if and only if the schedule is both valid and as short as possible. A schedule is valid if it uses exactly the same multiset of tasks as the input, uses '_' only as idle slots, and places equal task letters at least `cooldown` time slots apart. This problem captures the proof-of-minimality follow-up in a coding form.

Constraints

  • 0 <= len(tasks) <= 100000
  • 0 <= cooldown <= 100000
  • 0 <= len(schedule) <= 200000
  • Each element of `tasks` is a single uppercase English letter from 'A' to 'Z'

Examples

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

Expected Output: True

Explanation: The schedule is valid and its length 7 is the minimum possible.

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

Expected Output: False

Explanation: The schedule is valid but not minimal; 'ABA' is shorter.

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

Expected Output: False

Explanation: The two A tasks are too close together.

Input: ([], 2, '')

Expected Output: True

Explanation: The empty schedule is valid and minimal for empty input.

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

Expected Output: False

Explanation: The multiset of tasks does not match the input.

Hints

  1. First check correctness of the candidate schedule: task counts must match exactly, and repeated letters must be far enough apart.
  2. A lower bound on the shortest possible length comes from the most frequent task types. Compare the schedule length against that bound.

Part 4: Count Heap and Cooldown Operations

Use the same greedy scheduler as in Part 1. Count task frequencies, put each distinct task into a max-heap ordered by remaining count and then lexicographically by task, and keep a FIFO cooldown queue of tasks that cannot be reused yet. At each time slot, first move all tasks whose cooldown has expired back into the heap. If the heap is non-empty, pop one task and execute it; if it still has remaining copies, place it into the cooldown queue with ready time `current_time + cooldown + 1`. Otherwise the scheduler executes an idle slot '_'. Return a list `[heap_pushes, heap_pops, max_cooldown_size]`, where `heap_pushes` counts every insertion into the heap including the initial ones, `heap_pops` counts every extraction from the heap, and `max_cooldown_size` is the maximum number of task types simultaneously waiting in the cooldown queue immediately after any time slot.

Constraints

  • 0 <= len(tasks) <= 100000
  • 0 <= cooldown <= 100000
  • Each element of `tasks` is a single uppercase English letter from 'A' to 'Z'

Examples

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

Expected Output: [6, 6, 2]

Explanation: There are 6 total heap pushes, 6 heap pops, and the cooldown queue peaks at size 2.

Input: ([], 3)

Expected Output: [0, 0, 0]

Explanation: No tasks means no heap or queue activity.

Input: (['A'], 5)

Expected Output: [1, 1, 0]

Explanation: One initial heap insertion and one pop; nothing waits in cooldown.

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

Expected Output: [6, 6, 3]

Explanation: After scheduling A, B, and C once, all three task types are cooling down at the same time.

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

Expected Output: [3, 3, 1]

Explanation: The second A returns immediately on the next slot, and the cooldown queue never exceeds size 1.

Hints

  1. Simulate the scheduler exactly. Count heap pushes both when you build the initial heap and when cooled-down tasks return.
  2. The cooldown queue size changes only when you execute a task with remaining copies or when tasks become available again.
Last updated: Jun 6, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Containing Range - Google (medium)
  • Solve Three Array and Matrix Path Problems - Google (medium)
  • Consolidate On-Call Rotation Segments - Google (medium)
  • Solve Flower Placement and Directory Deletion - Google (medium)
  • Compute Turnstile Crossing Times - Google (hard)