<filename>interview/TuSimple/ThrottlingGateway.py
"""
Throttling Gateway (Test #8)
Non-critical requests for a transaction system are routed through a throttling 
gateway to ensure that the newwork is not choked by non-essential requests.

The gateways has the following limits:
* The number of transactions in any given second cannot exceed 3
* The number of transactions in any given 10 second period cannot exceed 20.
  A ten-second period includes all requests arriving from any time max(1, t-9) to t
  (inclusive of both) for any valid time t.
* The number of transactions in any given minute cannot exceed 60.
  Similar to above, 1 minute is from max(1, t-59) to t.

Any request that exceeds any of the above limits will be dropped by the gateway.
Given the times at which different requests arrive sorted ascending,
find how many requests will be dropped.

Note: Even if a request is dropped it is still considered for future calculations.
Although, if a request is to be dropped due to multiple violations, it is still counted only once.

Example:
n = 27
requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 11, 11, 11, 11]
output: 7
Explanation:
* Request 1: Not dropped.
* Request 1: Not dropped.
* Request 1: Not dropped.
* Request 1: Dropped. At most 3 requests are allowed in one second.
* No request will be dropped till 6 as all comes at an allowed rate of 3 requests per second 
  and the 10-second clause is also not violated.
* Request 7: Not dropped. The total number of requests has reached 20 now.
* Request 7: Dropped. At most 20 requests are allowed in ten seconds.
* Request 7: Dropped. At most 20 requests are allowed in ten seconds.
* Request 7: Dropped. At most 20 requests are allowed in ten seconds.
  Note that the 1-second limit is also violated here.
* Request 11: Not dropped. The 10-second window has now become 2 to 11. 
  Hence the 1-second limit is also violated here.
* Request 11: Dropped. At most 20 requests are allowed in ten seconds.
* Request 11: Dropped. At most 20 requests are allowed in ten seconds.
* Request 11: Dropped. At most 20 requests are allowed in ten seconds.
  Also, at most 3 requests are allowed per second.
Hence, a total of 7 requests are dropped.

Example:
n = 21
requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7]
output: 2
Explanation: In the first second, 4 requests arrive so one request is dropped.
Within 10 seconds, all request times from second 1 to 7, a total of 21 requests arrive.
The last request is dropped. The total number of dropped requests is 2.
"""
from typing import List

class Solution():
    def droppedRequest(self, requestTime: List[int]) -> int:
        """
        Time complexity : O(n)
        Space complexity: O(1)
        """
        dropped = 0
        for i in range(len(requestTime)):
            if i > 2 and requestTime[i] == requestTime[i - 3]:
                dropped += 1
            elif i > 19 and requestTime[i] - requestTime[i - 20] < 10:
                dropped += 1
            elif i > 59 and requestTime[i] - requestTime[i - 59] < 60:
                dropped += 1 
        return dropped


def main():
    requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 11, 11, 11, 11]
    result = Solution().droppedRequest(requestTime)
    print(result)


if __name__ == "__main__":
    main()

