fb国内申请的曲折经历+电面 - 未名空间MITBBS历史存档

t*32015-01-27 08:01

1 楼

国内申请的，今天早上刚电面挂了，比较郁闷，来发泄一下，然后继续努力。
去年11月在国内看到fb tech talk和招人的广告，于是就分别申请了。后来收到邀请参
加12月18日的talk，申请职位的截止日是12月15日。在快到12月15日时候，看到版上热
心内推，又特地在15号请内推了一把。18号的talk后来发现就是招人宣讲。会后跟组织
活动hr聊了一下，结果一个hr特意走上来看着我胸前label念我的名字，然后告诉我我
会被直接邀请参加今年2月份的onsite，我特意跟她确认了一下是不需要参加电面。她
还告诉我一个多星期前就知道要邀请我参加onsite，但是她们最近组织talk啥的实在太
忙了。最后这个hr还给我了如何准备onsite的建议。我激动万分啊，talk后立即恶补
system design的东西。
然后过了圣诞等到两周前，我想奇怪了，还不发正式邀请信。问了一个一起参加talk的
朋友，人家元旦刚过就收到onsite通知了，于是就发邮件问HR，没有回复。第二天收到
一个职位申请确认，然后收到一封邮件要求约个电面时间。我就奇怪了，就重复了一下
当初她告诉我的信息，结果没有回复。等了两天没有消息，我直接请fb内部朋友帮忙问
了一下。结果这个hr立即打电话给我，问我是不是误会什么了。她说可能她说把另一个
人的名字跟我搞混了，我说不可能，你是看着我的名字label念的，而且我的名字非常
不容易重复，不可能搞混的。她想想又说，对不起，她们hr是没有权利免我的电面的，
一定是什么地方误会了，她表示很抱歉，但是愿意立即帮我安排电面，以免赶不上2月
初北京的onsite。想想也没别的什么办法，就同意了，结果不幸悲剧了，题也不算难，
但是当时脑子就是转不快，followup没有做完，也许是被孩子闹的失眠惹得祸，只睡了
4个小时，唉。。。
电面题目是task scheduler，举例如下：
Tasks: AABABCD
Cooldown Time: 2
A__AB_ABCD
Output: 10
就是说同样类型的task之间至少要等2，每个task的执行时间是1
followup: 如果cooldown是个参数，也就是说有可能会很长时间，怎么修改之前的程序

c*72015-01-27 08:01

2 楼

真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
己以后肯定会有机会的。
你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
上一次index相差大于等于x

n*n2015-01-27 08:01

3 楼

唐。前面一段纯水。面试有变动很正常。

【在 t*****3 的大作中提到】

: 国内申请的，今天早上刚电面挂了，比较郁闷，来发泄一下，然后继续努力。
: 去年11月在国内看到fb tech talk和招人的广告，于是就分别申请了。后来收到邀请参
: 加12月18日的talk，申请职位的截止日是12月15日。在快到12月15日时候，看到版上热
: 心内推，又特地在15号请内推了一把。18号的talk后来发现就是招人宣讲。会后跟组织
: 活动hr聊了一下，结果一个hr特意走上来看着我胸前label念我的名字，然后告诉我我
: 会被直接邀请参加今年2月份的onsite，我特意跟她确认了一下是不需要参加电面。她
: 还告诉我一个多星期前就知道要邀请我参加onsite，但是她们最近组织talk啥的实在太
: 忙了。最后这个hr还给我了如何准备onsite的建议。我激动万分啊，talk后立即恶补
: system design的东西。
: 然后过了圣诞等到两周前，我想奇怪了，还不发正式邀请信。问了一个一起参加talk的

t*32015-01-27 08:01

4 楼

谢谢安慰。是这个思路，我已经写出来大部分了，面试官也说这个思路正确，但是说时
间到了，就让我停了。我犯的一个错误是几乎不停的解释自己每步在做什么，也可能是
不能更快速解决问题的一个原因。

【在 c*******7 的大作中提到】

: 真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
: 己以后肯定会有机会的。
: 你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
: 上一次index相差大于等于x

t*32015-01-27 08:01

5 楼

呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！

【在 n******n 的大作中提到】

: 唐。前面一段纯水。面试有变动很正常。

n*n2015-01-27 08:01

6 楼

拒几次就心静如水了，没什么大不了。
那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。

【在 t*****3 的大作中提到】

