微信面经(一二三面)

一面

1. 一上来四道算法题

   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)
2. epoll 原理， LT、ET 区别

3. http 报文怎么解析的

4. 小根堆定时器怎么实现？如果是百万并发请求怎么实现呢？

5. 说一下 raft，怎么选举，如果 leader 挂掉怎么办？

二面

算法题：

1.判断二叉树的同构，一棵树的任意节点的左右子树任意次交换后，能和另外一棵树相同，那这两颗树是b同构的

‌struct TreeNode {

int value;

TreeNode * left, * right;

};

 tree1:
     A 
   /   \
  D     C
 / \
F  E

tree2:
     B
   /   \
  C     D
       / \
      E   F 直接在下面编码 

1. 使用数组，实现一个的循环队列（先进先出）;不要增加额外全局变量

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;
}; 直接在下面编码

1. 说一下 raft
2. 忘了一部分。。。
3. 一个思考题：一千万个用户qq号（每个 qq 号 4Byte），每个用户有 500 个好友，如果 A 是 B 的好友，那么 B 的好友列表中一定有 A，如果没有则视为脏数据，请问怎么找出来大概几万条脏数据（用户好友列表在远程服务器，每次只能 RPC 调用获得一个好友列表（4ms），2GB 内存，不能用磁盘存）怎么做？
4. 如果每个列表只能请求一次呢？

三面

1. 实现一个基于Hash的全内存LRU cache，对外提供key-value读写接口。插入时，发现节点个数超过阈值，则按照全局最近最少使用淘汰节点。采用链地址法解决Hash冲突：Hash桶个数固定为1千万，最多只能存储1亿个的节点，key和value都为uint32。请分别实现Set，Get接口。
2. 工行有30万个员工，其工卡号码分别是1~30万，在接下来的某天他们将举行年会，需要抽出10万个员工发奖品。我们有一个随机数生成函数rand()能够生成0~65535的整数，请写一个公平的抽奖程序，输出这10万个员工的工卡号码。 注：直接在这里写代码
3. 小根堆的时间复杂度
4. raft 算法怎么判断数据是最新的
5. http1.0 和 http2.0 的区别