t*****3
发帖数: 112 | 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*******7
发帖数: 438 | 2 真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
己以后肯定会有机会的。
你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
上一次index相差大于等于x |
n******n
发帖数: 12088 | 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*****3
发帖数: 112 | 4 谢谢安慰。是这个思路，我已经写出来大部分了，面试官也说这个思路正确，但是说时
间到了，就让我停了。我犯的一个错误是几乎不停的解释自己每步在做什么，也可能是
不能更快速解决问题的一个原因。
【在 c*******7 的大作中提到】
: 真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
: 己以后肯定会有机会的。
: 你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
: 上一次index相差大于等于x
|
t*****3
发帖数: 112 | 5 呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！
【在 n******n 的大作中提到】
: 唐。前面一段纯水。面试有变动很正常。
|
n******n
发帖数: 12088 | 6 拒几次就心静如水了，没什么大不了。
那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。
【在 t*****3 的大作中提到】
: 呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！
|
w**********o
发帖数: 140 | 7 如果可以用Java的話, 直接用LinkedHashMap來做(preserve order). Php的話就不懂了. |
h****e
发帖数: 89 | 8 我倒觉得用一个长度是cooldown 数值的queue 来存， 如果queue里有相同的task就
push一个null进去 |
j**********3
发帖数: 3211 | 9 好像用个hashmap就可以了吧？边读数组边加入cool down，再搞个counter记录当时的
index，这样hash map的index也是加入cool down 之后的index了。。。 |
t*****a
发帖数: 106 | 10 直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
数组中的idx就行。 |
|
|
y*****e
发帖数: 712 | 11 不太明白。。是循环数组里存index， hashmap里存字母？
【在 t*****a 的大作中提到】
: 直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
: 数组中的idx就行。
|
t*****3
发帖数: 112 | 12 不能，就是按照输入顺序一个个处理，主要是一开始cooldown只有2，所以只要简单检
查前两个tasks即可,如果cooldown变长，就得记录当前同类型task的上一次截止时间。
【在 n******n 的大作中提到】
: 拒几次就心静如水了，没什么大不了。
: 那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。
|
w*****t
发帖数: 485 | 13 题意还不是太明白：
A__AB_ABCD
cooldown是2
AB 和 AB也算是同一个类型的任务吧？
中间怎么只有一个空格呢？ |
w********s
发帖数: 1570 | 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********s
发帖数: 1570 | 15 简单来说，就是用一个queue, size为gap
每次来一个字符，检查在不在queue里，在的话输出_ |
h**d
发帖数: 630 | 16 查找queue就O(n)了 还是hash吧
★ 发自iPhone App: ChineseWeb 7.8
【在 w********s 的大作中提到】
: 简单来说，就是用一个queue, size为gap
: 每次来一个字符，检查在不在queue里，在的话输出_
|
c*******7
发帖数: 438 | 17 stream的长度用n表示，task的长度用k表示，task的种类数用m表示的话，
Hash是O（m）空间，O（n）时间，Queue是O（k）空间，O（kn）时间，所以用什么
approach取决于m和k |
w********8
发帖数: 55 | |
M*********y
发帖数: 7 | 19 写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht |
w*****t
发帖数: 485 | 20 赞！
好好看看先
【在 M*********y 的大作中提到】
: 写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
: 另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
: http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht
|
|
|
t*****3
发帖数: 112 | 21 是的，你怎么知道的？
【在 w********8 的大作中提到】
: 是个新加坡姓Chua的HR吗？
|
t*****a
发帖数: 106 | 22 循环数组存一个pair, hashmap存char在循环数组里的index. 循环数
组里永远不会有重复元素（因为会被覆盖掉，覆盖了就到HashMap里把那个item删了）
【在 y*****e 的大作中提到】
: 不太明白。。是循环数组里存index， hashmap里存字母？
|
r*****e
发帖数: 30 | 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***c
发帖数: 32 | 24 fb onsite的通过率高不高？goog貌似少于20％。LZ没争取到onsite确实可惜 |
t*******e
发帖数: 274 | |
t*****3
发帖数: 112 | 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*******7
发帖数: 438 | 27 真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
己以后肯定会有机会的。
你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
上一次index相差大于等于x |
n******n
发帖数: 12088 | 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*****3
发帖数: 112 | 29 谢谢安慰。是这个思路，我已经写出来大部分了，面试官也说这个思路正确，但是说时
间到了，就让我停了。我犯的一个错误是几乎不停的解释自己每步在做什么，也可能是
不能更快速解决问题的一个原因。
【在 c*******7 的大作中提到】
: 真是可惜，不过不用太气馁，有时候找工作真的很看运气。来日方长，好好努力提升自
: 己以后肯定会有机会的。
: 你这题感觉可以用一个Hashtable来存task和index，碰到已经存在的task，检查是否和
: 上一次index相差大于等于x
|
t*****3
发帖数: 112 | 30 呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！
【在 n******n 的大作中提到】
: 唐。前面一段纯水。面试有变动很正常。
|
|
|
n******n
发帖数: 12088 | 31 拒几次就心静如水了，没什么大不了。
那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。
【在 t*****3 的大作中提到】
: 呵呵，是啊，发出的offer都能取消，我这个相比也就是小事了，谢谢开导！
|
w**********o
发帖数: 140 | 32 如果可以用Java的話, 直接用LinkedHashMap來做(preserve order). Php的話就不懂了. |
h****e
发帖数: 89 | 33 我倒觉得用一个长度是cooldown 数值的queue 来存， 如果queue里有相同的task就
push一个null进去 |
j**********3
发帖数: 3211 | 34 好像用个hashmap就可以了吧？边读数组边加入cool down，再搞个counter记录当时的
index，这样hash map的index也是加入cool down 之后的index了。。。 |
t*****a
发帖数: 106 | 35 直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
数组中的idx就行。 |
y*****e
发帖数: 712 | 36 不太明白。。是循环数组里存index， hashmap里存字母？
【在 t*****a 的大作中提到】
: 直接HashMap太浪费空间了，用一个cooldowntime+1的循环数组，然后HashMap存元素在
: 数组中的idx就行。
|
t*****3
发帖数: 112 | 37 不能，就是按照输入顺序一个个处理，主要是一开始cooldown只有2，所以只要简单检
查前两个tasks即可,如果cooldown变长，就得记录当前同类型task的上一次截止时间。
【在 n******n 的大作中提到】
: 拒几次就心静如水了，没什么大不了。
: 那个题目没说清楚啊。cool down时别的任务还能调度吗？如果不能，没办法改进。
|
w*****t
发帖数: 485 | 38 题意还不是太明白：
A__AB_ABCD
cooldown是2
AB 和 AB也算是同一个类型的任务吧？
中间怎么只有一个空格呢？ |
w********s
发帖数: 1570 | 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********s
发帖数: 1570 | 40 简单来说，就是用一个queue, size为gap
每次来一个字符，检查在不在queue里，在的话输出_ |
|
|
h**d
发帖数: 630 | 41 查找queue就O(n)了 还是hash吧
★ 发自iPhone App: ChineseWeb 7.8
【在 w********s 的大作中提到】
: 简单来说，就是用一个queue, size为gap
: 每次来一个字符，检查在不在queue里，在的话输出_
|
c*******7
发帖数: 438 | 42 stream的长度用n表示，task的长度用k表示，task的种类数用m表示的话，
Hash是O（m）空间，O（n）时间，Queue是O（k）空间，O（kn）时间，所以用什么
approach取决于m和k |
w********8
发帖数: 55 | |
M*********y
发帖数: 7 | 44 写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht |
w*****t
发帖数: 485 | 45 赞！
好好看看先
【在 M*********y 的大作中提到】
: 写了下code, 请大家多多指教哈,头顶锅盖收砖头(code and english),多谢多谢
: 另外吐槽写blog难,比code难,语言组织能力无语... 仰望blog达人
: http://elizaoncsmachine.blogspot.co.uk/2015/01/job-scheduler.ht
|
t*****3
发帖数: 112 | 46 是的，你怎么知道的？
【在 w********8 的大作中提到】
: 是个新加坡姓Chua的HR吗？
|
t*****a
发帖数: 106 | 47 循环数组存一个pair, hashmap存char在循环数组里的index. 循环数
组里永远不会有重复元素（因为会被覆盖掉，覆盖了就到HashMap里把那个item删了）
【在 y*****e 的大作中提到】
: 不太明白。。是循环数组里存index， hashmap里存字母？
|
r*****e
发帖数: 30 | 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***c
发帖数: 32 | 49 fb onsite的通过率高不高？goog貌似少于20％。LZ没争取到onsite确实可惜 |
t*******e
发帖数: 274 | |
|
|
a*******a
发帖数: 383 | |
j**7
发帖数: 143 | 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();
} |