: 呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！

w*o2015-01-27 08:01

7 楼

如果可以用Java的話, 直接用LinkedHashMap來做(preserve order). Php的話就不懂了.

h*e2015-01-27 08:01

8 楼

我倒觉得用一个长度是cooldown 数值的queue 来存，如果queue里有相同的task就
push一个null进去

j*32015-01-27 08:01

9 楼

好像用个hashmap就可以了吧？边读数组边加入cool down，再搞个counter记录当时的
index，这样hash map的index也是加入cool down 之后的index了。。。

t*a2015-01-27 08:01

10 楼

直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
数组中的idx就行。

y*e2015-01-27 08:01

11 楼

不太明白。。是循环数组里存index， hashmap里存字母？

【在 t*****a 的大作中提到】

: 直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
: 数组中的idx就行。

t*32015-01-27 08:01

12 楼

不能，就是按照输入顺序一个个处理，主要是一开始cooldown只有2，所以只要简单检
查前两个tasks即可,如果cooldown变长，就得记录当前同类型task的上一次截止时间。

【在 n******n 的大作中提到】

: 拒几次就心静如水了，没什么大不了。
: 那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。

w*t2015-01-27 08:01

13 楼

题意还不是太明白：
A__AB_ABCD
cooldown是2
AB 和 AB也算是同一个类型的任务吧？
中间怎么只有一个空格呢？

w*s2015-01-27 08:01

14 楼

easy job
#include
#include
#include

#include

std::string schedule(std::string tasks, int gap)

{

std::deque q;

std::string result;

for (int i = 0; i < tasks.length();)

{

char c = tasks[i];

if (std::find(q.begin(), q.end(), c) == q.end())

{

q.push_back(c);

result += c;

++i;

} else {

q.push_back('_');

result += '_';

}

if (q.size() > gap) {

q.pop_front();

}

}

return result;

}

int main(int arg, char* argv[])

{

std::string s(argv[1]);
std::cout << schedule(s, 2);
return 0;
}

w*s2015-01-27 08:01

15 楼

简单来说，就是用一个queue, size为gap
每次来一个字符，检查在不在queue里，在的话输出_

h*d2015-01-27 08:01

16 楼

查找queue就O(n)了还是hash吧

★ 发自iPhone App: ChineseWeb 7.8

【在 w********s 的大作中提到】

: 简单来说，就是用一个queue, size为gap
: 每次来一个字符，检查在不在queue里，在的话输出_

c*72015-01-27 08:01

17 楼

stream的长度用n表示，task的长度用k表示，task的种类数用m表示的话，
Hash是O（m）空间，O（n）时间，Queue是O（k）空间，O（kn）时间，所以用什么
approach取决于m和k

w*82015-01-27 08:01

18 楼

是个新加坡姓Chua的HR吗？

M*y2015-01-27 08:01

19 楼

写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht

w*t2015-01-27 08:01

20 楼

赞！
好好看看先

【在 M*********y 的大作中提到】

: 写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
: 另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
: http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht

t*32015-01-27 08:01

21 楼

是的，你怎么知道的？

【在 w********8 的大作中提到】

: 是个新加坡姓Chua的HR吗？

t*a2015-01-27 08:01

22 楼

循环数组存一个pair, hashmap存char在循环数组里的index. 循环数
组里永远不会有重复元素（因为会被覆盖掉，覆盖了就到HashMap里把那个item删了）

【在 y*****e 的大作中提到】

: 不太明白。。是循环数组里存index， hashmap里存字母？

r*e2015-01-27 08:01

23 楼

int schedule(string str,int cd){
int ts = 0;
map dict;
for(int i = 0; i < str.length(); i++){
if(dict.count(str[i]) == 0 || ts-dict[str[i]] >= cd+1){
dict[str[i]] = ts;
}
else i--; ts++;
}
return ts;
}

o*c2015-01-27 08:01

24 楼

fb onsite的通过率高不高？goog貌似少于20％。LZ没争取到onsite确实可惜

t*e2015-01-27 08:01

25 楼

mark

t*32015-01-27 08:01

26 楼

