Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
of 1 vote

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 {
	std::list<std::pair<int, int>> list_;
	std::unordered_map<int, decltype(list_)::iterator> map_;
	int capacity_;

	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
			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

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

- Chris May 11, 2017 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More