首页 > 微信面经(一二三面)
头像
baymax_hwy
编辑于 2021-04-21 11:12
+ 关注

微信面经(一二三面) 内部员工回复

一面

  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 的区别

更多模拟面试

全部评论

(15) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