国内申请的，今天早上刚电面挂了，比较郁闷，来发泄一下，然后继续努力。
去年11月在国内看到fb tech talk和招人的广告，于是就分别申请了。后来收到邀请参
加12月18日的talk，申请职位的截止日是12月15日。在快到12月15日时候，看到版上热
心内推，又特地在15号请内推了一把。18号的talk后来发现就是招人宣讲。会后跟组织
活动hr聊了一下，结果一个hr特意走上来看着我胸前label念我的名字，然后告诉我我
会被直接邀请参加今年2月份的onsite，我特意跟她确认了一下是不需要参加电面。她
还告诉我一个多星期前就知道要邀请我参加onsite，但是她们最近组织talk啥的实在太
忙了。最后这个hr还给我了如何准备onsite的建议。我激动万分啊，talk后立即恶补
system design的东西。
然后过了圣诞等到两周前，我想奇怪了，还不发正式邀请信。问了一个一起参加talk的
朋友，人家元旦刚过就收到onsite通知了，于是就发邮件问HR，没有回复。第二天收到
一个职位申请确认，然后收到一封邮件要求约个电面时间。我就奇怪了，就重复了一下
当初她告诉我的信息，结果没有回复。等了两天没有消息，我直接请fb内部朋友帮忙问
了一下。结果这个hr立即打电话给我，问我是不是误会什么了。她说可能她说把另一个
人的名字跟我搞混了，我说不可能，你是看着我的名字label念的，而且我的名字非常
不容易重复，不可能搞混的。她想想又说，对不起，她们hr是没有权利免我的电面的，
一定是什么地方误会了，她表示很抱歉，但是愿意立即帮我安排电面，以免赶不上2月
初北京的onsite。想想也没别的什么办法，就同意了，结果不幸悲剧了，题也不算难，
但是当时脑子就是转不快，followup没有做完，也许是被孩子闹的失眠惹得祸，只睡了
4个小时，唉。。。
电面题目是task scheduler，举例如下：
Tasks: AABABCD
Cooldown Time: 2
A__AB_ABCD
Output: 10
就是说同样类型的task之间至少要等2，每个task的执行时间是1
followup: 如果cooldown是个参数，也就是说有可能会很长时间，怎么修改之前的程序

c*72015-01-27 08:01

27 楼

真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
己以后肯定会有机会的。
你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
上一次index相差大于等于x

n*n2015-01-27 08:01

28 楼

唐。前面一段纯水。面试有变动很正常。

【在 t*****3 的大作中提到】

: 国内申请的，今天早上刚电面挂了，比较郁闷，来发泄一下，然后继续努力。
: 去年11月在国内看到fb tech talk和招人的广告，于是就分别申请了。后来收到邀请参
: 加12月18日的talk，申请职位的截止日是12月15日。在快到12月15日时候，看到版上热
: 心内推，又特地在15号请内推了一把。18号的talk后来发现就是招人宣讲。会后跟组织
: 活动hr聊了一下，结果一个hr特意走上来看着我胸前label念我的名字，然后告诉我我
: 会被直接邀请参加今年2月份的onsite，我特意跟她确认了一下是不需要参加电面。她
: 还告诉我一个多星期前就知道要邀请我参加onsite，但是她们最近组织talk啥的实在太
: 忙了。最后这个hr还给我了如何准备onsite的建议。我激动万分啊，talk后立即恶补
: system design的东西。
: 然后过了圣诞等到两周前，我想奇怪了，还不发正式邀请信。问了一个一起参加talk的

t*32015-01-27 08:01

29 楼

谢谢安慰。是这个思路，我已经写出来大部分了，面试官也说这个思路正确，但是说时
间到了，就让我停了。我犯的一个错误是几乎不停的解释自己每步在做什么，也可能是
不能更快速解决问题的一个原因。

【在 c*******7 的大作中提到】

: 真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
: 己以后肯定会有机会的。
: 你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
: 上一次index相差大于等于x

t*32015-01-27 08:01

30 楼

呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！

【在 n******n 的大作中提到】

: 唐。前面一段纯水。面试有变动很正常。

n*n2015-01-27 08:01

31 楼

拒几次就心静如水了，没什么大不了。
那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。

【在 t*****3 的大作中提到】

: 呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！

w*o2015-01-27 08:01

32 楼

如果可以用Java的話, 直接用LinkedHashMap來做(preserve order). Php的話就不懂了.

h*e2015-01-27 08:01

33 楼

我倒觉得用一个长度是cooldown 数值的queue 来存，如果queue里有相同的task就
push一个null进去

j*32015-01-27 08:01

34 楼

