FastPrep
Problem · Array

Count Processes Giving Inaccurate Results

● MediumAmazonOA
See Amazon hiring insights

In Amazon computing environment, there is a critical sequence of n processes that must be executed in a specific order to produce results. The prescribed order is represented by the array processOrder, where processOrder[i] (1 ≤ i ≤ n) denotes the process to be executed at the ith position. Accurate results require the execution of all n preceding processes.

Facing a challenge, an individual, guided by the array executionOrder, mistakenly runs the processes in a different order. Here, executionOrder[i] (1 ≤ i ≤ n) signifies the process executed at the ith position. Both processOrder and executionOrder are permutations of size n.

Determine the count of processes that fail to produce accurate results due to the deviation from the specified order.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once, for example [1, 3, 2] is a permutation while [1, 2, 2] is not.

Examples
01 · Example 1
processOrder = [2, 3, 5, 1, 4]
executionOrder = [5, 2, 3, 4, 1]
return = 2

We see that 2 processes would give inaccurate results and these would be the process number 5 and 4.

Process 5 gives inaccurate results because in the original order, it needs processes 2 and 3 to run successfully, and the individual executes both of them after process 5. Also, process 4 needs all the other processes to be executed before it runs properly. But the individual executes process 1 afterward, resulting in 4 giving inaccurate results.

Therefore, 2 processes give inaccurate results.

02 · Example 2
processOrder = [4, 2, 3, 5, 1, 6]
executionOrder = [2, 3, 5, 1, 6, 4]
return = 5

The only difference between the arrays processOrder and executionOrder is that process 4 is executed after all other processes, while the order of the remaining processes remains unchanged. Additionally, processes 2, 3, 5, 1, and 6 rely on process 4 to produce accurate results.

03 · Example 3
processOrder = [3, 2, 1]
executionOrder = [3, 2, 1]
return = 0

We see that the order of execution of processes in executionOrder matches that of processOrder. Hence, 0 processes give inaccurate results. Therefore, 0 processes give inaccurate results, and we return that.

Constraints
  • 1 ≤ n ≤ 2*10^5
  • actualSequence[i] ≤ n, actualSequence[i] ≤ n
  • requiredSequence and actualSequence are permutations of integers from 1 to n
    • More Amazon problems
    drafts saved locally
    public int countInaccurateResults(int[] processOrder, int[] executionOrder) {
  // write your code here
}
    processOrder[2, 3, 5, 1, 4]
    executionOrder[5, 2, 3, 4, 1]
    expected2
    sign in to submit