速读摘要文章源自JAVA秀-https://www.javaxiu.com/4612.html
很多人可能准备去一波阿里或者其他大厂，而这些大厂面试过程一般都会有笔试。我当时的题目是实现个LRU，面试官给了接口的定义，然后一些使用方法，以及一些注释说明(下文会有具体题目)。然后在纸上画画图，理一理思路，然后把思路讲出来给面试官听，得到一些反馈。思路得到认可了，那就大胆的写呗，就怕一开始思路就是错的，然后埋头写。当时面试官给的就这么个类，几个未实现的方法，还有个main方法我就没写了，就是使用例子。文章源自JAVA秀-https://www.javaxiu.com/4612.html
原文约 1467 字 | 图片 3 张 | 建议阅读 3 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/4612.html
去年，一道蚂蚁金服笔试题，还行，中等难度
三太子敖丙 文章源自JAVA秀-https://www.javaxiu.com/4612.html
以下文章来源于yes的练级攻略，作者是Yes呀文章源自JAVA秀-https://www.javaxiu.com/4612.html
文章源自JAVA秀-https://www.javaxiu.com/4612.html 文章源自JAVA秀-https://www.javaxiu.com/4612.html yes的练级攻略文章源自JAVA秀-https://www.javaxiu.com/4612.html 用接地气的话来分享一些后端技术或写一些想写的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
最近不是跳槽季嘛，今儿我就来分享一道我之前遇到的笔试题(上机写代码，这里统称笔试)，这道题遇到的几率还是比较高的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
很多人可能准备去一波阿里或者其他大厂，而这些大厂面试过程一般都会有笔试。文章源自JAVA秀-https://www.javaxiu.com/4612.html
不过有很多人可能没经历过笔试，所以我先分享一下我之前去面蚂蚁金服时候的笔试经历。文章源自JAVA秀-https://www.javaxiu.com/4612.html
一般没特意去练练是真的不习惯的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
1
当时我在经历了 1 个多小时的 BB 之后，面试官就让我打开邮箱，会有这么一条邮件。文章源自JAVA秀-https://www.javaxiu.com/4612.html
文章源自JAVA秀-https://www.javaxiu.com/4612.html
邮件里面有网址，打开网址之后，出来的就是这样的界面：文章源自JAVA秀-https://www.javaxiu.com/4612.html
当然现在截图上是没题目的，但真正面试的时候界面上就能看到面试官已经给你准备好的题目。文章源自JAVA秀-https://www.javaxiu.com/4612.html
我当时的题目是实现个 LRU，面试官给了接口的定义，然后一些使用方法，以及一些注释说明（下文会有具体题目）。文章源自JAVA秀-https://www.javaxiu.com/4612.html
一般而言，看个注释和使用方式就可以得知要实现什么东西了。文章源自JAVA秀-https://www.javaxiu.com/4612.html
这里要注意，不理解题目的要问清楚，不要自己瞎理解，不然咱就渐行渐远了。文章源自JAVA秀-https://www.javaxiu.com/4612.html
还有一点要注意，这里写代码是不会联想的，是不会联想的，是不会联想的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
因此所有的类名、方法名都得你一个字母一个字母的敲。文章源自JAVA秀-https://www.javaxiu.com/4612.html
这对于习惯用 IDE 的我们来说，是个致命打击。文章源自JAVA秀-https://www.javaxiu.com/4612.html
你可以试试看看优先队列、锁这些类名能不能敲出来。文章源自JAVA秀-https://www.javaxiu.com/4612.html
其实这些名字还好，打个八九不离十也差不多了，就是一些方法名想不起来就很蛋疼，所以一些常用的还是得注意一下。文章源自JAVA秀-https://www.javaxiu.com/4612.html
如果你实在敲不出来，次一级做法就是和面试官说你得在 idea 里面打。文章源自JAVA秀-https://www.javaxiu.com/4612.html
我之前问过一位在蚂蚁的小姐姐，她说最好是在网页上敲了，网页上敲的话基本上只会看逻辑，不会运行，也不会扣的太细。文章源自JAVA秀-https://www.javaxiu.com/4612.html
如果你拷到 idea 上写的话，那面试官估计得把你代码要拷下来运一运，而且可能会问的比较细。文章源自JAVA秀-https://www.javaxiu.com/4612.html
毕竟网页上写代码，面试官是能实时看到的，idea 可看不到。文章源自JAVA秀-https://www.javaxiu.com/4612.html
基本上就是这个样子了，我当时在网页上写的，面试官顺着逻辑看一遍就 ok 了。文章源自JAVA秀-https://www.javaxiu.com/4612.html
2
再说下笔试的小技巧。文章源自JAVA秀-https://www.javaxiu.com/4612.html
我推荐先和面试官说我能在纸上画画吗？文章源自JAVA秀-https://www.javaxiu.com/4612.html
答案肯定是能。文章源自JAVA秀-https://www.javaxiu.com/4612.html
然后在纸上画画图，理一理思路，然后把思路讲出来给面试官听，得到一些反馈。文章源自JAVA秀-https://www.javaxiu.com/4612.html
毕竟面试是要交流的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
思路得到认可了，那就大胆的写呗，就怕一开始思路就是错的，然后埋头写。文章源自JAVA秀-https://www.javaxiu.com/4612.html
或者没一点思路，埋着头，像线程被阻塞一样。文章源自JAVA秀-https://www.javaxiu.com/4612.html
要注意交流。文章源自JAVA秀-https://www.javaxiu.com/4612.html
至于题目的话，推荐自顶向下的写。文章源自JAVA秀-https://www.javaxiu.com/4612.html
举个经典的例子：排序里面数组交换数据。文章源自JAVA秀-https://www.javaxiu.com/4612.html
int temp = array[j] array[j] = array[j + 1] array[j + 1] = temp 这种一般都会封装成 swap 方法书写的时候就直接先写个 swap 方法，当做已经实现了逻辑，然后之后再补上实现。文章源自JAVA秀-https://www.javaxiu.com/4612.html
这样思路先沿着主线执行完，然后再去完成支线，在面试场景尤为重要，毕竟那时候是紧张的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
这个 swap 可能太简单的感受不到，看看下面的题就能感受到了。文章源自JAVA秀-https://www.javaxiu.com/4612.html
3
回到我之前的那个笔试题，LRU。文章源自JAVA秀-https://www.javaxiu.com/4612.html
至于 LRU 是什么我就不提了，不明白的同学自行查阅下，我们直接看题目。文章源自JAVA秀-https://www.javaxiu.com/4612.html
public class LRUCache<K, V> { public LRUCache() { } public V get(K k) { } public void put(K k, V v) { }}当时面试官给的就这么个类，几个未实现的方法，还有个 main 方法我就没写了，就是使用例子。文章源自JAVA秀-https://www.javaxiu.com/4612.html
现在你可以停下，思考下，你看看这样你能写的出来不？文章源自JAVA秀-https://www.javaxiu.com/4612.html
好了，我贴下答案，这题 LeetCode 上也有的，第 146 题，可以去练练。文章源自JAVA秀-https://www.javaxiu.com/4612.html
public class LRUCache<K,V> { class Node<K,V> { K key; V value; Node<K,V> prev, next; public Node(){} public Node(K key, V value) { this.key = key; this.value = value; } } private int capacity; private HashMap<K,Node> map; private Node<K,V> head; private Node<K,V> tail; public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(capacity); head = new Node<>(); tail = new Node<>(); head.next = tail; tail.prev = head; } public V get(K key) { Node<K,V> node = map.get(key); if (node == null) { return null; } moveNodeToHead(node); return node.value; } public void put(K key, V value) { Node<K,V> node = map.get(key); if (node == null) { if (map.size() >= capacity) { map.remove(tail.prev.key); removeTailNode(); } Node<K,V> newNode = new Node<>(key, value); map.put(key, newNode); addToHead(newNode); } else { node.value = value; moveNodeToHead(node); } } private void addToHead(Node<K,V> newNode) { newNode.prev = head; newNode.next = head.next; head.next.prev = newNode; head.next = newNode; } private void moveNodeToHead(Node<K,V> node) { removeNode(node); addToHead(node); } private void removeNode(Node<K,V> node) { node.prev.next = node.next; node.next.prev = node.prev; } private void removeTailNode() { removeNode(tail.prev); } public static void main(String[] args) { LRUCache<Integer,Integer> lruCache = new LRUCache<>(3); lruCache.put(1,1); lruCache.put(2,2); lruCache.put(3,3); lruCache.get(1); lruCache.put(4,4); System.out.println(lruCache); // toString 我就没贴了，代码太长了 }}这个题目就适合我上面说的自顶向下了。文章源自JAVA秀-https://www.javaxiu.com/4612.html
addToHead、moveNodeToHead、removeNode这几个我建议在主流程写完之前不要实现，把 get、put 写完之后，再实现逻辑，这样比较清晰，也不会乱。文章源自JAVA秀-https://www.javaxiu.com/4612.html
这种，我称之为自顶向下或者 BFS 写法。文章源自JAVA秀-https://www.javaxiu.com/4612.html
LRU还有一种取巧的实现，就是利用LinkedHashMap，继承实现removeEldestEntry方法，这种很简单，不过面试官不会让你用这种的，因为我当时提了哈哈哈。文章源自JAVA秀-https://www.javaxiu.com/4612.html
链表类题目或者二叉树之类的在纸上画画，还是比较容易的。文章源自JAVA秀-https://www.javaxiu.com/4612.html
评论