Amazon OA SDE 2 (2024)

Round 1

Questions: Amazon recently conducted interviews where the candidates were asked to sort the permutation p of length n. Each candidate sorted the permutation in moves[i] moves. To verify the result, the interviewer wanted to find if it is possible to sort the given permutation in the given number of moves. Given the original permutation array p and the number of moves made by each of the q candidates, find whether you can sort the permutation p by performing exactly moves[i] moves. Return the answer as a binary string of length q. The value at the ith index should be 1 if it is possible to sort the permutation at exactly moves[i], otherwise the value should be 0.

Note: A permutation is a sequence of n distinct integers such that each integer between [1, n] appears exactly once. For example, [1, 2, 3, 4] is a permutation of size 4, but [1,3,4,5] or [1,2,2,4] is not.

Example:

• Let n = 4, q = 2
  • p = [2, 3, 1, 4]
  • moves = [2, 3]

Example:

• Let n = 5, q = 3
  • p = [4, 5, 1, 3, 2]
  • moves = [1, 2, 3]

Constraints:

• 1 <= n <= 10^5
• 1 <= q <= 10^5
• 1 <= moves[i] <= 10^9
• It is guaranteed that p forms a permutation.