g*******e
发帖数: 140 | 1 难度应该是中等偏下，发挥一般，顺求bless
一共4轮技术面试，HM生病了，没见着。每轮2个工程师，一般是一个本地 + 一个远程
1st: 亚裔小弟弟+英式口音的大姐：
1. 项目自我介绍
2. 浮点bst，找greatest one in the tree that's smaller than the target，
二分搜索简单变形。我犯了个错误，但是自己dry run测试用例的时候发现更正了。另外
一个小问题要注意的就是处理查找结果不存在。
3. 类似utf8字符串(一个字符是单字节还是双字节取决于第一个字节的首bit)，给定中
间一个字符，删除前面一个。在这道题上卡了一会，关键是弄明白向前查找的终止
条件是什么。
2nd: 一位老美大叔+老美小弟弟
1. 项目介绍
2. 从stream中找到top-k frequent items 用hash-table + priority queue解即可,
解释了一下时间复杂度。问了一下写什么测试用例来测试代码。
3. 扩展到多机器大数据上500mm数据，500台机器，怎么解。就是用hash mapping分散
数据到500台机器上，分别求取top-k，然后再merge+topk即可。follow up，单机的内
存有限，不能把1mm数据全部装入内存怎么办。
3rd: 一位老美大哥+一位老美小弟:
1. 项目介绍
2. 设计battleship game, 就是我们小时候玩的战船游戏，不用担心如何放置战船，
就设计fire()方法，返回miss/hit/sink。其实是很简单的题目，但这个环节我答得
不好，我以为是考察c++类设计，花了挺长时间设计game class, ship class。但核
心算法不是最优，在提醒改善时间复杂度才给出最优的算法，不过已经没时间改代码了。
4th: 一位亚裔小哥＋一位印度小哥
1. 项目介绍，亚裔小哥对我做过的东西有点兴趣，多问了一些问题，但气氛还是很友
好的。同时告诉我这个面试注重代码的风格和清晰。
2. two sum 我一共让写了两类(sorting和hash-table)四个实现，sorting的夹逼去
重没什么可说的，hash的解法上，我先写了一边遍历一边生成hash table的解法，被告
知有点复杂，让改进。于是又写了一个完全遍历一遍数组来生成哈希，然后利用哈希来
产生结果，这个解法需要不断删除hash-table中已处理的item来避免重复。被告知这样
解法不intuitive。让保持hash-table的size不变再写一个解法，于是又写了个hash
table中元素的计数器置零而不删除元素的解法。
求个bless。 | j******o
发帖数: 4219 | | r**********i
发帖数: 134 | 3 bless. :-) thanks for sharing. |
|
