w******1
发帖数: 520 | 1 The Rabin-Karp Algorithm
The Knuth-Morris-Pratt Algorithm
The Boyer-Moore Algorithm |
|
j**l
发帖数: 2911 | 2 什么KMP, Rabin-Karp, BM, Suffix Tree, Suffix Array, 能用上的请尽量用
1. Write a function f(a, b) which takes two character string arguments and
returns a string containing only the characters found in both strings in the
order of a. Write a version which is O(n^2) and one which is O(n).
2. Given that one of the strings is very very long , and the other one could
be of various sizes. Windowing will result in O(N+M) solution but could it
be better? May be NlogM or even better?
3. Given that you have one str |
|
l*****a
发帖数: 14598 | 3 1.
for O(n^2) just use LCS(the longest common subsequence)
for O(n),create a hashtable for b and scan a to see whether each of
the characters are in the hashtable or not
2.
i can't understand what u want
3.
Rabin-karp
4.
a hash table stores the ocurrance of each word,a minimum heap of size 10
which contain the ten most frequent words.
pay attention once the memory can't hold all the words,need some ways to
solve.
such as divide them into K parts,each part use the same and find the top
10,then |
|
I**********s
发帖数: 441 | 4 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
j**l
发帖数: 2911 | 5 来自主题: JobHunting版 - AMZ面经 找出word的重复频率
是给定特定的一个单词还是所有的单词？
是考察KMP, Rabin-Karp之类的模式匹配算法还是考察Hash table? |
|
|
|
|
b******n
发帖数: 4509 | 9
对新加入的 interval 范围再合并
用一个marker来分隔每行即可
rabin karp
先把多边形画出二维地图，之后就容易了 |
|
g**e
发帖数: 6127 | 10 他考的应该是怎么写hash function。如果句子很长，可以取一个segment做hashing。
类似Rabin–Karp
当然可能会有collision |
|
f****4
发帖数: 1359 | 11 clrs 2rd, 32.2
或者直接wiki Rabin-Karp algorithm |
|
s**x
发帖数: 405 | 12 Please read this:
http://en.wikipedia.org/wiki/Primality_test
This is deterministic polynomial time.
Best known deterministic algorithm is AKS primality test in O((logn)^7.5).
Best practical probabilitic algorithm is Miller-Rabin in O((logn)^4) |
|
D*******e
发帖数: 151 | 13 就４５分钟来说，这题目够多的。
If string is short, consider TRIE.
Map each string to an integer by Rabin-Karp? Then maintain a map where key
is hash value and value is the list of strings mapped to this hash value.
Is this the solution? |
|
D*******e
发帖数: 151 | 14 Use the idea of Rabin-Karp. Map each string to an integer. Only compare
those mapped to the same integer. |
|
D*******e
发帖数: 151 | 15 Use the idea of Rabin-Karp. Map each string to an integer. Only compare
those mapped to the same integer. |
|
d*******l
发帖数: 338 | 16 如果是普通的hashtable，计算一个word的hash值至少是O(L)的，加上一些别的开销，
可能还不如trie最多访问L个节点效率高。如果用类似rabin-karp里那种hash，就是通
过前面的单词的hash值O(1)时间计算出后面的单词的hash值，就需要解决冲突来保证正
确性。我觉得都是可以的，hashtable也不是一定就会更好。 |
|
d*******l
发帖数: 338 | 17 如果是普通的hashtable，计算一个word的hash值至少是O(L)的，加上一些别的开销，
可能还不如trie最多访问L个节点效率高。如果用类似rabin-karp里那种hash，就是通
过前面的单词的hash值O(1)时间计算出后面的单词的hash值，就需要解决冲突来保证正
确性。我觉得都是可以的，hashtable也不是一定就会更好。 |
|
e***l
发帖数: 710 | 18 还有高级一点的随机算法，Miller-Rabin，知道的话应该能加分 |
|
a*****n
发帖数: 158 | 19 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。 |
|
a*****n
发帖数: 158 | 20 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。 |
|
S**I
发帖数: 15689 | 21 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 22 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
|
|
i******e
发帖数: 273 | 25 用DFA的是rabin karp吧？
把KMP改成匹配成功以后如果text string (B) 还没结束，
i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
function对应的位置继续匹配
ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
直到text string 结束，用一个counter记录匹配的次数 |
|
|
|
r**h
发帖数: 1288 | 28 miller rabin test这种东西，就算你会，和面试官也得解释半天。那几个数论的引理
就要说半天，没准人最后还觉得你错了
这种竞赛常用的东西我觉得不适用在面试上
n^ |
|
x*********w
发帖数: 533 | 29
见过有考Rabin Karp Hashing的 |
|
g**G
发帖数: 767 | 30 kmp每次都记不住，还是用rabin karp吧 |
|
A***o
发帖数: 358 | 31 如果允许漏掉一些质数，效率上可以做得比筛子法好很多，比如在第n个prime gap用
miller rabin找第一个质数作为第n个质数 |
|
A*********c
发帖数: 430 | 32 碰上这题，花5分钟列个表，把几个常见算法如bruteforce，KMP，Rabin，Boyer Moore
复杂度都分析一下，优劣大概一说。然后让面试官挑一个你bug free写出来，这轮我觉
得就没跑了。 |
|
n********e
发帖数: 41 | 33 楼主 看到 你 isDiffByOne 函数就知道你必然要超时
Leetcode免费给你用 就别挑剔了。凡事要先从自身找问题
你那个测试不是大数据
真正的大数据在这里：
start = "nanny";
end = "aloud";
String[] d = {"ricky","grind","cubic","panic","lover","farce","gofer
","sales","flint","omens","lipid","briny","cloth","anted","slime","oaten","
harsh","touts","stoop","cabal","lazed","elton","skunk","nicer","pesky","
kusch","bused","kinda","tunis","enjoy","aches","prowl","babar","rooms","
burst","slush","pines","urine","pinky","bayed","mania","light","flare","
wares","wom... 阅读全帖 |
|
u*****n
发帖数: 126 | 34 Rabin-Karp for strstr
I cannot quite understand your second question. |
|
p********n
发帖数: 165 | 35 用rabin-carp的方法 可以把每个单词都hash成一个数字，这样比较起来比较快，
至少可以优化成 O（n^2*m） m是平均每个句子里单词的个数， 稍微好一些。
另外一个优化： hash 每个句子的单词的时候，统计每个句子的单词数，并按照单词数
排序O(nlog(n))
这样，可以从第二最长的句子开始往后循环， 每次循环，假设到了第i个句子，要和所
有1...i-1的句子比，如果到目前为止share的单词数最大的solution >= 第i个句子的
整个单词数的时候，就可以中止程序。 算是一个early termination. |
|
M*******a
发帖数: 1633 | 36 所谓牛逼就是平时挺都不大听到的算法，用更用不到的算法，比如什么
max flow/min cut
bellman-ford
bi-partite matching
boyer-moore
red-black tree
rabin-karp
aho-corasick
min-hash
其他
看看概率多少 |
|
l**n
发帖数: 43 | 37 如果本科非科班出身，不建议去ebiz。2014级有一些非科班出身的ebiz学生目前还没找
到工作
没有水项目，只有水人
CMU INI BIC 这些项目招人标准虽然比正统cs program低不少，生源参差不齐，招生人
数多，但如果能坚持完成cs的一些课程:
15410 - Operating System。课程有四个Project，包括写两个简单的驱动，实现多线
程库(mutex, condition variable, rw_lock,fork,wait,exec)，实现简单的内存管理
和进程调度。比较了下MIT的操作系统课6.828 (xv6)，410的project难度要更大一些。
一周至少要花20+小时做project。
15440 - Distributed System。今年的授课老师是Andrew File System的架构师和主要
实现者Satyanarayanan。除了project之外，还包括二十几篇论文 http://www.cs.cmu.edu/~15-440/readings.html
15746 - Advanced Storage System。授课老... 阅读全帖 |
|
|
m****a
发帖数: 2593 | 39 我也觉得这个状元算不错的了
https://cchere.com/article/3888026
好学生进入大学后的颓废，在美国这里也存在，当然国内更多。我观察的感受是，与题
海战术和填鸭教学的关系都是表面化的，实质是学生本人自我管理的意识和意志不强。
很多孩子在有序严格的教学和生活管理环境中，能够亦步亦趋地跟随课程和作息时间表
，取得很好的成绩和日常表现。然而，大学是个班级、课堂和生活等方面管理都很松散
的集体，要求学生自行安排作息、选课、作业和论文，要求学生具备自我克制和井井有
条的素养。事实上我相信几乎每个人都经历过这个不适应自我的痛苦。
另外，“聪明”孩子颓废程度确实可能更严重，我的感觉是这类“聪明”是神经敏感程
度相对普通人高，往往反应奇快、记忆神速，容易在数学、音乐和美术等相对单纯的技
艺方面表现突出，但是往往这类神经类型的稳定性和协调性并不好，在冲动克制、自我
激励、规划安排等方面就比较弱，所以往往会在真实复杂的社会环境里挫折消沉下去，
长期来看还会更多地出现焦虑和抑郁等问题。这样的孩子在痛苦中如果利用好原有的“
聪明”去积极思考自我、探索出路，会在经历一个陧磐后，归于宁... 阅读全帖 |
|
e*******s
发帖数: 1979 | 40 string matching算法太多了
Rabin Karp KMP Boyer Moore 掌握一下主要的思路吧
理解其中的一些关键思想的话
在项目里面也会用到类似的时候
面试的时候稍微提一下感觉会有帮助的
认真刷就是做完题目 把别人博客上的代码+评论 leetcode的discussion好好看一遍
光做出来只是一部分 |
|
T******t
发帖数: 420 | 41 【 以下文字转载自 Parenting 讨论区 】
发信人: ThisThat (TicTac), 信区: Parenting
标 题: 说到包皮，贴一下纽约时报上的一篇文章吧。
发信站: BBS 未名空间站 (Thu Sep 2 14:20:05 2010, 美东)
August 30, 2009
The Latest Fight Over the Foreskin
By RONI CARYN RABIN
In the late 19th century, Victorian-era doctors described the male foreskin
as a “source of serious mischief.”
Convinced that masturbation led to insanity, and that it was the sensitive,
responsive foreskin that stimulated masturbation, surgeons started promoting
therapeutic circumcision to |
|
T******t
发帖数: 420 | 42 去年的文章。有点长，但是很全面，很中肯。
August 30, 2009
The Latest Fight Over the Foreskin
By RONI CARYN RABIN
In the late 19th century, Victorian-era doctors described the male foreskin as a “source of serious mischief.”
Convinced that masturbation led to insanity, and that it was the sensitive,responsive foreskin that stimulated masturbation, surgeons started promoting therapeutic circumcision to cure young men of the “sin” of excessive indulgence and prevent its corollary, “masturbatory insanity,” a catchall ph |
|
|
|
|
发帖数: 1 | 46 12月27日 为什么我要替中国辩护
我要替中国辩护，并不是因为我是一个中国人，而是因为我知道中国就和这世界上绝大
数的国家一样，虽然有很多丑陋的现象，但是他们是受害者。就
象这个犯罪集团里很多的人一样，他们来自各种种族，他们可能充当了工具，但他们不
是制造这一切，谋划这一切的人。虽然经常会暴露中国产品出现问题。但要知道中国是
世界工厂，他们只是打工者，他们只是按照各种雇主提供的配方来生产，他们并不知道
他们会产生怎样的后果。或者这些工人知道后果，但他们只是奴隶，他们又如何去改变
这一切？ 所以，当我的调查不断往前推进的时候，不可避免地会涉及各国的企业，但
这并不表明是针对这个国家或这个国家的人民，而是针对一种社会现实和丑陋现象。就
拿菲律宾来说，菲律宾是一个犯罪猖獗的国家，有很多犯罪分子，但是菲律宾人民却是
这个集团的受害者，他们／她们被绑架，沦为了牺牲品，人体实验对象。一个日本人，
强奸上千名菲律宾女孩，却没有受到惩罚。以前我也提到过，有20个国家的名单，这20
个国家的人民其实都是受害者。现在他们把矛头对准中国，或许仅仅是因为我揭示了他
们图害世界人民的内幕，而我是一个中国人的缘... 阅读全帖 |
|
c****e
发帖数: 2097 | 47 there are two kinds (or more) of origins for jewish last names.
obviously, there are names such as rabin, sever, sharon, and many others,
some sounds even arabic (we all know they're the closest relative of arabs).
these are real jewish last names.
jewish first names are more widespread nowadays, because of the christian
belief. names such as david are jewish. but now everyone takes their name
from the bible.
then, there are names which are not originally jewish names, they are
usually artificia |
|
i*****s
发帖数: 15215 | 48 中新网10月17日电 据台湾东森电视台网站报道，丁字裤获得很多女士们的喜爱，它
屡屡在女士们的臀部上创造奇迹，被视为时尚、。被誉为“最性感的内衣”。
但是专家提出警告说，丁字裤很可能有害健康：有时候它们太紧，有时候它们以不
当的方式磨擦私密部位；有时候，它们就是让人觉得不那么干净。
轻薄短小的内衣真的对健康有害吗？美国康乃狄克州爱因斯坦医学院(Albert
Einstein College) 的妇科权乌伊拉宾博士(Dr. Jill M. Rabin)指出，是否容易感染
的体质，主要决定了你是否适合穿丁字裤。
如果你容易感染尿道炎或阴道炎，一旦你穿上丁字裤，你可能更难摆脱上述的毛病
。她指出丁字裤的三大要“害”，内容如下：
许多丁字裤、特别是性感蕾丝的那种，采用的是不透气材质，而非棉质。因此会让
私密处因为不透气而潮湿，容易造成感染。
再者，即使整件丁字裤是棉质的，但由于它太小件，让外阴曝露更多的娇嫰肌肤，
跟紧身裤或牛仔裤等莱卡或丹宁布料磨擦，会增加“损伤”的风险。
最后，细小的布料在深处左右移动，很容易把裤裆上沾有的的细菌，从一个地方带
到另一处地方。 |
|
b****e
发帖数: 985 | 49 raiders -- bmouse, boxster, wofftt
titans -- ras, titan
steelers -- computarch, qiaqia, rabin
jets -- yankees, .....
colts -- rickgocolts, msee,
browns -- zhyue,
broncos -- gobuffs, firstdown, seconddown, thirdown, touchdown,
pats -- fasten
eagles -- douglas, babyvox
tampa -- wfk, underdog
packers --
niners -- boxster
falcons -- gardenia,opson,
giants -- DJ
panthers -- underdog
rams -- tintin, maclaonie
大家继续补充 |
|
l******g
发帖数: 115 | 50 Excess Pounds, but Not Too Many, May Lead to Longer Life
By RONI CARYN RABIN
Published: June 25, 2009
Being overweight won’t kill you — it may even help you live longer. That’
s the latest from a study that analyzed data on 11,326 Canadian adults, ages
25 and older, who were followed over a 12-year period.
The report, published online last week in the journal Obesity, found that
overall, people who were overweight but not obese — defined as a body mass
index of 25 to 29.9 — were actually less li... 阅读全帖 |
|
