queue

Question 1

Number of Recent Calls
You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
  It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Answer 1

class RecentCounter:

    def \_\_init\_\_(self):
        self.data = []
        self.head = 0

    def ping(self, t: int) -> int:
        self.data.append(t)
        while (t - self.data[0] > 3000):
            self.data.pop(0)
        return len(self.data)

Question 2

Dota2 Senate

intuition

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

• Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
• Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator’s party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".

Answer 2

1. Create two queues rQueue and dQueue to keep track of the eligible senators separately in sorted order.
2. Populate the queues with the indices of the respective senators from left to right.
3. While both parties have at least one Senator, do the following:

• Pop the Next-Turn Senator index from both queues.
• ONE having larger index will be banned by lower index. Thus, the lower index will again get Turn, so EN-Queue in the same queue with the index/turn increased by N.

4. Return the party name of the queue which is not empty.

Question 3

Dota2 Senate
code

Answer 3

def predictPartyVictory(senate: str) -> str:
    
    # Number of Senator
    n = len(senate)

    # Queues with Senator's Index.
    # Index will be used to find the next turn of Senator
    r_queue = deque()
    d_queue = deque()

    # Populate the Queues
    for i, s in enumerate(senate):
        if s == 'R':
            r_queue.append(i)
        else:
            d_queue.append(i)

    # While both parties have at least one Senator
    while r_queue and d_queue:
        
        # Pop the Next-Turn Senate from both Q.
        r_turn = r_queue.popleft()
        d_turn = d_queue.popleft()

        # ONE having a larger index will be banned by a lower index
        # Lower index will again get Turn, so EN-Queue again
        # But ensure its turn comes in the next round only
        if d_turn < r_turn:
            d_queue.append(d_turn + n)
        else:
            r_queue.append(r_turn + n)
    
    # One's which Empty is not the winner
    return "Radiant" if r_queue else "Dire"