P*******y 发帖数: 168 | 1 刚W家电面的,先给了O(n^2)的,然后问nlg(n)的解法,
提示用hash_map,想不出来,大伙想想,咋解? |
|
I**A 发帖数: 2345 | 2 Give some scenarios where you might favor O(n^2) algorithm over a O(nlg(n))
i. If O(nlg(n)) requires space, while O(n^2) doesn’t
ii. If O(nlg(n)) is difficult to understand and to implement, while O(n^2
) is easier
iii. If O(n^2) has a general running time less than O(nlg(n)) instead
iv. If O(n^2) is easy to serialize, while O(nlg(n)) not |
|
y**i 发帖数: 1112 | 3 可是sort就需要nlg(n),sort完了,怎么找也小于nlg(n)吧,那总得最快还是O(nlg(n)
),怎么也不如hash快啊 |
|
I**A 发帖数: 2345 | 4 这“只对10个数排序”还是没有说出你为什么favor O(n^2)吧
我说了几个。。
1. If O(nlg(n)) requires space, while O(n^2) doesn’t
2. If O(nlg(n)) is difficult to understand and implement, while O(n^2) is
easier
3. If O(n^2) has a general running time less than O(nlg(n)) instead, like
Quicksort
他后来提了一点 what about if there are multiple machines...
欢迎讨论~~~ |
|
|
r******r 发帖数: 700 | 6 海量数据处理:十道面试题与十个海量数据处理方法总结
作者:July、youwang、yanxionglu。
时间:二零一一年三月二十六日
说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量
数据处理的方法总结。
本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随
时交流、指正。
出处:http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据,提取出某日访问百度次数最多的那个IP。
首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中
。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把
整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash
_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最
大的IP中,找出那个频率最大的IP,即为所求。
或者如下阐述(雪... 阅读全帖 |
|
r******r 发帖数: 700 | 7 海量数据处理:十道面试题与十个海量数据处理方法总结
作者:July、youwang、yanxionglu。
时间:二零一一年三月二十六日
说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量
数据处理的方法总结。
本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随
时交流、指正。
出处:http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据,提取出某日访问百度次数最多的那个IP。
首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中
。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把
整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash
_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最
大的IP中,找出那个频率最大的IP,即为所求。
或者如下阐述(雪... 阅读全帖 |
|
b***u 发帖数: 61 | 8 算法书上讲的
h >= lg(n!)
>=lg((n/e)^n)
=nlg(n) - nlg(e)
=omega(nlgn)
所以对于任何一个基于比较的排序算法run time至少是nlgn |
|
l**********c 发帖数: 434 | 9 保险公司没问题,有问题的是agent。必须仔细看policy才知道trick在那里。
我查了一下,你这个叫"no lapse guaranteed" Universal Life with return of
premium,其实就是一种term life until age 105 or 121。这个可不便宜。我quote的
没有return of premium的59岁女性best class:
1. $5,675.00 per year with Aviva Life and Annuity Company Request an
Application
Advantage Builder Series III w/NLG 175k+ Premier Non-Tobacco
2. $5,785.30 per year with United of Omaha Life Insurance Company
Request an Application
Guaranteed Universal Life - to... 阅读全帖 |
|
z****l 发帖数: 5282 | 10 ☆─────────────────────────────────────☆
annachen0123 (安心) 于 h 提到:
本人对保险不是很了解,想在这里请教各位。
我想打算给我妈妈买份纽约人寿保险,不到60岁,比较感兴趣的是这种险种:
每个月交$250,一直交到我妈去世为止,到时除了把你每年交的这些前如数退还,还可
以额外得50万刀,就是没有现金值在里面,你交多少就会退多少给你。我妈现在没有身
份,探亲过来的。纽约人寿险说只要入保险时在美国就可以买,不限身份。
我买这个目的是想到时我女儿成人时可以给她用来上学,或者成家用。
请教各位,这种险种合适么?有没有更好险种?
谢谢!
☆─────────────────────────────────────☆
ljty (老家太原) 于 (Fri Jul 15 18:05:32 2011, 美东) 提到:
听着挺玄的,忽悠?
能不能把这个保险的英文名字报上来?
☆─────────────────────────────────────☆
annachen0123 (安心) 于 (Fri Jul 15 1... 阅读全帖 |
|
f********t 发帖数: 6999 | 11 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
s**********o 发帖数: 14359 | 12 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理:十道面试题与十个海量数据处理方法总结
作者:July、youwang、yanxionglu。
时间:二零一一年三月二十六日
说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量
数据处理的方法总结。
本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随
时交流、指正。
出处:http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据,提取出某日访问百度次数最多的那个IP。
首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中
。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
o***s 发帖数: 42149 | 13 20年前的一部《还珠格格》风靡大江南北,也由此捧红了一大批新人演员,比如“还珠三美”和苏有朋以及周杰。如今20年过去,“还珠三美”不仅个个成为一线大咖在娱乐圈站稳脚跟,而且还都把自己活成了豪门:小燕子赵薇投资有道成为“女版巴菲特”,林心如转型制片人成为霸道女总裁,范冰冰更是连续三年登顶富豪榜成为当之无愧的“福布斯女王”。五阿哥苏有朋发展得也很不赖,近年来不仅转型成新锐导演交出了数部佳作,还和赵薇合开公司共同奔向致富路。好像只有尔康周杰糊到地心,活成了行走的表情包。
所以很多人为周杰惋惜,觉得他把一手好牌打了个稀烂,混成了还珠里面最惨的那一个。但事实真的如此吗?当年火遍全国的尔康真的沦为了网友口中的“网红loser”吗?答案是否定的,因为从娱乐圈消失的那些年,他逐步完成了从艺人到商人的蜕变,闷声发大财开了好几家公司,早已成了娱乐圈内身家过亿的隐形富豪。
三家影视公司老板,投资多部影视剧
在演艺圈,周杰的起点不可谓不高:出道作品是张曼玉、梁家辉主演的《阮玲玉》;1997年因扮演《还珠格格》尔康一角一炮而红;《还珠格格2》的收视率一度飙至65%,创下纪录至今难打破;和其他人相比,他还是唯一一... 阅读全帖 |
|
u***************r 发帖数: 11227 | 14 发信人: inews(inews), 信区: Headline
标题: 周杰身家不输范冰冰,你喝的红酒可能就是他的
发信站: BBS未名空间站(Thu Sep 21 07:36:53 2017,GMT)
最近,周杰和林心如因为当年《还珠格格》的吻戏开撕,离开娱乐圈多年的周杰又被大家记住了。其实在与林心如互怼之前,他给大家留下的最深印象除了尔康,就是“魔性表情包”了。
1998年,《还珠格格》大火时,周杰一度成为内地知名影星,也拍了几部戏,但后来经历了“强吻门”、“撞车门”、“博客门”、“封杀门”等负面冲击后,他一直被指责、被黑、被调侃,甚至还一度传出惹怒陈道明被封杀的消息。
虽然这些传闻真假难辨,周杰本人也从未出来专门解释澄清,不过他的演绎事业似乎受到了影响。虽然后来也演了《梅花档案》、《夜幕下的哈尔滨》、《零点杀机》等,但都没溅出太大水花。
网上流传着一个段子:小燕子赵薇成为一线电影咖,五阿哥苏有朋转型当导演,紫薇林心如成功转型制片人,金锁范冰冰成为娱乐圈话题女王甚至冲入国际,而尔康周杰因表情包惨为“网红”。
不过,大家真的以为周杰像大众想象的活的那么惨吗?其实,周杰坐拥三个影视公司... 阅读全帖 |
|
j****y 发帖数: 1714 | 15 【 以下文字转载自 WaterWorld 讨论区 】
发信人: joyjoy (joy), 信区: WaterWorld
标 题: 知道你的权利—当遭遇执法人员时
发信站: BBS 未名空间站 (Mon May 20 01:55:08 2013, 美东)
本文档是 Know your Rights When Encountering Law Enforcement 手册的中文翻译。
翻译本手册的动机是太多的中国留学生,移民不知道自己的权力,在被执法人员宗族歧
视性调查的时候处理询问不当, 被执法人员抓住漏洞而被控向联邦执法人员撒谎(
lying to federal agents/officers), 即使执法人员根本没有其他任何证据来逮捕他
们。 最近的例子是NASA合同工姜波的案例: http://bojiangwatch.blogspot.com/ ) 在美国的中国血统人士必须吸取深刻教训防止种族迫害。
This document is the Chinese Translation of the Booklet published by ACLU:
Know your R... 阅读全帖 |
|
S*********g 发帖数: 24893 | 16 【 以下文字转载自 Stock 讨论区 】
发信人: StephenKing (金博士), 信区: Stock
标 题: 市面上流通1358种电子货币,包括ByteCoin
发信站: BBS 未名空间站 (Fri Dec 15 00:59:47 2017, 美东)
# Name Symbol Market Cap Price Circulating Supply Volume (
24h) % 1h % 24h % 7d
1
Bitcoin BTC $290,617,804,480 $17,358.40 16,742,200 $15,
825,500,000 -0.36% 5.62% 3.15%
2
Ethereum ETH $63,827,563,522 $662.47 96,348,146 $3,723,
910,000 -0.48% -10.50% 52.62%
3
Bitc... 阅读全帖 |
|
c********t 发帖数: 1756 | 17 大于n/k的element, 是不是得把数组无序变有序再找,preprocess: O(nlg(n)),
search time O(n) |
|
I**A 发帖数: 2345 | 18 45分钟,问了三道题目
(1)Give some scenarios where you might favor O(n^2) algorithm over a O(nlg
(n)) one
(2)Implement an algorithm int removeDuplicate(char[] s)
For instance change ”abbcccdda” to “abcda” and return 4(the number of
characters deleted).
(3)Implement an algorithm to check whether brace expressions are valid or
not
boolean isGood(String s, String braces); //assume braces are valid,{}[]()
题目超级简单
可是CODE第三题的时候犯了两个小的超级低级的错误
interviewer一问,我立刻就明白了忘了check。。。
郁闷死 |
|
d**e 发帖数: 6098 | 19 能说说第一题吗?
比如说"只对10个数排序"算不算?
nlg
or |
|
p*u 发帖数: 136 | 20 题目看起来都很厚道,祝LZ好运!
nlg
or |
|
f*********5 发帖数: 576 | 21 why there are 2 parameters of Issue 3)
O(nlg
or
valid,{}[]() |
|
I**A 发帖数: 2345 | 22 挂电话之前扔给我一道题,让我have fun (nnd, 这个我倒是听懂了)
怎么实现找kth element of a linkedlist, 条件是steps少于n+n-k
大家一起have fun吧
答之后的延续问题(而我,完全没明白他问的是什么)。
nlg |
|
G*******l 发帖数: 281 | 23 rrdw,what is LRU?
答之后的延续问题(而我,完全没明白他问的是什么)。
nlg |
|
|
d****o 发帖数: 1055 | 25 Give some scenarios where you might favor O(n^2) algorithm over a O(nlg
(n)) one" |
|
D**********d 发帖数: 849 | 26 想到一个 O(n^3) 的解法:
1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
if yes, check d(n2,n3) == sqrt(2)L,
if yes, output (x1,x2,x3,x4)
n^2 pairs * 2sum = O(n^3)
|
|
D**********d 发帖数: 849 | 27 想到一个 O(n^2 lg(n) ) 的解法:
1. sort on x axis, for the same x, sort on y both ascend-- O(nlg(n))
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2) L
if yes, solve a linear equation, get the axis of other two nodes (n2,n3)
of the sqare with (n1,n4) as diagonal nodes
check the existences of (n2,n3) in sorted list
n^2 * lg(n) = O(n^2lg(n)) |
|
|
|
P*******y 发帖数: 168 | 30 w...lab
是three sum,不是two sum |
|
|
P*******y 发帖数: 168 | 32 wiki上3SUM-hardness是不是说已经证明了最少只有O(n^2)解,对吧?
可能真被忽悠了。看我前面写太快让我来点思考这个问题。。。
不过刚通知过了,进入下一轮电面。他家要两轮哎 |
|
|
|
d**********x 发帖数: 4083 | 35 你就是被忽悠了
算法分析课上说了,我们至今不知道k-sum有没有优于O(n^(k-1))的解。。 |
|
|
|
|
|
j****y 发帖数: 1714 | 40 【 以下文字转载自 WaterWorld 讨论区 】
发信人: joyjoy (joy), 信区: WaterWorld
标 题: 知道你的权利—当遭遇执法人员时
发信站: BBS 未名空间站 (Mon May 20 01:55:08 2013, 美东)
本文档是 Know your Rights When Encountering Law Enforcement 手册的中文翻译。
翻译本手册的动机是太多的中国留学生,移民不知道自己的权力,在被执法人员宗族歧
视性调查的时候处理询问不当, 被执法人员抓住漏洞而被控向联邦执法人员撒谎(
lying to federal agents/officers), 即使执法人员根本没有其他任何证据来逮捕他
们。 最近的例子是NASA合同工姜波的案例: http://bojiangwatch.blogspot.com/ ) 在美国的中国血统人士必须吸取深刻教训防止种族迫害。
This document is the Chinese Translation of the Booklet published by ACLU:
Know your R... 阅读全帖 |
|
w********s 发帖数: 214 | 41 第二题貌似可以先把每个string变成 char array,然后排序,再变成string,然后存到
hashmap里。
,排序后的string做key, value就是一个string ()数组; 每个string都有同样的sorted
char array 也就是key.
最后把hashmap一个一个的值倒出来就是返回值了,时间复杂度是 O(m*nlg*n),空间复
杂度是O(n).
代码应该不长而且符合要求。 |
|
S*********g 发帖数: 24893 | 42 【 以下文字转载自 Stock 讨论区 】
发信人: StephenKing (金博士), 信区: Stock
标 题: 市面上流通1358种电子货币,包括ByteCoin
发信站: BBS 未名空间站 (Fri Dec 15 00:59:47 2017, 美东)
# Name Symbol Market Cap Price Circulating Supply Volume (
24h) % 1h % 24h % 7d
1
Bitcoin BTC $290,617,804,480 $17,358.40 16,742,200 $15,
825,500,000 -0.36% 5.62% 3.15%
2
Ethereum ETH $63,827,563,522 $662.47 96,348,146 $3,723,
910,000 -0.48% -10.50% 52.62%
3
Bitc... 阅读全帖 |
|
S*********g 发帖数: 24893 | 43 # Name Symbol Market Cap Price Circulating Supply Volume (
24h) % 1h % 24h % 7d
1
Bitcoin BTC $290,617,804,480 $17,358.40 16,742,200 $15,
825,500,000 -0.36% 5.62% 3.15%
2
Ethereum ETH $63,827,563,522 $662.47 96,348,146 $3,723,
910,000 -0.48% -10.50% 52.62%
3
Bitcoin Cash BCH $29,779,262,625 $1,766.66 16,856,250 $2
,532,880,000 -1.05% -5.14% 21.33%
4
Ripple ... 阅读全帖 |
|
j****y 发帖数: 1714 | 44 【 以下文字转载自 WaterWorld 讨论区 】
发信人: joyjoy (joy), 信区: WaterWorld
标 题: 知道你的权利—当遭遇执法人员时
发信站: BBS 未名空间站 (Mon May 20 01:55:08 2013, 美东)
本文档是 Know your Rights When Encountering Law Enforcement 手册的中文翻译。
翻译本手册的动机是太多的中国留学生,移民不知道自己的权力,在被执法人员宗族歧
视性调查的时候处理询问不当, 被执法人员抓住漏洞而被控向联邦执法人员撒谎(
lying to federal agents/officers), 即使执法人员根本没有其他任何证据来逮捕他
们。 最近的例子是NASA合同工姜波的案例: http://bojiangwatch.blogspot.com/ ) 在美国的中国血统人士必须吸取深刻教训防止种族迫害。
This document is the Chinese Translation of the Booklet published by ACLU:
Know your R... 阅读全帖 |
|
f********g 发帖数: 706 | 45 先回答beyond问题,爆发力训练秘诀: 适当负重下的高频率。
再谈谈我的感受吧,各位大多都是硅公,里边就设计一点儿算法思想大家好沟通。
基本的爆发力主要应用在进攻时快速超过防守和防守时瞬间迅速拦截。如果你在头脑里
形成一副抢劫球的动态画面,你就会看到你是在用前脚掌到脚尖进行发力。
我们已经知道了爆发力形成的原因。在针对性的练习之前,我还想谈谈爆发力的定义。顾
名思义,就是瞬间的力量。速度是形容词,力量是名词。 这个和绝对力量相反。 有了
这个定义,你就知道要练习爆发力,你需要的是做动作时速度“快”。
特别针对,足球专用的爆发力来讲。很明显,发出力量的根在脚尖上。我做为后卫,
爆发常用的就是一个斜线拦截,最核心的就是非常快速地迈出(跳出)拦截的最后一步
。 所以说,你要针对性的练习这个动作。练习方法有很多,但跟各种排序算法一样,
我们要nlg(n) 的方法。我介绍一种,不定仿真最优,但值得试试。可以腿上绑上沙袋
,向左前跳一次(注意大腿要平行与地),再在向右前跳一次,这是循环不变式,随时
间迭代到50米的距离,大家可以算算总共跳了多少米。我们来看训练到到什么程度呢?
或者说收敛判定。就... 阅读全帖 |
|
|
|
j****y 发帖数: 1714 | 48 本文档是 Know your Rights When Encountering Law Enforcement 手册的中文翻译。
翻译本手册的动机是太多的中国留学生,移民不知道自己的权力,在被执法人员宗族歧
视性调查的时候处理询问不当, 被执法人员抓住漏洞而被控向联邦执法人员撒谎(
lying to federal agents/officers), 即使执法人员根本没有其他任何证据来逮捕他
们。 最近的例子是NASA合同工姜波的案例: http://bojiangwatch.blogspot.com/ ) 在美国的中国血统人士必须吸取深刻教训防止种族迫害。
This document is the Chinese Translation of the Booklet published by ACLU:
Know your Rights When Encountering Law Enforcement.
The motivation for this Chinese Version is that so many innocent Chinese
scholars and im... 阅读全帖 |
|
a****o 发帖数: 686 | 49 The key invariant is to show that after every iteration of the loop, the
heap contains the smallest element in every list. (omit a formal induction
proof, as the question only asked you to devise an algorithm.) Notice that
each EXTRACT-MIN and INSERT operation requires O(lg k) time, since there are
never more than 2k elements in the heap. The loop requires only a constant
amount of other work, and is repeated n times, resulting in O(nlg k) running
time. |
|