花花酱 LeetCode 895. Maximum Frequency Stack

By zxi on August 26, 2018

Problem

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

push(int x), which pushes an integer x onto the stack.
pop(), which removes and returns the most frequent element in the stack.
- If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
The total number of FreqStack.push calls will not exceed 10000 in a single test case.
The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

Solution 1: Buckets

We have n stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x) # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 144 ms

class FreqStack {

public:

FreqStack() {}

void push(int x) {

auto it = freq_.find(x);

if (it == freq_.end())

it = freq_.emplace(x, 0).first;

int freq = ++it->second;

if (stacks_.size() < freq) stacks_.push_back({});

stacks_[freq - 1].push(x);

}

int pop() {

int x = stacks_.back().top();

stacks_.back().pop();

if (stacks_.back().empty())

stacks_.pop_back();

auto it = freq_.find(x);

if (!(--it->second))

freq_.erase(it);

return x;

}

private:

vector<stack<int>> stacks_;

unordered_map<int, int> freq_;

};

Solution2: Priority Queue

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 132 ms

class FreqStack {

public:

FreqStack() {}

void push(int x) {

int key = (++f_[x] << 16) | (++seq_);

q_.emplace(key, x);

}

int pop() {

int x = q_.top().second; q_.pop();

if (--f_[x] == 0)

f_.erase(x);

return x;

}

private:

int seq_ = 0;

unordered_map<int, int> f_; // {x -> freq}

priority_queue<pair<int, int>> q_; // {freq | seq_, x}

};

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Solution: Math

Time complexity: O(49/40) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int target = 40;

while (target >= 40)

target = 7 * (rand7() - 1) + (rand7() - 1);

return target % 10 + 1;

}

};

Time complexity: O(7/6 + 7 / 5) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int i = INT_MAX;

int j = INT_MAX;

while (i > 6) i = rand7(); // i = [1, 2, 3, 4, 5, 6]

while (j > 5) j = rand7(); // j = [1, 2, 3, 4, 5]

return j + 5 * (i & 1);

}

};

花花酱 LeetCode 622. Design Circular Queue

By zxi on July 12, 2018

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

MyCircularQueue(k): Constructor, set the size of the queue to be k.
Front: Get the front item from the queue. If the queue is empty, return -1.
Rear: Get the last item from the queue. If the queue is empty, return -1.
enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
isEmpty(): Checks whether the circular queue is empty or not.
isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Queue library.

Solution: Simulate with an array

We need a fixed length array, and the head location as well as the size of the current queue.

We can use q[head] to access the front, and q[(head + size – 1) % k] to access the rear.

Time complexity: O(1) for all the operations.
Space complexity: O(k)

C++

// Author: Huahua

class MyCircularQueue {

public:

MyCircularQueue(int k): q_(k) {}

bool enQueue(int value) {

if (isFull()) return false;

q_[(head_ + size_) % q_.size()] = value;

++size_;

return true;

}

bool deQueue() {

if (isEmpty()) return false;

head_ = (head_ + 1) % q_.size();

--size_;

return true;

}

int Front() { return isEmpty() ? -1 : q_[head_]; }

int Rear() { return isEmpty() ? -1 : q_[(head_ + size_ - 1) % q_.size()]; }

bool isEmpty() { return size_ == 0; }

bool isFull() { return size_ == q_.size(); }

private:

vector<int> q_;

int head_ = 0;

int size_ = 0;

};

Java

class MyCircularQueue {

private int[] q;

private int head;

private int size;

public MyCircularQueue(int k) {

this.q = new int[k];

this.head = 0;

this.size = 0;

}

public boolean enQueue(int value) {

if (this.isFull()) return false;

this.q[(this.head + this.size) % this.q.length] = value;

++this.size;

return true;

}

public boolean deQueue() {

if (this.isEmpty()) return false;

this.head = (this.head + 1) % this.q.length;

--this.size;

return true;

}

public int Front() {

return this.isEmpty() ? -1 : this.q[this.head];

}

public int Rear() {

return this.isEmpty() ? -1 : this.q[(this.head + this.size - 1) % this.q.length];

}

public boolean isEmpty() { return this.size == 0; }

public boolean isFull() { return this.size == this.q.length; }

}

Python3

class MyCircularQueue:

def __init__(self, k: int):

self.q = [0] * k

self.k = k

self.head = self.size = 0

def enQueue(self, value: int) -> bool:

if self.isFull(): return False

self.q[(self.head + self.size) % self.k] = value

self.size += 1

return True

def deQueue(self) -> bool:

if self.isEmpty(): return False

self.head = (self.head + 1) % self.k

self.size -= 1

return True

def Front(self) -> int:

return -1 if self.isEmpty() else self.q[self.head]

def Rear(self) -> int:

return -1 if self.isEmpty() else self.q[(self.head + self.size - 1) % self.k]

def isEmpty(self) -> bool:

return self.size == 0

def isFull(self) -> bool:

return self.size == self.k

Posts published in “Desgin”

花花酱 LeetCode 895. Maximum Frequency Stack

Problem

Solution 1: Buckets

C++

Solution2: Priority Queue

C++

Related Problems

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

Problem

Solution: Math

花花酱 LeetCode 622. Design Circular Queue

Solution: Simulate with an array

C++

Java

Python3