fb电面面经 print interval

发信人: pdu (PigDuckUnited), 信区: JobHunting
标  题: fb电面面经
发信站: BBS 未名空间站 (Thu Oct 17 20:02:42 2013, 美东)

给一堆用户的登陆日志，要求输出各时间段内的在线用户数。

例子：
user1:
login_time: 0
logout_time: 1

user2:
login_time: 0
logout_time: 2

user3:
login_time: 1
logout_time: 3

输出：
[0 - 2): 2
[2 - 3): 1
[3 - infinite): 0

0 - 1不用输出，因为时间点0有2个在线用户，时间点1也有2个在线用户，在线用户数
没有变，所以不用输出。在时间点2在线用户数变为1，所以输出0 - 2: 2

完成函数：
struct Log
{
  float login_time;
  float logout_time;
};
void online_user(vector<Log> &logs);

=====
刚开始是一些behavior question，后来就问了这一个题，算法2分钟就沟通好了，可是
后来代码写得很乱，到最后都还有bug
华人面试官，感觉人挺好的。可惜自己脑抽了，一紧张就出错，一出错更紧张，最后就
搞不定了
最后他建议在面fb之前，先找其他公司的面试，练练状态

这种情况挂了只能怪自己，不能埋怨同胞不留情。move on to next

-----
更新下：刚收到thank you letter @2013-10-29


发信人: pepero (迅哥儿，你忘了那...), 信区: JobHunting
标  题: Re: fb电面面经
发信站: BBS 未名空间站 (Sat Oct 19 09:24:04 2013, 美东)

void online_user(vector<Log> &logs){
    if (logs.empty()) return;
    map<float, int> table;
    for (vector<Log>::const_iterator it = logs.begin();
            it != logs.end(); ++it){
        table[it->login_time]++;
        table[it->logout_time]--;
    }

    float prev = table.begin()->first;
    int num = table.begin()->second;

    for (map<float, int>::const_iterator it = ++table.begin();
    it!=table.end(); ++it) {
        if (it->second!=0) {
            cout << "[" << prev << " - " << it->first << ") : " << num <<
endl;
            num += it->second;
            prev = it->first;
       }
    }
    cout << "[" << prev << " - " << "infinite) : 0 " << endl;
}

facebook面经 interval problem

 determine the minimum number of meeting rooms needed to hold all the
meetings.
Input array(pair(1, 4), pair(2,3), pair(3,4), pair(4,5))
 Output: 2


Ans:

treat each start and end time as a point, sort the points,
now process each point in order,
if hit a start time, cnt ++
if hit an end time, cnt --

the max of cnt in the process is the number of meeting rooms needed.

there is one catch
这个解法有个注意事项，如果interval 1的start time 和interval 2 的end time相等
，应该把 interval 2的 end time排在前面

不然像（２，　３），(3, 4)这样的可能返回2，实际应该返回1.


The following is a wrong dp solution:
 按pair.first sort,
f[i]为从第0个到第i个时间段需要的最小房间数
那么if(pair[i].first>=pair[i-1].second) f[i]=f[i-1]
else f[i]=f[i-1]+1

counterexample:（1，3）（2，6），（4，5）
 the result of the algo is 3, but the correct answer is 2

Insert Interval

idea: do it in a natural way.

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    vector<Interval> ret;
    int cur=0;
    int n= intervals.size();
    while(cur<n&&newInterval.start>intervals[cur].end)
        ret.push_back(intervals[cur++]);
    while(cur<n&&newInterval.end>=intervals[cur].start)
    {
        newInterval.start=min(newInterval.start,intervals[cur].start);
        newInterval.end=max(newInterval.end,intervals[cur].end);
        cur++;
    }
    ret.push_back(newInterval);
    while(cur<n)
        ret.push_back(intervals[cur++]);

    return ret;
}

Merge Intervals

 idea: sort by the first dimension and then do it in a natural way.


bool operator<(const Interval &v1, const Interval &v2) { return v1.start < v2.start; }
class Solution {
public:

vector<Interval> merge(vector<Interval> &intervals) {
    vector<Interval> cc;
    sort(intervals.begin(), intervals.end());
    int n = intervals.size();
    int i = 0;
    while(i < n) {
        cc.push_back(intervals[i++]);
        while(i < n && intervals[i].start <= cc.back().end)
            cc.back().end = max(cc.back().end, intervals[i++].end);
    }
    return cc;
}