A*********c
发帖数: 430 | 1 btw, 我觉得lz小看面试官了，他要是问strstr的话必然知道KMP。
这毕竟是他挑的题。你想他一个题面了那么多人，肯定有N个人曾经写过KMP，看都看会
了。
我觉得能把KMP解释清楚的人的个数远远小于能写出来的人个数。
他应该是在求解释。 |
|
e********3
发帖数: 18578 | 2 几个基本原则，indentation和curly braces是很重要的，还有就是变量和方法命名要
合理，让人一目了然，好的变量和函数方法名比comment强100倍。还有就是简洁不要牺
牲可达性，比如这么一段简单的代码，
char *strStr(char *haystack, char *needle) {
if (haystack==NULL || needle==NULL) {
return NULL;
}
char *needleHead = needle;
char *hsHead = haystack;
int hl=0, nl=0;
while(*haystack!='
我不知道这里hl, nl什么意思，如果改写成一个更加明确的变量名，这样感觉就好看一
些了，其实写代码跟写文章一样，虽然你要追求美丽的用词和简洁的文风，但是什么都
有个度，太抠语言的一些quirk了最后写出来的就是生涩难懂。
写简洁漂亮的代码最好的办法就是多看看牛人是怎么写的，和写作一样，熟读唐诗三百
首，不会作诗也会吟。还有一点就是要千锤百炼，反复斟酌，没有什么好的代码和... 阅读全帖 |
|
|
u*****n
发帖数: 126 | 4 继续发面经攒人品。因为第一门语言是Scheme，这个面试帮我复习了很多Java的知识。
Decline了他们的offer。
Phone:
Round 1:
把一个linked list里的元素两两交换。
Round 2:
在一棵binary search tree里找到小于某个值的最大元素。
设计一个地铁售票机。
Round 3：
Implement Singleton.
Implement Producer-consumer.
Onsite:
Round 1:
1' 有2 billion个URL，每个URL都有一个size, 对于所有的size, 怎么找出95th
percentile
2' Implement strstr.
Round 2：
1‘ 关于String的，不记得细节了。
2‘ 怎么判断一个数是否是2的整数次方。
3’ String matching，一个String里有字母和＊， 怎么判断是否能够match一个
dictionary中的任意单词。
Round 3:
1‘ Java的design pattern，你知道哪些， 最喜欢用哪一个？
2’ Implemen... 阅读全帖 |
|
x*******z
发帖数: 31 | 5 hi, 请问楼主一个问题哈，就是那道实现strstr的题，你是用brute force的方法做的
呢？还是用kmp啊？还是别的呢？
另外那道2 billion URL的题，可以直接当作一堆数当中找前50最小的数，那么就可以
直接用quick sort来做了？对吧？ |
|
u*****n
发帖数: 126 | 6 Rabin-Karp for strstr
I cannot quite understand your second question. |
|
g******y
发帖数: 143 | 7 Interviewed with Kinect group
Phone interview
1.implement an image convolution and optimize it
2. find the intersection of two rectangles
Onsite
Round1
1. Implement strstr() and optimize it
2. Implement histogram equalization algorithm
3. Bayes conditional probability
Round2
1. Implement a fixed floating point class
2. Square root of a number (the number can be less than 1)
Round3
1. Find subarray which has max sum
2. Find the kth element in two sorted arrays
Round4
1. Im... 阅读全帖 |
|
u*****n
发帖数: 126 | 8 一个月之前面的。题目都是简单题。自己感觉做的也不错，拿了据信。
面他们家要注意的地方是， 他们会从开始到最后对你做过的项目一个一个的提问。所
以在你的简历上尽量的把重要的项目放在前面。
phone:
1' atoi(String str)
onsite:
1' 实现tinyurl. 如果每个user都要管理自己的URL，怎么实现。怎么保存密码？比较
顺序和随机的URL ID的优劣。
2‘ 实现strstr
3' 实现LRU
4' 实现单链表以及增加、移除操作。 |
|
m*********y
发帖数: 111 | 9 千万不要在自己衣食无忧的时候，抱着所谓的大胸怀，为烙印说几句话。
自己一时意识不到问题严重性就算了，不要还发帖为烙印说好话。
我只想说：烙印黑中国人黑的还不够吗？
凡事都有自己的原因，可是明摆着的黑人还要满怀感激的自我反省吗？
电面第一轮写红黑树插入，O（n）时间判断字符串是否由重复字符串组成，用kmp写
strstr，或者迟到打入电话，不断打断你，不断否定你，不断唉声叹气，不断传来笑声
，提前挂电话，你觉得这些正常吗？
更有甚者，烙印recruiter面试前通知你不要来了，可是硬是去了发现没有这回事，原
来烙印要保护接下来面试的自己人；烙印recruiter生改你的简历，直到迂回被录取，
被hire manager查出来，你们觉得这些还正常吗？
有没有国人会如此黑人的？
相比烙印对烙印，只要能护就护能录就录，你们还觉得正常吗？
老中要觉醒阿，不要再执迷不悟了，不抱团，再强的老虎也都不过群狼。 |
|
|
|
c*******y
发帖数: 98 | 12 求KMP讲解链接，我看过一个帖子，理解了为什么要做那样的index，但看不懂index怎
么做的，为什么可以O(n)做出来。 |
|
Z**********4
发帖数: 528 | 13 这个可以过oj啊。。
我记得这种naive matching不能过的。 |
|
w***y
发帖数: 6251 | 14 找到他们网站看了一下课程安排
课程大纲（包含但不局限于）
1. 【免费试听】从strStr谈CodingStyle和面试基本技巧，从Permutation谈代码模板
的重要性
2. 从Binary Tree讲Divide & Conque, BFS, DFS
3. Linked List
4. 从Binary Search谈Sorted Array相关问题
5. Dynamic Programming
6. Data Structure (Queue, Stack, Hash, Heap)
7. Graph & Search
8. High Frequent Interview Problems
9. Resume , System Design, Big Data
感觉进度有点慢，我是急性子hehe
楼上上过课的，是开课后每周的周六周日都有课么？ 就是一个月可以讲完 |
|
|
a******d
发帖数: 82 | 16 面试中的coding 题目都答出来了, 虽然被指出几个小bug, 但是当时也立即就改过来了.
design 的题目也照自己复习的内容答了, 不是很有经验,但是对new grads 也就这个水
平了
最后还是收到被拒的邮件, 自己都不知道是怎么一回事.
Facebook onsite 问到的几个题目
1. moving all 0s to the beginning of the array
直接答出 constant space 的解法
2. strstr()
KMP
3. wordbreak
告诉面试官有DP 解法, 告知我写递归. 我也写出个递归解法, 并且用hashmap 保存出
现过的子串来优化. |
|
|
p**t
发帖数: 157 | 18 所以其实我觉得考strstr这种东西挺讨厌的。。 |
|
f********y
发帖数: 11 | 19 我觉得strstr写个不完整的Boyer-Moore就不错了，至少比暴力强 |
|
c*****n
发帖数: 123 | 20 做题的时候总觉得智商捉急。。。比如Implement strStr()首先还是会想最笨的brute
force而不是kmp。。。
算法好多都生疏了的感觉 是不是该把经典算法全部自己写一遍才能会用？就是觉得算
法本身和解题情境总是想不到一起。。。太笨太笨了>.<
求大牛们教一教怎么提高算法能力呀？真为自己智商感到深深的捉急。。。谢谢了先~~ |
|
r****7
发帖数: 2282 | 21 一般说strstr就是只brute force吧，不然那么多字符串匹配算法，你咋知道他问哪一
个。。
brute
~~ |
|
b**********5
发帖数: 7881 | 22 问题是谁他妈的工作的时候， 自己去implement个strstr？？！ string。indexOf 都
解决了。。。 也没人傻到自己去implement个LRU cache， 一个linkedHashMap就解决
了。 我工作到现在， 印象当中， 没看见过DP的。。。 of course, i mean dynamic
programming, not double penetration.... |
|
d*******8
发帖数: 23 | 23 版中大多数面经都是针对北美new graduate的, 在此贡献一下本人国内找北美工作的一
些经验吧, 也算是答谢mitbbs上分享面经的朋友对我的帮助. 更希望攒攒人品能够抽到
h1b签证 :)
[背景]
国内4年工作经验. 硕士毕业后一直在某做存储的外企工作.
14年7月份开始有出国打算并开始准备.
[准备]
在工作之余每天坚持至少刷3~4道算法题, 并关注各个公司的blog及github上的开源项
目.
1. 算法
Leetcode自然不必说, 必刷. 先是用了将近两个月的时间把leetcode刷了1.5遍, 然
后每次电面和onsite面之前挑一些觉得做得不好的题再刷.
其次就是看geeksforgeeks上题. 这是个老印host的网站, 但是上面的题目分类明晰
,有很多分类底下的题目非常好, 比如DP (印象最深的就是m个鸡蛋n层楼测在哪层楼鸡
蛋会被摔碎的问题)和graph (印象最深的就是单源/多源最短/最长路径和欧拉环). 每
天看一下还是能学到不少新鲜的知识的.
其他就没有了, career up和glass door也断断续续看了一些, ... 阅读全帖 |
|
d*******8
发帖数: 23 | 24 版中大多数面经都是针对北美new graduate的, 在此贡献一下本人国内找北美工作的一
些经验吧, 也算是答谢mitbbs上分享面经的朋友对我的帮助. 更希望攒攒人品能够抽到
h1b签证 :)
[背景]
国内4年工作经验. 硕士毕业后一直在某做存储的外企工作.
14年7月份开始有出国打算并开始准备.
[准备]
在工作之余每天坚持至少刷3~4道算法题, 并关注各个公司的blog及github上的开源项
目.
1. 算法
Leetcode自然不必说, 必刷. 先是用了将近两个月的时间把leetcode刷了1.5遍, 然
后每次电面和onsite面之前挑一些觉得做得不好的题再刷.
其次就是看geeksforgeeks上题. 这是个老印host的网站, 但是上面的题目分类明晰
,有很多分类底下的题目非常好, 比如DP (印象最深的就是m个鸡蛋n层楼测在哪层楼鸡
蛋会被摔碎的问题)和graph (印象最深的就是单源/多源最短/最长路径和欧拉环). 每
天看一下还是能学到不少新鲜的知识的.
其他就没有了, career up和glass door也断断续续看了一些, ... 阅读全帖 |
|
g*****c
发帖数: 106 | 25 弱问一下，微软on campus interview,问了一道leetcode原题 Implement strStr()，
很快写出来了，回来后对比答案是没有错误的。然后就收到标准据信了。请问这个被拒
的原因会是什么啊？
对了还问了一些behavior question，比如team里有人不合作怎么办，随便说了几句。
我个人感觉面试官也没有很care这些问题，走过场的样子，专注点是程序。不知道这个
感觉对吗？
新手找工作，求解答～以后面试好注意些。谢谢！ |
|
i*******e
发帖数: 7 | 26 是不是就是leetcode上的strStr？多练几遍就成了，加油 |
|
j********l
发帖数: 325 | 27 ms onsite interview面经
因为是hiring event，面试流程更紧，一轮只有45分钟，所有人都是4轮，全是白人面
试官
1st: implement queue by array assuming the size of array is enough, write
the enque and deque methods;
2st: implement c#'s dictionary, both k and v are generic, write put(k,
v), get(k) and remove(k) methods;
3rd,
a. insert an integer into an sorted linked list, implement the linked list
and write the insert method;
b. find the first occurrence of second string from the first string (
actually, it's the Implement strStr ... 阅读全帖 |
|
j********l
发帖数: 325 | 28 面试四轮，感觉算法和设计大约各一半，但设计题明显速度很慢，写的很拖拉，一个
session只能做出一道，代码还不够完整。题目在经过一些提示后，基本都做出。
coding的题应该不会有bug，不过第三轮的strStr时间不够，代码没有全部写出来，但
解法还是详细描述了，面试官也觉得够了。第四轮的battleship game，从没听说过，
游戏也没玩过，面试官先描述了规则，最后自己design，估计也就只有半个小时的时间
，最后用了hashmap来做HashMap的，把attack的问题也解决了，
面试官也满意。
第一轮的用array实现queue，没有第一时间想出循环利用array这点，最后提示了一下
，马上想出来了，这是这轮的一个挂点；
第二轮的实现hashmap的题，我只大概知道方法，构建hash function，用linkedlist来
解决collision，但在class设计的时候错误的把key和value都用class，而不是一个统
一的class，最后提醒写出来了。 但没来得及一一写清楚put，get和remove methods... 阅读全帖 |
|
b********a
发帖数: 70 | 29 经过版上的内推拿到了电面
两个星期以前面的
面试官从名字上看是华人 但是口音听不出来 可能是abc
先是向我介绍了他在facebook做的项目
然后我也介绍一下我的工作 然后开始写题
第一题
给出两个字符串s和t 如果s中含有t 返回t第一次出现的index,如果不含有返回-1.
就是leetcode里面的implement strStr()
我说可以naive的遂位对比 但是复杂度是n方 他马上说n方is good enough，于是明白
这是做为一个热身题，写代码的时候还是有点慌 状态不是很好 我刚一写完他就马上问
我如何测试，其实是他看到一个下标越界问题，我说了几个都没有cover到这个上，然
后他又说了几个，不过都被之前的code catch到也没有显出这个bug，最后他就直接指
出来了 囧。
第二题
leetcode 里的 regular expression match
我上来就说要dp 他说是的 可以recursive的dp 我不太明白怎么搞 最后还是直接dp了
埋头写 他提醒我要一边给他解释 最后写完了以后又提示我要给他解释整个算法 解释
了一下 感觉他最后还是理解了 ... 阅读全帖 |
|
x****k
发帖数: 2932 | 30 pls implement a strstr() using kmp algorithm. thx |
|
b**********5
发帖数: 7881 | 31 kmp 没几行字吧。。。
int strstr(String haystack, String needle) {
int hLen = hayStack.length();
int nLen = needle.length();
int i = 0; int j = 0;
int[] next = new int[nLen];
preProcess(needle, next);
while (i < hLen && j < nLen) {
if (haystack.charAt(i) == needle.charAt(j)) { i++; j++;}
else {
j = next[j];
}
}
if (j == nLen) return i-j;
else return -1;
}
void preProcess(String needle, int[] next) {
next[0] = -1;
int k = -1... 阅读全帖 |
|
|
S***w
发帖数: 1014 | 33 HR说只有 背景聊天， 还是面了2道算法
一半时间聊behavior questions
然后说做题吧， 真想说， HR说不考题啊
1. strstr
就用最简单那个办法，
我说还有rolling hash Rabin-Karp算法， KMP 但是没让我写
写的话， 我也会Rabin-Karp算法, 但不会KMP
2. 3 sum
两题都不难 , 觉得大家都能答上来，没法出彩
1) 没上KMP |
|
g****c
发帖数: 11 | 34 挂了有段时间了。现在上面经以答谢本版。
phone:
1. max sum subarray
2. tree level order traversal
onsite:
1. design a hash table
2. design a hash table, where the value must be stored in an append-only
file system
3. design a logging system which stores streams of integers within a time
period. implement get, put, getAvg
4. design an RSS feed
5. Edit distance; implement strstr |
|
g********i
发帖数: 770 | 35 电面：One Edit distance 和 min edit distance 老中大哥放水。秒过。
Onsite：
1. ML design设计一个根据用户信息的搜索，然后能辨识出来他的语言。
2. LC原题，3Sum + Trap water
3. System design： instgram
4. Coding： Sliding window maximum + LC原题，sliding window 包含所有字符那个
5. Culture fit： 有200M个用户，现在让你进行分组，将他们分成大概20个组，每个
组里大概有10M的用户，尽量让用户interaction多的在一起
6. 这轮coding不算： 类似一个读写锁，实现fair sync 和 nonfair sync 还有
strstr 暴力写完了，说了下kmp
已跪。
最近fresh 和 new graduate没有名额，只有E5有名额。recruiter原话。 |
|
r******y
发帖数: 21 | 36 这个周一刚刚面完，来发给面经回报本版，求个offer。
他家是按照组面的，面试流程很长，3轮phone + 6轮onsite，所以前后七个星期。
我面的是ArcGIS Server组，题目难度偏低，主要是culture fit + 聊天。
第一轮phone，问了stock I，strstr，Leetcode原题。
第二轮phone，特别简单，一个int数组求和。另一题是在[0, m]的随机数范围内产生[1
, n]个不重复的随机数。
第三轮phone，纯聊天，和一个Product engineer聊天。他家的product engineer相当
于QA。
两个星期后，收到onsite邀请。公司在redlands，位于LA东边，靠近Riverside。整个
onsite长达四天，第一天到达，第二天面试，第三天可以多逗留一天，访问当地社区，
逛一逛之类，第四天离开。
Onsite的每轮面试都是两个面试官。
Onsite第一面，ArcGIS组的VP，主要是问问简历，聊天，问了两个简单的rest设计题。
Onsite第二面，面试官是之前phone第三面的QA，也是聊简历，解释一下mapredu... 阅读全帖 |
|
I**********a
发帖数: 1183 | 37 来自主题: JobHunting版 - 刚跪的电面 1. strstr
2. find first K most frequent number
都是老题，但第二题事先准备时看面经，都是问Kth most frequent number. 解法就
是的HashMap建好，然后quickselect。 O(n).
这里要求first K， 想了半天我说那就整个maxheap, pop前Ｋ个freq, 再去HashMap
里找，而且考虑到重复频率的可能，还要一个HashSet避免重复频率只找到其中一个元
素。 Code写完，说复杂度太高，让优化，吭哧了半天也没想出咋优化，跪了。。
求大神指点，谢谢！ |
|
h**p
发帖数: 211 | 38 来自主题: JobHunting版 - 刚跪的电面 返回 第k个跟第前k个数是一样的
同样的写法，就是返回值不一样。第k个返回的是一个数，第前k个返回的就是一个数组
如果是quick select，既然你已经找到第k个了，那在array里之前的都已经是小于第k
个的，一起返回就好了。复杂度应该还是线性
LZ这是哪家的题？感觉难度跟类型像是FB的？strstr需要写kmp吗？
HashMap |
|
x******6
发帖数: 46 | 39 来自主题: JobHunting版 - 刚跪的电面 首先，如果用Max heap，time complexity最好是nlogn；但如果用min heap, 就可以改
善到nlogk。
其次，没必要pop之后再去map里找，可以建一个包含num和freq的class，然后heap里存
这个class的object，这样pop的时候可以轻易print number
[在 ItachiUchiha (仙人掌) 的大作中提到：]
：1. strstr
：2. find first K most frequent number
：........... |
|
d*********e
发帖数: 352 | 40 别提了
上次写了个及其简单的strstr
我用了python，直接compare substring
三姐说不能compare string。
只能compare char
三姐只会JAVA。。。 |
|
d*********e
发帖数: 352 | 41 别提了
上次写了个及其简单的strstr
我用了python，直接compare substring
三姐说不能compare string。
只能compare char
三姐只会JAVA。。。 |
|
s**********1
发帖数: 73 | 42 面经
1. Senior Manager：大组下另外一个平行小组的小boss，Resume，扯了好多好多，问
我各种细节，还问我latitude和longitude怎么存，精度，误差blabla==我其实就是调
用个API啊==
代码：一个游戏讲了五分钟==搞得紧张了五分钟，最后的变体其实就是判断一个String
的所有字符在不在另外一个String里面，但是不能是permutation，以及followup，
strstr etc.
2. Director，大组的大boss，也是1，3轮Senior manager的boss，上来白板先做了道
Coin Change，DP搞定，需要返回所有钱的List，后面问了点Design的东西，比较琐碎
，就不细说了，因为是大BOSS，聊了很多Groupon的情况以及组内正在focus的东西……
这时候发现口语差是多么捉急的一件事情……
一件事情没讲清，我只好说never mind。。。然后看他一脸迷惑的看着我==硬是换了种
明显有语病的方式问他
3. Senior Manger：我面的组的boss，大牛阿三，明明是面试==居然带我去食堂吃饭==... 阅读全帖 |
|
r*******g
发帖数: 1335 | 43 还记得找回文数subsequence那道题不？这道题很像啊。
给定aabbcccc, 记录每个地点向右看最近的aa,bb,cccc的位置，这个就是kmp，或者直
接调用strstr。然后就可以dfs了。空间开销也不大，因为输入只是abc，假设输入是3
个字符，那么空间就是N*3。
算法大概是
dfs(){
对当前位置，假设现在已经match了ab，那就在接下来位置找c，每次找的时候利用
前面记录的数组。
}
distinct subsequence不对吧，这里不是删除单个字符。 |
|
p*********w
发帖数: 606 | 44 onsite第一个问了load balancer和web server的design，第二个是lunch，随便聊，第
三个问了浏览器输入url后会发生什么，刷了两道题，一道strstr，一道矩阵里找path
，第四个问了testing和continuals integration注意些什么，怎么debug，log level
之类的，第五个问了问做过的项目。电话加面主要是问linux kernel编程和网络方面的
东西。 |
|
c******3
发帖数: 6509 | 45 看了半天题目，没看见不让用strlen啊，你还用strdup去分配内存来计算count
“without using a second string for temporary storage. ”，你以为char buf[
count]就不算string了？
最后的拷贝最狠，清空整个src[]，然后做strcpy，难道不知道strcpy带结尾0赋值能力
？完全是多余的运算
本来一个简单strstr+memmove搞定的小程序，你自己看看用了多少字符串操作，而且中
间src重来不移动，每次循环都是从头扫描到尾部，不挂就没天理了... |
|
e*******s
发帖数: 1979 | 46 还得看刷的质量吧
像strstr这样的题 认真刷可以顶10道 |
|
e*******s
发帖数: 1979 | 47 这我就不清楚了 至少他出一题strstr不是只为了让你展示一下brute force吧?
或者至少写一下boyer moore的bad character shift rule?
KMP完全写对是不容易 大概说一下思路 关键思想总不难吧.
思路看一下总归不会忘掉的 算法如果要最近研究才能去面试 那面试得花多少时间准备. |
|
o*q
发帖数: 630 | 48 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
T*******e
发帖数: 4928 | 49 那你多面几个ABC大一的。既然如你所说，“上来就能一边当场思考，
一边解说，最后大都能把题一点都不拖泥带水的解出来，有的甚至能想出匪夷
所思的绝妙解法来”。比如你问个leetcode easy strstr啥的, 他们十分钟
就能搞出个绝妙的Linear解法。。。K.M.P.都会自叹不如的。反正牛皮不上税。
怎么吹都行😉. |
|
发帖数: 1 | 50 这个就是典型space v time balance
你这办法就是最优了，strstr是线性的 |
|
