快手、搜狗、旷视面经

最近面了几家公司，收集了一波面试题分享给大家。

主要都是算法题和一些场景题，常见的基础题就略过了。

好多想不起来了，会一直更新的 = =。

ps：不要问我怎么投的简历，在牛客上都能找到 = =。

算法题：

两个有序链表，求并集。（尽可能得使代码简单，写起来很多坑）

判断麻将胡没胡。（考点是正则的状态机实现方式）

有N个人，其中有一个明星，所有人都认识明星，明星不认识所有人，只有一种查询方式：A是否认识B，给出找到明星的最优策略。

完全二叉树的一下个节点。（On的复杂度肯定是不够的，这题比较好玩~）

代码去注释。

一个图，起点为A，终点为B，可以选择图中一条边置为0，如何使A到B的最短路径最短。（顺便写写Dijkstra）（这题个人觉得比较难）

给出二叉树的先序和中序遍历，构建二叉树。

链表排序。

矩阵相乘的最优顺序。

二分图最大匹配，最小费用最大流。

把一堆数分成两堆，使和最相近。（背包搞一搞）

数据流找中位数。（大小堆搞一搞）

二叉树中权重最大的链，每个点的权重有正有负。

加上最少的括号，使括号匹配。

杂题：

广告投放策略，不同的广告语有不同的投放要求，怎么将各个广告主每天的预算尽可能地花完

设计一个网易云音乐，从不同的方面优化流量使用问题

给出程序，分析程序的性能问题，主要都是缓存相关的问题，尤其是多线程下一致性ping pong带来的性能问题。