美团基础架构面试 – 汪明鑫的个人博客

上午10点多跑来面的，把还记的住的一些问题记录一下。

一面：

上来就来了个算法，在循环有序的数组中查找给定的key，如10 11 12 13 14 1 2 3 4 5 6 7 8 9
i++是原子性操作吗
volatile有什么作用
线程的状态及状态转换
线程sleep方法和wait方法有什么区别
线程状态能直接从挂起到执行吗
0.3 == 0.1 * 3 返回true还是false

值传递和引用传递
sql优化
IO、Socket相关
TCP状态
TCP协议为什么可靠
用过RPC吗
CAP理论
Zookeeper实现了CAP哪几个
Zookeeper集群中的角色
Zookeeper一致性
Kafka实现了CAP哪几个
Kafka的基本原理
Kafka的broker是什么
Kafka的partition是什么
Kafka为什么可靠
前端会哪些
有没有可以展示的作品
然后面试给我看了下他们的系统的几个页面，问我做的好不好
有什么想问的

二面：

自我介绍
看过哪些分布式的书籍
实习中遇到过哪些挑战
CAP理论
Zookeeper实现了CAP哪几个
Zookeeper leader选举
Zookeeper什么情况下选不出leader
Zookeeper怎么保证一致性
Zookeeper是整体一致还是局部一致

给一个场景：有一个很大的数组装了所有的员工，需要抽奖（一个一等奖，一个二等奖，一个三等奖），中奖人不能重复，random( )函数只能调用三次。

这个问题看起来很简单，其实有几个坑，我当时说了几次，再面试官提醒下才说出正确答案

注意题设条件：

1）一个很大的数组

2）中奖人不能重复

3）random( )函数只能调用三次

//一个长度为n的数组，假设n很大
//random（）函数，每次在数组大小的范围内产生一个随机下标，表示一个人中奖
//还要保证一个人不能被重复中奖

我的第一版答案 (伪代码)

int count = 0;
        List<Integer> list = new ArrayList<>();  //存放中奖者下标
        while(true){

            调用random( )在数组长度范围内随机产生一个下标index

            if(index 不在list里面){
                则放入list里面;
                count++;
            }

            if(count == 3){
                break;
            }
        }

问题：如果命中同一个index，则又要重新调用random( )，所以不符合题意

我的第二版答案：

第一次调用random( ),产生三等奖的下标index，第二次调用random( )在[0,index-1]的范围产生二等奖下标

第三次调用random( )在[index+1，n）产生一等奖下标

这样的做法有2个问题：

1，如果第一个index，落在数组的0下标或者数组的最后一个下标怎么办？

2，如果第一个index落在的下标等于1 ，那二等奖是不是一定就是0下标，而三等奖在[2,n)产生下标，失去了公平性，所以不行

我的第三版答案：

把这个数组平均切成三份，在每一份产生一个下标作为中奖者。

那问题又来了，那一个数组分成3个部分，哪个部分获得一等奖？哪个部分获得二等奖？

如果指定了哪个部分获得几等奖，则失去了公平性，如果不指定，随机分配哪个部分获得几等奖，则又掉了3次以上得random( )函数

所以我想的几个都是馊主意，不是违背题意，就是违背公平性。