Data structures

641. Design Circular Deque

class MyCircularDeque {
private:
const int k_;
vector<int> q_;
int size_;
int head_;
int tail_;
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k): k_(k), q_(k), size_(0), head_(1), tail_(-1) {}

/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if (isFull())return false;
head_ = (head_-1+k_)%k_;
q_[head_] = value;
if (size_ == 0) tail_=head_;
size_++;
return true;
}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if(isFull())return false;
tail_ = (tail_+1+k_)%k_;
q_[tail_] = value;
if (size_ == 0) head_ = tail_;
size_++;
return true;

}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if(isEmpty())return false;
head_ = (head_+1+k_)%k_;
size_--;
return true;
}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if(isEmpty())return false;
tail_ = (tail_-1+k_)%k_;
size_--;
return true;

}

/** Get the front item from the deque. */
int getFront() {
if(isEmpty())return -1;
return q_[head_];

}

/** Get the last item from the deque. */
int getRear() {
if(isEmpty())return -1;
return q_[tail_];
}

/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return size_==0;
}

/** Checks whether the circular deque is full or not. */
bool isFull() {
return size_==k_;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/

622. Design Circular Queue

// Author: Huahua
// Running time: 20 ms
class MyCircularQueue {
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k): k_(k) {}

/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if (q_.size() == k_) return false;
q_.push_back(value);
return true;
}

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (q_.empty()) return false;
q_.pop_front();
return true;
}

/** Get the front item from the queue. */
int Front() {
if (isEmpty()) return -1;
return q_.front();
}

/** Get the last item from the queue. */
int Rear() {
if (isEmpty()) return -1;
return q_.back();
}

/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return q_.empty();
}

/** Checks whether the circular queue is full or not. */
bool isFull() {
return q_.size() == k_;
}
private:
const int k_;
deque<int> q_;
};
// Author: Huahua
// Running time: 20 ms
class MyCircularQueue {
private:
const int k_;
int size_;
int tail_;
vector<int> q_;
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k): k_(k),size_(0), tail_(-1), q_(k) {}

/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if(isFull())return false;
tail_ = (tail_+1+k_)%k_;
q_[tail_] = value;
size_++;
return true;
}

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (isEmpty())return false;
//tail_ = (tail_+1+k_)%k_;
size_--;
return true;
}

/** Get the front item from the queue. */
int Front() {
if (isEmpty()) return -1;
return q_[(tail_-size_+1+k_)%k_];
}

/** Get the last item from the queue. */
int Rear() {
if (isEmpty()) return -1;
return q_[tail_];
}

/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return size_==0;
}

/** Checks whether the circular queue is full or not. */
bool isFull() {
return size_ == k_;
}
};
// Author: Huahua
class LRUCache {
public:
LRUCache(int capacity) {
capacity_ = capacity;
}

int get(int key) {
const auto it = m_.find(key);
// If key does not exist
if (it == m_.cend()) return -1;

// Move this key to the front of the cache
cache_.splice(cache_.begin(), cache_, it->second);
return it->second->second;
}

void put(int key, int value) {
const auto it = m_.find(key);

// Key already exists
if (it != m_.cend()) {
// Update the value
it->second->second = value;
// Move this entry to the front of the cache
cache_.splice(cache_.begin(), cache_, it->second);
return;
}

// Reached the capacity, remove the oldest entry
if (cache_.size() == capacity_) {
const auto& node = cache_.back();
m_.erase(node.first);
cache_.pop_back();
}

// Insert the entry to the front of the cache and update mapping.
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
}
private:
int capacity_;
list<pair<int,int>> cache_;
unordered_map<int, list<pair<int,int>>::iterator> m_;
};
class LRUCache {
public:
LRUCache(int capacity) : _capacity(capacity) {}

int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1;
touch(it);
return it->second.first;
}

void set(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) touch(it);
else {
if (cache.size() == _capacity) {
cache.erase(used.back());
used.pop_back();
}
used.push_front(key);
}
cache[key] = { value, used.begin() };
}

