由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G四次电面面经
相关主题
Facebook电话面试总结palindrome int这个recursive能再java上实现么?
leetcode里的Palindrome partition问题这个题目怎么做
最长回文串Permutation leetcode-
大家帮忙看看我的Palindrome II 的解法Exposed上一道string permutation的题
DP通项公式Given a string, find all its permutations without any repetition?
FB Phone Interview Failed by a simple question回文数的问题
请教一道面试题leetcoede新题Valid Palindrome
Bloomberg面试题leetcode 一道题 valid palindrome
相关话题的讨论汇总
话题: string话题: int话题: return话题: example话题: split
进入JobHunting版参与讨论
1 (共1页)
f*******t
发帖数: 7549
1
这次申full-time两轮电面后被拒,干脆把面经发出来攒rp。因为没有on-site经验,题
目参考作用一般吧。
首先是申summer intern时的两次电面。记不清楚了,能想起多少coding题就写多少,
杂七杂八的问题就忽略了。当时准备得不充足,答得不太好,居然能过电面,实在幸运。但最终也没
能去成……
第一面,三哥:
1. A string consists of parentheses and brackets for example "(()([]))",
check if it is well formed. 经典题,我用stack做的。刚才顺手看了下当时写的代码,发
现还是有bug……
2.Given strings like "CB", "BD", "DE", find the sequence of alphabets.
The result is "CBDE" for the example. 当时完全没头绪,后来跟朋友讨论,解法是基本
算法Topsort。
第二面,大概是老美:
1. Verify whether a string contains all the characters of another
string. 经典题,开个数组计数。
2. Given two strings that one string contains the other string, while
the other string could be split into any set of substrings. Please find
the minimum split time. Example: "apple pie is deicious" contains
"applepie"'s substring set "apple" and "pie", so the minimum split time
is 1. 写伪代码,貌似是普通DP。
3.忘了具体题目,跟第二题类似,我没答好。
然后是最近的full-time电面。果断被某三哥坑了。
第一面,老美:
1. Is two arrays share the same set of objects but are probably
different permutations. 经典题,用hashmap。
2. 开放设计题,让第1 trillion次google搜索返回一个中奖页面。重点是怎样在分布式系统里
统计搜索次数;另外还要防止一个用户多次中奖。不懂,随便扯了点……
3. Use a dictionary to split search string into valid words. For
example, "applepie" -> "apple" + "pie". 自我感觉答的不错,网上有个详解:
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
problem/
第二面,三哥:
1. Test whether an integer is a palindrome. 我一开始的代码用sprintf打印到字符
串里,然后从字符串首尾开始比较是否相等。三哥又问如果不知道int有多少位怎么办,我又写了个
计算有多少位的代码,并动态分配相应长度的字符串。三哥还是不满意,非要in-place的解法。最
后我才想出最优解,虽然不难,但没见过的题真心难解啊……
附上代码,感觉不太需要考虑溢出的问题:
bool IsPalindrome(int i) {
if(i < 0)
return false;
int num = i;
int reversed = 0;
while(i > 0) {
reversed *= 10;
reversed += i % 10;
i /= 10;
}
if(reversed == num)
return true;
else
return false;
}
本来三哥就迟了十来分钟,纠结完这题花了差不多半个小时。我问接下来的题是什么,他说没了,进
入提问环节。我问他做什么项目,他说是跟chrome有关的保密project,不能透露信息,我就完全
无语了。还扯了些别的,他的态度比较差。
两周后HR打来电话把我拒了,dream company的面试就毁在三哥手上,郁闷啊。
md风水轮流转,以后我要是当了面试官,必然让三哥们求生不能求死不得!
r****t
发帖数: 10904
2
ding
B*******1
发帖数: 2454
3
我周1也刚2面完google,也肯定挂了,开始以为是3哥,后来看了名字才知道应该是俄
罗斯人,那英文真的把我搞到,有好几个重要条件都是因为他说太快了,发音不准,搞
到我miss掉了,想不到我准备了这么久,就这么挂在俄罗斯人身上了。
s******n
发帖数: 3946
4
2. Given two strings that one string contains the other string, while
the
other string could be split into any set of substrings. Please find the
minimum split time. Example: "apple pie is deicious" contains
"applepie"'s
substring set "apple" and "pie", so the minimum split time is 1
3. Use a dictionary to split search string into valid words. For
example, "
applepie" -> "apple" + "pie".
这两个是一个问题吧?recursive + DP
A**u
发帖数: 2458
5
请问这个怎么想的
Given strings like "CB", "BD", "DE", find the sequence of alphabets
("CBDE
" for the example")
C-B, B-D,D-E,
你用topsort, 是有向图?
那顺序不是唯一的吗
s******n
发帖数: 3946
6
我题目都看不懂。。。

