面试算法题

持续更新中
2016-4-21

最近校招实习什么的开始了,周围同学也在投简历,把他们的面试题目收集了供大家参考一下,欢迎各位提供题目和思路
.标号意为第几位同学的第几题,每次更新阅读数和评论都会被清零,orz)


微软

微软对代码能力要求高(一言不合写代码,leetcode hard级)

1.1、存有n个质数的数组,求以这些质数作为因子构成的第n大的数
1.2、八皇后

2.1、二叉树逆序层序遍历
2.2、链表局部反转
2.3、设计map

3.1、文件的append操作,如果操作对象是char则append是原子操作,如果是string则并不是一个原子操作,假设写到一半的时候,电脑崩溃了。如何操作使得append一个string是原子操作。

4.1、一个可能有环的链表,删除其中所有val等于给定target的节点

5.1、链表反转,链表局部反转、链表k-group反转


阿里

1.1、10亿个url,找到出现次数最多的top k个url(单机,不排序)
1.2、对于一个搜索引擎,你搜索的query,引擎会提示给你一些,想出一个完整的方案,去处理下拉推荐(排序啊什么的)。
1.3、求一个字符串中第一个出现3次的字符。
1.4、输入“I am a student.”,则输出“student. a am I”。
1.5、说说贝叶斯分类和LR的区别,还有LR效果不好怎么优化?
1.6、特征为什么要离散化
1.7、选个NLP方向随便讲讲
1.8、信息熵,怎么计算,为什么?

2.1、一堆文档,类似于“香蕉苹果八宝粥”,识别词性
2.2、LR多分类机制(源码细节)


因特尔

1.1、100个排好序的文件,外排(我觉得想考败者树)
1.2、一个有序数组,一个target,问有数组里多少对,它们的和恰为target。eg.(2,2,7,7),9,一共有四组,index不同即为一组
1.3、bitmap的应用
1.4、两个字符串,将在第二个字符串中出现过的字符,全部在第一个字符串中删掉再返回第一个字符串。(考察断链)
1.5、序列化协议,假设一个结构体组成为{long,int,char*a},如何制定一个协议,使得用户可以正确的解析出一串该结构体。


网易游戏

1.1、n个数找出前k个最大的数
1.2、100亿(10^11)个11位的QQ号(10^12-1)怎么存储在64台/10台/10台以下的机器上
1.3、100万个数,找出出现次数最多的数
(摩根和网易都有问到上海地铁设计的问题,有兴趣的同学可以自己去搜搜看看)

2.1、static在何种情况下使用
2.2、C++多态的实现
2.3、如何判断C++一个类的大小
2.4、TCP和UDP的区别
2.5、循环数组求第k的数的大小?12345678->56781234即为循环数组
2.6、给定两个数组,如何判断A、B是包含关系
2.7、判断n是不是2的幂次方

3.1、三个发射器,每个发射器可以发射a-z中的一个字母,每个发射器一共可以发射26次。现每次随机挑选一个发射器发射,当有一个发射器全部发射完即停止,问一共有多少种发射可能顺序?
3.2、扑克牌,见腾讯6.1
3.3两个水杯,容量不一样,让你倒出给定大小的水(网上类似题目较多)
3.4、非递归实现快排
3.5、估算一个游戏的登陆人数(多开开脑洞)


摩根

(摩根一轮是电话面,有同学说一共六轮,也有同学再有一轮on site就可以了)
1.1、给定数组,找出和等于给定数s的两个数a,b(leetcode原题,还有一个蛮有意思题的是找出所有的三个数,他们的和等于0)
1.2、给100GB的Interger排序(面试者说没太听懂)
1.3、将一个集合s分成两块a、b,使得sum(a)和sum(b)之间的差最小
1.4、1-n,共n+1个数,只有一个数是重复的,找出这个数(不是排序)

2.1、判断两颗二叉查找树是否一致
2.2、有序数组去重(O(1)空间O(n)时间)
2.3、设计一个停车场(画一下类图,每个类的属性,写一下各个类的实现和函数例如停车场,停车位,收费等)

3.1、一个str拆开,长度为偶数则对半拆(如10->5,5),奇数则中间为1,另外对半拆(11->5,1,5),这样不停的拆下去,一共拆n次后,返回每个子串逆序后再合并的结果
3.2、栈实现队列
3.3、C++虚函数、虚表
3.4、实现map


百度

1.1、给定一个无序数组,找出其中一个数,使得它至少大于其余60%的数
1.2、给出一个url,找到其中的网址,该url可能含有https这些前缀,也有可能含有一些子网页路径
1.3、给定一个数组,找到最大和的子序列(加强版,限定子序列的长度至少大于L)
1.4、一个单机,内存一个G,两个极大的文件各100G,找出两个文件中的相似行

2.1、str转int函数,考虑异常字符情况
2.2、合并两个有序链表,给定两个指针和链表的长度(不要破坏原来的两个指针结构)
2.3、给一个网站的访问日志,找到访问这个网站最多的k个用户(mapreduce,我说的是在reduce阶段保存一个map,存储前k个用户,然后又问我,如果k特别大怎么办?而且你这个map每次都遍历怎么办) 话说top k真是必考题
2.4、如果组织一堆电话号码,使得给定一个前缀后,可以快速找到具有该前缀的号码(我说的是树结构,每个节点就是一个号码数字,从根节点到叶节点就是一个号码,然后面试官又问空间复杂度了)

