实习

头条

1. hadoop 已知每一个点的neighbor，求每一个点的二度邻居

2. 有一个排好序的数组，先将其随机循环右移，求在数组中查找指定target的位置 lgn

3. 有字符串,将所有连续的ac跟单独的b去掉后的字符串：如acccccb->ccc; aacceacdb->ed

时间复杂度O(n) 空间复杂度O(n) --> 时间复杂度O(n) 空间复杂度O(1)

4. 二分查找，查第一个出现的位置

5. 数组：找第k大的数 （无序数组） O(N) -> 数组无法修改，额外空间O(1) 时间O(N)

6. tcp慢启动过程

阿里:

1. [LeetCode]Implement Trie(Prefix Tree)

2. Java语言知识,同步，线程安全，threadpool

校招：

搜狐：

1. 回形遍历数组
2. map-reduce：
   file1:
   article_id1 keyword1 keyword2 ….
   article_id2 keyword1 keyword2 ….
   file2:
   User article_id rate
   User article_id rate
   求
   User keyword rate

搜狐：

1. 二叉树的中序非递归遍历
2. 第k层二叉树的节点个数（递归&&非递归）

3. storm hadoop: storm并行数，hadoop瓶颈，99%停住问题
   http://chengjianxiaoxue.iteye.com/blog/2188864

4. 求一条线段划为三段，能围成三角形的概率
   求【0,1】随机找2个数的最小值，最大值的期望

5. a b c 分别循环投掷硬币，直到正面出现胜利，求a b c获胜的概率
6. n个有序的数组，共N个数，求topK个最大的数
   NlgK(最小值堆) -> nk(归并算法) -> klgn(最小值堆)

唯品会：

1. 各种排序算法比较
2. mapreduce 相似度
3. 先根遍历
4. b树，b+树，红黑树

腾讯:

1. mapreduce解决kmeans问题
2. 1亿*1亿文章，100台机器，求两两之间的文本cos相似度
3. 各种排序算法比较，手写快速排序
4. 两个数组a，b；同时有i<j，求a[i]+b[j]的最大值
5. trie树最长匹配
6. 先根遍历，非递归
7. 二叉树蛇形遍历（1->3->2->4->5->6->7->15->14….）
8. 搜索纠错：湖人队比赛->胡人队比赛
9. 知识图谱：三元组的抽取（文本）
10. 1亿int的文件，2g内存 排序（去重）

搜狗：

1. 二分搜索变形：找第一个target
2. LCS
3. 设y=0与y=h之间存在一条河流；河流中有一些睡莲，中心店为xi,yi，半径为ri；求问能够从x=负无穷游到x=正无穷（如果睡莲横在河面，完全覆盖，则不能游过去），分析复杂度.

美团：

1. 反爬取的特征选择
2. SVM原理
3. 一天内时针跟分针的重合次数？

小米：

1. mapreduce过程求笛卡尔积：
   有两个文件
   A: a1, a2, …, am
   B: b1, b2, …, bn
   用MapReduce过程计算所有的aibj, (i ∈[1,m], j ∈[1, n])
2. 求数组a是不是一棵二叉搜索树的后序遍历二叉树序列
3. 给定num∈(0,1)，实现sqrt(num) tips:二分查找，优化：牛顿法

美团：

1. 给定一个数组[ 1, 4, 3 , 9 , 8] 求去掉任意k个数之后排列得到的最小数，如k=2，则最小数为134；如果要求去掉连续的2个数，连续的k个数呢？
2. 判断链表是否有环？环的大小是什么？
3. 给定一个矩阵M×N表示草坪，现在可以进行如下操作：
   割草：按列或者按行
   可以进行多次割草
   每次割草的距离不定
   求问给定一个矩阵，是否是以上的割草得到的？

小米：

1. 二叉树层次遍历
2. 翻转有序数组查找指定元素
3. 最长上升子序列
4. 矩阵旋转打印
5. 怎么检测deep learning中的局部最优解

滴滴:

1. 二分查找实现
2. 二叉树最近相同父节点
3. 单链表实现push_back()和析构函数~(优化)
4. 直接插入排序实现