【在 A**u 的大作中提到】
: 请问这个怎么想的
: Given strings like "CB", "BD", "DE", find the sequence of alphabets
: ("CBDE
: " for the example")
: C-B, B-D,D-E,
: 你用topsort, 是有向图?
: 那顺序不是唯一的吗

A**u
发帖数: 2458
7
Verify whether a string contains all the characters of another
string. 经
典题,开个数组计数。
这个不应该是建立hash map吗 你怎么设置数组呢
f*******t
发帖数: 7549
8
因为ascii码只有256个,所以用256的数组够用了。其实这就是简化的hash map。后面
关键字permutation的那题与这道基本相同,因为是Object所以用hash map。

【在 A**u 的大作中提到】
: Verify whether a string contains all the characters of another
: string. 经
: 典题,开个数组计数。
: 这个不应该是建立hash map吗 你怎么设置数组呢

f*******t
发帖数: 7549
9
当作有向图来解咯。
有环的时候,比如"AB", "BC", "CA",通过topsort可以检测出来。
面试官应该是想让我讲出基本算法,不过因为我从一开始就没头绪,所以如何检测/处
理这种情况更是无法回答了。

【在 A**u 的大作中提到】
: Verify whether a string contains all the characters of another
: string. 经
: 典题,开个数组计数。
: 这个不应该是建立hash map吗 你怎么设置数组呢

f*******t
发帖数: 7549
10
貌似是一个问题,详细解答看后面的链接

【在 s******n 的大作中提到】
: 2. Given two strings that one string contains the other string, while
: the
: other string could be split into any set of substrings. Please find the
: minimum split time. Example: "apple pie is deicious" contains
: "applepie"'s
: substring set "apple" and "pie", so the minimum split time is 1
: 3. Use a dictionary to split search string into valid words. For
: example, "
: applepie" -> "apple" + "pie".
: 这两个是一个问题吧?recursive + DP

相关主题
FB Phone Interview Failed by a simple questionpalindrome int这个recursive能再java上实现么?
请教一道面试题这个题目怎么做
Bloomberg面试题Permutation leetcode-
进入JobHunting版参与讨论
B*******1
发帖数: 2454
11
http://www.mitbbs.com/article_t/JobHunting/31865333.html

【在 f*******t 的大作中提到】
: 当作有向图来解咯。
: 有环的时候,比如"AB", "BC", "CA",通过topsort可以检测出来。
: 面试官应该是想让我讲出基本算法,不过因为我从一开始就没头绪,所以如何检测/处
: 理这种情况更是无法回答了。

s******n
发帖数: 3946
12
这题啥意思?打印每个单词第一个字母和最后一单词的最后一个字母?
2.Given strings like "CB", "BD", "DE", find the sequence of alphabets.
The result is "CBDE" for the example. 当时完全没头绪,后来跟朋友讨论,解法是
基本
算法Topsort。
A**u
发帖数: 2458
13
谢谢你分享
谢谢fantasist分享

【在 B*******1 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/31865333.html
s******n
发帖数: 3946
14
这下看懂这道题了

【在 B*******1 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/31865333.html
A**u
发帖数: 2458
15
我又看蒙了