<filename>interview/TuSimple/ThrottlingGateway.py
"""
Throttling Gateway (Test #8)
Non-critical requests for a transaction system are routed through a throttling 
gateway to ensure that the newwork is not choked by non-essential requests.

The gateways has the following limits:
* The number of transactions in any given second cannot exceed 3
* The number of transactions in any given 10 second period cannot exceed 20.
  A ten-second period includes all requests arriving from any time max(1, t-9) to t
  (inclusive of both) for any valid time t.
* The number of transactions in any given minute cannot exceed 60.
  Similar to above, 1 minute is from max(1, t-59) to t.

Any request that exceeds any of the above limits will be dropped by the gateway.
Given the times at which different requests arrive sorted ascending,
find how many requests will be dropped.

Note: Even if a request is dropped it is still considered for future calculations.
Although, if a request is to be dropped due to multiple violations, it is still counted only once.

Example:
n = 27
requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 11, 11, 11, 11]
output: 7
Explanation:
* Request 1: Not dropped.
* Request 1: Not dropped.
* Request 1: Not dropped.
* Request 1: Dropped. At most 3 requests are allowed in one second.
* No request will be dropped till 6 as all comes at an allowed rate of 3 requests per second 
  and the 10-second clause is also not violated.
* Request 7: Not dropped. The total number of requests has reached 20 now.
* Request 7: Dropped. At most 20 requests are allowed in ten seconds.
* Request 7: Dropped. At most 20 requests are allowed in ten seconds.
* Request 7: Dropped. At most 20 requests are allowed in ten seconds.
  Note that the 1-second limit is also violated here.
* Request 11: Not dropped. The 10-second window has now become 2 to 11. 
  Hence the 1-second limit is also violated here.
* Request 11: Dropped. At most 20 requests are allowed in ten seconds.
* Request 11: Dropped. At most 20 requests are allowed in ten seconds.
* Request 11: Dropped. At most 20 requests are allowed in ten seconds.
  Also, at most 3 requests are allowed per second.
Hence, a total of 7 requests are dropped.

Example:
n = 21
requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7]
output: 2
Explanation: In the first second, 4 requests arrive so one request is dropped.
Within 10 seconds, all request times from second 1 to 7, a total of 21 requests arrive.
The last request is dropped. The total number of dropped requests is 2.
"""
from typing import List

class Solution():
    def droppedRequest(self, requestTime: List[int]) -> int:
        """
        Time complexity : O(n)
        Space complexity: O(1)
        """
        dropped = 0
        for i in range(len(requestTime)):
            if i > 2 and requestTime[i] == requestTime[i - 3]:
                dropped += 1
            elif i > 19 and requestTime[i] - requestTime[i - 20] < 10:
                dropped += 1
            elif i > 59 and requestTime[i] - requestTime[i - 59] < 60:
                dropped += 1 
        return dropped


def main():
    requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 11, 11, 11, 11]
    result = Solution().droppedRequest(requestTime)
    print(result)


if __name__ == "__main__":
    main()

Throttling Gateway (Test #8) Non-critical requests for a transaction system are routed through a throttling  gateway to ensure that the newwork is not choked by non-essential requests.  The gateways has the following limits: * The number of transactions in any given second cannot exceed 3 * The number of transactions in any given 10 second period cannot exceed 20.   A ten-second period includes all requests arriving from any time max(1, t-9) to t   (inclusive of both) for any valid time t. * The number of transactions in any given minute cannot exceed 60.   Similar to above, 1 minute is from max(1, t-59) to t.  Any request that exceeds any of the above limits will be dropped by the gateway. Given the times at which different requests arrive sorted ascending, find how many requests will be dropped.  Note: Even if a request is dropped it is still considered for future calculations. Although, if a request is to be dropped due to multiple violations, it is still counted only once.  Example: n = 27 requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 11, 11, 11, 11] output: 7 Explanation: * Request 1: Not dropped. * Request 1: Not dropped. * Request 1: Not dropped. * Request 1: Dropped. At most 3 requests are allowed in one second. * No request will be dropped till 6 as all comes at an allowed rate of 3 requests per second    and the 10-second clause is also not violated. * Request 7: Not dropped. The total number of requests has reached 20 now. * Request 7: Dropped. At most 20 requests are allowed in ten seconds. * Request 7: Dropped. At most 20 requests are allowed in ten seconds. * Request 7: Dropped. At most 20 requests are allowed in ten seconds.   Note that the 1-second limit is also violated here. * Request 11: Not dropped. The 10-second window has now become 2 to 11.    Hence the 1-second limit is also violated here. * Request 11: Dropped. At most 20 requests are allowed in ten seconds. * Request 11: Dropped. At most 20 requests are allowed in ten seconds. * Request 11: Dropped. At most 20 requests are allowed in ten seconds.   Also, at most 3 requests are allowed per second. Hence, a total of 7 requests are dropped.  Example: n = 21 requestTime = [1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7] output: 2 Explanation: In the first second, 4 requests arrive so one request is dropped. Within 10 seconds, all request times from second 1 to 7, a total of 21 requests arrive. The last request is dropped. The total number of dropped requests is 2. Time complexity : O(n)         Space complexity: O(1)