有木有少花钱将父母UA帐号上的点数转到我帐号上 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

有木有少花钱将父母UA帐号上的点数转到我帐号上

有木有少花钱将父母UA帐号上的点数转到我帐号上# Money - 海外理财

J*n2013-02-19 08:02

1 楼

之前的遇到过的一道面试题，还是用skype面试的，感觉很别扭。当时因为前面被问了
很多data mining的问题，答得不好，到时后面有点乱套了，代码还没写完时间就到了，
结果就挂了。。。。
从log文件里找出访问次数最多的10个url,经典的做法是用hashtable算出每个url访问
的次数，然后遍历hashtable中的每个url，用minHeap找出最大的十个。时间复杂度为O
(n+mlog10), n为log里url的数目，m为distinct url的数目，空间复杂度为O(m), 如果
扩展到最多的k个url，时间复杂度就是O(n+mlogk), 空间不变(因为k超过了m的话只能
返回m个url)。
如果有更好的解法可以把时间或者空间复杂度降下来，还望不吝赐教，多谢！

l*d2013-02-19 08:02

2 楼

各位钱版友人，大家好。我父母在UA帐号上有几K点数。我想把点转过来买机票。从UA
网站用transfer to family/freind，要$15/1K miles.还是要花钱啊。不知道有木有什
么办法能不花moeny就转过来的。或者少花点钱也行啊。请民间高手指教。Thanks a
lot.

a*m2013-02-19 08:02

3 楼

找最大的k个你只要大小为k的buffer, 空间复杂度是0(k)。

F*n2013-02-19 08:02

4 楼

木有

UA

【在 l*******d 的大作中提到】

: 各位钱版友人，大家好。我父母在UA帐号上有几K点数。我想把点转过来买机票。从UA
: 网站用transfer to family/freind，要$15/1K miles.还是要花钱啊。不知道有木有什
: 么办法能不花moeny就转过来的。或者少花点钱也行啊。请民间高手指教。Thanks a
: lot.

J*n2013-02-19 08:02

5 楼

你说的只是minHeap的空间把，难道不需要用到hashtable？

【在 a********m 的大作中提到】

: 找最大的k个你只要大小为k的buffer, 空间复杂度是0(k)。

g*n2013-02-19 08:02

6 楼

已经在ua账户里没法免费转了

k*n2013-02-19 08:02

7 楼

这个是经典题了，我都怀疑是不是还有面试官会问
hashtable的部分是必须的, O(n)
对整个数组用maxHeap做k次siftdown，O(m+klogm)
一般会比mlogk好一点。

了，
为O

【在 J*********n 的大作中提到】

: 之前的遇到过的一道面试题，还是用skype面试的，感觉很别扭。当时因为前面被问了
: 很多data mining的问题，答得不好，到时后面有点乱套了，代码还没写完时间就到了，
: 结果就挂了。。。。
: 从log文件里找出访问次数最多的10个url,经典的做法是用hashtable算出每个url访问
: 的次数，然后遍历hashtable中的每个url，用minHeap找出最大的十个。时间复杂度为O
: (n+mlog10), n为log里url的数目，m为distinct url的数目，空间复杂度为O(m), 如果
: 扩展到最多的k个url，时间复杂度就是O(n+mlogk), 空间不变(因为k超过了m的话只能
: 返回m个url)。
: 如果有更好的解法可以把时间或者空间复杂度降下来，还望不吝赐教，多谢！