一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2103|回复: 27
收起左侧

[找工就业] Facebook Additional Phone Interview

[复制链接] |试试Instant~ |关注本帖
austurela 发表于 2014-11-18 07:51:28 | 显示全部楼层 |阅读模式

2016(10-12月)-[12]CS本科+fresh grad 无实习/全职 - 校园招聘会| 码农类实习@Facebook

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
input:
04: (......................)
07:              (.........)
09: (........)
11:     (..)
12:        (............)
15:                  (..)

struct Employee {
i64 id,
i64 startTime,
i64 endTime
};

output:
2004-2007: 2 // 4,9
2007-2008: 3 // 4,9,11
2008-2009: 3 // 4,9,12
2009-2011: 2
2011-2013: 3. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2013-2014: 4
2014-2015: 2

lz知道这题用segment tree,但从来没研究过怎么用segment tree,lz当场也没办法啊。。。lz已挂,正在流泪,希望大家都能拿到想要的offer



补充内容 (2014-11-28 04:47):
update: 已挂
chaorenkuaile 发表于 2014-11-18 08:05:00 | 显示全部楼层
楼主不要灰心,会有更好的offer的!. more info on 1point3acres.com
不过这个题我没看懂啊?是说每个员工有不同的起始和终止时间,给一个时间段,output这个时间段内在职的员工ID吗?这个暴力解就可以啊,是面试官说一定要用segment tree?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

weiqitoby600 发表于 2014-11-18 08:13:31 | 显示全部楼层
不要放弃, 也许是offer
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-11-18 08:14:26 | 显示全部楼层
看不懂啊。  。  。
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-18 08:15:47 | 显示全部楼层
chaorenkuaile 发表于 2014-11-18 08:05
楼主不要灰心,会有更好的offer的!.鏈枃鍘熷垱鑷1point3acres璁哄潧
不过这个题我没看懂啊?是说每个员工有不同的起始和终止时间,给一个 ...

理解的对,但要output所有区间。要求nlogn,猜是segment tree吧,求讨论
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-18 08:16:10 | 显示全部楼层
yzl232 发表于 2014-11-18 08:14
看不懂啊。  。  。

see first floor
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-18 08:17:58 | 显示全部楼层
weiqitoby600 发表于 2014-11-18 08:13
不要放弃, 也许是offer

lz没写完 已死
回复 支持 反对

使用道具 举报

tbu 发表于 2014-11-18 08:26:01 | 显示全部楼层
没写完也可能是offer啊,LZ看起来这么流逼的赶脚!
回复 支持 反对

使用道具 举报

weiqitoby600 发表于 2014-11-18 08:41:13 | 显示全部楼层

依然祝愿楼主拿到offer!
回复 支持 反对

使用道具 举报

xiaoyin_2013 发表于 2014-11-18 09:02:08 | 显示全部楼层
楼主一定有大offer等你呢
能再解释一下这个input什么意思嘛? (......................) 代表什么啊?
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-18 09:02:37 | 显示全部楼层
感觉把start time和end time拆开来,排个序就好了吧。。start time权值为1,end time权值-1
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-18 09:04:51 | 显示全部楼层
1guangnian 发表于 2014-11-18 09:02. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感觉把start time和end time拆开来,排个序就好了吧。。start time权值为1,end time权值-1

This is my final answer...but lz did not finish....crycrycry
回复 支持 反对

使用道具 举报

pazzaintermilan 发表于 2014-11-18 09:07:02 | 显示全部楼层
为什么lz的实习面都这么难。。。其他全职的onsite都很多原题的感觉。。。
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-11-18 09:09:23 | 显示全部楼层
austurela 发表于 2014-11-18 09:04
This is my final answer...but lz did not finish....crycrycry

pat pat...
回复 支持 反对

使用道具 举报

yvetterowe 发表于 2014-11-18 09:10:40 | 显示全部楼层
。。。我几个月前面G家intern转正也问的这道题。。。当时也没想好怎么做。。。也栽了T T. 1point3acres.com/bbs
这道题可以从左往右扫描时间线。全局维护一个count,如果扫到的时间是start time,就输出当前count以后++count。如果扫到的是end time,就输出count以后--count。. 1point3acres.com/bbs
排序时间线用O(nlgn),扫一遍O(n)。。

补充内容 (2014-11-18 09:12):
囧 没看到LZ的final answer也是这个做法= =。。pat pat lz...
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-18 09:14:35 | 显示全部楼层
pazzaintermilan 发表于 2014-11-18 09:07
为什么lz的实习面都这么难。。。其他全职的onsite都很多原题的感觉。。。

fate               
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-11-18 10:25:46 | 显示全部楼层
不用急, intern 的 bar并不高。
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-18 10:29:42 | 显示全部楼层
北美农民 发表于 2014-11-18 10:25
不用急, intern 的 bar并不高。

请烧纸                  
回复 支持 反对

使用道具 举报

中庸人90 发表于 2014-11-18 14:09:19 | 显示全部楼层
求问大神,如何用segement tree做,插入的时候当某个区间往下递归的时候跨了几个区间,怎么标记以及查询的时候怎么回收统计的值?或者别的思路??
回复 支持 反对

使用道具 举报

sweeney1130 发表于 2014-11-19 03:53:11 | 显示全部楼层
先排序,然后再扫一遍,感觉代码写的很冗余。

  1. struct CompareStart
  2. {
  3.     bool operator() (const Employee &a, const Employee &b){-google 1point3acres
  4.         return a.startTime < b.startTime;
  5.     }
  6. };

  7. struct CompareEnd
  8. {
  9.     bool operator() (const Employee &a, const Employee &b){
  10.         return a.endTime < b.endTime;
  11.     }
    .1point3acres缃
  12. };

  13. void PrintEmployeeWorkTime(vector<Employee> start_staff){
  14.     int num_em = start_staff.size();
  15.     if (num_em == 0) return; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.     vector<Employee> end_staff(start_staff);
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.     sort(start_staff.begin(), start_staff.end(), CompareStart());
  18.     sort(end_staff.begin(), end_staff.end(), CompareEnd());
  19.     int idx_st = 1, idx_end = 0, count = 1, timestamp = start_staff[0].startTime;. visit 1point3acres.com for more.
  20.     int cur_st, cur_end;
  21.     while (start_staff[0].startTime == start_staff[idx_st].startTime) {idx_st++;count++;}
  22. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.     while (idx_st < num_em || idx_end < num_em){
  24.         cur_st = start_staff[idx_st].startTime;
  25.         cur_end = end_staff[idx_end].endTime;
  26.         cout << timestamp << "-" << min(cur_st,cur_end) << ":\t" << count << endl;
  27.         if (cur_st <= cur_end){. 1point3acres.com/bbs
  28.             count++;
  29.             idx_st++;
  30.             while (idx_st < num_em && cur_st == start_staff[idx_st].startTime) {idx_st++;count++;}
  31.             timestamp = cur_st;
  32.         }
  33.         if (cur_st >= cur_end){
  34.             count--;
  35.             idx_end++;
  36.             while (idx_end < num_em && cur_end == end_staff[idx_end].endTime) {idx_end++;count--;}
  37.             timestamp = cur_end;
  38.         }. from: 1point3acres.com/bbs
  39.     }
  40. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表