写点什么

去年,蚂蚁一面的一道笔试题,中等难度

发布于: 2021 年 03 月 13 日
去年,蚂蚁一面的一道笔试题,中等难度

你好,我是 yes。


最近不是跳槽季嘛,今儿我就来分享一道我之前遇到的笔试题(上机写代码,这里统称笔试),这道题遇到的几率还是比较高的。


很多人可能准备去一波阿里或者其他大厂,而这些大厂面试过程一般都会有笔试。


不过有很多人可能没经历过笔试,所以我先分享一下我之前面蚂蚁金服时候的笔试经历。


一般没特意去练练是真的不习惯的


1


当时我在经历了 1 个多小时的 BB 之后,面试官就让我打开邮箱,会有这么一条邮件。



邮件里面有网址,打开网址之后,出来的就是这样的界面:


当然现在截图上是没题目的,但真正面试的时候界面上就能看到面试官已经给你准备好的题目。


我当时的题目是实现个 LRU,面试官给了接口的定义,然后一些使用方法,以及一些注释说明。


一般而言,看个注释和使用方式就可以得知要实现什么东西了。


这里要注意,不理解题目的要问清楚,不要自己瞎理解,不然咱就渐行渐远了。


​还有一点要注意,这里写代码是不会联想的,是不会联想的,是不会联想的


因此所有的类名、方法名都得你一个字母一个字母的敲。


这对于习惯用 IDE 的我们来说,是个致命打击


你可以试试看看优先队列、锁这些类名能不能敲出来。


其实这些名字还好,打个八九不离十也差不多了,就是一些方法名想不起来就很蛋疼,所以一些常用的还是得注意一下。


如果你实在敲不出来,次一级做法就是和面试官说你得在 idea 里面打。


我之前问过一位在蚂蚁的小姐姐,她说最好是在网页上敲了,网页上敲的话基本上只会看逻辑,不会运行,也不会扣的太细。


如果你拷到 idea 上写的话,那面试官估计得把你代码要拷下来运一运,而且可能会问的比较细。


毕竟网页上写代码,面试官是能实时看到的,idea 可看不到


基本上就是这个样子了,我当时在网页上写的,面试官顺着逻辑看一遍就 ok 了。


2

再说下笔试的小技巧


我推荐先和面试官说我能在纸上画画吗?答案肯定是能。


然后在纸上画画图,理一理思路,然后把思路讲出来给面试官听,得到一些反馈


毕竟面试是要交流的。


思路得到认可了,那就大胆的写呗,就怕一开始思路就是错的,然后埋头写。


或者没一点思路,埋着头,像线程被阻塞一样。


要注意交流


至于题目的话,推荐自顶向下的写。


举个经典的例子:排序里面数组交换数据。


	int temp = array[j]                    array[j] = array[j + 1]                    array[j + 1] = temp      这种一般都会封装成 swap 方法
复制代码

书写的时候就直接先写个 swap 方法,当做已经实现了逻辑,然后之后再补上实现。


这样思路先沿着主线执行完,然后再去完成支线,在面试场景尤为重要,毕竟那时候是紧张的。


这个 swap 可能太简单的感受不到,看看下面的题就能感受到了。


3

回到我之前的那个笔试题,LRU。


至于 LRU 是什么我就不提了,不明白的同学自行查阅下,我们直接看题目。


public class LRUCache<K, V> {    public LRUCache() {    }      public V get(K k) {    }    public void put(K k, V v) {    }}
复制代码

当时面试官给的就这么个类,几个未实现的方法,还有个 main 方法我就没写了,就是使用例子。


现在你可以停下,思考下,你看看这样你能写的出来不?


好了,我贴下答案,这题 LeetCode 上也有的,第 146 题,可以去练练。

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 我就没贴了,代码太长了 }}
复制代码


这个题目就适合我上面说的自顶向下了。


addToHeadmoveNodeToHeadremoveNode这几个我建议在主流程写完之前不要实现,把 get、put 写完之后,再实现逻辑,这样比较清晰,也不会乱


这种,我称之为自顶向下或者 BFS 写法


LRU 还有一种取巧的实现,就是利用LinkedHashMap,继承实现removeEldestEntry方法,这种很简单,不过面试官不会让你用这种的,因为我当时提了哈哈哈。


链表类题目或者二叉树之类的在纸上画画,还是比较容易的。


最后

题目就分享到这儿了。


更多内容,欢迎关注我的公众号【yes 的练级攻略】,每周保证至少分享一篇原创技术文。





我是 yes,从一点点到亿点点,欢迎在看、转发、留言,我们下篇见


发布于: 2021 年 03 月 13 日阅读数: 34
用户头像

分享后端技术干货,驰骋技术的江湖。 2019.01.17 加入

公众号「yes的练级攻略」

评论

发布
暂无评论
去年,蚂蚁一面的一道笔试题,中等难度