h**6
发帖数: 4160 | 1 四流学校Fresh EE PhD年底毕业，找了半年的工作终于有着落了。
微软Windows Live 59级SDE，给的是master的价：
8.1w + 0-20%bonus + $5w stock/4 years + 0.5w搬家费
网上投的简历，三周后网上测试，四周后hr电面，六周后onsite面试，七周后offer。
onsite面了五个人，第三人包括吃午饭共90分钟，其余每人60分钟。
1.C语言字符串相关问题。
1)写出strstr函数，准备好的BM算法没有用上，用的最土的O(nm)算法。
注意两点：a.不要用strlen(防止某个字符串很长)，b.只检查长度许可的部分(起始位
置为0到n-m+1)
2)在长度未知的文件中查找字符串。
2.定义无符号可变长度长整数类并实现加减乘除。
1)加法因为内存分配研究了半天，定义了分配和使用两个size而搞定；
3)乘法提到可以使用FFT，但仍然用普通方法实现。
4)除法的试商函数没有时间写了，但我说用二分法实现，面试官表示满意。
3.吃饭时未必需要参考版上的建议什么可以吃，什么不能吃。我的饮食一向比较独特，
选自己熟悉的吃就行了。吃... 阅读全帖 |
|
D***h
发帖数: 183 | 2 恭喜。
strstr source code里面就是用的strlen阿。 |
|
c***2
发帖数: 838 | 3 One Indian interviewer asks me to write strstr()
I gave him the implementation from C lib, then he complains about missing
NULL check and length check, which are not needed at all.
So it all depends... |
|
d**f
发帖数: 264 | 4 来自主题: JobHunting版 - 贡献两个题 我也来贡献一个不算无聊的题目
考基本功
function prototype:
bool ReplaceSubString( char* ori, const char* sub, const char* rep, int
buffersize );
要求不能用任何std lib,也就是strlen(),strstr()都需要你自己写
要求O(n) and in place.
ori is the original string;
sub is the sub-string need to be replaced;
rep is the replaced string;
buffersize is the 'ori' buffersize.
If the result str size is larger than the buffersize, return false.
题目的idea也很容易想出来，但是要在半个小时写出clean的code,必须是一个非常熟练
的码工. |
|
r*****b
发帖数: 8 | 5 刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
第一轮:
经典stack题 pop, push, getmin
实现一下strcmp
第二轮:
打印一棵二叉树最深的路径
实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
注意一下 needle可能比haystack长.. (俺忘了这个..)
ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :( |
|
g*********s
发帖数: 1782 | 6 这个strstr的实现里为什么要考虑needle长于haystack？我试了一下，可以自然处理啊。 |
|
l*****a
发帖数: 14598 | 7
），first
brute force, then optimize. 第二天通知安排OnSite.
it is strstr, haha
决。 |
|
l*****a
发帖数: 14598 | 8 I assume that is KMP for strstr |
|
|
l*****a
发帖数: 14598 | 10 strcpy
strcat
strcmp
strstr
substring |
|
f*****w
发帖数: 2602 | 11 还不知道接下来结果怎么样 不过还是趁有空先回馈一下版面
第一次
居然是大牛Andrew Ng的学生；
为什么要FB
如果来了FB 最想做的事情 project 会是什么
然后问了个简历上的问题
然后 两个技术问题 很简单的
1. 实现一个strstr() 我说我可写不出KMP， 他说没事没事 就写个普通的就好
2. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点。 我很stupid
地卡了很
久 最后给了一个不是很好的答案(O(lgn*lgn))。 他最后告诉我了更好的方法, 这个方
法确实比
我的好很多,lgN时间O(1)空间 就可以了。
我以为我挂了，但是有了第二次
这次好一些
1) 为什么FB
2) 简历上的好几个问题
3) 技术问题是找一个binary tree的叶子的最少depth。 我很stupid地给了个递归方法
。他说
不行啊， 要是很不balance的话，效率会很低。 我又很stupid的说那我会randomize每
次递归
的时候是左子树还是右子树，这样average 复杂度会低一些。
他忍无可忍了，说他expect something li... 阅读全帖 |
|
z*******y
发帖数: 578 | 12 前些日子面的，尽管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... 阅读全帖 |
|
a**********2
发帖数: 340 | 13 都是老题，攒攒人品
1.分层打印二叉树
2.strstr（）
3.count words
4.tic-tac toe winning条件，如何update board
5.hash table和 BST的优劣势，什么时候该用什么结构。 |
|
P**********c
发帖数: 3417 | 14 是用suffix tree还是针对这个题目有更简单直观的解法？ |
|
w******a
发帖数: 236 | 15 Here is my code. Tested on my dev box:
const char * my_strstr(const char * s1, const char * s2)
{
int i;
for (;s1;s1++) {
for(i=0;s1&s;s1++,s2++,i++) {
if (*s1 != *s2) {
s1 -= i;
s2 -= i;
break;
}
else if (!(*(s2+1))) {
return s1-i;
}
}
}
return 0;
} |
|
|
p*****u
发帖数: 310 | 17 Did not check if point is null. |
|
k*j
发帖数: 153 | 18 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 | 19 Should we write the kmp during the interview? Or just write the brute force? |
|
y****d
发帖数: 52 | 20 有没有朋友有类似的经历？
我现在学校做postdoc，持有cap-exempt的H1B，有效至今年8月31日。半个月前拿到一个
公司的offer，公司希望我9月1日就开始上班。我第一次申请cap-subject的H1B，
公司律师说2007年有一个什么memo，即使有cap，10月1日之前也能合法工作。
因为我现在的H1B 8月31日到期，律师递交了两份申请：
一份是H1B extension, 将我现在的H1B延长到9月30日；
一份是H1B transfer, 将我的H1B的sponsor转到新的公司，9月1日开始。
各位觉得靠谱吗？ USCIS批准的可能性大吗？
要是USCIS只能准许10月1日开始新的cap-subject H1B的话，那我9月份是不是就
只能回国签证去了？ 多谢！
这是我从网上找的一个类似的case：
Question 7: A Ph.D. student began her first H-1B employment in August 2009,
working as a postdoctoral associate at a university, w... 阅读全帖 |
|
s*******f
发帖数: 1114 | 21 面试了很多，有一个offer，不过没赶上H1B。我懒，一直没总结，多数问题板上都有。
慢慢更新帖子列出来，不列公司名。
1. 正则表达式匹配字符串，包含 *， ?
2. give u a function IsBad(item) and an array: good, good, .., bad, bad, ...
always bad, find out first bad
3. design a data structure, support 2 functions: Insert and GetMedian.
4. give a matrix, sorted as follow, M[i][col - 1] < M[i + 1][0]
1 3 4
5 6 8
10 14 16
write function: bool Find(int k)
5. linkedin经典format文本题，我居然没复习到，真得给h1b进度逼死了
6. write function: search(keywords). you have invert table, return top10
b... 阅读全帖 |
|
S**I
发帖数: 15689 | 22 ☆─────────────────────────────────────☆
ch222 (ch) 于 (Fri May 6 01:16:18 2011, 美东) 提到:
Apple Offer
------------
Package一般, 与Glassdoor相符
知足常乐: 满意.
面试过程:(两次onsite)
---------------------
for(round=1;round<=6;round++) {
/* 1-2 minutes */
Two new Interviewers:寒喧;
/* 25-30 minutes */
大算法题 1道: DP/Trie/Hash/Sorting的组合;
例子: Num of coins for a target value
/* 10-15 minutes */
小算法题 2-3道: White-board coding.
例子: 1) 数Integer中1的个数
2) ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 23 这要看coding题的难度。
例如strstr/atoi要求一次写对不算过分，但是regular expression matching这种难度
的可以写的不是很clean，但是主要的corner cases都得考虑清楚，一些小bug应该不大
问题。 |
|
q********c
发帖数: 1774 | 24 Isn't it similar to strstr? Is it a phone or onsite question? |
|
q********c
发帖数: 1774 | 25 Isn't it similar to strstr? Is it a phone or onsite question? |
|
S**I
发帖数: 15689 | 26 ☆─────────────────────────────────────☆
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 | 27 ☆─────────────────────────────────────☆
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... 阅读全帖 |
|
d********w
发帖数: 363 | 28 coding:
- JOIN: nested join, hash join, sort-merge join
- Number: Fibonacci, prime，随机取文件某一行
- String: strstr, wordcount
- Tree: height, lca, balance tree
- Heap: 查找最大的k个数
- DP: 最大连续子串和
- array: find a key in rotated array, 去除重复字符
- linkedlist: 是否有环，插入结点，删除重复结点
- 递归回溯：变化很多，这方面需要大量练习
知识性：
多线程，mutex/semaphore
java GC
C++ virtual, smart pointer
regex使用
数据库：知道btree, 索引
search engine: 倒排表,拉链，稀疏索引，空间向量模型，tf*idf,
large scale data: hash, consistent hash, bloom filter, bitmap, 外排序，
partition
分布式：CAP理论，gos... 阅读全帖 |
|
d********w
发帖数: 363 | 29 coding:
- JOIN: nested join, hash join, sort-merge join
- Number: Fibonacci, prime，随机取文件某一行
- String: strstr, wordcount
- Tree: height, lca, balance tree
- Heap: 查找最大的k个数
- DP: 最大连续子串和
- array: find a key in rotated array, 去除重复字符
- linkedlist: 是否有环，插入结点，删除重复结点
- 递归回溯：变化很多，这方面需要大量练习
知识性：
多线程，mutex/semaphore
java GC
C++ virtual, smart pointer
regex使用
数据库：知道btree, 索引
search engine: 倒排表,拉链，稀疏索引，空间向量模型，tf*idf,
large scale data: hash, consistent hash, bloom filter, bitmap, 外排序，
partition
分布式：CAP理论，gos... 阅读全帖 |
|
i**********e
发帖数: 1145 | 30 F:
3Sum
Add Binary
Combination Sum
Count and Say
Divide Two Integers
Edit Distance
Implement strStr()
Letter Combinations of a Phone Number
Longest Palindromic Substring
Merge Intervals
Multiply Strings
Next Permutation
Permutations, Permutations II
Regular Expression Matching
Remove Duplicates
Remove Element
Search in Rotated Sorted Array
String to Integer (atoi)
Sqrt(x)
Substring with Concatenation of All Words
Trapping Rain Water
Unique Paths, Unique Paths II
G:
3Sum
Climbing Stairs
Container... 阅读全帖 |
|
i**********e
发帖数: 1145 | 31 不用 dp，这个 greedy 就可以解了。
思路就类似 strstr 的解法。 |
|
s*******f
发帖数: 1114 | 32 觉得中文是一种太聪明的语言，曾经用中文和面试官聊得很专业很欢，被拒了。
当时的场景如果是用英文面对老白烙印，估计好很多。
用中文，bar自然高了，平均110的智商。
最好把同胞当笨烙印面，这样他写出个strstr，你会很惊喜。 |
|
H****r
发帖数: 2801 | 33 KMP 通过
BoyerMoore 通过small,卡large... 手工测试发现除最后一个test外都可以，最后一个
test太长在网站上看不到.... 自己测试的一些都可以啊。 leetcode 能告诉最后一个
test 具体是啥吗？ |
|
l*********8
发帖数: 4642 | 34 aaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaab |
|
H****r
发帖数: 2801 | 35 worst-case running time of O(n+m) only if the pattern does not appear in the
text. 怎么超时了尼？ |
|
|
H****r
发帖数: 2801 | 37 还是自己程序有点问题，现在改了可以通过了 ：）
谢 长路08！ |
|
h**********l
发帖数: 6342 | 38 考点是 二分，别太挑剔吗
一些corner cases
不然， 你直接 return strstr()。。。。。。 一行
面试的人疯掉来的 |
|
I*I
发帖数: 618 | 39 1. strstr肯定不行，不光要match string，还要match大小。
2. 也不用二分，
3. 有O(N)算法 |
|
h****e
发帖数: 928 | 40 你还是要这儿继续多灌水，大家做题才有乐趣，否则太枯燥了。
LeetCode上的题目你大概是用Java做的吧，那么就再用C++做一遍。做完了
再用Javascript、PHP、Python...
我还想出LeetCode上的一些题目的扩展。例如，做了字符串的加法和
乘法，就再做字符串的减法和除法。做了Integer to Roman，就再做
Roman to Integer。做了strstr，就再做strtok, strspn, strcspn等等。 |
|
c***p
发帖数: 221 | 41 编程：
1. strstr(char* str, char* substr)
与常规要求不同的是，需要返回最后一个匹配的子串
2. c++ STL 中 map 的实现细节(redblack tree). 比如， 如果删除了一个元素，以前
得到的iterator是否valid.
基础知识：
1. socket API: both client side and server side;
connect 如何setup. (three-way hand shaking protocol)
2. VLAN (没答上来)
3. tcp protocol: flow control, congestion control.
4. memory management:
how to manage; (my answer: linked list)
how to check if some address has been allocated
5. 如何debug memory leak.
我回答了很多：看ps, strace, valgrind. 最后才知道他要的是g... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 42 应该不会吧。。。
这个kmp主要觉得思想很巧。我一边看一边膜拜knuth。。。
不过leetcode上不是有个strstr的题么 |
|
|
l****c
发帖数: 838 | 44 You should read in the string and parse.
You don't know how long the first part string is or how long the number is.
So if you define:
char tempprice[10];
char ticker[10];
You have the risk of buffer overflow.
Here is my solution. I debug it as I wrote it, so it is not optimized.
it is pure C. You can get result with 2 lines of perl or python code
============================
#include
#include
#include
int main()
{
char *str = "GOOD|89.34";
char *ptoken, *... 阅读全帖 |
|
j******2
发帖数: 362 | 45 看了下，好像不是很简单的啊，尽是些paper。。。
这个suffix array和suffix tree的linear算法要不要掌握啊？本来是在搞DP，结果被
这个longest common substring引得来看这个suffix tree/array，投入的时间越来越
多，但是150和leetcode上都没啥suffix tree/array的问题啊，只有个strstr还蛮简单
的。。。
不是科班出身的就是累啊，千疮百孔的。。。 |
|
l*********8
发帖数: 4642 | 46 我写一个 （还没有考虑“”的问题，好像挺复杂）
bool removeComment(char * s)
{
char *r = s, *w = s;
while (r && *r){
if ( !strncmp(r, "/*", 2) ) {
r = strstr(r+2, "*/");
r = (r!=NULL) ? r+2 : r;
} else if ( !strncmp(r, "//", 2) ) {
r = strchr(r+2, '\n');
r = (r!=NULL) ? r : s+strlen(s);
} else {
*w++ = *r++;
}
}
if (w != NULL)
*w = '\0';
return r!=NULL;
} |
|
s******y
发帖数: 72 | 47 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... 阅读全帖 |
|
s******y
发帖数: 72 | 48 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... 阅读全帖 |
|
f****e
发帖数: 34 | 49 来自主题: 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 | 50 来自主题: 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... 阅读全帖 |
|
