x****k
发帖数: 2932 | 1 第一道题可以用KMP 算法，但感觉面试时问KMP有点难了
第二道板上有人提过，实际上是用在embedded的环境中的，
p是个寄存器的地址，函数入口需要声明为volatile，循环检查第n bit是否被置为1，
严格的话还要一些入口参数检查。volatile会强迫编译器不能优化这段代码，每次循环
都需要重新读取 *p.
void wait(volatile int* p, int n )
{
assert(NULL ！= p)
while ((*p & (1 << n)) == 0);
} |
|
A********l
发帖数: 184 | 2 网上扔的简历，一周后recruiter来电话约了电话面试。
hiring manager打来电话，问了简历上的问题，比较简单。然后问了一个简单的题目:
如何找出apache weblog中访问最多的几个url。用linux shell如何实现，用java如何实现。
过几天另一个组的hiring manager也来电话，聊了聊，比较开心。
几天后约了onsite，见了10个人，每次两个人。问题都比较简单。
round 1:
hiring manager 1， 聊天，很开心。
round 2:
一个在akamai干了11年的老年软工
2.1 设计course registration的数据库schema
2.2 Fibonacci递归和非递归实现
2.3 三个盒子，一个装的全是白旗子，一个全是黑棋子，一个是混合，但是所有的
label都是错误的，你可以从盒子中draw几个棋子。如何纠正盒子的label，同时保证
draw的次数最少
2.4 两个dice，如何label，使得他们的可以表示01-31中的所有数字
round 3：
两个老年软工:
3.1 聊天
3.2 程序找错，一个计算两个集... 阅读全帖 |
|
K******g
发帖数: 1870 | 3 面试的是美国人，英语很好
一上来就问为什么申请twitter
然后马上coding，实现strstr（）。还没有写完，就问我complexity。我说是O(nm),他
追问一下，什么情况下是exactly O（nm)，我说是当str2不是str1的substring的时候。
写完代码后，就问优化。首先是算法上，我说了KMP，然后要我大概讲一下KMP的思路，
我只记得有个preprocess的过程，把一个string的prefix弄到一个array里去。然后又
问，怎么从程序结构上优化，比如str1非常非常长，我就说分成很多chunks，放到不同
的machine上去跑。他又说，那样会有问题，有可能在分chunks的时候把一个substring
的match打断，问我怎么办。我没有答上来，后来想通了，其实很简单。在分chunk的时
候，把断开的地方的左边和右边一定范围内，再弄一个chunk出来，这样子如果有match
的话，就逃不掉了。
接下来，就是设计问题。许多machine，每个machine上有许多user，每个user有很多
followers，怎么统计每个user的平均foll... 阅读全帖 |
|
s*****n
发帖数: 5488 | 4 这题看上去可以从kMP变化得到一个解。
如果是一个., 那么KMP的prefix 表对应项++.
如果是一个*,那么happy了，或者match，或者从不match那里从新开始。
应该是O（n)算法。 |
|
g*******s
发帖数: 2963 | 5 我记得KMP好像也是O(n)吧，但是KMP优势是可以找出一个连续string是否是另一个的
substring |
|
r**d
发帖数: 316 | 6 用kmp匹配算法的变形。
同样先算overlap函数，然后从字符尾向头反向匹配。同一般匹配不同的是context结束
就认为成功。第一个匹配 成功的即为所求。
kmp是o(m+n)所以此算法也是o(2n)=o(n)
prefix
S |
|
z*******y
发帖数: 578 | 7 前些日子面的，尽管code都写出来了 但那个面试官好像很不喜欢Java，我的code都用
Java写的
最后也没给下一轮
1) Locate a substring within a string. (Find the first occurance of
needle in haystack, or return null.)
char* strstr(char* haystack, char* needle) {
}
mention了一下KMP算法，然后用那个最直接的方法写的code. 他该不会是想让我把KMP
算法在interview里敲出来吧
2)/*
* Given an array and a value, remove all instances of that
* value in place and return the new length. The order of
* elements can be changed. It doesn't matter what you leave
* beyond the new length.
*/
size_t remo... 阅读全帖 |
|
g*****k
发帖数: 623 | 8 电话里写KMP不太可能吧。
还会有更好的。继续努力
KMP |
|
b******t
发帖数: 965 | 9 有谁能讲讲这个题的解答么 我也是用KMP怎么也找不到感觉
关键 KMP会skip outer iteration 但是似乎这里不太能skip |
|
S**I
发帖数: 15689 | 10 ☆─────────────────────────────────────☆
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 | 11 ☆─────────────────────────────────────☆
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*********6
发帖数: 261 | 12 KMP我电面的时候网页开着就是KMP算法的code:-) |
|
h****n
发帖数: 1093 | 13 暴力写个strstr不行么
非得KMP？ KMP除非事先背下来，否则现编肯定不行 |
|
P*******b
发帖数: 1001 | 14 真要kmp，这种算法看了我也记不住啊，咋整？
面试不大可能要求kmp吧。 |
|
h*******e
发帖数: 1377 | 15 strstr 实际code 并不是用KMP KMP 只是 next 函数 或者有重复序列出现很多的串有
些作用。。 |
|
p*****2
发帖数: 21240 | 16
能想到。不过online test不好写呀。hash那个，我不清楚怎么选mod。kmp我从来也没
写过。不知道能不能写对，通过test case呢。话说tc用到kmp的时候多不多呀？ |
|
p*****2
发帖数: 21240 | 17
能想到。不过online test不好写呀。hash那个，我不清楚怎么选mod。kmp我从来也没
写过。不知道能不能写对，通过test case呢。话说tc用到kmp的时候多不多呀？ |
|
l****i
发帖数: 2772 | 18 正确题意:
按照string长度N，一共有N种shift.当i shift （0=
叫做cyclic automorphism。要求return一共有多少cyclic automorphism。
byebye 0 shift counter = 1
yebyeb 1 shift
ebyeby 2 shift
byebye 3 shift counter = 2
yebyeb 4 shift
ebyeby 5 shift
return counter;
可以用KMP去比较（s+s,s）。结果我早上傻了，用KMP把所有的s在s+s里找了一遍。。
。。提交了才发现，我跪了。其实只要找到第一个出现的重复出现的S的位置就够了。
比如byebye，第一次重复在位置3,用s的length去除第一次位置，就是结果。
所有a*5,其实是aaaaa，应该结果是5！ |
|
l****i
发帖数: 2772 | 19 我的意思是，比如这题输入是"abab"
KMP("abababab","abab")，从index位置1开始找，可以找到index位置2，发现找到了。
这样KMP找到index是2.这个2就是你所说的周期吧。 |
|
f******t
发帖数: 18 | 20 咦，kmp估計是正解，感覺還有個nlogn的算法好像也還將就。
掃一遍字符串統計各字符出現次數，得到一個stat[]數組
如果只有一種字符而字符串長度大於一，return true
else
求stat所有值的最大公約數(nlogn)，假設為gcd
if gcd==1，return false
否則，如果存在一種重複T構造S的方法的話，gcd一定是K的因子
而無論K等於gcd的多少倍，S能分成K份就一定能分成gcd份（因為gcd
只能是K的因子）
然後檢測K=gcd，S是否符合要求，符合返回true，否則return false（O(n))
實際上上面的的nlogn複雜度遠遠達不到的~~仔細分析也許會跟kmp的正解差不多？ |
|
r*********n
发帖数: 4553 | 21 为什么KMP不适合呢？KMP只学要预处理一次pattern，然后用生成的dfa去查每个word |
|
y*****i
发帖数: 141 | 22 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
一个新pattern都得重新搜一次。
就是做题的时候suffix tree感觉比KMP难写多了。。。 |
|
t***t
发帖数: 6066 | 23 难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。 |
|
h********3
发帖数: 2075 | 24 KMP算法实际用途很小。本质上，如果真的要进行大规模字符串的查询，一般都用index
的办法，suffix array之类的办法。真的上大规模匹配之后，KMP和直接一个一个匹配
没多大本质区别，五十步和百步的区别，解决不了问题本质。 |
|
q****m
发帖数: 177 | 25 还是用kmp吧。 假设string是 s. 那么用kmp的话，pattern是s,要匹配的字符串是s.
substr(1),比pattern少第一个字符 |
|
q****m
发帖数: 177 | 26 还是用kmp吧。 假设string是 s. 那么用kmp的话，pattern是s,要匹配的字符串是s.
substr(1),比pattern少第一个字符 |
|
d********y
发帖数: 2114 | 27 用KMP的next table
1.计算KMP的next table。这个是O(n)
2.如果有重复字符串组成，用输入字符串长度减去next table的最后一个值再减1，得
到重复字串的长度。
3.验证此子串长度大于1，子串最后一个字符和输入字符串最后一个字符相等，字符串
长度可以整除字串长度。
假设计算出的子串长度为p。根据next table的定义，对于0 <= i < i+p <= s.Length
- 1, s[i] = s[i + p]。这就是一个周期函数的表达式。 |
|
J*****a
发帖数: 4262 | 28 你类比不恰当
kmp可能算面试题里比较难的，但绝不是cs算法分析教材里很难的东西。随便证明个某
个问题的复杂度的上下界都比这个难多了，随便举个例子，请给出kth-smallest问题复
杂度的紧上界和紧下
界
你就算看kmp一遍能懂，不代表你看算法分析一遍就能懂（除非你用的教材太简单），
也许和“射频通信电路一样”，三遍还是一知半解。说到底，晃得响的是半瓶水基本是
对的 |
|
h***s
发帖数: 45 | 29 如果也可以把KMP的细节解释清楚是算背题还是算熟练掌握了KMP？ |
|
z*t
发帖数: 13 | 30 第二个用kmp很直观。z算法本质跟kmp也是一样的 |
|
D*********G
发帖数: 193 | 31 解释思路，然别人知道你是怎么思考和解决问题。
还有，你需要run several tests。这些怎么着也需要5-10分钟了
另外，不要assuming面试官知道最优解
想想看，加入你的算法最优，但是面试官从来没停过，那怎么半，你有没有能力给他解
释清楚，这就要看你对问题理解的深度了。举个最简单的例子，KMP，不是每个人都记
着这个算法的具体实现的。如果你给出KMP，就要有准备解释清楚 |
|
d*******8
发帖数: 23 | 32 请问能具体解释一下在下面这个例子中KMP如何发挥作用么? 多谢.
S = "ABBCCD"
P = "ABCD"
如何忽略无关的char然后用KMP搜索啊? 按照我的理解,S中所有的char都是相关的char,
在S中是搜索不到"ABCD"这个子串的. |
|
d*******8
发帖数: 23 | 33 请问能具体解释一下在下面这个例子中KMP如何发挥作用么? 多谢.
S = "ABBCCD"
P = "ABCD"
如何忽略无关的char然后用KMP搜索啊? 按照我的理解,S中所有的char都是相关的char,
在S中是搜索不到"ABCD"这个子串的. |
|
M**********7
发帖数: 378 | 34 看面经好像有问kmp的 准备了一下
主要是那道最多重复子串的题要用类似的思路
如果考了也是够bt的。
如果不是故意黑 也许可以准备几个优化方案然后讨论实现吧 如果我们自己就知道坚持
kmp没有备选方案 那对方让写也不能算太离谱 如果对方点名让写感觉题出的不好 因为
考这种熟悉的就会 不熟悉就不会的是没啥意思。
amp在 codereview (codereview) 的大作中提到: 】 |
|
M**********7
发帖数: 378 | 35 看面经好像有问kmp的 准备了一下
主要是那道最多重复子串的题要用类似的思路
如果考了也是够bt的。
如果不是故意黑 也许可以准备几个优化方案然后讨论实现吧 如果我们自己就知道坚持
kmp没有备选方案 那对方让写也不能算太离谱 如果对方点名让写感觉题出的不好 因为
考这种熟悉的就会 不熟悉就不会的是没啥意思。
amp在 codereview (codereview) 的大作中提到: 】 |
|
G*********e
发帖数: 56 | 36 显然用KMP算法呀。DFA version的KMP就可以搞定。线性时间，空间复杂度是pattern的
长度* the number of distinct characters in pattern。 |
|
c******n
发帖数: 4965 | 37 考算法本来意思是靠problem solving, 解决问题的能力 ， approach 问题的过程，
你再怎么玩文字游戏，背code lines 跟背算法概念 都是domain -specific knowledge
,
完全背离考coding 的本意。
你知道kmp 又有什么意义呢？ 仅仅说明你某天看过这么一篇文章。 并不表明来一个类
似的新的问题你就能推个新的算法出来。 在problem solving 以外，"知道KMP可以解
string match" 这件事一点意义没有， 实际工作中首先能有1%的case能用到任何算法
，即使碰到string match 这个问题， 上google 10分钟的事情。
我们仅讲狗家这样general hire 下exclusively 看coding 跟design的情况。 我所知
很明确T5以下进去的根本不看你的experience |
|
|
T****U
发帖数: 3344 | 39 也可以用kmp
翻转字符串加到前面，然后求字符串的kmp值
algorithm
then
. |
|
T*C
发帖数: 5492 | 40 http://seekingalpha.com/article/737691-cramer-s-mad-money-21-ea
21 Earnings To Watch This Week: Eaton (ETN), Halliburton (HAL), Dupont (DD),
Biogen (BIIB), Dominos (DPZ), Panera Bread (PNRA), Buffalo Wild Wings (BWLD
), Apple (AAPL), Caterpillar (CAT), Wyndham Worldwide (WYN), Boeing (BA),
Whole Foods (WFM), Kimberly-Clark (KMB), Dunkin' Brands (DNKN), Hershey (HSY
), International Paper (IP), Celgene (CELG), 3M (MMM), Chevron (CVX),
Weyerhaeuser (WY), Merck (MRK). Other stocks mentioned: Cooper... 阅读全帖 |
|
z**********8
发帖数: 2049 | 41 有始有终，灌完算了。。。
接下来的第三局， 走了py, 伤了188， 第二局被狂扫的阴影依然笼罩。我比较客观的
觉得，能上20分就算完成任务了。
果然，我们前半局，依然低迷。kmp依然给与我们强大的压力， 他们的发挥，还是继续
着前一局的高昂。几乎没有多少“漏洞”。 好像比分接近19分了，而我们好像只有尴
尬的14，15分。 难道真的大势已去了吗？ 我想大概又要被横扫了。我已经在给自己寻
找失利的理由了。主力队员受伤，后防线掉链子，等等。
但是，局势竟然在不知不觉中开始扭转了。。。
有一个球，对方有四次接球的嫌疑。我们平时也就算了，但是，现在的情势下，一帮博
士也开始较真了。哈哈。。我马上跟着起哄，对方的前排队员，在网线以下，两次碰球
，应该已经算连击了。。。艰难得拿回了一分。kmp因为领先优势明显，也没有过分的
“争”。
有一个球， 好像是j的扣球打网带，球还没有死，我就喊了起来，别碰，别碰。非常急
吼吼。。。其实，那个球有没有碰到拦网队员的衣服或者手，哪怕一丁点，死活不认账
了。哈哈。没有裁判啊。。。
我的一个招牌性的萎缩球，又一次得逞。鲍里斯防守起来一个对方的进攻，我在二号位
的 |
|
P****D
发帖数: 11146 | 42 单说日本动漫/电视剧/电影，片源不是rmvb没错，但国内字幕组加完字幕之后重新压制
的就都是rmvb了。不懂日语、必须依赖字幕的人，没有其他选择。
当然土豆上或优酷上也能找到，但是网络的原因断断续续，而且有广告。我宁可用BT下
载之后，安心地看，省得一会儿一断。你说的“网上视频有很多选择”，都避不开这个
缺点。
另外播放器我推荐Daum PotPlayer，作者就是KMP的作者。跟KMP一样，就是菜单里的东
西变了变位置。 |
|
F********y
发帖数: 7139 | 43 那我就不清楚了，但是我当时在实验室的台式机上试验的时候，那台机器是没有装
realplayer的，所以要么就是kmp的安装文件把那个引擎built-in了，不然解释不通为
什么可以播放。
还有同样的rmvb视频，用realplayer播放cpu占用率要比用kmp播放高达约15%，估计和
reaplayer自己带很多垃圾有关系。 |
|
k**o
发帖数: 15334 | 44 呵呵，亵渎都拿出来显摆了？这垃圾我逼着自己看了一大半，最后还是受不了，放弃不
看了。
pps，暴风，迅雷是不错，但是哪个核心技术是自己开发的？
pps等p2p流媒体软件全部用的还是国外开发的BT协议。
暴风用的全是国外的人开发的filter，只不过做了个前台播放器而已，而且也不算是业
内最好用的，我个人更喜欢KMP，zoomplayer等等功能更强大百倍的同类软件，我装过
暴风，但是现在我电脑上已经没有暴风了。
迅雷确实好用，可就是不太道德，属于偷带宽，也就是网上深恶痛绝的盗链行为。P2P
功能也是只管下载，不管上传。verycd出的电驴软件会自动封禁迅雷客户端，还有很多
BT用户也自发的封迅雷（http://www.167bt.com/bbs/viewthread.php?tid=336980）。在国内迅雷也是法院的常客，经常被人告。
of
？？ |
|
|
|
|
o****u
发帖数: 714 | 48 两岸关系是有国际因素的内政问题，真正问题是制度，而不是主权
45-49年是，
现在也是。
45-49 TG政策比KMP 好。
现在 TAIWAN 比 大陆 好。
TAIWAN 是真选举，好歹有制约。 |
|
|
