Solve three scheduling and array problems
Overview
This multi-part question evaluates algorithmic problem-solving skills across task scheduling with cooldowns, in-place array deduplication, and string rearrangement to avoid adjacent duplicates, highlighting concepts such as frequency counting, scheduling constraints, and two-pointer or in-place techniques within the Coding & Algorithms domain.
In this round you are given three separate coding problems to solve.
Problem 1: Schedule tasks with cooldown
You are given:
-
A list of tasks, where each task is represented by a capital letter
'A'to'Z'. -
An integer
n >= 0, the cooldown period .
A single CPU can execute at most one task per time unit. The same type of task must be separated by at least n idle intervals (or other tasks) between two executions.
You may insert idle slots (no task executed) if needed.
Return the minimum number of time units required to execute all tasks.
Example:
-
Input:
tasks = ['A','A','A','B','B','B'],n = 2 -
One optimal schedule:
A B idle A B idle A B -
Output:
8
Constraints:
-
1 <= tasks.length <= 10^4 -
0 <= n <= 10^4
Describe an efficient algorithm and then implement it.
Problem 2: Remove duplicates from sorted array in-place
You are given a sorted integer array nums (non-decreasing order).
Remove the duplicates in-place such that each unique element appears only once and the relative order of elements is preserved.
The function should return the new length k of the array containing only the unique elements. The first k elements of nums should hold the unique values; the remaining elements beyond k can be any value and are not important.
You must use O(1) extra space.
Example:
-
Input:
nums = [0,0,1,1,1,2,2,3,3,4] -
Output:
-
Return value:
5 -
numsis modified to start with[0,1,2,3,4, ...]
-
Return value:
Constraints:
-
0 <= nums.length <= 10^5 -
-10^9 <= nums[i] <= 10^9
Describe your approach (pointer technique, etc.) and implement the function.
Problem 3: Rearrange string to avoid adjacent duplicates
You are given a string s consisting of lowercase English letters.
Rearrange the characters of s so that no two adjacent characters are the same. If it is not possible, indicate failure (for example, return an empty string or a special value as defined by the language/boilerplate).
Example 1:
-
Input:
s = "aab" -
One valid output:
"aba"
Example 2:
-
Input:
s = "aaab" -
Output: impossible (because any arrangement has at least two adjacent
'a's).
Constraints:
-
1 <= s.length <= 10^5 -
scontains only lowercase English letters'a'to'z'.
Design an efficient algorithm (both time and space) and implement it.