让我们使用 LRU 缓存机制构建 Spotify 的“最近搜索”功能。微软面试题。
什么是LRU？为什么要使用LRU？
当我们在 Spotify 上搜索歌曲时，你最近的所有搜索记录都会保存在“最近搜索”列表中。让我们看看如何实现类似的功能。
了解需求
让我们来看看Spotify“最近搜索”组件的所有功能。1
> 搜索歌曲：
当你搜索一首歌时，这首歌会列在最近的搜索记录中，由于列表为空，所以 Coldplay 被添加到了第一个列表中。
2> 正在搜索更多歌曲：
当你搜索更多歌曲时，列表会不断增长，歌曲也会被添加到列表中。
让我们把清单填满：
观察结果：当我们搜索某个内容时，它会被添加到列表的最前面。
3> 当列表已满时搜索歌曲：
当我们搜索且列表已满时，第一首歌（即 Coldplay）由于排在列表末尾而被删除。
这里我们第一次看到了LRU缓存。LRU
是最近最少使用（Least Recent Use）的缩写。由于我们最初搜索了Coldplay，但之后没有再次搜索，它就被移到了列表的末尾，成为使用频率最低的组件，因此从列表中移除。
随着我们深入探讨，这个概念会逐渐清晰。
4> 从列表中删除：
这里我们从列表中删除了棉花糖，但相对顺序保持不变。
5> 搜索的歌曲已存在于列表中：
名单上原本有艾伦·沃克，但我们搜索了一下，所以艾伦·沃克的卡片被移到了前面。
什么是LRU？它有什么用？
首先，什么是缓存？
缓存本质上是一种存储介质，可以实现高速读写功能。
什么是缓存机制？
缓存机制是一组能够提升读写速度的操作。由于缓存容量有限，因此使用能够充分利用有限缓存并高效存储数据的最佳缓存机制至关重要。
你可能对这个很熟悉：
什么是LRU？为什么要使用LRU？
LRU 是一种缓存机制，它执行以下操作：
1> 当缓存已满时，将最少使用的项移出缓存。2
> 如果某个项被频繁访问，则将其移到缓存前端，以利用其更快的读写速度。3
> 对缓存项执行相关的删除和更新操作。
主要限制条件是所有操作必须在 O(1) 时间内完成。
我觉得 Spotify 的例子可能有点令人困惑，请考虑以下情况。
你暗恋的女孩要来你家，你想给她留下好印象，于是决定用你的厨艺给她烤披萨。你决定去市场买披萨的食材，顺便也买了鸡蛋和牛奶做早餐。
我们将购物车视为我们的储物柜，它可以容纳 5 件物品。
让我们来看看我们执行的操作，请在新标签页中打开图片并放大，然后逐一查看不同的LRU操作：
现在你知道了什么是 LRU，为什么要使用它，它有哪些应用，让我们来编写代码吧！
要求：设计一个组件/LRU，使其满足以下性能要求：
1> 添加项目的时间复杂度为 O(1)。2
> 溢出时移除项目的时间复杂度为 O
(1)。3> 删除项目的时间复杂度为 O(1)。4
> 获取项目的时间复杂度为 O(1)。5
> 更新项目的时间复杂度为 O(1)。
数据结构
哈希表看起来是个不错的选择，但它不是列表，它不会保持元素之间的顺序。
💡 何不将两种数据结构结合起来呢？
哈希表唯一的问题是顺序问题，所以让我们将数据结构与哈希表结合起来，以满足我们的需求。
正如你可能已经猜到的那样，栈/队列/树与哈希表配合使用效果并不理想。
为了简化操作，我们将使用双向链表而不是单向链表，这样删除操作会快得多。
1> 让我们来构建双向链表：
class DLL {
int key; // stores the key which we will use to reference the item
int val; // stores the actual information
DLL prev; // Points towards previous item
DLL next; // points towards next item
}
2> 让我们来构建缓存结构：
Map<Integer,DLL> cache = new HashMap<>();
我们将创建键到节点的映射。
由于这是我们自定义的双向链表，我们将创建两个节点：头节点和尾节点。这两个节点将帮助我们添加和删除元素。
3> 让我们来构建我们的运营体系。
运营 ：
movetohead 是以下几种常见方法之一：
add()：创建一个节点并将其移动到头节点；
get()：使用哈希表检查给定的键是否存在，如果存在则将其移动到头节点。
这些函数中，delete 函数很常见：
delete()：从其位置移除节点并将其丢弃；
popTail()：移除尾部的节点并将其丢弃。
棘手之处：
update()：当我们更新一个节点时，
1> 我们会将其从列表中的原位置移除。2
> 我们会将其移动到头节点。
一些可视化示例：
（抱歉画质不好，请推荐一个好用的GIF制作网站）
首先，让我们编写一些函数，借助这些函数我们将与缓存进行交互。
// add a new item
public void add(int key,int value){
DLL node = new DLL();
node.key = key;
node.val = value;
this.moveToHead(node);
}
// get a item
public int get(int key){
DLL node = cache.get(key);
if(node == null){
return -1;
}else{
this.moveToHead(node);
return node.val;
}
}
// delete a item
public boolean delete(int key){
DLL node = cache.get(key);
if(node == null) return false;
this.deleteNode(node);
return true;
}
//pop from tail
public void popTail(){
DLL nodeToBeRemove = tail.prev;
DLL newTail = nodeToBeRemove.prev;
newTail.next = tail;
tail.prev = newTail;
}
//update an item
public boolean update(int key,int value){
DLL node = cache.get(key);
if(node == null){
return false;
}else{
node.val = value;
this.deleteNode(node);
this.moveToHead(node);
return true;
}
}
现在让我们编写一些函数来帮助我们处理缓存。
public void deleteNode(DLL node){
DLL next = node.next;
DLL prev = node.prev;
next.prev = prev;
prev.next = next;
}
public void moveToHead(DLL node){
DLL next = head.next;
head.next = node;
node.prev = head;
node.next = next;
next.prev = node;
}
现在我们已经有了所有必需的功能，让我们把它们整合在一起：
class LRUCache {
class DLL{
int val;
int key;
DLL next;
DLL prev;
}
public void moveToHead(DLL node){
DLL next = head.next;
head.next = node;
node.next = next;
next.prev = node;
node.prev = head;
}
public void deleteNode(DLL node){
DLL prev = node.prev;
DLL next = node.next;
prev.next = next;
next.prev = prev;
}
DLL head;
DLL tail;
Map<Integer,DLL> map;
int count;
int capacity;
public LRUCache(int capacity) {
map = new HashMap<>();
this.count = 0;
this.capacity = capacity;
head = new DLL();
tail = new DLL();
head.prev = null;
head.next = tail;
tail.prev = head;
tail.next = null;
}
public int get(int key) {
DLL node = map.get(key);
if(node == null) return -1;
this.moveToHead(node);
return node.val;
}
public void add(int key,int value){
DLL node = cache.get(key);
if(node != null){
this.update(key,value);
}else{
node = new DLL();
node.key = key;
node.val = value;
this.moveToHead(node);
}
public boolean delete(int key){
DLL node = cache.get(key);
if(node == null) return false;
this.deleteNode(node);
cache.remove(key);
return true;
}
public void popTail(){
DLL nodeToBeRemove = tail.prev;
DLL newTail = nodeToBeRemove.prev;
newTail.next = tail;
tail.prev = newTail;
cache.remove(nodeToBeRemove.key);
}
public boolean update(int key,int value){
DLL node = cache.get(key);
if(node == null){
return false;
}else{
node.val = value;
this.deleteNode(node);
this.moveToHead(node);
return true;
}
}
}
就是这样！这就是完整的LRU算法实现。我们的版本是模块化的，如果不需要某个功能，可以轻松移除。
Spotify 最近的搜索组件只实现了添加、删除和弹出尾音功能。为了完整性，我们实现了其余功能。
希望这个解释对您有帮助！非常感谢您读到这里。
如果我犯了任何错误或者您有任何疑问，请留言。
文章来源：https://dev.to/akhilpokle/let-s-build-spotify-s-recent-search-functionity-with-lru-caching-mechanism-microsoft-interview-question-5che