回复: 27
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook Additional Phone Interview

🔗
匿名用户-VVM0T  2014-11-18 07:51:28 |倒序浏览

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
input:
04: (......................)
07:              (.........)
09: (........)
11:     (..)
12
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
希望大家都能拿到想要的offer



补充内容 (2014-11-28 04:47):
update: 已挂

上一篇:无波尔 phone
下一篇:Dropbox OA & 第一轮电面
推荐
jarfield 2015-10-7 22:53:16 | 只看该作者
全局:
  1. class TimeNode {
  2. public:
  3.     int time;
  4.     bool start;
  5.    
  6. public:
  7.     TimeNode(int time, bool start) : time(time), start(start) {}
  8.    
  9.     bool operator < (const TimeNode &t) const {
  10.         return this->time < t.time;
  11.     }
  12. };

  13. class Solution {
  14. public:
  15.     vector<string> statistics(const vector<Employee> &employees) {
  16.         // base case
  17.         vector<string> result;
  18.         if (employees.empty()) return result;
  19.         
  20.         // sort
  21.         vector<TimeNode> times;
  22.         for (const auto employee : employees) {
  23.             times.push_back(TimeNode(employee.startTime, true));
  24.             times.push_back(TimeNode(employee.endTime, false));
  25.         }
  26.         sort(times.begin(), times.end());
  27.         
  28.         // scan
  29.         int i = 1, count = 1, begin = 0;
  30.         while (i < times.size()) {
  31.             if (times[i].time != times[i - 1].time) {
  32.                 result.push_back(make_statistics(times[begin].time, times[i].time, count));
  33.                 begin = i;
  34.             }

  35.             count += times[i].start? 1: -1;
  36.             i++;
  37.         }
  38.         
  39.         return result;
  40.     }
  41.    
  42.     string make_statistics(int start, int end, int count) {
  43.         return to_string(start) + "->" + to_string(end) + ": " + to_string(count);
  44.     }   
  45. };

  46. int main(int argc, const char * argv[]) {
  47.     vector<Employee> employees;
  48.     employees.push_back(Employee(4, 2004, 2015));
  49.     employees.push_back(Employee(7, 2011, 2015));
  50.     employees.push_back(Employee(9, 2004, 2009));
  51.     employees.push_back(Employee(11, 2007, 2008));
  52.     employees.push_back(Employee(12, 2008, 2014));
  53.     employees.push_back(Employee(15, 2013, 2014));

  54.     for (const auto str : Solution().statistics(employees)) {
  55.         cout << str << endl;
  56.     }
  57.    
  58.     return 0;
  59. }
复制代码
回复

使用道具 举报

推荐
sweeney1130 2014-11-19 03:53:11 | 只看该作者
全局:
先排序,然后再扫一遍,感觉代码写的很冗余。

  1. struct CompareStart
  2. {
  3.     bool operator() (const Employee &a, const Employee &b){
  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.     }
  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;
  20.     int cur_st, cur_end;
  21.     while (start_staff[0].startTime == start_staff[idx_st].startTime) {idx_st++;count++;}

  22.     while (idx_st < num_em || idx_end < num_em){
  23.         cur_st = start_staff[idx_st].startTime;
  24.         cur_end = end_staff[idx_end].endTime;
  25.         cout << timestamp << "-" << min(cur_st,cur_end) << ":\t" << count << endl;
  26.         if (cur_st <= cur_end){
  27.             count++;
  28.             idx_st++;
  29.             while (idx_st < num_em && cur_st == start_staff[idx_st].startTime) {idx_st++;count++;}
  30.             timestamp = cur_st;
  31.         }
  32.         if (cur_st >= cur_end){
  33.             count--;
  34.             idx_end++;
  35.             while (idx_end < num_em && cur_end == end_staff[idx_end].endTime) {idx_end++;count--;}
  36.             timestamp = cur_end;
  37.         }
  38.     }
  39. }
复制代码
回复

使用道具 举报

推荐
中庸人90 2014-11-19 09:45:59 | 只看该作者
全局:
这道题感觉不用排序的啊
  1. public void printIntervals(Employee[] employees){
  2.                 // the whole range from l ~ r
  3.                 int l = employees[0].startTime;
  4.                 int r = employees[0].endTime;
  5.                 for(Employee e : employees){
  6.                         l = Math.min(l, e.startTime);
  7.                         r = Math.max(r, e.endTime);
  8.                 }

  9.                 int[] timeSlots = new int[r-l+1];
  10.                 boolean[] delimiters = new boolean[r-l+1];
  11.                 for(Employee e : employees){
  12.                         timeSlots[e.startTime-l]++;
  13.                         timeSlots[e.endTime-l]--;
  14.                         delimiters[e.startTime-l] = true;
  15.                         delimiters[e.endTime-l] = true;
  16.                 }

  17.                 int count = timeSlots[0];
  18.                 int preStart = 0;
  19.                 for(int i = 1; i < timeSlots.length; i++){
  20.                         if(delimiters[i] == false) continue;
  21.                         System.out.println((preStart+l) + "-" + (i+l) + ": " + count);
  22.                         count += timeSlots[i];
  23.                         preStart = i;
  24.                 }
  25.         }
复制代码
欢迎指正~
回复

使用道具 举报

🔗
chaorenkuaile 2014-11-18 08:05:00 | 只看该作者
全局:
楼主不要灰心,会有更好的offer的!
不过这个题我没看懂啊?是说每个员工有不同的起始和终止时间,给一个时间段,output这个时间段内在职的员工ID吗?这个暴力解就可以啊,是面试官说一定要用segment tree?

评分

参与人数 1大米 +1 收起 理由
austurela + 1 Output is all the times together

查看全部评分

回复

使用道具 举报

🔗
weiqitoby600 2014-11-18 08:13:31 | 只看该作者
全局:
不要放弃, 也许是offer
回复

使用道具 举报

🔗
yzl232 2014-11-18 08:14:26 | 只看该作者
全局:
看不懂啊。  。  。
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-VVM0T  2014-11-18 08:15:47
chaorenkuaile 发表于 2014-11-18 08:05
楼主不要灰心,会有更好的offer的!
不过这个题我没看懂啊?是说每个员工有不同的起始和终止时间,给一个 ...

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

使用道具 举报

地里匿名用户
🔗
匿名用户-VVM0T  2014-11-18 08:16:10
yzl232 发表于 2014-11-18 08:14
看不懂啊。  。  。

see first floor
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-VVM0T  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什么意思嘛? (......................) 代表什么啊?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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