【原创】不想一轮游？大厂面试官教你怎么过笔试_蚂蚁笔试题没做出来

 【背景】：

       面试过几个公司的人都会有笔试经验，不少人有这样的错觉：觉得笔试题挺简单，也做出来了，为啥没有通知面试？其实作为应聘者，一个重要的点需要踩对： 笔试题究竟要考察的是什么点？针对这要考察的点再来审视自己的笔试情况，就知道差距在哪里了。

鉴于这个初衷，想从以下四个角度给你做个参考：

     1.从大厂 2021 年几个真实新鲜笔试题谈如何审题。

     2.从阿里一道笔试题谈最简单的数组也能在笔试中玩出不同的花样。

     3.如果没按要求做出来，笔试还有救场的可能吗？

     4.笔试之后，作为应聘者还需要准备什么？

 

【从大厂 2021 年几个真实新鲜笔试题谈如何审题】

         1）我们先看下今年上半年蚂蚁的一道笔试题：

/**
非常诚挚邀请您参加蚂蚁金服代码评测，请在本地用自己熟悉的语言实现题目，然后在1小时之内回复邮件，内附源码。
请勿上网直接搜答案，因为信任，所以简单~
如有疑问，请及时联系。
实现如下的IP地址黑白名单过滤功能。
*/
public interface IpList {
/**
* 判断指定的ipv4地址是否在当前名单中
* @param ip
* 指定的ip地址值(v4)
* @return true: 在名单中， false: 不在名单中
*/
boolean isInList(String ip);
}
 
/**
要求
1.'isInList'操作为常数级时间复杂度
2.'isInList'内部操作完全基于内存，不得有网络或文件读取; 对象初始化部分如构造函数则不受此限制(如初始化时可从文件中load ip名单列表)
3.让此工具所能支持的ip列表数量尽可能大(甚至能否覆盖整个ipv4地址空间?), 内存占用尽可能小
4.此工具可能在多线程环境被使用
*/
 

从上述题目你看出了什么？我认为你首先应该注意到： 对外只要一个方法， isInList，入参是个String ip ,从这点来说，面试官给你的发挥空间是很大的。为什么这么说？你想 他只约束你 这一个方法，这个方法依赖什么存储，依赖什么内存管理，依赖什么样的IP处理，都是你去决定的，给这种题，我认为公司还是挺尊重候选人的，能让候选人依据自己的特长去选择实现的方法。其次你应该关注什么？肯定是要求啊，4点要求你是怎么理解的？我们一一对标下：

1.'isInList'操作为常数级时间复杂度： 

      这个要求在做IP白名单匹配的时候时间复杂度不能太高啊，常数级是什么意思？就是说不管你的名单数量有多大，你给我常数级别查找，如果是顺序匹配时间复杂度是 n，肯定是不满足要求的。常数级的时间复杂度，你想到了什么？ Hash 表？ 还有什么结构呢？。。。。。。。

2.'isInList'内部操作完全基于内存，不得有网络或文件读取; 对象初始化部分如构造函数则不受此限制(如初始化时可从文件中load ip名单列表)

      这点的要求，你得在初始化时候就把IP名单全部内存化，说明IP的白名单表你可以当做一开始就确定的，重点不会变化来处理，后续的所有操作就用内存进行。其实这点要求是为 第3点要求做准备的，因为要全部内存化，所以你的名单需要占用最少的内存！

3.让此工具所能支持的ip列表数量尽可能大(甚至能否覆盖整个ipv4地址空间?), 内存占用尽可能小

     第三点我想用红色字体表示，这个是整个笔试题的核心，面试官想考核你你有多少众方式来表征 ipv4的地址。然后这些方式里面占用内存最少的是那种方式。如果把这点理解透彻了，那么这道题你就基本心中不虚了。那么ip到底该怎么存储？ 直接用string  存储 “127.0.0.1” ？未免太简单了吧。IP地址是多少位？每个段是8位，4个段是32 位。。。32位对应啥类型，好像有点套路了。

4.此工具可能在多线程环境被使用

        支持多线程是最基本的要求，其实多线程支持有很多种方式： 比如加锁，但是这个就影响性能了。如果不加锁那么你能保证所有对共享内存的都只要读操作，所有新生成的内存对象不会把内存地址给传递到其他线程，那么也是线程安全的。本题你就可以通过不加锁来实现线程安全，但是你要保证共享内存的初始化是能多线程安全的。

如果这套题你能把这些潜在点的要求全部摸清楚，那么我认为审题是OK的。这个过程大概需要15分钟左右（总体时间要求是1个小时），所以需要快速去决定。

2） 我们再看一道题上半年阿里云的笔试题

/**
 * Alipay.com Inc.
 * Copyright (c) 2004-2021 All Rights Reserved.
 */
 //对单链表表示的大数进行求和：1->2->3+4->5=1->6->8 (123+45=168)。