【在 s******n 的大作中提到】
: 这下看懂这道题了
r*******g
发帖数: 1335
16
还是没看看懂题
题目是说,要求生成的是一个string,这个string是由原始若干string构成,并且不能
break原始的string,也就是说,原始的string假设是ABD,你不能只把AB选出来构成生
成的string,对不对?
这样的话,不但要求起始letter构成了单增,而且每个string内部也必须单增。
不知道我理解题意对不对。

【在 B*******1 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/31865333.html
q****x
发帖数: 7404
17
full-time二面回文题,直接reverse判断是否相等即可。O(n) + O(1)
不过你前三个面试难度不低。

运。但最终也没
代码,发

【在 f*******t 的大作中提到】
: 这次申full-time两轮电面后被拒,干脆把面经发出来攒rp。因为没有on-site经验,题
: 目参考作用一般吧。
: 首先是申summer intern时的两次电面。记不清楚了,能想起多少coding题就写多少,
: 杂七杂八的问题就忽略了。当时准备得不充足,答得不太好,居然能过电面,实在幸运。但最终也没
: 能去成……
: 第一面,三哥:
: 1. A string consists of parentheses and brackets for example "(()([]))",
: check if it is well formed. 经典题,我用stack做的。刚才顺手看了下当时写的代码,发
: 现还是有bug……
: 2.Given strings like "CB", "BD", "DE", find the sequence of alphabets.

g*****i
发帖数: 2162
18
topsort的结果不一定唯一

【在 A**u 的大作中提到】
: 我又看蒙了
B*******1
发帖数: 2454
19
nod
不是唯一的。

【在 g*****i 的大作中提到】
: topsort的结果不一定唯一
l*****a
发帖数: 14598
20
reverse显然效率不高
因为对于回文reverse到一半就应该知道结果

【在 q****x 的大作中提到】
: full-time二面回文题,直接reverse判断是否相等即可。O(n) + O(1)
: 不过你前三个面试难度不低。
:
: 运。但最终也没
: 代码,发

相关主题
Exposed上一道string permutation的题leetcoede新题Valid Palindrome
Given a string, find all its permutations without any repetition?leetcode 一道题 valid palindrome
回文数的问题palindrome partioning II
进入JobHunting版参与讨论
q****x
发帖数: 7404
21
整数是二进制表示,你怎么知道reverse到一半?

【在 l*****a 的大作中提到】
: reverse显然效率不高
: 因为对于回文reverse到一半就应该知道结果

l*****a
发帖数: 14598
22
仔细看我说的
对于回文,到了1半你就知道了
非回文,当然不知到

【在 q****x 的大作中提到】
: 整数是二进制表示,你怎么知道reverse到一半?
q****x
发帖数: 7404
23
仔细看题。问的是整数,不是字符串。
而且就算是字符串,你也未必知道长度。

【在 l*****a 的大作中提到】
: 仔细看我说的
: 对于回文,到了1半你就知道了
: 非回文,当然不知到

q****x
发帖数: 7404
24
没考虑负数和溢出的话很简单。
int rev_int(int x);
{
int y = x, t = 0;
while ( y != 0 ) {
t = 10 * t + y % 10;
y = y / 10;
}
return t;
}
bool is_palind(int x)
{
return (x == rev_int(x));
}

【在 q****x 的大作中提到】
: 仔细看题。问的是整数,不是字符串。
: 而且就算是字符串,你也未必知道长度。

l*****a
发帖数: 14598
25
我给的例子不是整数?

【在 q****x 的大作中提到】
: 仔细看题。问的是整数,不是字符串。
: 而且就算是字符串,你也未必知道长度。

l*****a
发帖数: 14598
26
bool IsPalindrome(int i) {
if(i < 0)
return false;
int num = i;
int reversed = 0;
while(num) {
reversed *= 10;
reversed += num % 10;
if (num==reversed) return true;
num /= 10;
if (num==reversed) return true;
}
return false;
}

【在 q****x 的大作中提到】
: 没考虑负数和溢出的话很简单。
: int rev_int(int x);
: {
: int y = x, t = 0;
: while ( y != 0 ) {
: t = 10 * t + y % 10;
: y = y / 10;
: }
: return t;
: }

