骨骼骨骼 昂赛特 山景城

骨骼大佬的面试,在一栋有很可爱的map marker楼里面,基本都是搜索和地图组的

第一轮:
印度小姐姐
打破了我面试从没遇到印度人的优良传统,小姐姐虽然还是一直保持微笑和认可,但是一丁点hints都不给然后认真的说“是你在面试哦”
-“好哦我知道了哦”
题是有一个cache,里面有很多entries,自己设计class和methods,要求可以add entry和get entry value,每个entry有一个过期时间,如果过期了取出来就是-1(自己假设的过期时间是int),自行想数据结构等等
比较简单的是直接建一个item class然后储存key,value,addtime和expiration(每个item不一样,addtime初始情况是System.currentTimeMills(),取出来的时候要compute difference),然后取出来的时候要看看过期没有,过期就remove,然后返回-1
另一个是用hashmap+doublylinkedlist,定期从头遍历list,删除过期的entry
然后印度小姐姐让我说两种方法各自好的地方 balabala一段时间
然后写了比较简单的hashmap的方法,写完让我来一场unit test
说了很多正常的不正常的test case,嘴跑几遍,然后印度小姐姐说如果expiration是12s,那我们怎么确定我们测的这个时候这个entry expire没有,我就说可以用类似java自带TimeUnit.SECONDS.sleep(12)这样让他过12s,然后肯定就过期啦。小姐姐就说这样work,还没有别的方法?我就说run 12个case绝对超过了12s啦,她说也行那还有别的方法吗?
想不到了,我就问了问想知道有没有别的好方法,但是不告诉。。。
然后最后又问了问clean up,比如我们有1milllion的数据,但是很多时候用户不retrive,然后可能很多都过期了,那我们就浪费空间了,说了说clean up要怎么写

第二轮:
中国/韩国小姐姐(全程期待中文脸,然而小姐姐全程英文,也许不是中国人?)
问我玩过candy crash没有,然后给我解释了一下游戏怎么玩(是消消乐吧?)
题目是candy crush游戏:一个board,每个格子里都要放随机的颜色。如果连续三个格子颜色相同,就可以消掉。可以swap相邻格子的颜色,使得出现能消掉的颜
input是int row, int col, int color,m和n是board的长宽,int color是颜色的种类。比如我假设是color = 5的时候,我们可以选0,1,2,3,4这样,小姐姐说可以哇
写一个method生成游戏的开局
要求:
随机生成,不能有地方直接消掉(不能有连续三个相同的颜色),比如:
1 2 3
1 3 4
1 3 4, 这样第一列就消掉了
follow up:能够走至少一步(必须存在至少一个地方,通过swap能消掉颜色)
这题还蛮好玩的,小姐姐也全程积极一起讨论,还会鼓励笑着跟你说that’'s prety cool!哈哈哈感谢小姐姐!

lunch的白人小哥人超级有趣,还提醒我还多次吃饭不feedback叫我别感到压力hhh。聊了好多一直没空吃饭,小哥说来到这边即使在酒吧都能听到大家探讨技术,所以他很开心因为他可以聊他会的而不是足球啊明星啊什么的之类的
然后说山景城这边就是大家都不问你从事什么行业,直接问你在哪个tech 公司hhh
还聊到Amazon go,他说并不是ai呢,只是一个非常expensive的代替人类劳动的商店,然后意识到时间不够我们就狼吞虎咽几分钟跑回去面试了,一边往回赶一边还跟我说我面试房间的名字很好玩

第三轮:
韩国大叔,此轮很是非主流
一坐下还没顺一口气就开始出题了:
先问了一些list, set, hashmap的基本知识,做了一个简单的implement queue using array,有pop()和push(int v),有1billion 的数据,要放进去拿出来
然后一开始写的版本是有int head和int tail,加进去和poll出来的时候他们都会往后移位,然后大叔说这样浪费空间了,然后就写了类似于circular queue的东
大叔虽然人还不错,但是你说完改进想法之后他会严肃地说“so where is it??”,然后我就一脸懵我们这不是在讨论怎么改吗那我这就写嘞!
然后说好这个ok了那我们来一个有趣的,正兴致盎然,来了一个hashmap
题目:1billion的数据,我们放到hashmap里面我们需要多少bytes的memory
于是后面就直接一行代码都没写把hashmap的结构都画出来了什么buckets和list of entry node,在一点一点抠hashmap的东西,什么node里面是什么啦,多少byte啦,我们hash是干嘛,还有说list of node的pointer也占内存吗什么什么??
总之转专业学生表示迷茫。。。
最后还说如果比如10用int 存和integer存空间有什么不一样,谁比较大,然后还让我画object pointer图,然后就是integer是store by copying value 还是reference这种问题
锦鲤显灵吧这轮= =move on

第四轮:新加坡小哥哥
人超级nice,会引导会hints

有1million的餐厅,和一个人的location,要找出离这个人最近的10家餐厅。先说nlogn的当然就是算好distance放到pq里面,但complexity太高了,然后优化到nlog10的,就是保持一个pq of size 10
小哥说,but!我们要优化到xlog10,怎么确定这个x呢?我说这个x是要binary search出来的,不是能确定的,他说对的对的
再说可以用类似bst的方法,后来小哥说可以的然后开始举例子给我一些hints,说我们可以用quadtree啊(我此时点头+这是啥?)
小哥问你们算法课没学过吗?我一脸真诚的说 嗯我们没学。然后开始科普教学
每个node代表一个space,每个space里面有很多很多餐厅,一点一点比较哪个child node更近。只有leaf node是餐厅,但有一种情况是在boundary的点,可能更近的餐厅在adjacent node(不是sibling node) 的space里,但是我们没有考虑到,我说嗯对哇!还是有点懵但是题真的蛮好玩的
然后开始写代码,pq+recursion,时间有点不够了,但小哥说没事我知道you get it 了!

感觉题答的最好的一轮是印度小姐姐,完整的写好了讨论完了follow up也ok了,但是印度小姐姐只要我一写代码就全程玩手机然后最后没有拍照的,求放过!
发帖攒人品!~

给楼主点个赞 不过感觉有两轮有点奇怪 现在骨骼怎么这么非主流 怕怕

楼主之前什么经历 同是转专业求建议

master转的cs,之前是电商专业,有cs实习有科研

建议就是好好刷题!!!

最后一轮小哥说的是KD Tree不是Quad Tree吧…

看来实习刷了不少题

感谢楼主分享呀! 请问第二题的follow up,楼主怎么答的? 第四轮优化到 xlog10, x怎么用binary search得到的呀?第四轮用quad tree recursion的思路也不是太清晰,楼主能不能详细说一下

是quad tree呀,还给我写出来了

能问问楼主candy crush follow up的大致思路吗?谢谢~