Is LinkedHashMap possible?


  • 2
    S

    I used LinkedHashMap to implement Cache but OJ doesn't support this API. I think it is much simpler than creating a doubleLinkedList.


  • 1
    S

    Seems it is a hacky way, and will forbid in real interview.


  • 0
    Z

    Hi, I used LinkedHashMap to solve this (with inheritance).

    Did you include import directive?


  • 0
    X
    This post is deleted!

  • 0

    You can use LinkedHashMap in Java to solve this problem, but I can assure you that it will not be allowed in a technical interview.

    http://oj.leetcode.com/discuss/1188/java-is-linkedhashmap-considered-cheating


  • 3
    S

    My C++ O(1) solution uses a hash table and a list separately, yet may functions as a LinkedHashMap. Hash table is implemented as unordered_map keeps <key, iterator of list member>. So when we need to delete any key (i.e., when update an existing key in get() ), we can do it in constant time. While set() function can pop up from the list<key, value> when reaches to max size, in constant time, and we need to remove the corresponding key from hash table, which is also constant.

    class LRUCache{ 
        public:
            LRUCache(int capacity) {
                max_size = capacity;
                cur_size = 0;
            }
            
            int get(int key) {
                auto it = cache_map.find(key);
                if (it != cache_map.end()) {
                    // update queue
                    int value = it->second->second;
                    cache_list.erase(it->second);
                    cache_map[key] = cache_list.insert(cache_list.end(), make_pair(key, value));
                    return value;
                }
                else
                    return -1;
            }
            
            void set(int key, int value) {
                if (get(key) < 0) {
                    // no such key, do insertion
                    if (cur_size == max_size) {
                        int old = cache_list.front().first;
                        cache_list.pop_front();
                        cache_map.erase(old);
                    }
                    else
                        cur_size++;
                    cache_list.push_back(make_pair(key, value));
                }
                cache_list.pop_back();
                
                // here we play a trick to get the iterator of the queue back
                cache_map[key] = cache_list.insert(cache_list.end(), make_pair(key, value));
            }
            
        private:
            int cur_size;
            int max_size;
            unordered_map<int, list<pair<int, int> >::iterator> cache_map; // key + list iterator
            list<pair<int, int> > cache_list; // key + values
        };

  • 0
    K

    In c++ you have iterator which are not invalidated when inserting or deleting new element in list. Hence you can get reference to that node in O(1) step. But is it possible in java


  • 0
    D
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.