微信面经(一二三面)
一面
-
一上来四道算法题
1 有一个二叉树，每个节点的值是一个整数。写一个函数，判断这颗树中是否存在从根到叶子节点的一个路径，这个路径上所有节点之和为某一个值sumvalue。存在返回1，否则返回0。实现haspath函数 struct TreeNode { int value; TreeNode * left, * right; }; int haspath(TreeNode *root, int sumvalue) { }
2 给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。 输入: S = "my_test_str", C = 't' 输出: [3,2,1,0,1,1,0,1,1,0,1] vector<int> shortestToChar(string S, char C)
3 给定一个字符串，由字符"0"和"1"组成。 找到含有相同数量的"0"和"1"的最长子串的长度。如： 输入: 01001001 输出: 4 说明: 1001 是具有相同数量"0"和"1"的最长子串。 int findMaxLength(string s)
4 给出一个整数N，求小于N的所有整数中，哪个数A的每个位上的数乘积最大。如：N=220,A=199,199=81;N=28,A=27,2*7=14 void GetMaxNum(int N, int & A) - epoll 原理， LT、ET 区别
-
http 报文怎么解析的
-
小根堆定时器怎么实现？如果是百万并发请求怎么实现呢？
-
说一下 raft，怎么选举，如果 leader 挂掉怎么办？
二面
算法题：
1.判断二叉树的同构，一棵树的任意节点的左右子树任意次交换后，能和另外一棵树相同，那这两颗树是b同构的
struct TreeNode {
int value;
TreeNode * left, * right;
};
tree1:
A
/ \
D C
/ \
F E
tree2:
B
/ \
C D
/ \
E F 直接在下面编码 - 使用数组，实现一个的循环队列（先进先出）;不要增加额外全局变量
int data[10000]; int tail； int head; int pop(int * d); //取出来到d int push(int d); // 把d存进去
2.1 要无锁支持并发（一个push线程、多个pop线程;单个生产者多个消费者)
提示：可以使用 cas 原子操作
bool succ = __sync_bool_compare_and_swap(*a, b, c）
{
if(*a ==b ){
*a = c;
return true;
}else{
return false;
}
} 直接在下面编码 3、在二叉排序树上面找出第N大的节点。注意：不能把二叉树全量存储到另外的存储空间，比如存储到数组中，然后取出数组的第三个元素。
struct TreeNode {
int value;
TreeNode * left, * right;
}; 直接在下面编码
- 说一下 raft
- 忘了一部分。。。
- 一个思考题：一千万个用户qq号（每个 qq 号 4Byte），每个用户有 500 个好友，如果 A 是 B 的好友，那么 B 的好友列表中一定有 A，如果没有则视为脏数据，请问怎么找出来大概几万条脏数据（用户好友列表在远程服务器，每次只能 RPC 调用获得一个好友列表（4ms），2GB 内存，不能用磁盘存）怎么做？
- 如果每个列表只能请求一次呢？
三面
- 实现一个基于Hash的全内存LRU cache，对外提供key-value读写接口。插入时，发现节点个数超过阈值，则按照全局最近最少使用淘汰节点。采用链地址法解决Hash冲突：Hash桶个数固定为1千万，最多只能存储1亿个的节点，key和value都为uint32。请分别实现Set，Get接口。
- 工行有30万个员工，其工卡号码分别是1~30万，在接下来的某天他们将举行年会，需要抽出10万个员工发奖品。我们有一个随机数生成函数rand()能够生成0~65535的整数，请写一个公平的抽奖程序，输出这10万个员工的工卡号码。 注：直接在这里写代码
- 小根堆的时间复杂度
- raft 算法怎么判断数据是最新的
- http1.0 和 http2.0 的区别
三奇智元机器人科技有限公司公司福利 74人发布