z*******y
发帖数: 578 | 1
suffix tree肯定行，不过电话interview这点时间 建树的code还是挺challenging的
呵呵
suffix tree的code不太好写
我觉得他可能就是想让我写那个KMP算法 |
|
|
k*j
发帖数: 153 | 3 2 solutions
1.brute force, complexity O(m*n), m is the length of the pattern, n is the
length of the string
2. KMP O(m+n) |
|
s*****y
发帖数: 897 | 4 Should we write the kmp during the interview? Or just write the brute force? |
|
g**********y
发帖数: 14569 | 5 Careercup上看到的：怎么判断两个String是否rotational equivalent? O(N)
把KMP实现一遍，是O(N)。除此之外呢？
能想到的一个是算hashcode, sum(c[i]*31^i)对一个大数取模，然后移位比较。感觉不
是很好。
有什么想法？ |
|
g**********y
发帖数: 14569 | 6 Careercup上看到的：怎么判断两个String是否rotational equivalent? O(N)
把KMP实现一遍，是O(N)。除此之外呢？
能想到的一个是算hashcode, sum(c[i]*31^i)对一个大数取模，然后移位比较。感觉不
是很好。
有什么想法？ |
|
K*****k
发帖数: 430 | 7 大公司的码工面试题范围广阔，千变万化，再怎么准备都会有盲点。面试官真要考倒一个人，不要太简单。
感觉就象要在16番棋挑战卡斯帕罗夫一样难，要实力到了才行，偶然赢他一局，却输他N局不行，不如求稳，13平2胜足以拿到offer。现在还是信心不够，生怕哪一轮面试开局不利，全局皆输。
还恳请给些复习的建议。比如比KMP差的常规Brute Force法求子串是否也要苦练反复纸上写？就怕不练，到时白板写这个都可能写不好，所谓眼高手低。 |
|
d*******l
发帖数: 338 | 8 直接贪心的匹配不行吗？比如先从头找target第一次出现的地方，然后跳过这个target
的长度，在剩下的里面继续找target，以此类推。最后找到多少个就是多少。想了一下
这样好像就是最优的了。字符串匹配的时候可以用KMP之类的办法做到线性复杂度。 |
|
|
p*****2
发帖数: 21240 | 10
Activity里边能看到最近的submission, 我做题的时候，正好看到你的submission
succeeded了。我主要是做similarity那题，我看一下KMP算法去。 |
|
p*****2
发帖数: 21240 | 11
我用了用KMP好像找不到感觉。后来把我的代码稍微优化了一下，竟然就过了。 |
|
d*******l
发帖数: 338 | 12 开始看着像KMP但后来也没想出来怎么弄。直接二分加hash过了。 |
|
|
w********n
发帖数: 58 | 14 没人要KMP直接BUG FREE写出来，但是对于大部分简单的面试题都不能bug free，怎么
可能pass interview，要知道大部分面试题都是20-30行能搞定的简单题。
team |
|
f*********i
发帖数: 197 | 15 可以把两个树A,B分别preorder,inorder遍历
然后问题就变成
longest common string in preorder[A], preorder[B] => string 1
longest common string in inorder[A], inorder[B] => string 2
最后再次longest common string in string 1，string 2
如果全部用KMP来做，时间复杂度O(n) |
|
|
H****r
发帖数: 2801 | 17 KMP 通过
BoyerMoore 通过small,卡large... 手工测试发现除最后一个test外都可以，最后一个
test太长在网站上看不到.... 自己测试的一些都可以啊。 leetcode 能告诉最后一个
test 具体是啥吗？ |
|
z*********8
发帖数: 2070 | 18 来自主题: JobHunting版 - 最新面试题 KMP + minimum window? |
|
l*****a
发帖数: 14598 | 19 string比就是KMP吧？
似乎有序的条件用不上 |
|
v****c
发帖数: 29 | 20 这不就是KMP算法吗，O(k)
s2作为pattern去match s1 |
|
p*****2
发帖数: 21240 | 21
白芷你太帅了。KMP算法我从来没研究过。面试会考吗？ |
|
Z*****Z
发帖数: 723 | 22 应该不会吧。。。
这个kmp主要觉得思想很巧。我一边看一边膜拜knuth。。。
不过leetcode上不是有个strstr的题么 |
|
a*******8
发帖数: 110 | 23 面试时的String match题，如果要求比brute force更好的解的话，都可以考虑这个。
看了半天Wiki，才弄明白。。。
//KMP algorithm
//Reference WIKI: //http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
String getCommon(String s1, String s2) {
int maxLength = Math.min(s1.length(), s2.length());
int[] table = buildFailureTable(s2, maxLength);
int m = s1.length() - maxLength;
int i = 0;
while (m + i < s1.length()) {
if (s1.charAt... 阅读全帖 |
|
q***y
发帖数: 24 | 24 kmp改一点
把A做一个自动机，B在A自动机上过一遍
O(n) |
|
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记录匹配的次数 |
|
W******g
发帖数: 887 | 26 啊？怎么实现？KMP? fingerprint? suffix trie? 直接比较？ |
|
l***i
发帖数: 1309 | 27 treat the sequence as a string and use KMP to match. You have to cut the
famous sequence at some point. Usually it is not a problem as most sequences
are increasing so you know you can stop when the last integer in your
sequence is smaller than the last one in the prefix of a famous sequence.
oeis is a website to do this search quite efficiently, not sure how they
implemented it. |
|
n******n
发帖数: 567 | 28 如果是想进FGT这类的公司，要怎么复习呢？
1，是不是重点是做算法题？如果只做leetcode的话，面试的时候一紧张或者疲劳，就
会做不出来的。比如上次面我kmp，之前写过两次，之后一紧张就直接不敢照亮了。
2，是不是要把本科的课都复习一遍啊？当时就混GPA了，也学的不扎实，现在想捡起来
很费时间，就和1矛盾了。是不是只要把简历上出现的方向复习到就行？？
3，是不是选一个方向，研究的比较彻底？？我的intern经历和项目经历都是关于
virtual machine的，我觉得做的挺尴尬的，根本不精通，很多概念和popular的软件都
不知道，但也确实写了一些代码，但面试官一问我概念我都不知道，就直接被当成傻逼
了。这要是复习的话也无从下手啊。。。。
大家给点建议吧。。。谢谢 |
|
|
w*********0
发帖数: 48 | 30 有几个蛮常见的
longest increasing subsequence 有O(nlogn)的 我只能写到O(n^2)的 O(nlogn)基本
只能靠背
longest palindrome substring 有O(n)的
还有就是经典的KMP，这个貌似还好
这种题目 需要背下来最优解么。。。。 |
|
s******y
发帖数: 72 | 31 Phone Interview:
research + coding,
Coding: String Match strstr(); naive way and KMP, write code
Onsite:
一共见了八个人，六个Enginneers， 两个senior manager，给了一个talk。
问了很多research和system相关的问题，以及coding， 记得的问题有
Coding and Language questions:
1) Given a interger array, find a consective subarray with maximal sum
2) 3Sum, without extra space. How to extend to handle KSum?
3) Write a thread safe queue
4) Editing distance, return minimal distance and the operations (remove,
insert, replace) to convert one strin... 阅读全帖 |
|
b*****x
发帖数: 48 | 32 现在店面都要KMP啊。。lz当场写的？
bless~ |
|
a*****n
发帖数: 158 | 33 BLESS,好难啊，，KMP，DP。。第６题能用除法吗？？可能会溢出吧。。。 |
|
s******y
发帖数: 72 | 34 Phone Interview:
research + coding,
Coding: String Match strstr(); naive way and KMP, write code
Onsite:
一共见了八个人，六个Enginneers， 两个senior manager，给了一个talk。
问了很多research和system相关的问题，以及coding， 记得的问题有
Coding and Language questions:
1) Given a interger array, find a consective subarray with maximal sum
2) 3Sum, without extra space. How to extend to handle KSum?
3) Write a thread safe queue
4) Editing distance, return minimal distance and the operations (remove,
insert, replace) to convert one strin... 阅读全帖 |
|
b*****x
发帖数: 48 | 35 现在店面都要KMP啊。。lz当场写的？
bless~ |
|
a*****n
发帖数: 158 | 36 BLESS,好难啊，，KMP，DP。。第６题能用除法吗？？可能会溢出吧。。。 |
|
|
f****e
发帖数: 34 | 38 来自主题: JobHunting版 - G/F面经 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见
过这个题目。
3. 9月底的时候google安排10月11号onsite... 阅读全帖 |
|
c*****r
发帖数: 214 | 39 来自主题: JobHunting版 - G/F面经 cong!
现在从国内直接过来人的太多了，这条路比当年考T考G读phd的那批人真是平坦太多了
第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random... 阅读全帖 |
|
d**********x
发帖数: 4083 | 40 KMP常数太大，一般实际应用不多
但是我觉得过数据是没问题的，建议你用那几个没过的数据debug一下是不是死循环了
。。 |
|
P******r
发帖数: 842 | 41 不是大牛，经验如下。
写brute force就能过judge large。KMP可以过的。 |
|
l***i
发帖数: 1309 | 42 I use KMP. Admire to those pass by brute force. |
|
|
|
C***U
发帖数: 2406 | 45 找工作篇：
2012年的春季，想开始尝试一下CS的找工作的过程，所以投了3个公司的暑假实习。
Halliburton, iseatz和gameloft。他们都算是来学校招人的公司。
Halliburton是一个老印面的，题目很简单，但是没有选我。我觉得他们肯定是安排好
人了，我只不过去做个分母而已。
第二个是iseatz，是一个给航空业提供软件支持的公司。他们寻找的是large data和网
页制作的人。我当时mysql都不会，很自然就挂了。
第三个是Gameloft。 上来就让做一个3小时的online test，题目很多，不过都是C++的
基本知识，然后还让写了4个程序，都很简单那种。他们很快给了offer，但是没去。一
个是因为他们的工资和麦当劳一样，还有一个是因为老婆要去别的城市，所以我决定和
老婆一起过去，好有个照应。后来觉得这个选择是对的。一方面暑假的时候在那边和一
个教授做出来一个结果，多写一篇论文（后来种种原因，论文到现在还有一些没写完）
。另一方面，我有很多时间来做找工作的准备。
暑假的前两个月心里还是很懒散，除了每周和教授见面讨论问题一次，基本就在家里无
聊，然后把... 阅读全帖 |
|
p*****p
发帖数: 379 | 46 LZ面的java？
写些自己的解法，求指导：
一电：
1. 两个变量
2. 两个index，typeof比较类型然后调用compare？
二电：
1. 不清楚，如果电话号码是确定格式xxx-xxx-xxxx的话直接线性查找或者KMP之类？
2. 冲突用list储存？
3. 两个list
4. O(n)求到原点距离，然后quick select
onsite1：
2. 线性扫一遍
followup：排序后线性扫一遍？
onsite2：
2. 二分
3. 不清楚数据模型的角度是啥
onsite4：
2. 线性比较一下
followup：排序一下？这个不清楚
onsite5：
2. 我能想到的问题有：
每个人等待时间不同，时间长的应该有high priority，优先服务
聊天服务器可以有多个，牵扯到数据同步、负载平衡等等问题 |
|
|
P*******b
发帖数: 1001 | 48 kmp两年前找工作的时候搞的很熟，现在一点都记不起来了，这次不想看了。 |
|
|
p*****2
发帖数: 21240 | 50
substring O(n)
这题rolling hash, 不过要选mod的话，我就没有经验了。不知道应该怎么选择好。
再有就是KMP。mshearts说的。 |
|
