Huahua’s Tech Road

花花酱 LeetCode 460. LFU Cache

By zxi on September 14, 2017

Problem:

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // returns 1

cache.put(3, 3); // evicts key 2

cache.get(2); // returns -1 (not found)

cache.get(3); // returns 3.

cache.put(4, 4); // evicts key 1.

cache.get(1); // returns -1 (not found)

cache.get(3); // returns 3

cache.get(4); // returns 4

Idea:

Hashtable + balanced search tree

Hashtable + double linked list

Solution 1: O(logc) c is the capacity

// Author: Huahua

// Running time: 99 ms

struct CacheNode {

int key;

int value;

int freq;

long tick;

// Defines the order, smaller one will be evicted first

bool operator <(const CacheNode& rhs) const {

if (freq < rhs.freq) return true;

if (freq == rhs.freq) return tick < rhs.tick;

return false;

}

};

class LFUCache {

public:

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

int get(int key) {

auto it = m_.find(key);

if (it == m_.cend()) 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);

if (it != m_.cend()) {

// Key exists, update value and touch

it->second.value = value;

touch(it->second);

return;

}

if (m_.size() == capacity_) {

// Remove the first node in cache

const CacheNode& node = *cache_.cbegin();

m_.erase(node.key);

cache_.erase(node);

}

CacheNode node{key, value, 1, ++tick_};

m_[node.key] = node;

cache_.insert(node);

}

private:

void touch(CacheNode& node) {

cache_.erase(node); // log(capacity)

++node.freq;

node.tick = ++tick_;

cache_.insert(node); // log(capacity)

}

long tick_;

int capacity_;

unordered_map<int, CacheNode> m_;

set<CacheNode> cache_;

};

Solution 2: O(1)

// Author: Huahua

// Running time: 89 ms (beats 96.3%)

struct CacheNode {

int key;

int value;

int freq;

// pointer to the node in the list

list<int>::const_iterator it;

};

class LFUCache {

public:

LFUCache(int capacity): capacity_(capacity), min_freq_(0) {}

int get(int key) {

auto it = n_.find(key);

if (it == n_.cend()) return -1;

touch(it->second);

return it->second.value;

}

void put(int key, int value) {

if (capacity_ == 0) return;

auto it = n_.find(key);

if (it != n_.cend()) {

// Key already exists, update the value and touch it

it->second.value = value;

touch(it->second);

return;

}

if (n_.size() == capacity_) {

// No capacity, need to remove one entry that

// 1. has the lowest freq

// 2. least recently used if there are multiple ones

// Step 1: remove the element from min_freq_ list

const int key_to_evict = l_[min_freq_].back();

l_[min_freq_].pop_back();

// Step 2: remove the key from cache

n_.erase(key_to_evict);

}

// We know new item has freq of 1, thus set min_freq to 1

const int freq = 1;

min_freq_ = freq;

// Add the key to the freq list

l_[freq].push_front(key);

// Create a new node

n_[key] = {key, value, freq, l_[freq].cbegin()};

}

private:

void touch(CacheNode& node) {

// Step 1: update the frequency

const int prev_freq = node.freq;

const int freq = ++(node.freq);

// Step 2: remove the entry from old freq list

l_[prev_freq].erase(node.it);

if (l_[prev_freq].empty() && prev_freq == min_freq_) {

// Delete the list

l_.erase(prev_freq);

// Increase the min freq

++min_freq_;

}

// Step 4: insert the key into the front of the new freq list

l_[freq].push_front(node.key);

// Step 5: update the pointer

node.it = l_[freq].cbegin();

}

int capacity_;

int min_freq_;

// key -> CacheNode

unordered_map<int, CacheNode> n_;

// freq -> keys with freq

unordered_map<int, list<int>> l_;

};

花花酱 LeetCode 451. Sort Characters By Frequency

By zxi on September 13, 2017

Problem:

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
“tree”

Output:
“eert”

Explanation:
‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:

Input:
“cccaaa”

Output:
“cccaaa”

Explanation:
Both ‘c’ and ‘a’ appear three times, so “aaaccc” is also a valid answer.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:

Input:
“Aabb”

Output:
“bbAa”

Explanation:
“bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.

Idea:

Counting sort

Solution 1:

Sort the string based on element frequency

// Author: Huahua

// Running time: 289 ms

