骨骼骨骼 昂赛特 山景城

骨骼大佬的面试，在一栋有很可爱的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要怎么写


第二轮：
中国/韩国小姐姐（全程期待中文脸，然而小姐姐全程英文，也许不是中国

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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了，但是印度小姐姐只要我一写代码就全程玩手机然后最后没有拍照的，求放过！
发帖攒人品！求米求米～

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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

pandami 发表于 2018-10-10 08:02
楼主之前什么经历 同是转专业求建议

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

pandami 发表于 2018-10-10 08:02
楼主之前什么经历 同是转专业求建议

建议就是好好刷题！！！

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

看来实习刷了不少题

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

tinylic 发表于 2018-10-10 08:29
最后一轮小哥说的是KD Tree不是Quad Tree吧....

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

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