[type]面试经典

[Alice52]

经典题目

LRU算法

1. 时间复杂度 O(1)
2. 查找时间复杂度 O(1): HashMap
3. 删除嘴久不用元素O(1): LinkedLit: 自己实现双向链表的crud O(1)
4. HashMap + LinkedList ==> LinkedHashMap {删除第一个元素[iterator]}

5. code

   class LRU {
      Map<Integer,Node> map;
       DoubleList cache;
       int cap;
       public int get(int key) {}
       public void put(int key, int value) {}
   }
   class Node {
      int val, key; 
       Node prev, next;
   }
   
   class DouleLinkedList {
       Node dummyHead, dummyTail;
       private int size;
       public DoubleList() {
             head = new Node(0, 0);
             tail = new Node(0, 0);
             head.next = tail;
             tail.prev = head;
             size = 0;
         }
       public void addLast(Node x) {}
       public void remove(Node x) {}
       public Node removeFirst() {}
       public int size() {}
   }

LFU算法

1. 最近最少频率使用
   • 相同频率下淘汰最近最少使用的{LRU}
2. data struct

   // 查询 k-v
   HashMap<Integer, Integer> keyToVal;
   // 指定 key 出现次数
   HashMap<Integer, Integer> keyToFreq;
   // 出现指定次数的有哪些 key: 相等次数则删除第一个
   HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
   // 获取不到最小次数 {除非遍历}
   int minFreq;
   int cap;

3. code

   class LFUCache {
   
       // 查询 k-v
       HashMap<Integer, Integer> keyToVal;
       // 指定 key 出现次数
       HashMap<Integer, Integer> keyToFreq;
       // 出现指定次数的有哪些 key: 相等次数则删除第一个
       HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
       // 获取不到最小次数 {除非遍历}
       int minFreq;
       int cap;
   
       public LFUCache(int capacity) {    }
   
       public int get(int key) {    }
   
       public void put(int key, int value) {    }
   
       private void increaseFreq(int key) {    
            int freq = keyToFreq.get(key);
             // core: minfreq
             if (freqToKeys.get(freq).isEmpty()) {
                // freqToKeys.remove(freq);
                 if (minFreq == freq) {
                     minFreq++;
                 }
             }
       }
   
       private void removeLeastFreq() {    }
   }

[Alice52]

大顶推/小顶推

1. 优先队列