class Solution {

public:

string frequencySort(string& s) {

array<int, 128> f{0};

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

// Author: Huahua

// Running time: 139 ms

class Solution {

public:

string frequencySort(string& s) {

map<char, int> f;

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

string frequencySort(string& s) {

array<int, 128> f{0};

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

Solution 2:

Counting sort

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

string frequencySort(const string& s) {

vector<int> f(128, 0);

for(char c:s) ++f[c];

vector<pair<int,char>> v;

for (int i = 0; i < 128; ++i) {

if (f[i] > 0) v.emplace_back(f[i], i);

}

sort(v.rbegin(), v.rend());

string ans;

for(const auto& kv : v) {

ans.append(kv.first, kv.second);

}

return ans;

}

};

花花酱 LeetCode 332. Reconstruct Itinerary

By zxi on September 12, 2017

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Idea:

Convert the graph to a tree and do post-order traversal

Solution:

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<string> findItinerary(vector<pair<string, string>> tickets) {

route_.clear();

trips_.clear();

for(const auto& pair : tickets)

trips_[pair.first].push_back(pair.second);

for(auto& pair : trips_) {

auto& dests = pair.second;

std::sort(dests.begin(), dests.end());

}

const string kStart = "JFK";

visit(kStart);

return vector<string>(route_.crbegin(), route_.crend());

}

private:

// src -> {dst1, dest2, ..., destn}

unordered_map<string, deque<string>> trips_;

// ans (reversed)

vector<string> route_;

void visit(const string& src) {

auto& dests = trips_[src];

while (!dests.empty()) {

// Get the smallest dest

const string dest = dests.front();

// Remove the ticket

dests.pop_front();

// Visit dest

visit(dest);

}

// Add current node to the route

route_.push_back(src);

}

};

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)

By zxi on September 12, 2017

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) – Add a integer number from the data stream to the data structure.
double findMedian() – Return the median of all elements so far.

For example:

addNum(1)

addNum(2)

findMedian() = 1.5

addNum(3)

findMedian() = 2

Idea:

Min/Max heap
Balanced binary search tree

Time Complexity:

add(num): O(logn)

findMedian(): O(logn)

Solution1:

// Author: Huahua

// Running Time: 152 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder() {}

// l_.size() >= r_.size()

void addNum(int num) {

if (l_.empty() || num <= l_.top()) {

l_.push(num);

} else {

r_.push(num);

}

// Step 2: Balence left/right

if (l_.size() < r_.size()) {

l_.push(r_.top());

r_.pop();

} else if (l_.size() - r_.size() == 2) {

r_.push(l_.top());

l_.pop();

}

double findMedian() {

if (l_.size() > r_.size()) {

return static_cast<double>(l_.top());

} else {

return (static_cast<double>(l_.top()) + r_.top()) / 2;

}

private:

priority_queue<int, vector<int>, less<int>> l_; // max-heap

priority_queue<int, vector<int>, greater<int>> r_; // min-heap

};

Solution 2:

// Author: Huahua

// Running time: 172 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder(): l_(m_.cend()), r_(m_.cend()) {}

// O(logn)

void addNum(int num) {

if (m_.empty()) {

l_ = r_ = m_.insert(num);

return;

}

m_.insert(num);

const size_t n = m_.size();

if (n & 1) {

// odd number

if (num >= *r_) {

l_ = r_;

} else {

// num < *r_, l_ could be invalidated

l_ = --r_;

}

} else {

if (num >= *r_)

++r_;

else

--l_;

}

// O(1)

double findMedian() {

return (static_cast<double>(*l_) + *r_) / 2;

}

private:

multiset<int> m_;

multiset<int>::const_iterator l_; // current left median

multiset<int>::const_iterator r_; // current right median

};

Related Problems

花花酱 LeetCode 146. LRU Cache O(1)

By zxi on September 10, 2017

Problem:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // returns 1

cache.put(3, 3); // evicts key 2

cache.get(2); // returns -1 (not found)

cache.put(4, 4); // evicts key 1

cache.get(1); // returns -1 (not found)

cache.get(3); // returns 3

cache.get(4); // returns 4

Idea:

Use Hashtable for fast mapping and double linked list for fast manipulation.

Time Complexity:

Put O(1)

Get O(1)

Solution:

// 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_;

};

/**

* 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);

Huahua's Tech Road

花花酱 LeetCode 460. LFU Cache

花花酱 LeetCode 451. Sort Characters By Frequency

花花酱 LeetCode 332. Reconstruct Itinerary

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)

花花酱 LeetCode 146. LRU Cache O(1)