Easy

933. Number of Recent Calls

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now. Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Thought process:

  • If we store the timestamps of history pings, they are FIFO, thus we should use a queue.
class RecentCounter:
    def __init__(self):
        self.queue = deque()        

    def ping(self, t: int) -> int:
        queue = self.queue
        queue.append(t)
        while queue and queue[0] < t - 3000: queue.popleft()
        return len(queue)

346. Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Thought process:

  • Use a fix size queue to store the window of numbers.
  • Use a accumulator for the moving sum of the window.
class MovingAverage:
    def __init__(self, size: int):
        self.queue = deque(maxlen=size)
        self.total = 0

    def next(self, val: int) -> float:
        if len(self.queue) == self.queue.maxlen: self.total -= self.queue.popleft()
        self.queue.append(val)
        self.total += val
        return self.total / len(self.queue)

Medium

582. Kill Process

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Thought process:

  • Construct the adjacency list from parent to childrens.
  • Initialize a queue with the kill node on it, basically do bfs and kill the entire subtree from it.
def killProcess(pid, ppid, kill):
    edges = defaultdict(list)
    for p, c in zip(ppid, pid): edges[p].append(c)

    killed = []
    queue = deque([kill])
    while queue:
        p = queue.popleft()
        killed.append(p)
        queue.extend(edges[p])
    return killed