Amazon Interview Question - Tasks That Software Solve Given Task Difficulties & Software’s Abilities

Round 1

Questions: To evaluate advanced AI software at Amazon, we have q different programs set to undergo testing on n problems. Each problem has its own difficulty level difficulty[i] and a score tied to its complexity. Each AI program also comes with a specific ability level denoted by ability[i].

In practical terms, as software encounters each problem, it checks if its ability is sufficient to solve it. If the ability meets or exceeds the difficulty level, the program successfully solves the problem, earning a score equal to the problem's complexity. The program then moves on to the next problem. If the ability falls short, the evaluation for that problem concludes.

Formally, given two arrays: one array ability of size q, representing the ability level of all AI software, and another array difficulty of size n, representing the difficulty level of the problems.

Figure out the total score achieved by each of the q AI programs. It's important to note that if a program can't solve any problems, its score is zero.

Example 1

q = 2
ability = [2, 3]
n = 4
difficulty = [2, 1, 3, 1]

• 1st software:
  • It solves the first two problems and at the third problem, since the difficulty is greater than the ability, it stops. So score = 2 + 1 = 3
• 2nd software:
  • It solves all the tasks. So, score is 2 + 1 + 3 + 1 = 7

Output = [3, 7]

Example 2

ability = [5, 1, 4]
difficulty = [4, 1, 2, 5, 1]

• 1st software:
  • It solves all tasks 4, 1, 2, 5, 1 = 4 + 1 + 2 + 5 + 1 = 13
• 2nd software:
  • It solves nothing because the first task itself is greater than the ability = 0
• 3rd software:
  • It solved the first 3 tasks = 4 + 1 + 2 = 7

Output = [13, 0, 7]

def calculate_scores(ability, difficulty):
    total_scores = []
    memo = {}
    
    for ab in ability:
        if ab in memo:
            total_scores.append(memo[ab])
            continue
        score = 0
        for diff in difficulty:
            if ab >= diff:  # Ability can solve the problem
                score += diff  # Add the difficulty as the score
            else:
                break  # Stop evaluating further problems
        memo[ab] = score
        total_scores.append(score)
    
    return total_scores