有木有少花钱将父母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)。
: 如果有更好的解法可以把时间或者空间复杂度降下来，还望不吝赐教，多谢！

s*g2013-02-19 08:02

8 楼

话说二手版收UA账户的是怎么弄的？高级会员免费转？

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

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

a*m2013-02-19 08:02

9 楼

用选择算法可以减到n，需要排序的话是n+klgk时间复杂度。

s*t2013-02-19 08:02

10 楼

那如果还没在ua账户里能免费转？

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

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

a*m2013-02-19 08:02

11 楼

恩。hash确实需要空间。

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

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

p*a2013-02-19 08:02

12 楼

没在UA账户里那现在在哪里？其实我觉得父母的机票里程完全可以积攒到国内的合作伙
伴账户里，省得浪费了。

【在 s*********t 的大作中提到】

: 那如果还没在ua账户里能免费转？

J*n2013-02-19 08:02

13 楼

这一步怎么做？

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

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

s*g2013-02-19 08:02

14 楼

没在UA账户的是蓝宝点数吧
（飞完没claim的不算）

【在 s*********t 的大作中提到】

: 那如果还没在ua账户里能免费转？

J*n2013-02-19 08:02

15 楼

选择算法是可以，但只在平均情况下是O(n), 最坏情况是O(n^2),要保证O(n)需要用到
CLRS里面提到的那种方法
排序的话应该是O(n + mlogm)把

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

: 用选择算法可以减到n，需要排序的话是n+klgk时间复杂度。

h*G2013-02-19 08:02

16 楼

充够32.5k买票

【在 s**********g 的大作中提到】

: 话说二手版收UA账户的是怎么弄的？高级会员免费转？

q*x2013-02-19 08:02

17 楼

面试题答到一楼程度够了。

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

:
: 选择算法是可以，但只在平均情况下是O(n), 最坏情况是O(n^2),要保证O(n)需要用到
: CLRS里面提到的那种方法
: 排序的话应该是O(n + mlogm)把

s*t2013-02-19 08:02

18 楼

哦，我以为父母飞的有办法搞到自己账户下呢

【在 s**********g 的大作中提到】

: 没在UA账户的是蓝宝点数吧
: （飞完没claim的不算）

a*m2013-02-19 08:02

19 楼

恩。关键是m大小，如果m很大的话选择算法优势很大，毕竟能保证o(n)。

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

:
: 选择算法是可以，但只在平均情况下是O(n), 最坏情况是O(n^2),要保证O(n)需要用到
: CLRS里面提到的那种方法
: 排序的话应该是O(n + mlogm)把

d*n2013-02-19 08:02

20 楼

you are expected to use grep, cut, sort, sed, etc hell sscripts.

了，
为O

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