FastPrep
Problem · Greedy

Inventory Processes Survival Possibility

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Within Amazon’s vast fulfillment system, there exist n distinct inventory tasks, each operated by bots[i] bots. These tasks compete, leading to conflict rounds every minute where two random tasks are chosen.

During each conflict:

  • The task with more bots defeats the other and absorbs all of its bots. 😱
  • If both tasks have an equal number of bots, one is randomly chosen as the winner and takes over the losing task’s bots. 🏳️

    • This sequence continues until only one inventory task remains active.

    Your objective is to determine which of these tasks have a chance to survive as the final remaining task in at least one possible sequence of events.

    Return the 1-based indices of all such tasks, and also please sort it in ascending order 📈.

    p.s. if you are applying for a L5 position, you may not want to miss this question..🤧

    Gooood news! We might found the shoe selling question: Selling Shoes

    The second question in the same batch..Will update once find reliable source..like always~~

    Function

    inventoryProcessesSurvivalPossibility(n: int, bots: int[]) → int[]

    Examples

    Example 1

    n = 5bots = [1, 6, 2, 7, 2]return = [2, 4]
    The inventory task at position 2 can potentially survive by following these possible clashes (where bots[i] = 0 indicates that its bots have been absorbed by another task): First, the 2nd task defeats the 1st task, acquiring its bots and increasing its count to 6 + 1 = 7. The updated bots array becomes [0, 7, 2, 7, 2]. Next, it eliminates the 3rd task, boosting its total to 7 + 2 = 9. The bots array is now [0, 9, 0, 7, 2]. Afterward, it overpowers the 4th task, raising its bot count to 9 + 7 = 16. The bots array updates to [0, 16, 0, 0, 2]. Finally, it conquers the 5th task, reaching a total of 16 + 2 = 18 bots. The final state is [0, 18, 0, 0, 0]. ~~~~~~~~~😇😇😇😇😇😇😇😇😇😇 Similarly, the inventory task at position 4 can also manage to be the last remaining after these rounds: Initially, the 4th task absorbs the 1st task, collecting its bots to get 7 + 1 = 8. Now the bots array reads [0, 6, 2, 8, 2]. Then, it overtakes the 3rd task, increasing its count to 8 + 2 = 10. The bots array becomes [0, 6, 0, 10, 2]. Following that, it defeats the 2nd task, resulting in a total of 10 + 6 = 16 bots. Updated bots: [0, 0, 0, 16, 2]. Lastly, it overcomes the 5th task, boosting its final count to 16 + 2 = 18. The final bots array is [0, 0, 0, 18, 0]. Therefore, inventory tasks 2 and 4 have the potential to survive until the end in at least one scenario. All other tasks will be eliminated eventually in every possible sequence.

    Constraints

  • 1 <= n <= 2 * 10^5
  • 1 <= robots[i] <= 10^9

    • More Amazon problems

    drafts saved locally
    public int[] inventoryProcessesSurvivalPossibility(int n, int[] robots) {
  // write your code here
}
    n5
    bots[1, 6, 2, 7, 2]
    expected[2, 4]
    checking account