笔试面经笔记

2017-03-25 | 阅读：次

2017微软转正实习生

第一面没问算法，直接问项目，首先我解释了几个课程设计，后来按着机器学习一直问。。没怎么回答好。。后来讲了一下简历写的个小游戏。

二面开始问我迷宫查找怎么实现的，就是深度优先和广度优先的搜索。问了俩算法，比较简单：一个是树的层序遍历，另一个求经过root的两个树节点之间的路径长度。手写代码，讲思路和测试用例。另外引申了一下求两个节点的不经过root的最短路径长度。我说要求最近公共祖先，但是代码还没想出来咋写呢，时间也差不多，就结束了二面。

三面竟然问一些语言特性。。java hashmap 和 hashtable的区别（线程安全）。。c++ virtual，析构函数，重载重写。按着线程安全的问题问啊问。。我就知道互斥锁。。最后给看了一个c语言strtoken函数的定义，然后白板实现。自我感觉这个函数写的差不多，就是前面一些语言特性没回答好。。对了，因为strtoken 不是线程安全的，面试官又问我该咋办。。我又只能回答说加锁。。。。。。

微软的消息等了太久了！！备胎一个月了，苏州那边打电话问我能不能去苏州实习。。然后说不太可以。。毕竟学校在北京。。然后GG了。。现在后悔，不该为了怕导师而拒绝微软啊，校招的时候还是看实习的。啊心塞。。。如果给我一个机会。。我肯定会请一个月假加上暑假去的，没实习现在校招特别难受，而且感觉再也没机会去微软了。

小米实习面试

1 最近公共祖先。如果有parent 指针，相当于求两个链表的交点了。如果是普通二叉树就递归判断。当初没好好刷题呀。https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

2 旋转数组二分查找

最后小米实习去了一周。迫于导师淫威，怕怕地辞职了。太怂了。。而且等我辞职后竟然放假了并且导师也对我们找工作放水了！！又心塞！！！

头条实习面试

一面挂。问求第k大个数字。用快排写的。写的比较慢。又问项目。感觉没亮点。挂！

百度复合搜索提前批面试

一面：进程线程，三次握手，死锁以及怎么处理。项目。算法题：两个链表求交点
二面： 1）智力题，一个密码锁有6个数字，求不小心拿反了还是正常数字的概率；求不小心拿反了和拿正的数字一样的概率 2）算法题，一个数组 1-n 中缺失了一个数字。查找到那个数。我用二分查找做的。 3）面试官感觉不懂机器学习，让我讲了下svm，给她说了下原理。
三面：部门经理，有点傲气。。喜欢打断人说话，问职业规划之类的（职业规划真的会有很多人问到，好好准备）。问有没有男朋友（懵逼），问对头条和百度的看法。问遇到困难怎么解决，我一不注意说Google一下。。然后马上意识到啊这是在百度啊。。接着添上或者百度一下。。。

最终说两周给消息，也没给。挂了！！/(ㄒoㄒ)/~~

360中科院专场

面试真的靠缘分和运气吗，感觉水过的。

1 一面问，写个atoi吧，考虑好各种情况。我就写。。刚写了两分钟，面试官忍不住了，你咋写这么多。。。我说我得考虑充分啊，他说别写了讲讲吧。。。就讲了下。然后又问，编辑距离知道吗？我说动态规划，刚要写，然后他说好，知道了不用写。然后问了下svm，gbdt 的东西，就过了

2 二面说，山东人啊。。360好多山东人呢。。哎你这项目都是工程的呀，咋来找算法，我说因为热爱 = =（内心：我就是试试看啊）。没写算法题，聊了聊项目，过了（黑人问号？？）

3 三面hr：自我介绍，优点，对360的了解，对人工智能研究院的了解。。。

最近要出offer结果了。我感觉很有可能被刷掉的，毕竟水过的。心里虚。希望能好运一次！（更新，第一批offer已经出来，没我。。已经进入备胎池。。）

百度本地凤巢

1面：由于我简历写的熟悉java， c++略懂，他就问了下简单的c++的语言特性， const 关键字。面试官很nice,告诉我别紧张。。就想了解一下我会的东西。然后问了排序，按某种分类把排序算法分类一下。我按时间复杂度分的。后来又问了下各个排序的原理讲了一下。算法题：记不太清了，就是一个二叉树遍历的变形，输出二叉树中路径尾节点能被5整除的路径？写了个递归的，又问非递归的。。大致说了下。他问，是不是刷题挺多。。我说，大家都会刷一些吧。。。问用linux开发吗？我说写过c/c++ makefile。面试官就噼里啪啦记录。

