h**********d
发帖数: 4313 | 1 1. Amazon二面
上周面的. 烙印迟到45分钟后,又让我等了30分钟,后来让hr给我约第二天
第二天烙印迟到20分钟后给我打的...
上来就一个问题,设计一个网上预定飞机票的系统
讨论了50分钟左右,弄的很细,每个class里有啥variable,啥method,都要说. 比如
Controller class谁去call, 怎么用Controller class. 还有内存怎么寸(不用数据库,
全存memory里),用什么数据结构,(他提出hashtable),什么作为key,什么作为value
一开始还好,后来纠结在一个如何给用户一个指定日期的航班信息,因为我没有存日期,
最后时间快到了,他让我把想好的设计发邮件给他...
面完就忽然想出来了, 不过觉得面的一般,老被烙到处印牵着问
今天都周末了还没消息,准备move on..
2. Boston的一个大公司,老板转给我的邮件,发信给老板说招人
马上给我安排了电面,结果发现是project manager
1小时左右,都是算法题
一个问apache一个什么log里面如何找前10个频率最高的ip
然后说如果前k个呢
第二题就那啥了,说从n个数里取m个随即数,前后不重复
我说了reject sampling, shuffle algorithm, 提到了reservior sampling,他说他没
听说过reservior sampling
然后就悲剧了,他要我优化shuffle那个算法,说现在是一个连续的整数空间,要keep
track of the holes, 不要象shuffle那样swap来maintain O(n)的space
我讲了一个O(m^2) time的, 用LL存holes, 还要求被优化, 后来我犯晕了, 他说我想好
后给他邮件.....
我想了一个下午也没想出来怎么不用linear data structure 去maintain那个holes
list, 发信给他说没想出来, 拜托告诉我solution, 另外副了之前说的3个算法
他给我安排了2nd 店面,到现在也没告诉我算法,还说那个reservior sampling不错, 时
间O(n)小于O(m^2),靠,不废话吗,害我白想一下午! 八成自己回家发现自称的优化的结
果不存在.. | R***i
发帖数: 78 | 2 一个问apache一个什么log里面如何找前10个频率最高的ip
然后说如果前k个呢
这道题解法是用Hashtable遍历存frequency，最后再倒到max heap吗?
还是直接用max heap来存？ | h**********d
发帖数: 4313 | 3 我是用第一个,不过应该是min heap吧
【在 R***i 的大作中提到】
: 一个问apache一个什么log里面如何找前10个频率最高的ip
: 然后说如果前k个呢
: 这道题解法是用Hashtable遍历存frequency，最后再倒到max heap吗?
: 还是直接用max heap来存？
| R***i
发帖数: 78 | 4
应该是max heap吧，倒完后frequency最高的值是tree root，然后取出+删除root 10次
得到10
个最高频的node
【在 h**********d 的大作中提到】
: 我是用第一个,不过应该是min heap吧
| h**********d
发帖数: 4313 | 5 不是那意思，你说的max heap size是n？那也太大了。。
我是说keep 一个size 是m（10）的min heap，每次遇到比min 大的数就替换，然后
build a heap，这样时间是O(nlogm)，
【在 R***i 的大作中提到】
:
: 应该是max heap吧，倒完后frequency最高的值是tree root，然后取出+删除root 10次
: 得到10
: 个最高频的node
| r******y
发帖数: 471 | | z*s
发帖数: 209 | |
|
