l*****a
发帖数: 14598 | 1 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 | 2 问了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 | 3 来自主题: JobHunting版 - AMZ面经 找出word的重复频率
是给定特定的一个单词还是所有的单词？
是考察KMP, Rabin-Karp之类的模式匹配算法还是考察Hash table? |
|
|
b******n
发帖数: 4509 | 5
对新加入的 interval 范围再合并
用一个marker来分隔每行即可
rabin karp
先把多边形画出二维地图，之后就容易了 |
|
P********i
发帖数: 172 | 6 Phone 1:
:
What is “static” variable?
How can many instance share a resource
What is deadlock, how to prevent it?
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
One short circuit is to use the length, since s1.len <> s2. len , then
return false. Anything else you can think of in the similar way?
My answers:
Hashtable? No, need extra spac... 阅读全帖 |
|
g**e
发帖数: 6127 | 7 他考的应该是怎么写hash function。如果句子很长，可以取一个segment做hashing。
类似Rabin–Karp
当然可能会有collision |
|
b*****1
发帖数: 52 | 8 可以用double hash reduce collision , e.g., use different base in robin karp. |
|
g**u
发帖数: 583 | 9 马上就要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 with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F ... 阅读全帖 |
|
f****4
发帖数: 1359 | 10 clrs 2rd, 32.2
或者直接wiki Rabin-Karp algorithm |
|
D*******e
发帖数: 151 | 11 就４５分钟来说，这题目够多的。
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 | 12 Use the idea of Rabin-Karp. Map each string to an integer. Only compare
those mapped to the same integer. |
|
D*******e
发帖数: 151 | 13 Use the idea of Rabin-Karp. Map each string to an integer. Only compare
those mapped to the same integer. |
|
d*******l
发帖数: 338 | 14 如果是普通的hashtable，计算一个word的hash值至少是O(L)的，加上一些别的开销，
可能还不如trie最多访问L个节点效率高。如果用类似rabin-karp里那种hash，就是通
过前面的单词的hash值O(1)时间计算出后面的单词的hash值，就需要解决冲突来保证正
确性。我觉得都是可以的，hashtable也不是一定就会更好。 |
|
d*******l
发帖数: 338 | 15 如果是普通的hashtable，计算一个word的hash值至少是O(L)的，加上一些别的开销，
可能还不如trie最多访问L个节点效率高。如果用类似rabin-karp里那种hash，就是通
过前面的单词的hash值O(1)时间计算出后面的单词的hash值，就需要解决冲突来保证正
确性。我觉得都是可以的，hashtable也不是一定就会更好。 |
|
a*****n
发帖数: 158 | 16 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。 |
|
a*****n
发帖数: 158 | 17 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。 |
|
|
i******e
发帖数: 273 | 19 用DFA的是rabin karp吧？
把KMP改成匹配成功以后如果text string (B) 还没结束，
i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
function对应的位置继续匹配
ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
直到text string 结束，用一个counter记录匹配的次数 |
|
|
|
x*********w
发帖数: 533 | 22
见过有考Rabin Karp Hashing的 |
|
g**G
发帖数: 767 | 23 kmp每次都记不住，还是用rabin karp吧 |
|
p*****3
发帖数: 488 | 24
一定要看Robin Karp hashing啊~~ |
|
t***t
发帖数: 6066 | 25 靠，我2周前面试就用了这个。我还不知道是啥Robin Karp hashing，自己当场想出来
的，以前没看过。佩服自己一下。 |
|
J****3
发帖数: 427 | 26 Strstr() using Robin-Karp alg
large case 会有6个过不了。。求大牛帮我看下哪里有问题。
const int base = 26, mod = 997;
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int l_h = strlen(haystack);
int l_n = strlen(needle);
if(l_n > l_h) return NULL;
int h_hash = 0, n_hash = 0;
for(int i = 0; i < l_n; i++){
n_hash = (n_hash*base + needle[i])%mod;
... 阅读全帖 |
|
A*********c
发帖数: 430 | 27 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
空格是pattern的一部分，无所吧。
第二题就是多了一个数字少了一个数字。
抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
找出2XOR4的一个非0位，就是2和4不一样的bit位置
再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。 |
|
A*********c
发帖数: 430 | 28 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
空格是pattern的一部分，无所吧。
第二题就是多了一个数字少了一个数字。
抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
找出2XOR4的一个非0位，就是2和4不一样的bit位置
再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。 |
|
l*******n
发帖数: 101 | 29 1. since it asks for a binary way. maybe use robin karp? as for the hashing,
just xor all the elements in str and when u move forward the window in the
file, xor the first element at the front, which will cancel out the first
element, then xor the next element and so on.. |
|
u*****n
发帖数: 126 | 30 Rabin-Karp for strstr
I cannot quite understand your second question. |
|
M*******a
发帖数: 1633 | 31 所谓牛逼就是平时挺都不大听到的算法，用更用不到的算法，比如什么
max flow/min cut
bellman-ford
bi-partite matching
boyer-moore
red-black tree
rabin-karp
aho-corasick
min-hash
其他
看看概率多少 |
|
l***i
发帖数: 1309 | 32 知道名字不算什么，能不看书证出SAT is NP complete，再能reduce Karp 21
problems才算入门。 |
|
|
c******n
发帖数: 4965 | 34 paper 的最大贡献是什么？就是找到这个算法！ 可能30%的贡献是complexity proof.
但让你一个普通程序员45分钟想出来 karp (kmp 的k) 可能几个想出来的东西，你不
觉得要踢这个出题的么？ |
|
c******n
发帖数: 4965 | 35 明摆着你找到的会做的人 肯定不是Karp or Papadimitriou, 那他们肯定就是先前看了
这个算法（三个作者都几个月琢磨出来的， 得神仙才能45分钟写出来），
那狗家还唧唧歪歪说不让背题， 出这题的人自己都知道就要看背出来的结果， 他不是
神经分裂么？ |
|
|
e*******s
发帖数: 1979 | 37 string matching算法太多了
Rabin Karp KMP Boyer Moore 掌握一下主要的思路吧
理解其中的一些关键思想的话
在项目里面也会用到类似的时候
面试的时候稍微提一下感觉会有帮助的
认真刷就是做完题目 把别人博客上的代码+评论 leetcode的discussion好好看一遍
光做出来只是一部分 |
|
n******h
发帖数: 2482 | 38 Palantir CEO Alex Karp.
Can you read? |
|
|
l****u
发帖数: 1764 | 40 RT，我用chase freedom买的1500刀costco的cash card都拿到5X了，用LD的账号买，居
然就给了1X。发message去argue，居然说Costco.com不算WholeSale Club而算Misc
请问现在应该打电话据理力争么？ 其他账号都拿到5X了，可以作为一个理由么？如果
都不行，costco买的cash card没activate没花过可以退货么？
下面是message 内容
=============================================================
Dear XXX,
Thank you for contacting Chase with youre rewards inquiry.
The rewards adjustment you requested cannot be made
because the merchant is not in an eligible category. Upon
review, I confirm that Costco.com is categorized ... 阅读全帖 |
|
s*****e
发帖数: 6053 | 41 The New Way to Calm Crying And Help Your Baby Sleep Longer
The Happiest Baby on the Block.
Harvey Karp, M.D.
看了感觉挺神奇的，一朋友推荐给我们的，她家宝宝不到5个月就已经能睡整夜了。。
。 |
|
h***a
发帖数: 338 | 42 今天在国内论坛上刚看到这个，觉得很有用，大家看看。
用BT可下载“The_Happiest_Baby_on_the_Block”，我花了12分钟就下载好了，种子请
google。 以下非原创，从坛子里妈妈的帖子中截取的。
这个片子里面基本上告诉你，所有的BB，出生后2个礼拜，他就开始觉得身边的环境和
他以前在母体里面太不一样了。于是这个小小人就感到非常的害怕。害怕所以狂哭。
从图书馆借了盘非常不错的DVD《the happiest baby on the block》，介绍了五个迅
速让小宝宝安静下来的方法，这两天尝试了一下，除了最后一种其他都很好用，真是父
母的好帮手，强烈推荐，感谢Dr. Harvey Karp
1、swaddling。小宝宝初生的前三个月就像是怀孕的第四个阶段（the fourth
trimester），他需要时间渐渐地了解接受这个复杂的世界，他在母亲子宫里是被紧紧
包裹着的，所以刚出来他仍然喜欢被紧紧地包裹着，swaddling是最好的让小宝宝有安
全感冷静下来的方式。本来以为宝宝大了不喜欢被裹了，所以我们的“swaddle me“已
经闲置了不少时间，现在拿出 |
|
d*********s
发帖数: 109 | 43 我是不赞成打很多疫苗的，但是startle的问题有可能和你swaddle的方法有关。
可以看一部片子，或许会有帮助：
《The Happiest Baby on the Block》by Harvey Karp |
|
H**********s
发帖数: 303 | 44 昨天上了个课叫：how to calm a crying baby，教了一些安抚colic baby的技巧，大
部分的内容都是来自Dr. Harvey Karp的光碟，http://www.happiestbaby.com/，也可以从Youtube搜到一些片断。主要的是用以下的五个S's：
1) Swaddle the baby
2) place the baby on his side or stomach;
3) shush him loudly;
4) swing or bounce him rhythmically;
5) give him something to suck on.
最令我惊讶的是他真的对着宝宝的耳朵大声地嘘，马上就把宝宝安抚好了。帮我们上课
的护士说新生的宝宝耳朵里还有残留物保护着，不会伤到耳朵。
这个youtube vedio很搞笑：
http://www.youtube.com/watch?v=kO6CR2aAM3I
希望对大家有帮助。 |
|
x******n
发帖数: 35 | 45 swaddle在美国也是很好的方法。
建议看看Dr harvey karp的Happiest Baby Swaddle Technique on youtube... |
|
J*******a
发帖数: 96 | 46 你要不试试看Dr. Karp的 the happiest baby on the block里面的方法。我以前觉得
别人都是瞎吹捧的，后来试了才知道真的挺神的。你可以买dvd来看。 |
|
D*******r
发帖数: 7 | 47 一定要看书，要对宝宝的基本生长发展和常见问题心里有数才行，这样遇到问题才不会
慌张。比如脐带什么时候掉，屁股红了怎么办，几天不拉才需要担心？什么时候可能有
growth spurt, 固定时间哭可能是colic, 万一生病发烧该怎么办, 怎么测体温，多少
度该打电话给医生 etc.
The happiest baby on the block 三s大法哄睡非常有效。这个没时间看书可以到
youtube上搜视频
http://amzn.to/Happiest-Baby-Block-Harvey-Karp |
|
|
|
H**********l
发帖数: 44 | 50 If this is a low risk pregnancy,
Did you consider having the baby at home or hospital?
If you're having the baby at a hospital,
Did you consider hiring a midwife as a monitrice or a birth/labor doula?
In any case,
Pregnancy is a rite of passage. It's a time of personal growth. Time to
improve life style and face your fears, etc.
I suggest you read some books. For example, books written by Ina May,
Elisabeth Davis, Henci Goer, Aviva Jill Romm, Sheila Kitzinger, Harvey Karp,
Sears and Sears, Ro... 阅读全帖 |
|
