本帖最后由 匿名 于 2019-9-9 12:24 编辑
八月初勾搭HR投的简历，交流了一番然后同意直接onsite。预约到八月中。
面试当天出了一点小插曲。第一个来lobby接我的面试官第一次面试，经验不足，我们都模糊得互相喊了一声名字，接着就一起进了小房间，略微自我介绍了一下就开始coding。然而，10分钟后，另一个面试官敲开了房门，说你接错人了。巨搞笑...大写的尴尬。好在面试官及时和HR沟通，把后面的面试都往后顺延了15分钟，对面试体验没有太大的影响。
话不多说，进入正题。一共五轮，上午三轮coding，下午一轮behavior+一轮coding
1. 木箱挡板小钢珠
如下图所示，给一个箱子，每个格子里都有一个斜挡板(用1和-1表示：\"\\\" -> 1, \"/\" -> -1)，会让小球根据重力向不同方向滚落。写一个query API，从箱子顶部的任意一个坐标i处drop the ball，问小球会从哪个坐标掉出来？注意如果小球被卡在某处，则return -1。
Follow-up 1：如何优化query API的time complexity？
Follow-up 2：如果我们现在加一个update API，会修改某一处的斜挡板的方向，问如何保持query API的最优时间复杂度？
2. 有奖问答猜猜猜
类似于李口上的猜词游戏。
secret word是一串颜色字符，比如是 rgrgb，guessed word比如是rrgrb,那么实现一个记分function： Score calculate(String secretWord, String guessWord),
class Score {
int correctColorButIncorrectPosition;
int correctColorAndCorrectPosition;
}
那么上面的例子就会return {2, 2}
Follow-up: 如果给定secret word最多可能有的颜色种类，和word length，写一个算法，用尽可能少的次数猜出secret word。
提示：可以使用上面写的function。思路类似于李口吧撕散。
3. 上课偷偷传纸条
如图所示，是一个教室平面图，然后每个位置前后或者左右相邻的同学可以互传纸条，然后每个path都已知一个被老师发现的概率。
先问一个数学问题：从学生A到学生B传纸条，问最小被发现的概率是什么？
好coding部分来了，如下图，现在除了已知每个path的被发现概率，由于学生品行有差异，每个学生自己也有一个拿到纸条后被老师发现的概率。写一个function，return从学生A把纸条传到学生B最小被发现的概率。
4. 开会玩耍两不误
现在出差n周开会，给一个数组表示每个会议的时长，会议可以由我们决定什么时候开，但先后顺序不能改变。现在我们想劳逸结合，如果我们想尽可能地平摊每周开会时间，问每周最多开几个小时的会？（不用考虑每天24小时，一周7天的限制，本质上就是把数字尽可能平均地分到n个bucket里并保持相对顺序）
举个例子 meetings = {3, 7, 4, 6, 5, 8, 2, 4}, n = 5
===============
面试不易，写面经也不易。希望各位觉得有用，也希望多多给米。谢谢！
| 
匿名用户-H3SO6
2019-9-9 15:56:24
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
狗仔卡