2面：shell 命令。。不熟，问怎么用shell脚本写内存监控，直接说不会。后来又让我用shell查找统计一个文件里的几行记录，我说我用sql吧。。。。面试官无奈地点头了。后来问 linux 读文件的时候内核发生了啥？然后问了selector, poll epoll… 当时都没看（现在也没来得及看~~~~(>_<)~~~~），就记得selector 监控多个io通道啥的，大致说了下。算法题： minstack. 参见剑指offer，但是第二个栈不用每次都push min

3面：开放题。问了搜索相关的。问好多url怎么存储。开始说前缀树，想了想，说先按照？ / 分词，存储倒排索引。面试官莫名觉得我不错，但我自己感觉二面三面答的都不好。

百度金融

一面 java 内存结构，程序计数器存的啥？为啥建立连接三次握手，而释放连接要四次挥手？（把过程说了下，说四次挥手是因为服务器还要发数据给客户端，发送完毕后还要确定一次，不知道对不对）算法题：1）两个字符串中，一个字符串相比另一个字符串少了一个字符，找出来这个字符。我说排序后用双指针或者hash表，写了代码。2）算 a + b, 不能用加号或减号。说了用位运算，但是进位那里卡壳了，正确答案见http://blog.csdn.net/unimen/article/details/6776138

int add(int num1, int num2)  
{  
    if (0 == num2)  
        return num1;  

    int sum = num1 ^ num2;  
    int carry = (num1 & num2) << 1;  
    return add(sum, carry);  
}  

3）二叉树中序遍历，递归非递归都写了遍。。。

二面，问项目，然后看到我有个模拟挖矿（比特币相关的东西）的小应用，和金融比较相关，就简单介绍了下。以为我懂区块链之类的，然而并没有。算法题！链表带random指针深拷贝的问题！！我竟然忘记咋做了，一直在想不用hash表的那种算法，最后面试官提示可以用额外的数据结构，就说了用hash表存原节点和新节点的关系。完整答案：http://www.cnblogs.com/chrischennx/archive/2014/10/15/4026101.html
三面人生理想，职业规划，性格优点。然后说我不大自信。以后面试要自信

链家

5个笔试题，现场笔试后再面试。

1 数组中超过一半的数。 http://blog.csdn.net/lskyne/article/details/9360639

2 括号是不是合法匹配，用了个栈

3 m个连续珠子有n个不同的颜色，求最小包含n个颜色的连续珠子长度 http://blog.csdn.net/zhccl/article/details/8044449

4 一堆ip访问记录，如果10分钟内连续访问超过1024次就是非法的，找出这些非法ip

5 判断循环依赖。（图里是否有环）

一面：线程有没有自己的独立资源？三次握手过程。 b+树 data存在哪？（叶子节点），叶子节点有联系吗？（有，链表相连的形式）为啥？（方便遍历，区间查找）你觉得笔试题能答多少分？我说七八十吧，他说差不多。说他觉得没啥问题了，问了解链家吗，我说。。租房卖房的吧。。。北京好多门头店啊。。。最后又说链家技术不错。。

二面：鄙视我的项目，觉得太简单。。哎，我也知道啊。。我也很绝望啊。。。写了个sql，问职业规划，我说做搜索相关的吧。。他说链家没有。。我说比较偏算法的研发吧，他说这说法好虚啊。。。最后说嗯你等一下我考虑一下吧。。。然后过几分钟给我挂了。感觉职业规划真的挺重要的，虽然之后不一定按自己说的做，但还是要大致有个规划，让面试官觉得你这个人是对自己负责的。所以我职业规划是什么，我研究生上的这么杂我也很绝望啊。。。。

网易有道

算法岗，不match. 记得一个题大约是： http://www.cnblogs.com/huangwei1024/archive/2012/09/28/min-len-substring.html

百度运维

数据库索引用了什么数据结构，和红黑树区别

hashMap 初始化多大，什么时候重新扩容

两个链表判断是否有交点

翻转字符串 in-place “how are you” 转成 “you are how”

三次握手；四次挥手什么时候是在 time-wait 状态

http 协议组成部分

jvm 垃圾回收， cms 收集器

elatic search 索引合并?

线程 interrupted 是进入什么状态

读写锁 : 读写锁特点：
1）多个读者可以同时进行读
2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

jvm OM 异常通常是怎么个情况，如何调优。。。

华为优招

啥也没问基本。。聊项目也有没有引申出一些知识点

祖龙娱乐

