CareerCup

Q1. use a linked list to keep the order and a hashtable for lookup. place the list-element as value into the hash table, so O(1) from key to list-element to value (see code below)

Q2. Frequency is number of times accessed per time frame. Most simple way would be to use the time the service is running as time frame, so it's just the number of times accessed. It might be tempting to use a priority queue here, but it's not efficient. You can just move the accessed item in the queue up and down according to the Number of times it was accessed - there is a worst case scenario making this algorithm O(cachsize) when a cached item is accessed that I would fix using a skiplist or something the like). Priority queue removes worst case, but average case will be worse, further probably the priority queue must be re-implemented to allow priority change)

Q3. If the cache is occupied by items that were used in high frequency in the past, it might prevent new items from ever getting into the cache. That's tricky but important. Maybe we can give a new item a frequency offset, so it has chances to compete with items that have been used often in the past. This offset will increase over time and eventually overflow. An alternative could be to have two cache generations a current and a next and put new items into the next generation, and items from the current generation move to the next generation after being hit again. after a while, when freeing space we can consequently free space from the current generation... if it's empty, we can start over again, just like life ;-)

class LRUCache {
private:
	std::list<std::pair<int, int>> list_;
	std::unordered_map<int, decltype(list_)::iterator> map_;
	int capacity_;

public:
	LRUCache(int capacity) : capacity_(capacity) { }

	int get(int key) { return getValueInFrontIfExists(key); }

	void put(int key,int value) {
		if (getValueInFrontIfExists(key) != -1) { // key existed, patch value
			list_.front().second = value;
		} else { // key does not exist, add to list and map
			list_.push_front(std::pair<int,int>(key,value));
			map_[key] = list_.begin();
			if (list_.size() > capacity_) { // capacity exceeded, remove least used
				map_.erase(list_.back().first); // patch map first
				list_.pop_back(); // remove least used element
			}
		}
	}

private:
	// gets the value and moves value to front of list if exists otherwise returns -1
	int getValueInFrontIfExists(int key) {
		auto it = map_.find(key);
		if (it != map_.end()) {			
			int value = it->second->second; // get the value
			list_.splice(list_.begin(), list_, it->second);
			return value;
		}
		return -1;
	}
};