private:
typedef list<int> LI;
typedef pair<int, LI::iterator> PII;
typedef unordered_map<int, PII> HIPII;

void touch(HIPII::iterator it) {
int key = it->first;
used.erase(it->second.second);
used.push_front(key);
it->second.second = used.begin();
}

HIPII cache;
LI used;
int _capacity;
};
int size;
list<int> lru; // MRU ... LRU
unordered_map<int, list<int>::iterator> mp; // key -> iterator
unordered_map<int, int> kv; // key -> value
LRUCache(int capacity) : size(capacity) {}
int get(int key) {
if (kv.count(key) == 0) return -1;
updateLRU(key);
return kv[key];
}
void put(int key, int value) {
if (kv.size() == size && kv.count(key) == 0)
evict();
updateLRU(key);
kv[key] = value;
}
void updateLRU(int key) {
if (kv.count(key))
lru.erase(mp[key]);
lru.push_front(key);
mp[key] = lru.begin();
}
void evict() {
mp.erase(lru.back());
kv.erase(lru.back());
lru.pop_back();
}
class LRUCache {
private:
int capacity_;
list<pair<int, int>> cache_;
unordered_map<int, list<pair<int, int>>::iterator> m_;
public:
LRUCache(int capacity): capacity_(capacity) {}

int get(int key) {
const auto it = m_.find(key);
//if not find
if(it==m_.cend())return -1;
//if find 1) update list 2) return value
cache_.splice(cache_.begin(), cache_, it->second);
return it->second->second;

}

void put(int key, int value) {
const auto it=m_.find(key);
//if find: update list and update value
if(it != m_.cend()){
it->second->second=value;
cache_.splice(cache_.begin(), cache_, it->second);
//m_[key] = cache_.begin();
return;
}
//if not find
// reach capacity
if(cache_.size()==capacity_){
const auto & node = cache_.back();
m_.erase(node.first);
cache_.pop_back();
}
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

LeetCode 460. LFU Cache

struct CacheNode {
int key;
int value;
int freq;
long tick;
//define the order. Least frequence is smaller. If same frequency, the old will smaller.
bool operator <(const CacheNode & rhs) const {
if(freq<rhs.freq)return true;
if (freq==rhs.freq)return tick<rhs.tick;
return false;
}
};
class LFUCache {
private:
long tick_;
int capacity_;
unordered_map<int, CacheNode> m_;
set<CacheNode> cache_;
void touch(CacheNode & node){
cache_.erase(node);//log(capacity)
++node.freq;
node.tick = ++tick_;
cache_.insert(node); //log(capacity)
}

public:
LFUCache(int capacity) : capacity_(capacity), tick_(0) {}

int get(int key) {
auto it=m_.find(key);
//not find
if (it==m_.end())return -1;
int value = it->second.value;
touch(it->second);
return value;
}

void put(int key, int value) {
if (capacity_==0)return;
auto it=m_.find(key);
//key exists. Update the value and set
if(it!=m_.end()){
it->second.value=value;
touch(it->second);
return;
}
//key not exist
//1) reach the capacity
if(capacity_==m_.size()){
const CacheNode& node = *cache_.cbegin();
m_.erase(node.key);
cache_.erase(node);
}
//2) not reach the capacity
CacheNode node{key, value, 1, ++tick_};
m_[key] = node;
cache_.insert(node);
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

716. Max Stack

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Working with Metrics Server and Horizontal Pod Autoscaling in Kubernetes

Leetcode Series. No 098: Validate Binary Search Tree

How to Handle sigterm in a Docker Entrypoint Script

Weekly Development Update 39 & 40

| Engineering News-Record

Improve Your Coding

Building an Android application using APIs

Creating and Accessing WCF Services

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Dynamic Allocation of Objects Quiz

Boruvka’s Algorithm

LeetCode 110- Balanced Binary Tree

Meta Interview Question Leetcode 121