B*******1
发帖数: 2454
27
en. 学习了,我一直都用整个reverse再比较的方法。

【在 l*****a 的大作中提到】
: bool IsPalindrome(int i) {
: if(i < 0)
: return false;
: int num = i;
: int reversed = 0;
: while(num) {
: reversed *= 10;
: reversed += num % 10;
: if (num==reversed) return true;
: num /= 10;

q****x
发帖数: 7404
28
不错。

【在 l*****a 的大作中提到】
: bool IsPalindrome(int i) {
: if(i < 0)
: return false;
: int num = i;
: int reversed = 0;
: while(num) {
: reversed *= 10;
: reversed += num % 10;
: if (num==reversed) return true;
: num /= 10;

s*****n
发帖数: 162
29
似乎不对。
比如:10100
应该不算回文,但你的算法会返回true.

【在 l*****a 的大作中提到】
: bool IsPalindrome(int i) {
: if(i < 0)
: return false;
: int num = i;
: int reversed = 0;
: while(num) {
: reversed *= 10;
: reversed += num % 10;
: if (num==reversed) return true;
: num /= 10;

f*******t
发帖数: 7549
30
我发现只算一半的话如果输入110会返回true,所以还是得全算一遍。
话说这帖都能上十大= =

【在 s*****n 的大作中提到】
: 似乎不对。
: 比如:10100
: 应该不算回文,但你的算法会返回true.

相关主题
Palindrome那题,OJ上通不过leetcode里的Palindrome partition问题
Palindrome那题,OJ上通不过最长回文串
Facebook电话面试总结大家帮忙看看我的Palindrome II 的解法
进入JobHunting版参与讨论
l*****a
发帖数: 14598
31
说的很对啊
那就加上尾数为0的特殊处理,尾数为0的return false
这回够不够?

【在 s*****n 的大作中提到】
: 似乎不对。
: 比如:10100
: 应该不算回文,但你的算法会返回true.

q****x
发帖数: 7404
32
仔细想了一下,即使在效率方面,你这个实现也未必好。
1. 循环体本身很短,多加两个判断等于加倍了处理时间。
2. 如果数字不是回文,你还是要查完所有位数。加上条件判断,实际慢了很多。
3. 如果数字是回文,你虽然只查一半位数,但考虑判断,也没有快。
综合考虑,效率更低,也不如全扫完简单易懂不容易错。
所以程序改进不能只看循环次数,还要看循环体的复杂度。

【在 l*****a 的大作中提到】
: 说的很对啊
: 那就加上尾数为0的特殊处理,尾数为0的return false
: 这回够不够?

l*****a
发帖数: 14598
33
how do u know the judgement is slower than / and %?

【在 q****x 的大作中提到】
: 仔细想了一下,即使在效率方面,你这个实现也未必好。
: 1. 循环体本身很短,多加两个判断等于加倍了处理时间。
: 2. 如果数字不是回文,你还是要查完所有位数。加上条件判断,实际慢了很多。
: 3. 如果数字是回文,你虽然只查一半位数,但考虑判断,也没有快。
: 综合考虑,效率更低,也不如全扫完简单易懂不容易错。
: 所以程序改进不能只看循环次数,还要看循环体的复杂度。

q****x
发帖数: 7404
34
how do you know it's faster?
keep in mind if the input is not a palind, your code is slower for sure. how many palind are there?

【在 l*****a 的大作中提到】
: how do u know the judgement is slower than / and %?
o****r
发帖数: 36
35
这些题为什么会比其他那些面经的题容易很多呢? 还有啊三哥有的也很好。 我就遇到
一个。口音特别重,我每个问题都要他重复好几遍, 结果人家也不嫌烦。 倒是一起面
我的一个老美都烦了。
不过关键点是我和这老印以前曾经在同一个公司工作过,虽然是不同城市。 最后还是
拿到offer
n*******w
发帖数: 687
36
1. A string consists of parentheses and brackets for example "(()([]))",
check if it is well formed.
用stack。遇到( 和 [ 入栈,遇到 ) 或者 ] 查栈顶是不是匹配。不匹配return false
。否则pop栈顶继续。到string结束,return true。
2. Given strings like "CB", "BD", "DE", find the sequence of alphabets.
The result is "CBDE" for the example.
topsort。重点是考虑node的入度和出度。有环的话可以检测出来。
3. Verify whether a string contains all the characters of another
string.
简单的数组,当做hashtable用。
4. Given two strings that one string contains the other string, while
the other string could be split into any set of substrings. Please find
the minimum split time. Example: "apple pie is deicious" contains
"applepie"'s substring set "apple" and "pie", so the minimum split time
is 1.
DP + recursive + backtrace
5. Is two arrays share the same set of objects but are probably
different permutations.
允许额外空间的话,用hashtable。否则直接排序后比较是否相等。
6. 开放设计题,让第1 trillion次google搜索返回一个中奖页面。重点是怎样在分布
式系统里
统计搜索次数;另外还要防止一个用户多次中奖。
这个题看interviewer的要求,可以弄得非常非常难。比如要考虑server crash,实时
返回中奖结果,最小化io cost等等。。。
设计太复杂,就不写了。
7. Use a dictionary to split search string into valid words. For
example, "applepie" -> "apple" + "pie". 自我感觉答的不错,网上有个详解:
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
problem/
跟4一样。
8. Test whether an integer is a palindrome.
看了上面的讨论,有两个疑问。
1、测试palindrome是基于binary representation还是十进制。得问interviewer。
比如,十进制下11是palindrome,二进制下不是的(1011)。
2、末尾有0算不算palindrome
比如1210。可以当做01210看,还是当做1210看。前者返回true,后者false。
至于用不用reverse方法做,反正integer一共就那么几十个bits,线性复杂度,基本没
太大区别。

运。但最终也没
代码,发

【在 f*******t 的大作中提到】
: 这次申full-time两轮电面后被拒,干脆把面经发出来攒rp。因为没有on-site经验,题
: 目参考作用一般吧。
: 首先是申summer intern时的两次电面。记不清楚了,能想起多少coding题就写多少,
: 杂七杂八的问题就忽略了。当时准备得不充足,答得不太好,居然能过电面,实在幸运。但最终也没
: 能去成……
: 第一面,三哥:
: 1. A string consists of parentheses and brackets for example "(()([]))",
: check if it is well formed. 经典题,我用stack做的。刚才顺手看了下当时写的代码,发
: 现还是有bug……
: 2.Given strings like "CB", "BD", "DE", find the sequence of alphabets.

K*******g
发帖数: 26
37
O(n)是肯定的,不过可以有个小的技巧,算到一半即可。
以下不考虑负数情况。
int isPalindrome(int n){
if(n<10) return 1;
if(n%10==0) return 0;
int rev = 0;
while(rev rev = rev*10+n%10;
n /= 10;
}
if(rev == n || rev/10 == n) return 1;
//former is for even number of digits, latter is for odd number of
digits
return 0;
}

【在 q****x 的大作中提到】
: full-time二面回文题,直接reverse判断是否相等即可。O(n) + O(1)
: 不过你前三个面试难度不低。
:
: 运。但最终也没
: 代码,发

s***n
发帖数: 373
38
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
这个solution为什么是 O(2^n)呢?我觉得O(n)就够了

false

【在 n*******w 的大作中提到】
: 1. A string consists of parentheses and brackets for example "(()([]))",
: check if it is well formed.
: 用stack。遇到( 和 [ 入栈,遇到 ) 或者 ] 查栈顶是不是匹配。不匹配return false
: 。否则pop栈顶继续。到string结束,return true。
: 2. Given strings like "CB", "BD", "DE", find the sequence of alphabets.
: The result is "CBDE" for the example.
: topsort。重点是考虑node的入度和出度。有环的话可以检测出来。
: 3. Verify whether a string contains all the characters of another
: string.
: 简单的数组,当做hashtable用。

f*******t
发帖数: 7549
39
不一定只分成两个单词啊,结果从1个单词到length个单词都有可能

【在 s***n 的大作中提到】
: http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
: 这个solution为什么是 O(2^n)呢?我觉得O(n)就够了
:
: false

s***n
发帖数: 373
40
如果输入的是 aaaaab, 'a'是一个word
他这个solution难道不是返回 a a a a ab?

【在 f*******t 的大作中提到】
: 不一定只分成两个单词啊,结果从1个单词到length个单词都有可能
相关主题
大家帮忙看看我的Palindrome II 的解法请教一道面试题
DP通项公式Bloomberg面试题
FB Phone Interview Failed by a simple questionpalindrome int这个recursive能再java上实现么?
进入JobHunting版参与讨论
s****a
发帖数: 528
41
you have two conditions in the while loop,
actually I don't think this is more efficient :P

【在 l*****a 的大作中提到】
: bool IsPalindrome(int i) {
: if(i < 0)
: return false;
: int num = i;
: int reversed = 0;
: while(num) {
: reversed *= 10;
: reversed += num % 10;
: if (num==reversed) return true;
: num /= 10;

s***n
发帖数: 116
42
开放式设计题,怎么统计分布式系统的搜索次数呢?
哪位给指点一下基本思路?

false

【在 n*******w 的大作中提到】
: 1. A string consists of parentheses and brackets for example "(()([]))",
: check if it is well formed.
: 用stack。遇到( 和 [ 入栈,遇到 ) 或者 ] 查栈顶是不是匹配。不匹配return false
: 。否则pop栈顶继续。到string结束,return true。
: 2. Given strings like "CB", "BD", "DE", find the sequence of alphabets.
: The result is "CBDE" for the example.
: topsort。重点是考虑node的入度和出度。有环的话可以检测出来。
: 3. Verify whether a string contains all the characters of another
: string.
: 简单的数组,当做hashtable用。

s******n
发帖数: 3946
43
把搜索次数存在分布式文件系统上?瞎猜一个

【在 s***n 的大作中提到】
: 开放式设计题,怎么统计分布式系统的搜索次数呢?
: 哪位给指点一下基本思路?
:
: false

e***n
发帖数: 42
44
"ab" 不是字典里的word,所以“a a a a ab” 不是solution, 程序会继续寻找其他
的组合,比如“a, a, a, aa, b”etc. 但每次最后都遇到 b, 所以就是所有不同数量
的a 都会被test,总共的次数是\sum_{i=0}^{n} C(n, i) = 2^n 这是“aaaaab”的
power set 所含元素的数量(参考:http://en.wikipedia.org/wiki/Power_sethttp://en.wikipedia.org/wiki/Binomial_theorem

【在 s***n 的大作中提到】
: 如果输入的是 aaaaab, 'a'是一个word
: 他这个solution难道不是返回 a a a a ab?

z****u
发帖数: 104
45
这道题的 DP 解法怎么做? http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/ 里面没写!
还有,前边 lz 面试的题目要求尽可能的少 split,这个怎么解?

【在 e***n 的大作中提到】
: "ab" 不是字典里的word,所以“a a a a ab” 不是solution, 程序会继续寻找其他
: 的组合,比如“a, a, a, aa, b”etc. 但每次最后都遇到 b, 所以就是所有不同数量
: 的a 都会被test,总共的次数是\sum_{i=0}^{n} C(n, i) = 2^n 这是“aaaaab”的
: power set 所含元素的数量(参考:http://en.wikipedia.org/wiki/Power_sethttp://en.wikipedia.org/wiki/Binomial_theorem

1 (共1页)
进入JobHunting版参与讨论
相关主题
leetcode 一道题 valid palindromeDP通项公式
palindrome partioning IIFB Phone Interview Failed by a simple question
Palindrome那题,OJ上通不过请教一道面试题
Palindrome那题,OJ上通不过Bloomberg面试题
Facebook电话面试总结palindrome int这个recursive能再java上实现么?
leetcode里的Palindrome partition问题这个题目怎么做
最长回文串Permutation leetcode-
大家帮忙看看我的Palindrome II 的解法Exposed上一道string permutation的题
相关话题的讨论汇总
话题: string话题: int话题: return话题: example话题: split