Tommy回家了,总结一下猫咪堵尿的经历吧# pets - 心有所宠
z*e
1 楼
已经挂了 发面经。
其他的都很简单,说一个印度人问我的问题比较难:
在一个2D空间里面有很多矩形,矩形都是不overlapping的。 给一个query,也是一个
矩形,问是否空间里面存在一个矩形与其overlapping。
我当时想到了用quad tree, 然后面试官简单的问了思路,然后让我分析复杂度,然后
我又提出使用kdtree,面试官说,分析复杂度啊,然后这就是悲剧的开始了,我分析错
了,说是lgn,其实应该是根号n。
然后他说你把你刚刚说的kdtree数据结构定义是什么,查询一个矩形的代码写出来。本
来挺有信心,但是因为剩下的时间不多了,所有优点慌,写的代码有一个bug被他揪出
来了。我看他撇着嘴就知道要跪了。
还有国人大哥,本来想放水,无奈我不给力,不过人很nice 赞一个。
其他的都很简单,说一个印度人问我的问题比较难:
在一个2D空间里面有很多矩形,矩形都是不overlapping的。 给一个query,也是一个
矩形,问是否空间里面存在一个矩形与其overlapping。
我当时想到了用quad tree, 然后面试官简单的问了思路,然后让我分析复杂度,然后
我又提出使用kdtree,面试官说,分析复杂度啊,然后这就是悲剧的开始了,我分析错
了,说是lgn,其实应该是根号n。
然后他说你把你刚刚说的kdtree数据结构定义是什么,查询一个矩形的代码写出来。本
来挺有信心,但是因为剩下的时间不多了,所有优点慌,写的代码有一个bug被他揪出
来了。我看他撇着嘴就知道要跪了。
还有国人大哥,本来想放水,无奈我不给力,不过人很nice 赞一个。