s*****1
发帖数: 134 | 1 这题我用了三种方法做:
1) Rabin–Karp, 这个方法大小测试时间上均能通过,但是可能是hash function内部实
现的问题,大测试有三个fail了(我在我的电脑上测试了fail的数据,应该是对的)
2) Boyer-Moore, 这个算法好理解,测试也通过了
3) KMP, 这个算法太复杂,没怎么弄明白,写了书上的code,大数据居然exceed time
limit了.
想问大牛们:
1. 你们做这题时,用Rabin-Karp是不是也遇到我这种情况?
2. KMP不是优于BM嘛,为何会超时?
3. 一般KMP面试考吗?如考,怎么考?
谢谢啦 |
|
d**********x
发帖数: 4083 | 2 KMP常数太大，一般实际应用不多
但是我觉得过数据是没问题的，建议你用那几个没过的数据debug一下是不是死循环了
。。 |
|
P******r
发帖数: 842 | 3 不是大牛，经验如下。
写brute force就能过judge large。KMP可以过的。 |
|
l***i
发帖数: 1309 | 4 I use KMP. Admire to those pass by brute force. |
|
n******n
发帖数: 567 | 5 onsite给我出个brute force，写出bug了。。。。。。估计挂在这题上了 |
|
h****n
发帖数: 1093 | 6 暴力写个strstr不行么
非得KMP？ KMP除非事先背下来，否则现编肯定不行 |
|
d**e
发帖数: 6098 | 7 ☆─────────────────────────────────────☆
wwzz (一辈子当码工) 于 (Wed Apr 25 13:10:33 2012, 美东) 提到:
这个问题，我真不敢说。
如果面中国同胞，用中文会不会觉的不太professional?
我面别人的时候，很想用中文，大家交流方便一点。就两人面对面，还tmd说英语。不
知大家觉的如何？从面人，和被面的都可以说说想法。
☆─────────────────────────────────────☆
StevenLow (CrossLayer) 于 (Wed Apr 25 13:13:34 2012, 美东) 提到:
有啊 我遇到有的面试官就用中文
☆─────────────────────────────────────☆
wwzz (一辈子当码工) 于 (Wed Apr 25 13:17:31 2012, 美东) 提到:
那觉的好还是不好？
☆─────────────────────────────────────☆
StevenLow (CrossLayer) 于... 阅读全帖 |
|
p*****2
发帖数: 21240 | 8 面试题总结(2) - Two/Three pointers
简称two pointers吧。大概把分类粗略的搞了一遍（http://leetcode.cloudfoundry.com/), 发现利用two pointers解决的题目数量很大。two pointers我指的是一类题，而不一定是真正的two pointers, 比如可能是three pointers, 也可能不是pointer， 而是index。这类题基本上就是发生在array, string, linked list这三种数据结构上，是一种基本的算法和编程技巧，同样超高频率的出现，可以说是面试必遇的题。
two pointers常常和其他的算法混杂起来出现。比如binary search本身也可以归类为
two pointers的。如果这样算的话，Leetcode上边1/4的题目都跟它相关。因此，two
pointers是必须熟练掌握的基本编程技巧。
Two pointers大概分三种类型
1. 两个pointers从头往后走：感觉绝大多数的linked list的题目都涉及到这个操作，
当然还有array。
Imple... 阅读全帖 |
|
|
|
P*******b
发帖数: 1001 | 11 真要kmp，这种算法看了我也记不住啊，咋整？
面试不大可能要求kmp吧。 |
|
P*******b
发帖数: 1001 | 12 c++，我记得上次我也通过了，这次通不过了，奇怪 |
|
h*******e
发帖数: 1377 | 13 又run了一下我的代码， 就是 普通的 brute force c 语言的还可以过 |
|
l*****a
发帖数: 14598 | 14 仔细看
其实挺简单的
就是找一个头一段==后一段
而且预处理的程序跟实际程序流程基本一样 |
|
P*******b
发帖数: 1001 | 15 看了leetcode上面的代码，原来outer loop有点小trick，可以节约一点循环时间。 |
|
P*******b
发帖数: 1001 | 16 kmp两年前找工作的时候搞的很熟，现在一点都记不起来了，这次不想看了。 |
|
|
f*********r
发帖数: 85 | 18 上周做了一个电面，然后收到recruiter邮件说“went very well”，然后说要再一轮
电面，如果OK的话就host match
好奇到底需要多少轮面试。。。好像两轮电面有点奇怪。
顺便贡献一下题，很基本，就是考coding：
1. 8 queens，被我decline了说我碰到过
2. implement strstr，give test cases
3. 给一个基础密码串比如说password，打印所有的变种比如说Pas$W0Rd，每一个字母
可能变成的其他character是预先已知的。 |
|
f*********r
发帖数: 85 | 19 这题写程序还挺长的吧，光print board就得写两个loop... strstr让我写了个O(nm)的
解法，整个就只有两个loop |
|
|
p*****2
发帖数: 21240 | 21 leetcode strStr, KMP跟暴力时间差不多呀。一点也看不出来快呀。怎么回事？ |
|
h*********e
发帖数: 91 | 22 本来满简单的，一个hay_str.compare(i, needle_len, needle)就出来了。 我知道复
杂度比KMP 高，但是KMP记不住。 真的面试的时候，可不可以不用KMP， 就用一个
compare function阿？ |
|
|
|
|
d*k
发帖数: 207 | 26 除非诚心做的数据，KMP和暴力算法的效率差不多。 |
|
j******2
发帖数: 362 | 27 假如haystack的长度为n，needle的长度为m，我觉得应该是O(n)。
最坏情况比如haystack是"abcabcabc"，needle是"abcd"，比较的次数也就是4+1+1+4+1
+1+4+1+1，大约就是2n。
各位觉得呢？ |
|
|
r*******e
发帖数: 7583 | 29 咋就直接跟m没关系了？
按你的数法，最坏情况显然是O(m*n)
haystack = 01010101010101010101010101010101010101010101010101010...
needle = 010101010101010101011
+1 |
|
d*********g
发帖数: 154 | 30
嗯应该是这样，如果是KMP的话就是O(n)了~ |
|
d*****c
发帖数: 605 | 31 最后的onsite一家小公司。。。等回来散尽家财发包子上面经。
update：
14包子已发，没发到的不好意思啦，谢谢你们bless。。。。在等结果。因为签了nda所
以我就报个别家面经吧。
1. strstr，一个string很长，一个很短。
2. 继续第一题，除去所有短string之后组成的string的anagram
3.radix sort
再次感谢大家bless。 |
|
g***j
发帖数: 1275 | 32 大小集合都过了，大部分一次过，请问这算快还是慢的？才开始做题，不可能每天都2
个小时，如果要做完，这要多久啊!
都是老题
1) 3 sum
2) valid parentheses;
3) merge two sorted lists;
4) implement strstr();
5) pow(x,n);
6) merge intervals; |
|
p*****2
发帖数: 21240 | 33
Id Question Difficulty Freqency Data Structures Algorithms
1 Two Sum 2 5
array
set
sort
two pointers
2 Add Two Numbers 3 4
linked list
two pointers
math
3 Longest Substring Without Repeating Characters 3 2
string
hashtable
two pointers
4 Median of Two Sorted Arrays 5 3
array
binary search
5 Longest Palindromic Substring 4 2
string
6 ZigZag Conversion 3 1
string
7 Reverse Integer 2 3
math
8 ... 阅读全帖 |
|
s*****n
发帖数: 5488 | 34 几句话可以说清楚。
1.kmp算法有strstr变化而来。一旦不匹配，不是推到头，而是吧pattern推到另外一个
next array指示的位置,重新开始比较。
2.next array和pattern错开一位匹配而来，一旦开始匹配，顺序++,一旦不匹配，清零
重来。
例如：
ababaca
0012301
其实主要靠的逻辑和编码能力。 |
|
J****3
发帖数: 427 | 35 水一记！
naive 的算法竟然可以过大OJ！以前怎么没有发现! |
|
r*c
发帖数: 167 | 36 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... 阅读全帖 |
|
s*********n
发帖数: 191 | 37 一般strstr的expectation就是写O(MN)优化一点可以是N-M+1，一般不会要求写KMP，掌
握知识点就可以了。要求你写O(MN)很中规中矩吧。
distinguished,
very |
|
r******l
发帖数: 10760 | 38 strstr的一个变种。输入是两个string A和B，长度分别是n和k（n>>k）。输出是A里面
的一个长度为k的substr C，要求B和C之间的距离最小。两个等长的string的距离的定
义为每个对应字符之间距离的平方之和。两个字符之间的距离就是ASCII码的差（比如A
和B的距离为1，A和Z的距离为25）。
如果B是A的子串，则C=B，最小距离就是0。这个可以用KMP、BM、RK等很多方法快速解
决。但是如果B不一定是A的子串，除了最直接的双重循环O(nk)的解法，还有没有更好
的解法呢？ |
|
h****g
发帖数: 308 | 39 Entry level 职位
电面一轮.很简单的题目.我都不好意思说了. strstr 还有design card game 写洗牌还
有取牌方程
onsite:
题目不难板上都有.个人觉得manager 问的问题还挺难的,不知道回答的好不好.
觉得不一定要答对所有的题目, 他们还挺看重解决问题的能力. 做题的时候要多交流,
让他们知道 你是怎么分析, 怎么把大问题break down 然后 一步一步解决问题. 交流
特别特别特别重要. 一定要先搞清楚问题, 然后说说你的解法,然后再开始写代码.
面试我的有两个组 (应该两个都属于 大组 E-Commerce Platform)
1. Identity and Auth . 这个manager 比 Recruitor 还早通知我.说想跟我打电话聊
聊.其实我面他那一轮的时候感觉不好.但是看来他现在倒是还挺想要我的.这个组现在
主要的project 就是处理各种mobile device 的 authentication 啊, Prevent and
detect identity theft 之类的吧. 他说是有前端也有后端. 他说mo... 阅读全帖 |
|
p*u
发帖数: 136 | 40 题目依然和glassdoor上一样：
1，实现strstr
2，图的深拷贝：一个连通无向图，图的每个节点除了邻居节点以外没有其他信息。
struct node
{
vector neighbors;
};
实现node* copy(node *root); |
|
p*****2
发帖数: 21240 | 41 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 42 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
n****e
发帖数: 678 | 43 看了讨论后，是不是要写一个这样的function
这题应该没有regular expression难吧。regular expression还有'.', '*'啥的，这里
只有'?'
bool isMatch(string str1, string str2) {
if (str1.size() != str2.size()) {
return false;
}
for (int i = 0; i < str1.size(); i++) {
if (str2[i] == '?')
continue;
if (str2[i] != str1[i])
return false;
}
return true;
}
vector wordmatching(vector words, string str) {
vector res;
for (int i = 0 ; i < words.size(); i++) {
... 阅读全帖 |
|
G*********n
发帖数: 53 | 44 大牛啊！Congrats。 PS. strstr() 除了KMP rolling hash， suffix tree 都是可以
做的，所以至少有4种解法。那个阿三出这种题目难为人真是太2了。 |
|
G*********n
发帖数: 53 | 45 大牛啊！Congrats。 PS. strstr() 除了KMP rolling hash， suffix tree 都是可以
做的，所以至少有4种解法。那个阿三出这种题目难为人真是太2了。 |
|
l*n
发帖数: 529 | 46 这几天是v家的event recruit，有幸给了onsite机会，已挂。
电面题目是什么是mutex，为啥要有；binary tree仅有单个child的节点数；和简单
binary search。
onsite第一个是问distributed，四个机器各32g+2t内存和硬盘，如何最快速sort 一个
repository里8t的64位整数，uniform distributed。
第二个是判断链表是否有环。又问，fast赶上slow之前有几次超过slow，如何证明。后
续是解开环。这里当时没想清楚，简单的追赶想到圈长上去了，导致做解环的时候也把
自己搞懵了。
第三个是说64位机器只用long的低48位寻址，前16位必须跟sign位即第47位一致，如何
判断。还问了个strstr，如果输入是user defined的实现，该怎么办。 |
|
a********9
发帖数: 129 | 47 之前稍微收集了一下
glassdoor
===================
edit distance
level traverse tree(高频）
1) Calculate the square root of a double（高频）
2) Given n intervals [si, fi], find the maximum number of overlapping
intervals.
3) Print all the paths from root to every leaf in a binary tree.
4) Print the sum of all the numbers at every vertical level in a binary tree
5) Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum ?
6) Given 1 trillion messages ... 阅读全帖 |
|
x******1
发帖数: 155 | 48 两个电话面试，有一些小问题忘了,大概周一给feedback，希望可以move on.
Person 1：
Class vs object
Hashtable vs binary search tree, insert, search, delete
What is balanced binary search tree?
The worst complexity of binary search tree: O(n), why O(n)? not O(logn)
Singleton, follow-up: how to prevent from producing multiple instances
coding question:
bool strStr(char *s1, char *s2) leetcode原题
Person 2:
Write a function to reverse the sentence such that all words are reveresed
in place, but numbers and punctuation marks remain... 阅读全帖 |
|
x******1
发帖数: 155 | 49 两个电话面试，有一些小问题忘了,大概周一给feedback，希望可以move on.
Person 1：
Class vs object
Hashtable vs binary search tree, insert, search, delete
What is balanced binary search tree?
The worst complexity of binary search tree: O(n), why O(n)? not O(logn)
Singleton, follow-up: how to prevent from producing multiple instances
coding question:
bool strStr(char *s1, char *s2) leetcode原题
Person 2:
Write a function to reverse the sentence such that all words are reveresed
in place, but numbers and punctuation marks remain... 阅读全帖 |
|
|