好像用个hashmap就可以了吧？边读数组边加入cool down，再搞个counter记录当时的
index，这样hash map的index也是加入cool down 之后的index了。。。

t*a2015-01-27 08:01

35 楼

直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
数组中的idx就行。

y*e2015-01-27 08:01

36 楼

不太明白。。是循环数组里存index， hashmap里存字母？

【在 t*****a 的大作中提到】

: 直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
: 数组中的idx就行。

t*32015-01-27 08:01

37 楼

不能，就是按照输入顺序一个个处理，主要是一开始cooldown只有2，所以只要简单检
查前两个tasks即可,如果cooldown变长，就得记录当前同类型task的上一次截止时间。

【在 n******n 的大作中提到】

: 拒几次就心静如水了，没什么大不了。
: 那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。

w*t2015-01-27 08:01

38 楼

题意还不是太明白：
A__AB_ABCD
cooldown是2
AB 和 AB也算是同一个类型的任务吧？
中间怎么只有一个空格呢？

w*s2015-01-27 08:01

39 楼

easy job
#include
#include
#include

#include

std::string schedule(std::string tasks, int gap)

{

std::deque q;

std::string result;

for (int i = 0; i < tasks.length();)

{

char c = tasks[i];

if (std::find(q.begin(), q.end(), c) == q.end())

{

q.push_back(c);

result += c;

++i;

} else {

q.push_back('_');

result += '_';

}

if (q.size() > gap) {

q.pop_front();

}

}

return result;

}

int main(int arg, char* argv[])

{

std::string s(argv[1]);
std::cout << schedule(s, 2);
return 0;
}

w*s2015-01-27 08:01

40 楼

简单来说，就是用一个queue, size为gap
每次来一个字符，检查在不在queue里，在的话输出_

h*d2015-01-27 08:01

41 楼

查找queue就O(n)了还是hash吧

★ 发自iPhone App: ChineseWeb 7.8

【在 w********s 的大作中提到】

: 简单来说，就是用一个queue, size为gap
: 每次来一个字符，检查在不在queue里，在的话输出_

c*72015-01-27 08:01

42 楼

stream的长度用n表示，task的长度用k表示，task的种类数用m表示的话，
Hash是O（m）空间，O（n）时间，Queue是O（k）空间，O（kn）时间，所以用什么
approach取决于m和k

w*82015-01-27 08:01

43 楼

是个新加坡姓Chua的HR吗？

M*y2015-01-27 08:01

44 楼

写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht

w*t2015-01-27 08:01

45 楼

赞！
好好看看先

【在 M*********y 的大作中提到】

: 写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
: 另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
: http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht

t*32015-01-27 08:01

46 楼

是的，你怎么知道的？

【在 w********8 的大作中提到】

: 是个新加坡姓Chua的HR吗？

t*a2015-01-27 08:01

47 楼

循环数组存一个pair, hashmap存char在循环数组里的index. 循环数
组里永远不会有重复元素（因为会被覆盖掉，覆盖了就到HashMap里把那个item删了）

【在 y*****e 的大作中提到】

: 不太明白。。是循环数组里存index， hashmap里存字母？

r*e2015-01-27 08:01

48 楼

int schedule(string str,int cd){
int ts = 0;
map dict;
for(int i = 0; i < str.length(); i++){
if(dict.count(str[i]) == 0 || ts-dict[str[i]] >= cd+1){
dict[str[i]] = ts;
}
else i--; ts++;
}
return ts;
}

o*c2015-01-27 08:01

49 楼

fb onsite的通过率高不高？goog貌似少于20％。LZ没争取到onsite确实可惜

t*e2015-01-27 08:01

50 楼

mark

a*a2015-01-27 08:01

51 楼

hashmap

j*72015-01-27 08:01

52 楼

int smallestTime(String tasks, int coolDownTime) {
int time = 0;
// assume uppercase English letters
int[] lastSeen = new int[26];
for (int i = 0; i < 26; i++) {
lastSeen[i] = -1;
}
int index = 0;
for (int i = 0; i < tasks.length(); i++) {
int last = tasks.charAt(i) - 'A';
if (lastSeen[last] != -1) {
time += Math.max(0, coolDownTime - (index - lastSeen[last] +
1 - 2));
index += Math.max(0, coolDownTime - (index - lastSeen[last]
+ 1 - 2));
}
lastSeen[last] = index++;
}
return time + tasks.length();
}