链家-大数据开发(机器学习方向)-笔试+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,感觉回答的不好,自己需要注意下。

        最后来个总结吧,感觉现场面试还是比电话面试要能看出更多东西的,也能发现自己在哪些方面做得不够好,比如我自己在基础知识上不够扎实,打算以后着重看神经网络相关的基础知识,然后再考虑实践检验。
全部评论
第二题,[{]}也是不合法的,但是楼主的方法没有办法判断出来,应该用栈来做
点赞 回复 分享
发布于 2017-08-27 21:54
第一题 可以O(n)
点赞 回复 分享
发布于 2017-08-27 22:23
面到几面
点赞 回复 分享
发布于 2017-08-27 21:52
面前端的表示和你拿到了一样的题
点赞 回复 分享
发布于 2017-08-27 21:52
***一面没过
点赞 回复 分享
发布于 2017-08-27 21:55
第四题大佬们有什么解法啊
点赞 回复 分享
发布于 2017-08-27 22:33
第四题用hashmap,键是ip,value是队列,当有新的ip时先比较队顶元素和新时间的差,不行就pop,然后维护队列长度即可
点赞 回复 分享
发布于 2017-08-27 22:36
第一题为hashmap记录即可,第二题用stack即可,第三题hashmap维护长度里各种颜色球的个数,然后设置一个头指针,o(n)即可第五题拓扑排序,找一个没有前置的节点,dfs即可
点赞 回复 分享
发布于 2017-08-27 22:38
你们面试都问笔试题啦?我一题都没问
点赞 回复 分享
发布于 2017-08-27 23:16
第一题应该是剑指offer原题,一个变量记录数组值,一个变量记录次数,当前遍历的值跟记录的一样,次数加一,不一样次数减一,最后剩的就是要找的数,O(n)
点赞 回复 分享
发布于 2017-08-28 00:42
现场撸代码么?如何报名?
点赞 回复 分享
发布于 2017-08-28 02:01
如果遇到左边的括号,则入栈; 如果遇到右边的括号,且栈不空,则栈顶元素出栈与右边的括号比较。 如果遇到右边的括号,且栈为空,则不合法。 如果是别的字符,则不作处理。 (希望有人帮我指出不足)
点赞 回复 分享
发布于 2017-11-08 13:38

相关推荐

10-15 09:13
已编辑
天津大学 soc前端设计
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务