c*****t
发帖数: 93 | 1 来自主题: JobHunting版 - 问道算法题 这题看样子是kmp，O(n)的 |
|
c********t
发帖数: 5706 | 2 二爷，我敲错了，是O(m*n) n: a.length m: b.length
如果是slide windows一个个划过去,比较a.substring(i, i+b.length())与b是O(m*n)
复杂度，除非有类似KMP的解法才有可能降为O(n) |
|
r**********a
发帖数: 71 | 3 我是从去年10月开始job hunting,中间圣诞节回国待了一个月，然后到这个月初全部面
完。基本上湾区最出名最火的几家公司都面了一遍，大多数都顺利拿到了Offer. 所以
在这里也把自己的面经贴一下，回馈版面感谢大家。
因为签了NDA，我就不具体提公司的名字，也不区分哪些题是哪些公司面的。就把它们
统一的描述一下，而且不少题是在不止一家公司被问过的。
我是今年毕业找工作，所以都是new grad类型的面试，大家可以对难度有个参考。个人
背景是cs专业美东在读，然后以前在国内的时候是ACM业余爱好者。没有代表学校参赛
过，但是在学校的OJ上有三位数的AC题量，基础还算不错吧。
华丽的分割线----------------------------------------------------------------
-----------------
Top K in N sorted array:
这题n多公司面。。就是Multiple merge sort的思路吧。然后弄个size为K的heap存结
果。大部分公司都只要求你说出思路，没要求实现。有一家要求我具体写出来了，我是
用... 阅读全帖 |
|
s*w
发帖数: 729 | 4 不看任何提示，纯自己想，碰上难题(或者需要一些 trick 的)几天(每天3个小时)都出
不来的是常事，比如 soduko, kmp 这种；所以一天能刷 5 题很牛 |
|
|
g********E
发帖数: 178 | 6 wiki一下KMP算法，那个弄懂了自然就会做这个了 |
|
c*****9
发帖数: 4247 | 7 面试中会考吗？
看了一天 感觉只看会80% 还不太会灵活运用
谢谢 |
|
s*****n
发帖数: 5488 | 8 不会。但是其实蛮简单的
算法导论的叫兽们写得太复杂了。 |
|
d*****c
发帖数: 605 | 9 相当重要。。。。。
面到现在，一共被考过3次。。。。。。都是要写code的。。。。 |
|
|
c*********8
发帖数: 561 | 11
我还真是别人code和分析啥的没看懂....看导论一下就看懂了.... |
|
|
x*********w
发帖数: 533 | 13
见过有考Rabin Karp Hashing的 |
|
|
|
|
|
|
|
|
|
H****r
发帖数: 2801 | 22 听说实际应用BM是标杆
★ 发自iPhone App: ChineseWeb 7.8 |
|
l***i
发帖数: 1309 | 23 Z algorithm, suffix tree |
|
|
l***i
发帖数: 1309 | 25 some idea like KMP would work for this problem, although you can also use
much more powerful Manacher's algorithm which finds all maximal palindrome
in a string. |
|
|
w****y
发帖数: 9 | 27 你是对的。
给定一个string, 用pat = string[:-1] (除去最后一个char) 作为pattern, 在str =
string[1:] (除去第一个char) 中，用kmp搜索。搜索结束后得到的state值即为pat的
prefix（也即string的prefix）长度，同时也是str的suffix.
string = abcabca
str = bcabca
pat = abcabc
搜索结束时,虽然pattern没有找到(除非pat==str)，结束时state的值即为所求长度。
bcabca
abcabc |
|
d**e
发帖数: 6098 | 28 ☆─────────────────────────────────────☆
seahope (seahope) 于 (Wed Jun 5 20:45:27 2013, 美东) 提到:
别把CS神化了，别动不动就劝人转专业也不看看是不是合适。别搞的好像读个CS就个个
都进大公司高新高福利，绿卡在手万事不愁的样子。能在板上报OFFER的都是牛人，背
后还有好多找不到工作或者在小公司熬日子的，也不一定个个都能找到，有时候运气也
是很重要的。
☆─────────────────────────────────────☆
rhsh (天晴) 于 (Wed Jun 5 20:52:49 2013, 美东) 提到:
是啊
100人面google，5个拿offer，其中3个报offer
然后其他人看来CS随随便便进google。。。
我现在都觉得能找个公司做有点意思的东西就很开心了，flag算中大奖
☆─────────────────────────────────────☆
naiveso (树袋熊) 于 (Wed Jun 5 21:41:46 2013,... 阅读全帖 |
|
r**h
发帖数: 1288 | 29 后缀树的意义就是可以高效的查一个串的子串
如果查询次数多的话，后缀树比KMP节省时间 |
|
|
p*****3
发帖数: 488 | 31
一定要看Robin Karp hashing啊~~ |
|
i******t
发帖数: 22541 | 32 必看吗？
必看的话 我就看看 string的东西都没看还。。。。 |
|
t****i
发帖数: 88 | 33 我只看了broteforce 汗
★ 发自iPhone App: ChineseWeb 7.5 |
|
t***t
发帖数: 6066 | 34 靠，我2周前面试就用了这个。我还不知道是啥Robin Karp hashing，自己当场想出来
的，以前没看过。佩服自己一下。 |
|
|
t***t
发帖数: 6066 | 36 也算运气，因为以前看过一种rolling hashing的算法。正好用上。 |
|
|
|
r********d
发帖数: 7742 | 39 你牛逼，两个图灵奖得主合力才想出来的算法你一袋烟的功夫就搞定了！ |
|
r*********n
发帖数: 4553 | 40 帅是帅，可是要写出来一个deterministic finite automaton的transition matrix还
是不容易
相对来说Z Algorithm直观很多。 |
|
|
|
y*****i
发帖数: 141 | 43 自己顶一下。
KMP不适合多次查询的情况，Aho-Corasick适合查前缀而不是任意位置的子串，所以只
能是suffix tree吧？ |
|
s******e
发帖数: 493 | 44 3. sorting on start time and then move to check till a start time is bigger
than the end time of the currently checked one. keep going. might not be
optimal. seems to be able to borrow kmp idea for reducing the time. |
|
|
|
p*****2
发帖数: 21240 | 47
感觉KMP应该可以呀。内存占用少多了。不过你需要判断前后要是空格或者起点，终点
吧。感觉不是这题考察的目的。 |
|
J****3
发帖数: 427 | 48 恩恩 二爷说的是。如果这题确实是考察模式匹配， 二爷你觉得用KMP还是RK还是别的
？个人感觉RK比较容易实现点 |
|
r*c
发帖数: 167 | 49 RK肯定好写些，尽管它比KMP要慢不少。
前些天看到一个帖子，把RK的实现搞得特麻烦。下面贴个改进的，其中hash function
可替换，只要把各个char的信息都用到就好了。
class RobinKarpSolution
{
public:
char *strStr(char *haystack, char *needle) {
int nHSLen = strlen(haystack), nNDLen = strlen(needle);
if(nNDLen > nHSLen) return NULL;
int h_hash, n_hash = hashAString(needle, nNDLen, 0);
for(int i = 0; i <= nHSLen-nNDLen; ++i){
h_hash = hashAString(haystack, nNDLen, i);
if(n_hash == h_hash) {
if(!C... 阅读全帖 |
|
v*****d
发帖数: 348 | 50 这个面经对找工作的童鞋没啥用，纯吐槽。
老公最近搬去加州，于是我骑驴找马想着要一家团聚。朋友在paypal是distinguished,
让朋友refer了我 。
首先是面试过程极度混乱，前前后后大概有六七个组要电面我，甚至我onsite
paypal的那天还有组给我发信约电面，感觉各个组的recruiter完全不知道其他组
recruiter的存在，非常各自为政的感觉。
然后极品的onsite来了。老实说，作为一个码婆还是第一次被人这么鄙视。见的五六个
人，除了一个中国人很不错，其他人都傲慢无比，glassdoor上这么一段评论， ”very
arrogant set of people. It appeared if they are from spaceship.“ 简直太对
了。问题都极其简单 (同学，你那么arrogant, 要是出的题有点水平，我还可以改观一
下)，有一道题具体忘了，类似一堆数字求重复数字那种，我用了hashset, 老印摇摇头
，你为什么不用hashmap， hashmap check一个key是constant time， hashset不是... 阅读全帖 |
|