1 给一个java 程序，说出执行期间，jvm各个内存存储数据的变化，包括各个变量存储在哪，对象构造的过程，程序计数器，栈的压栈返回过程。然后评价我答的不太具体，只是说了各个数据的存储区域。

2 申请了很多对象，会出现什么问题? 各个内存区域都有可能因为什么而出现问题？

3 垃圾回收算法说了eden和 survivor 后，让具体描述那个 8:1:1 怎么复制回收的

4 判断html 字符串是否合法，给合法的标签列表，要合法不能不同的标签相互交错。

5 account (aid, money) 设计 addMoney, subMoney transMoney(Account a, int money) 的线程安全的算法。我写了之后，忘记考虑money的正负是否溢出的情况，把我鄙视一番。还有转账的方法，两个对象都加锁，会造成死锁产生，他问我咋办，我说一次都申请了，写的代码成了整个串行的了。最后才想到按顺序申请，可以每次先给id小的account对象加锁，然而他已经对我彻底失望。其实感觉一开始就对我没抱希望的样子。

头条校招面试

一面：

（1）大文件100亿个数字，求前m大的数
（2）进程和线程区别，啥时候应该用多线程，啥时候用多进程。 线程的好处？ 协程？ http://www.cnblogs.com/lxmhhy/p/6041001.html
（3）索引为何用b树 不用二叉树 http://database.51cto.com/art/201504/473322_all.htm 索引很大需要存到磁盘，高度小了，需要的io操作少
（4）两个有序数组，求第k个数， 说了双指针的做法，O（k）， 面试官让想更优的， 没想出来。应该是用二分查找的方法。
  http://bookshadow.com/weblog/2015/02/05/find-kth-smallest-element-in-the-union-of-two-sorted-arrays/
（5） 看什么技术类的书籍，讲讲jvm里都讲了啥。

二面：

面试官脾气很好。。问了下数据库事物隔离，一开始说不大了解，突然想到之前看了脏读，不可重复读，幻读。。说了之后面试官也没深入问。http://www.cnblogs.com/zhoujinyi/p/3437475.html
然后问mysql的一些问题，为何一般不用select *， 要用select 需要的字段呢？尝试回答了，不大对，面试官就解释了一遍。。我忘了他讲的啥了。。。好像之前还被问到 limit 分页的数字大为啥效率会变低。。数据库不太了解。

然后问一个shell， Ctrl+C 发生了啥。。我扯了一堆进程销毁的过程。。结果面试官是说和信号量有关。。尴尬。。

算法题。。面试官拿了俩题，让我选，我一看。。最大连续子数组和。。。然后写完了， 扯了一会，说。。你写个二分查找吧。。我就迅速写了个。。 他看了一眼。。然后结束了面试。。

三面：

问了jvm的， gc, 怎么判断对象存活。 volatile（两个特性）
sychronized.
 修饰一个类，其作用的范围是synchronized后面括号括起来的部分， 作用的对象是这个类的所有对象。
  修饰一个方法，被修饰的方法称为同步方法，其作用的范围是整个方法， 作用的对象是调用这个方法的对象；
  修改一个静态的方法，其作用的范围是整个静态方法， 作用的对象是这个类的所有对象；
  修饰一个代码块，被修饰的代码块称为同步语句块，其作用的范围是大括号{}括起来的代码， 作用的对象是调用这个代码块的对象；
  http://wiki.jikexueyuan.com/project/java-concurrency/synchronized.html

实现LRU O(1) 但是面试官描述得有问题，说使最近用次数最少的blabla..，我说你说的是LFU啊，不是LRU. 他说差不多！！？？说了LRU的数据结构，他又说加过期时间怎么整。。 我只能想到O(n)遍历删除的。

后来写了求树中两个子节点直接最长距离的。。差点没写上来。 一开始想对每个节点求左右高度，有重复计算，后来写代码时，就想到在递归中可以求一遍就好了。写好了问了下，边界情况。没问题。。然后说今天面试结束了，日常提问环节。。 瞎问了点问题。。

最后面头条的感受：感觉面了假的头条。。头条实习一面挂的阴影还在，咋还能给我终面过了。。面试真是运气+眼缘啊。。忐忑。。 hr说九月中下旬给通知，不一定给offer

小米内推

一面：瞎扯项目，算法题：二维数组中，每个元素有个数字，求某一个点到任意一点的sum和（只能向右或者向下） dp记录到每个点的sum。第二个题，求一个字符串，包含一个字符集的最短长度。网易有道一面题

二面：项目，讲了java 内存。进程线程。 26进制转换。一堆ip中，查找一个ip是否存在。

beibei

AlwaysRight