3.1、一个无序数组,定义差为后面的元素减去前面的元素(不一定相邻),找到这个最大差
3.2、两台电脑各有一个16T的大文件,两台电脑之间的带宽非常小,其中一个文件连续10B的字节已损坏,利用另一台电脑上的完好文件来修复该损坏文件。
3.3、如何优化快排,比较各排序算法
3.4、写出二叉排序树非递归遍历,在此基础上,翻转该二叉树,得到镜像二叉树
3.5、hashtable的线程安全如何实现的?锁是怎么加的?
3.6、hashmap哪些操作是不安全的?(对于put一个新元素时的确是不安全的,如果两个线程同时put,最后get的时候会死循环,面试官说的,然而我并不懂)
3.7、jvm、gc
3.8、线程、进程,有这两个点展开,把你所会的操作系统讲讲
3.9、tcp、udp,讲讲计算机网络
3.10、单例模式的五种写法,各自优劣


谷歌

1.1、给定两个set,去重
1.2、给定两个函数,一个是f(n) = 3*n+1,一个是f(n)=n/2,如果是奇数使用第一个函数,偶数使用第二个函数,给定一个数,对该数不停地使用上述两个函数,直到最后为1。现给你一个数组,求整个数组最后都变为1时的所花费的时间


腾讯

(C++)
1.1、给定两个链表,判断是否有共同后缀
1.2、判断一个链表是否有环
1.3、手写memcpy和快排
1.4、用O(1)时间复杂度在2G的内存里查找2亿个qq号
1.5、static和const性质
1.6、拷贝构造函数和赋值构造函数的区别
1.7、vector和list的区别

2.1、一个多叉树,记录根节点到叶节点之和为sum的路径(该题也曾出现在谷歌的面试中)

3.1、写一个函数,翻转英文句子。例如“I am on duty today”,处理之后为“today duty on am I”。函数原型为void a(char* pStr,int iLen),其中pStr是输入输出参数,iLen为字符串长度
3.2、请写一个二叉排序树,并实现按层次遍历输出
3.3、C编码,找出满足下面两个条件的元素,要求时间复杂度尽量小
a)它前面的元素都比它小
b)它后面的元素都比它大
3.4、设计一个算法,找出二叉树上任意两个节点最近的公共父节点,空间复杂度最大值允许为树的深度,时间复杂度要求小于O(n^2),每个节点不存在指向父节点的指针

4.1、海量大数据,找出前k个最小的元素(快排、位向量等方法均被否决)
4.2、给定固定内存空间,实现两个栈
4.3、为什么电影里,车子向前驶,而我们看到的轮子却好像逆时针旋转一样(这个问题也困扰了我好久好久啊啊啊啊)

5.1、单链表合并
5.2、25匹马找出最快三匹
5.3、top k问题,一般情况和mapreduce情况
5.4、不知道行数的情况随机选取文件一百行
5.5、推荐系统的多样性

6.1、给一个瞎子52张扑克牌,并告诉他里面恰好有10张牌是正面朝上的.要求这个瞎子把牌分成两堆,使得每堆牌里正面朝上的牌的张数一样多.
6.2、全国任意6个人中,必有3个人互相认识或有3个人互相都不认识,为什么?

7.1、怎么实现连连看两个点是不是能消除
7.2、买火车票怎么查出余票,5000个车,10站,站之间可以互达
7.3、百度搜索时所用到的所有技术


微信

1.1、判断正整数是否是对称数,如3,123,121,12321。不能把整数转为字符串来判断。
1.2、给定一个递增循环整数数组,从里面找出最小的元素,使用的算法越快越好。特别地,最小的元素可能出现在数组中间。比如:50, 52, 63, 90, 3, 8, 15, 44。
1.3、给定一个单向链表,请给出从最后节点倒数第n个节点。例如,{1, 2, 3, 4, 5, 6},倒数第3个节点为{4}。
1.4、在二叉排序树上面找出第3大的节点。注意:不能把二叉树全量存储到另外的存储空间,比如存储到数组中,然后取出数组的第三个元素。
1.5、给定两个字符串 s1 和 s2 ,从 s1 中删除在 s2 中出现过的字符。
1.6、在机场中,你想从A点前往B点。(为了将问题简化,假设机场是一条线性通道。)一些区域有电动扶梯(双向的),另一些区域没有。你的步行速度恒定为v,电动扶梯的运行速度为u,因此在扶梯上,你的实际速度为v+u。(显然,你不会搭乘与你前进方向不一致的扶梯。)你的目标是尽可能快地从A点到达B点。
1) 假定你需要暂停片刻,比如系鞋带。请问你应该在电动扶梯上系,还是在没有上电动扶梯时系?假定两种情况下,系鞋带的时间相同。
2) 假定你有有限数量的多余能量,用来奔跑。在跑动时,你的速度提高到v’(如果在电动扶梯上,就相应为v’+u)。请问你应该在电动扶梯上跑,还是在没有上电动扶梯时跑?假定两种情况下,你可供奔跑的能量相同。
【用数学方式证明】


面试时都是要求手写代码的,做可能暴力都可以做,但是还是要考虑一下复杂度的