FastPrep
Problem · Array

Total Waiting Time for Handmade Items

Learn this problem
● MediumMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

There are N clients who have ordered N handmade items. The K-th client ordered exactly one item that takes T[K] hours to make. There is only one employee who makes items for clients, and they work in the following manner:

  • spend one hour making the first item;
  • if the item is finished, the employee delivers it to the client immediately;
  • if the item is not finished, they put it after the N-th item for further work;
  • the employee starts making the next item.

    • As the result may be large, return its last nine digits without leading zeros (in other words, return the result modulo 10^9).

    Function

    microsoftHandmadeItem(T: int[]) → int

    Complete the func in the editor 👉

    that, given an array of integers T of length N, returns the total time that the clients need to wait (modulo 109).

    Examples

    Example 1

    T = [3, 1, 2]return = 13
    The employee spends 6 hours making items in the following order: [1, 2, 3, 1, 3, 1]. The first client waited 6 hours for their item, the second client received their item after 2 hours and the third client after 5 hours. The total waiting time of all clients is 6 + 2 + 5 = 13.

    Example 2

    T = [1, 2, 3, 4]return = 24
    The employee prepares the items in the following order: 1, 2, 3, 4, 2, 3, 4, 3, 4, 4. The first client waited for 1 hour, the second client for 5 hours, the third client for 8 hours, and the fourth client for 10 hours. The total waiting time of all clients is 1 + 5 + 8 + 10 = 24 hours.

    Example 3

    T = [7, 7, 7]return = 60
    No explanation provided

    Example 4

    T = [10000]return = 10000
    No explanation provided

    Constraints

  • N is an integer within the range [1..100,000]
  • each element of array T is an integer within the range [1..10,000]

    • More Microsoft problems

    drafts saved locally
    public int microsoftHandmadeItem(int[] T) { 
  // write your code here 
  }
    T[3, 1, 2]
    expected13
    checking account