359. Logger Rate Limiter

Leetcode Link

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed{" "} at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

Logger() Initializes the logger object.
bool shouldPrintMessage(int timestamp, string message){" "} Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

    Input
    {"\n"}["Logger", "shouldPrintMessage", "shouldPrintMessage",
    "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage",
    "shouldPrintMessage"]{"\n"}[[], [1, "foo"], [2, "bar"], [3, "foo"], [8,
    "bar"], [10, "foo"], [11, "foo"]]{"\n"}
    Output
    {"\n"}[null, true, true, false, false, false, true]{"\n"}
    {"\n"}
    Explanation
    {"\n"}Logger logger = new Logger();{"\n"}logger.shouldPrintMessage(1,
    "foo");{"  "}// return true, next allowed timestamp for "foo" is 1 + 10 = 11
    {"\n"}logger.shouldPrintMessage(2, "bar");{"  "}// return true, next allowed
    timestamp for "bar" is 2 + 10 = 12{"\n"}logger.shouldPrintMessage(3, "foo");
    {"  "}// 3 < 11, return false{"\n"}logger.shouldPrintMessage(8, "bar");
    {"  "}// 8 < 12, return false{"\n"}logger.shouldPrintMessage(10, "foo");
    // 10 < 11, return false{"\n"}logger.shouldPrintMessage(11, "foo"); // 11
    >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21
    {"\n"}

Constraints:

0 <= timestamp <= 10⁹
Every timestamp will be passed in non-decreasing order (chronological order).
1 <= message.length <= 30
At most{" "} 10⁴{" "} calls will be made to shouldPrintMessage.

Solution

Naive Solution

We can store a list of all previous (timestamp, message) pairs. In each call, we loop through the list to get the most recent time message was logged and check if it was within 10 seconds of timestamp. Let $n$ be the number of times shouldPrintMessage is called. Checking through the list takes $\mathcal{O}(n)$ , so we take $\mathcal{O}(n^2)$ in total. Our list has size $n$ , taking $\mathcal{O}(n)$ space. This is fast enough, but we can do better.

Faster Solution

We use a hashmap that maps messages to their most recent timestamps. Retrieving/assigning hashmap[message] takes $\mathcal{O}(1)$ , so we take $\mathcal{O}(n)$ in total. We also take $\mathcal{O}(n)$ space (in the worst case, every message is different, so all of them need to be inserted into the hashmap).

C++ Solution

1class Logger {
2public:
3    unordered_map<string, int> lastTime;
4    bool shouldPrintMessage(int timestamp, string message) {
5        if (lastTime.count(message) and timestamp - lastTime[message] < 10)
6            return false;
7        lastTime[message] = timestamp;
8        return true;
9    }
10};
11
12/**
13 * Your Logger object will be instantiated and called as such:
14 * Logger* obj = new Logger();
15 * bool param_1 = obj->shouldPrintMessage(timestamp,message);
16 */

Java Solution

1class Logger {
2    HashMap<String, Integer> lastTime;
3    public Logger() {
4        lastTime = new HashMap<>();
5    }
6    public boolean shouldPrintMessage(int timestamp, String message) {
7        if (timestamp - lastTime.getOrDefault(message, -100) < 10)
8            return false;
9        lastTime.put(message, timestamp);
10        return true;
11    }
12}
13
14/**
15 * Your Logger object will be instantiated and called as such:
16 * Logger obj = new Logger();
17 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
18 */

Python Solution

1class Logger:
2    def __init__(self):
3        self.lastTime = dict()
4    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
5        if message in self.lastTime and timestamp - self.lastTime[message] < 10:
6            return False
7        self.lastTime[message] = timestamp
8        return True
9
10# Your Logger object will be instantiated and called as such:
11# obj = Logger()
12# param_1 = obj.shouldPrintMessage(timestamp,message)

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Solution Implementation

Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

359. Logger Rate Limiter

Solution

Naive Solution

Faster Solution

C++ Solution

Java Solution

Python Solution

Solution Implementation

Recommended Readings