题目要求是不是很简单？其实笔试题都是面试官根据简历的情况筛选不同有针对性的题目，这个题就是个基本的笔试题。但是如果没做过你也是会比较懵逼的。因为你要仔细看他题目的要求。首先从题目你看到哪些信息?

    1) 理解什么叫大数？就是一个可以很大的整型数字

    2）有两个这样的大数，不然怎么相加啊。相加之后肯定会产生一个新的大数，所以你的程序里面涉及3个大数。

    3）这个大数是需要用单链表表示的。单链表就有头和尾，只能从头到位去遍历。头表示的是高位   位表示的是低位。但是常识知道数字相加是从 低位往高位运算的，因为会涉及到满 10 进位啊。所以这个题给的入参并不能满足我们直接运算的要求？怎么办呢？把链表倒序转化下啊。 

    4）经过上述3）之后你就得到最终的结果了吗？这里有个小陷阱，因为你是把入参两个链表给倒序转化的，相加后的链表就是倒序转化之后的结果，而最终的结果是需要按大数格式要求的，链表头还是表征高位，尾表示低位。所以你需要倒序把最终的链表转换一次。

如果你从从上述三点理解题目，那么这个题该怎么做自然也就把握十足了，你要做的是先把入参的两个链表list1  list2  给倒序排列下 得到两个新的链表，然后用心链表顺序遍历做数值相加，得到list3 ，而此时的list3格式 不是按大数格式的，需要把list3 倒序转换下得到最终返回结果。

【从阿里一道笔试题谈最简单的数组也能在笔试中玩出不同的花样】

     之所以想跟大家聊聊数组，就是让大家有个体感，不要眼高手低，数组能实现一些很巧妙的功能。

      我们继续分析蚂蚁上半年的那道笔试题，你知道把 ip v4 地址用 转换为int去表示了，那么存储的时候该怎么搞？无非就是判断一个数在一个集合中存在还是不存在，如果这个数就就对应一个集合的坐标，坐标上的值表示这个数在不在，是否查询的时候更快，比hash表还快，因为是直接按数组下标去查询，不用时间复杂度。如果能分析到这里，你就知道需要用位图去存储Ip地址，可以参考这篇位图是一个二进制数组，用位图之后你就大大缩短了内存占用，以及查询速度。毕竟一个int 数值你只占一个 bit位。

      那么该部分的程序逻辑就是下面这个样子： 

          1）ip的内存名单表征：   用BitSit(二进制的bit数组) ，如果是java 语言得用两个，因为java里面 int 是有符号的，而Ip地址其实是无符号的int。      

          2）内存初始化的时候需要对输入的字符串Ip做 3）步骤操作

                入参的 String  ip  ---->转换为 int ip（32位），然后设置 BitSit里面对应的 ip位为1

          3）isInList方法调用的时候，先把 String ip 转为 int Ip，然后从 bitSit里面查询对应的坐标为Ip的值是否为 1  ，为1 是在白名单里面，否则不在。

       程序大概流程就是上述步骤，从这里你就会发现全部都是围绕数组在组织你的程序，只是数组的类型是bit，你没有用到很高端的数据结构。

 

【如果没按要求做出来，笔试还有救场的可能吗】

       我这里建议，如果你不是简历太牛逼（有些人因为有特殊的项目经验，是由笔试优待的，但是大多数人是没这个待遇的），笔试就不要在搞不出来的时候交白卷。但是你又没按要去想到解法，这时候你该怎么搞？

       1. 首先一点，别直接就说你做不出放弃。这个从态度上就说明你是个轻易放弃的人，大多数公司是喜欢有韧劲的人，能坚持搞定事情的人。你可以跟面试官探讨。有些面试官是愿意给一些暗示性的提醒。但是如果给一些提示性的暗示你还是无解怎么办？

       2. 不排除有些情况就是不能按要求想到解法。我建议你按你会的方式去实现，不管是否符合技术要求，你要做到符合公司的文化要求，用人单位是喜欢有毅力坚持忍耐的人，他们希望找到这样的人：不管在什么情况下，都会想着找到问题的解法，做问题的解决者。

      总之一点：让别人相信你有搞定事情的毅力以及态度，态度决定一切。

【笔试之后，作为应聘者还需要准备什么】

     为啥单独把笔试之后这个环节又提出来。是因为有些人在明明笔试之后，后面的面试环节 面试官反过来又跟他讨论笔试内容，结果由于对笔试解法没做进一步的思考导致了面试过程不理想。

     比如蚂蚁这道面试题，最理想的内存存储方式是 BitSet ，但是你没想到，你用的是 HashMap<Integer,Boolean>  这样的方式去实现。面试官让你笔试过了，因为他觉得你对内存的使用是有一定的基础的（毕竟大多数人的常规套路就是用HashMap），还是有改进空间的。他肯定会在面试环节跟你再讨论下这个问题。而这个时候你还是坚持你的HashMap 存储，这个时候面试官就会觉得你对代码的追求完美度不够。就会打犹豫了，这个时候有另外的候选人，那么你就是被pass掉的那个。

    所以我们在完成笔试题之后，一定要精益求精，去从两个维度思考改进空间： 

    1） 空间能再优化吗？

    2） 时间能再优化吗？

     如果对空间没要求，对时间要求更高，能用空间换时间吗（比如可以增加内存让查找效率更高）？

本次就分享到这里，这里想告诉大家，程序员可能只是把功能实现了，如果是工程师，那就要有一定的追求，精益求精。希望对大家有益。