Facebook Additional Phone Interview

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： 已挂

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. 
    
14. class Solution {
    
15. public:
    
16.     vector<string> statistics(const vector<Employee> &employees) {
    
17.         // base case
    
18.         vector<string> result;
    
19.         if (employees.empty()) return result;
    
20.         
    
21.         // sort
    
22.         vector<TimeNode> times;
    
23.         for (const auto employee : employees) {
    
24.             times.push_back(TimeNode(employee.startTime, true));
    
25.             times.push_back(TimeNode(employee.endTime, false));
    
26.         }
    
27.         sort(times.begin(), times.end());
    
28.         
    
29.         // scan
    
30.         int i = 1, count = 1, begin = 0;
    
31.         while (i < times.size()) {
    
32.             if (times[i].time != times[i - 1].time) {
    
33.                 result.push_back(make_statistics(times[begin].time, times[i].time, count));
    
34.                 begin = i;
    
35.             }
    
36. 
    
37.             count += times[i].start? 1: -1;
    
38.             i++;
    
39.         }
    
40.         
    
41.         return result;
    
42.     }
    
43.    
    
44.     string make_statistics(int start, int end, int count) {
    
45.         return to_string(start) + "->" + to_string(end) + ": " + to_string(count);
    
46.     }   
    
47. };
    
48. 
    
49. int main(int argc, const char * argv[]) {
    
50.     vector<Employee> employees;
    
51.     employees.push_back(Employee(4, 2004, 2015));
    
52.     employees.push_back(Employee(7, 2011, 2015));
    
53.     employees.push_back(Employee(9, 2004, 2009));
    
54.     employees.push_back(Employee(11, 2007, 2008));
    
55.     employees.push_back(Employee(12, 2008, 2014));
    
56.     employees.push_back(Employee(15, 2013, 2014));
    
57. 
    
58.     for (const auto str : Solution().statistics(employees)) {
    
59.         cout << str << endl;
    
60.     }
    
61.    
    
62.     return 0;
    
63. }

复制代码

先排序，然后再扫一遍，感觉代码写的很冗余。

1. 
   
2. struct CompareStart
   
3. {
   
4.     bool operator() (const Employee &a, const Employee &b){
   
5.         return a.startTime < b.startTime;
   
6.     }
   
7. };
   
8. 
   
9. struct CompareEnd
   
10. {
    
11.     bool operator() (const Employee &a, const Employee &b){
    
12.         return a.endTime < b.endTime;
    
13.     }
    
14. };
    
15. 
    
16. void PrintEmployeeWorkTime(vector<Employee> start_staff){
    
17.     int num_em = start_staff.size();
    
18.     if (num_em == 0) return;
    
19.     vector<Employee> end_staff(start_staff);
    
20.     sort(start_staff.begin(), start_staff.end(), CompareStart());
    
21.     sort(end_staff.begin(), end_staff.end(), CompareEnd());
    
22.     int idx_st = 1, idx_end = 0, count = 1, timestamp = start_staff[0].startTime;
    
23.     int cur_st, cur_end;
    
24.     while (start_staff[0].startTime == start_staff[idx_st].startTime) {idx_st++;count++;}
    
25. 
    
26.     while (idx_st < num_em || idx_end < num_em){
    
27.         cur_st = start_staff[idx_st].startTime;
    
28.         cur_end = end_staff[idx_end].endTime;
    
29.         cout << timestamp << "-" << min(cur_st,cur_end) << ":\t" << count << endl;
    
30.         if (cur_st <= cur_end){
    
31.             count++;
    
32.             idx_st++;
    
33.             while (idx_st < num_em && cur_st == start_staff[idx_st].startTime) {idx_st++;count++;}
    
34.             timestamp = cur_st;
    
35.         }
    
36.         if (cur_st >= cur_end){
    
37.             count--;
    
38.             idx_end++;
    
39.             while (idx_end < num_em && cur_end == end_staff[idx_end].endTime) {idx_end++;count--;}
    
40.             timestamp = cur_end;
    
41.         }
    
42.     }
    
43. }
    

复制代码

这道题感觉不用排序的啊

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. 
   
10.                 int[] timeSlots = new int[r-l+1];
    
11.                 boolean[] delimiters = new boolean[r-l+1];
    
12.                 for(Employee e : employees){
    
13.                         timeSlots[e.startTime-l]++;
    
14.                         timeSlots[e.endTime-l]--;
    
15.                         delimiters[e.startTime-l] = true;
    
16.                         delimiters[e.endTime-l] = true;
    
17.                 }
    
18. 
    
19.                 int count = timeSlots[0];
    
20.                 int preStart = 0;
    
21.                 for(int i = 1; i < timeSlots.length; i++){
    
22.                         if(delimiters[i] == false) continue;
    
23.                         System.out.println((preStart+l) + "-" + (i+l) + ": " + count);
    
24.                         count += timeSlots[i];
    
25.                         preStart = i;
    
26.                 }
    
27.         }

复制代码

欢迎指正～

楼主不要灰心，会有更好的offer的！
不过这个题我没看懂啊？是说每个员工有不同的起始和终止时间，给一个时间段，output这个时间段内在职的员工ID吗？这个暴力解就可以啊，是面试官说一定要用segment tree？

不要放弃, 也许是offer

看不懂啊。  。  。

chaorenkuaile 发表于 2014-11-18 08:05
楼主不要灰心，会有更好的offer的！
不过这个题我没看懂啊？是说每个员工有不同的起始和终止时间，给一个 ...

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

yzl232 发表于 2014-11-18 08:14
看不懂啊。  。  。

see first floor

weiqitoby600 发表于 2014-11-18 08:13
不要放弃, 也许是offer

lz没写完 已死

没写完也可能是offer啊，LZ看起来这么流逼的赶脚！

论坛匿名用户 发表于 2014-11-18 08:17
lz没写完 已死

依然祝愿楼主拿到offer!

楼主一定有大offer等你呢
能再解释一下这个input什么意思嘛？ (......................) 代表什么啊？