链家-大数据开发（机器学习方向）-笔试+1面

总结记录下自己的面试经历，大家共勉。

1. 笔试

笔试一共1个小时，5道编程题，现场手撸代码还是第一次，感觉还是时间还是有些紧张的。

1）给定一个数组，其中有一个数的出现次数超过数组长度的一半，要求找出这个数，空间复杂度和时间复杂度尽量低。

我的思路是对数组排序，那么要求的数就在排序后数组长度的一半处。这样没有使用额外空间，时间复杂度主要看排序的时间复杂度，我用的java.util.Arrays类中的Arrays.sort()方法，感觉是O(nlogn)

2）4类括号{}, [], (), <>，括号的出现规则是只能嵌套，不能交叉，例如{1,2}[a(b)]就是合法的，而{a)}就是不合法的。要求判断给定字符串中括号的使用是否合法。

我的思路是分别利用4个整型变量来记录4类括号的出现情况，遍历字符串，如果出现左括号，就将对应变量加1，如果出现右括号，就将对应的变量减一，如果这4个变量有任何一个小于0，那么就有不合法的括号，结束遍历。

3）一串珠子A，有m个珠子，n种不同颜色（n<m），要求子串B中包含所有的颜色，求子串B的长度最小是多少？

我用了双指针，i从前往后，j从后往前， i往后走，B为A中从i到j的子串，如果B中包含A中i处的珠子颜色，那么i继续往后走，直到B中不包含为止，然后j开始往前走，类似的，如果B中包含A中j处的珠子颜色，那么j继续往前走，否则停止。此时B的长度最小。

4）Web日志记录了IP和访问时间，恶意攻击指某一IP在时间t内（如10分钟内）连续访问的次数超过n次（如1024次），要求给定的Web日志中恶意攻击的IP地址。

这个题没来得及写，在面试的时候说了暴力的解法，用Map<IP, List<访问时间>>来存储，如果对应IP的List的size小于n，那么肯定不是恶意攻击，如果大于n，那么就从List的第一个元素开始遍历，元素的下标索引表示截止到该访问时间为止，一共有多少次访问。那么从头开始遍历，当遍历到第i个元素的时候，得到第(i+n)元素处的访问时间，如果两个时间相隔大于t，那么继续遍历，否则该IP存在恶意攻击。然后面试官说有两个问题：① 时间复杂度是多少？然后就知道面试官肯定不满意这个答案；② 两天前的日志怎么办？这个问题就真的没考虑过了。。。

5）程序引入的第三方库多了，就可能会有循环依赖，要求找出循环依赖的模块。

这个只知道是要找有向图中的环，从A出发能否再回到节点A，代码就写不出来了，然后就有些GG了。。。

2. 一面

一面问的很细致，按照简历上的内容一条条的过，包括项目和研究方向，我主要写了两个比赛，其中一个是研究生期间做的CCF一个对汽车评论文本进行基于视角的情感分析比赛，然后讲了是怎么做的，包括任务的切分：抽取汽车视角+判定情感分析。然后面试官问了用了什么方法来抽取视角，我主要是用了分词工具，然后问了是什么工具，接着问用怎么分析这个视角的情感分析，我当时主要是统计情感词，用字符串的正则化来处理，感觉没什么工作量，很水。。。

之后又问了欠拟合与过拟合，解释原因和解决办法，当时先答的欠拟合，主要原因是模型过于简单，不能捕捉到足够多的特征，解决方法在神经网络中可以是增加隐藏层等，在机器学习中，以SVM为例，当数据集线性不可分时，可以利用核函数，将数据映射到高维空间，变成线性可分。然后面试官问了SVM引入核函数的本质是啥，答曰从一个空间映射到另一个空间，面试官不满意，提示说其实是提高了维度，增加了模型复杂度（感觉自己总结能力有点弱）。

然后讲过拟合，主要原因是模型过于复杂，捕捉的特征太多（当时说的逻辑有些混乱==），然后解决方法有L2正则化，然后面试官顺势问了L2正则化的本质是什么，没答出来，面试官提醒说是限制解空间范围，缩小解空间，来控制模型复杂度（再次感觉自己基础也不扎实，总结的也不到位，这个其实之前有看到过，但是给忘了，或者没想到要这么答得）。面试官说这些在吴恩达的机器学习课程里都有（之前聊怎么学习的时候，有说过看公开课，看官方文档，感觉给自己挖了个坑），如果好好看了就都会知道的。感觉还是自己没有钻研下去吧，如果有静下心看的话，这些的确应该是知道的，能够想起来的。

之后因为自己简历比较寒碜，没有项目也没有实习经历，面试官就问了在学校都干了什么，自己有些虚，确实没什么工作量，平时也就是看看论文，找模型，试模型，结果模型也看的一知半解，就有些尴尬。面试官问最近情感分析都有什么方法，准确率大概是什么，用LSTM怎么对文本进行情感分析。这个前两个回答出来了，第三个当时看论文的时候就看了个大概，也没有深入学习LSTM，感觉回答的不好，自己需要注意下。

最后来个总结吧，感觉现场面试还是比电话面试要能看出更多东西的，也能发现自己在哪些方面做得不够好，比如我自己在基础知识上不够扎实，打算以后着重看神经网络相关的基础知识，然后再考虑实践检验。