Amazon | FAANG | OA Coding Questions and Solutions | Set - 24 | 2022

Question

All past online assesments of Amazon can be found using the tag "amazon_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/amazon_oa

Answer 1

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.

You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

 

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

 

Constraints:

• 1 <= jobDifficulty.length <= 300
• 0 <= jobDifficulty[i] <= 1000
• 1 <= d <= 10

Code : 

const minDifficulty = (A, D) => {
    let n = A.length, inf = Infinity, maxd;
    
    if (n < D) return -1;
    
    let dp = new Array(n + 1).fill(Infinity);
    dp[n] = 0;
    
    for (let d = 1; d <= D; d++) {
        for (let i = 0; i <= n - d; i++) {
            maxd = 0, dp[i] = inf;

            for (let j = i; j <= n - d; j++) {
                maxd =  Math.max(maxd, A[j]);
                dp[i] = Math.min(dp[i], maxd + dp[j + 1]);
            }
        }
    }
    
    return dp[0];
}