Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Use LinkedHashMap. The JavaDoc has an implementation of Simple Cache

- Chander Shivdasani October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It would be good to point out that something like LinkedHashMap can do the job. But since its a interview better to discuss using a hashmap and a DLL to do the job.

- kingKode October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It can be implemented with hash table and linked list. Nice document at: eli.thegreenplace.net/files/docs/forays/col8.html

- Kallu October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

_Map_ into node addresses of a self organizing (e.g. "Move to Front") doubly linked list.

- S O U N D W A V E October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ implementation of a LRU cache. All operations are O(1).

#include <iostream>
#include <unordered_map>
#include <list>
#include <stdexcept>

template <typename K, typename V>
class lru_cache {
private:
	typedef std::pair<K, V> cache_entry;
	typedef std::list<cache_entry> cache_list;
	typedef std::unordered_map<K, typename cache_list::iterator> cache_map;
	
public:
	typedef typename cache_list::iterator iterator;
	typedef typename cache_list::const_iterator const_iterator;
	
	lru_cache(size_t size) : size_(size) {
		cache_map_.reserve(size_);
	}
	
	void add(const K& key, const V& value) {
		if (cache_map_.size() >= size_)
			remove_eldest();
		
		auto map_it = cache_map_.find(key);
		if (map_it == cache_map_.end()) {
			// Add element to list and save iterator on map
			auto list_it = cache_list_.insert(cache_list_.begin(), std::make_pair(key, value));
			cache_map_.emplace(key, list_it);
		} else {
			// Copy entry from list
			auto& list_it = map_it->second;
			cache_entry entry = *list_it;
			
			// Remove entry from list
			cache_list_.erase(list_it);
			
			// Update entry and add to beginning of the list
			entry.second = value;
			cache_list_.push_front(entry);
		}
	}
	
	V remove(const K& key) {
		auto map_it = cache_map_.find(key);
		if (map_it == cache_map_.end())
			throw std::runtime_error("key not found");

		auto& list_it = map_it->second;
		cache_map_.erase(map_it);
		cache_entry entry = *list_it;
		cache_list_.erase(list_it);
		return entry.second;			
	}

	V remove_eldest() {
		if (cache_map_.empty())
			throw std::runtime_error("cache is empty");
			
		cache_entry entry = cache_list_.back();
		cache_map_.erase(entry.first);
		cache_list_.pop_back();
		return entry.second;
	}
	
	iterator begin() {
		return cache_list_.begin();
	}

	iterator end() {
		return cache_list_.end();
	}

	const_iterator cbegin() const {
		return cache_list_.cbegin();
	}

	const_iterator cend() const {
		return cache_list_.cend();
	}
	
	size_t size() const {
		return cache_map_.size();
	}
	
	bool empty() const {
		return cache_map_.empty();
	}
	
private:
	size_t size_;
	cache_map cache_map_;
	cache_list cache_list_;
};

int main() {
	lru_cache<std::string, int> cache(3);
	cache.add("one", 1);
	cache.add("two", 2);
	cache.add("three", 3);
	cache.add("four", 4);
	std::cout << cache.size() << std::endl;
	std::cout << cache.remove("four") << std::endl;
	std::cout << cache.size() << std::endl;

	for (const auto& p : cache)
		std::cout << p.first << " = " << p.second << std::endl;
		
	return 0;
}

- Diego Giagio November 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Won't LinkedHashMap degrade to a linked list though? (all hashes are the same) Which will be O(N) for remove.

Is removeCache just supposed to remove the last recently used item or a specific item? Is the cache supposed to hold a finite number of elements? Is it OK to have a really poor space complexity, reducing the number of elements the cache can hold?

- shinsetsu October 15, 2013 | Flag Reply


Add a Comment
Name:

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

Books

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

Videos

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