猫捉回来一条蛇（怕蛇的mm慎入） (转载) - 未名空间MITBBS历史存档

猫捉回来一条蛇（怕蛇的mm慎入） (转载)# PhotoGear - 摄影器材

b*i2011-05-22 07:05

1 楼

首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
，最后的时间提问。
1. 一来就是一道简单题，翻转链表
// Reverse a Singly Linked List
// Example Input: A -> B -> C
// Example Output: C -> B -> A
他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部
分，所以很快就写完了。
2.第二题直接copy 题目，感觉跟leetcode上面的interval那题很相似，简单一点点。
// Given a array of pairs where each pair contains the start and end time of
a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False
同样的思路+复杂度。同样是变种题，还变简单了，很快写完。（主要是考比较器的
override吧）
3. follow up第二题
// 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
我看表还剩下10分钟，然后想了3min钟，面试官就说没时间了，要不你说说思路。然后
说了一下思路，面试官说OK。让我提问题。瞎问了一个问题。面试官还特别详细的解答
了。他说超了一点时，不过没关系。然后互相感谢了一下，客套了一下。就再见了。
第二天HR说下一轮Onsite了。
最后求大家祝福，希望能onsite好运~~ 祝大家都能拿到心仪的offer~

L*k2011-05-22 07:05

2 楼

【以下文字转载自 pets 讨论区】
发信人: icytide (小新但不是蜡笔的), 信区: pets
标题: 猫捉回来一条蛇（怕蛇的mm慎入）
发信站: BBS 未名空间站 (Fri May 20 16:04:38 2011, 美东)
灰猫一早就在嚎叫，要多难听有多难听，闹着要出去。没办法，上了点revolution就打
开院子门让他出去了。没一会儿，又听见他嚎叫，吵着要进来。没办法，打开门让他进
来。以为这位爷吃饱了会睡个午觉，结果他又闹着要出去。“来来回回的，你走城门啊
？”
一劳永逸，我把门儿开个小缝，你爱进来就进来，爱出去就出去，出出进进的没人管你。
过了一会儿，我去楼下倒水。就看见一个灰猫华丽丽的叼着一条扭动的绳子进来了。我
的嘴巴张大成"O"形，请参考youtube上的OMG cat。
这猫把蛇放在地上，可怜的小蛇儿蜷成一团。乍一看像一坨便便。便便里伸出一个头，
时不时吐个黑色的信子。灰猫满意的坐下来，伸个爪子拨拨，再拨拨。小蛇鼓起勇气，
抬起半截身子做攻击状。灰猫才不怕，爪子一挥一个嘴巴就扇过去了。小蛇于是想跑在
地上滑动想钻进沙发缝隙里去。都进去3/4了，硬是被两猫活活拽了出来。
到这个份上，我不能不主持一下公道。上去看看，是条草蛇，无毒的。捏起三寸，
拍照留个纪念，放出去了。好在老公不在家，要是他在家，可能会吓晕过去。
下面是照片。第一张照片照得很吓人。别害怕其实是条小蛇儿。

Y*o2011-05-22 07:05

3 楼

Bless! 祝早日拿到offer

c*s2011-05-22 07:05

4 楼

猫咪可爱哇

r*e2011-05-22 07:05

5 楼

new grad 么？硕士or PhD

x*02011-05-22 07:05

6 楼

前两天有人奔球蟒吞鼠，不知道球蟒和猫单挑结果会如何。

l*42011-05-22 07:05

7 楼

感谢分享

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

X*U2011-05-22 07:05

8 楼

让嘟嘟默默去试试

【在 x**0 的大作中提到】

: 前两天有人奔球蟒吞鼠，不知道球蟒和猫单挑结果会如何。

h*d2011-05-22 07:05

9 楼

谢谢面经！
第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
.first 如果不是 return false应该就行了
第三题得用dp
还是先按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

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

S*M2011-05-22 07:05

10 楼

这猫妈很猛

你。

【在 L*****k 的大作中提到】

: 【以下文字转载自 pets 讨论区】
: 发信人: icytide (小新但不是蜡笔的), 信区: pets
: 标题: 猫捉回来一条蛇（怕蛇的mm慎入）
: 发信站: BBS 未名空间站 (Fri May 20 16:04:38 2011, 美东)
: 灰猫一早就在嚎叫，要多难听有多难听，闹着要出去。没办法，上了点revolution就打
: 开院子门让他出去了。没一会儿，又听见他嚎叫，吵着要进来。没办法，打开门让他进
: 来。以为这位爷吃饱了会睡个午觉，结果他又闹着要出去。“来来回回的，你走城门啊
: ？”
: 一劳永逸，我把门儿开个小缝，你爱进来就进来，爱出去就出去，出出进进的没人管你。
: 过了一会儿，我去楼下倒水。就看见一个灰猫华丽丽的叼着一条扭动的绳子进来了。我

r*e2011-05-22 07:05

11 楼

用dp怎么做？能给出公式么？我感觉不是那么容易，不如divide conquer

1]

【在 h**d 的大作中提到】

: 谢谢面经！
: 第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
: .first 如果不是 return false应该就行了
: 第三题得用dp
: 还是先按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
:
: coding

k*t2011-05-22 07:05

12 楼

上次俺家的猫活捉回来一头兔子.

r*e2011-05-22 07:05

13 楼

这个不行
举例
（1，3）（2，6），（4，5）
你的算法结果是3，肉眼判断结果是2.

1]

【在 h**d 的大作中提到】

: 谢谢面经！
: 第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
: .first 如果不是 return false应该就行了
: 第三题得用dp
: 还是先按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
:
: coding

s*s2011-05-22 07:05

14 楼

强……

【在 k****t 的大作中提到】

: 上次俺家的猫活捉回来一头兔子.

s*p2011-05-22 07:05

15 楼

那个最小会议室的这样行吗？先按开始时间和结束时间排序，然后逐个对比，有点类似
merge sort 的merge 阶段。
public class Solution {
public int numOverLaps(List start, List end) {
if (start == null || start.size() == 0 || end == null || end.size()
== 0) {
return 0;
}

if (start.size() != end.size()) {
return 0;
}

Collections.sort(start);
Collections.sort(end);

int startP = 0;
int endP = 0;

int numActive = 0;
int numOverlap = 0;

while (startP < start.size() && endP < end.size()) {
if (start.get(startP) < end.get(endP)) {
numActive++;
numOverlap = Math.max(numOverlap, numActive);
startP++;
} else {
numActive--;
endP++;
}
}
return numOverlap;
}
public static void main(String[] args) {
Solution sol = new Solution();
List start = new ArrayList();
List end = new ArrayList();
start.add(1);
start.add(2);
start.add(5);
start.add(4);
end.add(3);
end.add(4);
end.add(6);
end.add(7);
int result = sol.numOverLaps(start, end);
System.out.println("Result is " + result);
}
}

c*s2011-05-22 07:05

16 楼

以前国内邻居养的泰国猫，时不时的抓鸟当早餐。不过最近刚去世，邻居妈和她非常
hot的女儿哭个半死

s*p2011-05-22 07:05

17 楼

实际上DP 是这个题，
Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum.
一直不知道怎么解，搭车问一下哈

x*02011-05-22 07:05

18 楼

你确定你家养的不是老虎或者豹子啥的？

【在 k****t 的大作中提到】

: 上次俺家的猫活捉回来一头兔子.

l*i2011-05-22 07:05

19 楼

prob 2:
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.

x*02011-05-22 07:05

20 楼

恩，关键词是"非常hot的女儿"

【在 c******s 的大作中提到】

: 以前国内邻居养的泰国猫，时不时的抓鸟当早餐。不过最近刚去世，邻居妈和她非常
: hot的女儿哭个半死

h*d2011-05-22 07:05

21 楼

有大牛在另一个帖子里给出答案了
摘录：
所有时间排序到一起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是
解。

)

【在 s*********p 的大作中提到】

: 那个最小会议室的这样行吗？先按开始时间和结束时间排序，然后逐个对比，有点类似
: merge sort 的merge 阶段。
: public class Solution {
: public int numOverLaps(List start, List end) {
: if (start == null || start.size() == 0 || end == null || end.size()
: == 0) {
: return 0;
: }
:
: if (start.size() != end.size()) {

a*e2011-05-22 07:05

22 楼

你是不是也准备抓鸟当早餐了？

【在 c******s 的大作中提到】

: 以前国内邻居养的泰国猫，时不时的抓鸟当早餐。不过最近刚去世，邻居妈和她非常
: hot的女儿哭个半死

m*12011-05-22 07:05

23 楼

mark

x*72011-05-22 07:05

24 楼

“好在老公不在家，要是他在家，可能会吓晕过去。”
haha

x*j2011-05-22 07:05

25 楼

同搭车问

【在 s*********p 的大作中提到】

: 实际上DP 是这个题，
: Given a set of n jobs with [start time, end time, cost] find a subset so
: that no 2 jobs overlap and the cost is maximum.
: 一直不知道怎么解，搭车问一下哈

a*s2011-05-22 07:05

26 楼

我记得外婆说面条喂大的猫咪喜欢捉蛇，所以小时候不让我喂面条给猫咪。

y*22011-05-22 07:05

27 楼

第二题能解释一下解法吗
/ Given a array of pairs where each pair contains the start and end time of
a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False
另外，另外允许部分conflict吗？如果是(1, 4) (3, 5) ，是return False吗？

s*i2011-05-22 07:05

28 楼

第二题有没有可能O(n)？

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

C*M2011-05-22 07:05

29 楼

怎么觉得应该按照end time 排序，然后看interval.end[i]和interval.end[i-1] 有没
有overlapping，每重叠一次add一个room

l*42011-05-22 07:05

30 楼

第二题前面有人说了啊
“第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+
1]
.first 如果不是 return false应该就行了”

of

【在 y****2 的大作中提到】

: 第二题能解释一下解法吗
: / Given a array of pairs where each pair contains the start and end time of
: a meeting (as in int),
: // Determine if a single person can attend all the meetings
: // Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
: // Output: False
: 另外，另外允许部分conflict吗？如果是(1, 4) (3, 5) ，是return False吗？

M*l2011-05-22 07:05

31 楼

谢谢楼主分享！

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

z*b2011-05-22 07:05

32 楼

这个解法有个注意事项，如果interval 1的start time 和interval 2 的end time相等
，应该把 interval 2的 end time排在前面（ｉｎｃｒｅａｓｉｎｇ　ｏｒｄｅｒ）
不然像（２，　３），(3, 4)这样的可能返回2，实际应该返回1.

【在 l***i 的大作中提到】

: prob 2:
: 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.

b*i2011-05-22 07:05

33 楼

恩是的 MS new grad

【在 r*******e 的大作中提到】

: new grad 么？硕士or PhD

b*i2011-05-22 07:05

34 楼

HI
我觉得你第二题不大对哈
比如（1,2）（1,3）（2,4）（2,5）（3,7）

1]

【在 h**d 的大作中提到】

: 谢谢面经！
: 第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
: .first 如果不是 return false应该就行了
: 第三题得用dp
: 还是先按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
:
: coding

d*m2011-05-22 07:05

35 楼

多谢OP！！
Bless！

L*p2011-05-22 07:05

36 楼

没看懂，求贴？

【在 h**d 的大作中提到】

: 有大牛在另一个帖子里给出答案了
: 摘录：
: 所有时间排序到一起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是
: 解。
:
: )

h*02011-05-22 07:05

37 楼

为什么不对？展开来说说？

【在 b**********i 的大作中提到】

: HI
: 我觉得你第二题不大对哈
: 比如（1,2）（1,3）（2,4）（2,5）（3,7）
:
: 1]

w*n2011-05-22 07:05

38 楼

不错

m*a2011-05-22 07:05

39 楼

第三题
brute force 解法N R*ln(R) R meeting room number
#include
#include
using namespace std;
struct Interval{
int start;
int end;
};
bool comp(Interval a, Interval b){
return a.start}
class Solution{
public:
int meetingSchedule(vector interval){
sort(interval.begin(),interval.end(),comp);
vector rooms;
if (!interval.empty()){
rooms.push_back(interval[0].end);
}
for (int i=1;iint merged=false;
sort(rooms.begin(),rooms.end());
for (int j=rooms.size()-1;j>=0;j--){
if (interval[i].start>=rooms[j]) {
rooms[j]=interval[i].end;
merged=true;
break;
}
}
if (!merged){
rooms.push_back(interval[i].end);
}
}
return rooms.size();
}
};
int main()
{
vector interval={{2,3},{1,4},{3,4},{4, 5}};
vector interval2={{1,3},{2,6},{4, 5}};
vector interval3={{1,2},{1,3},{2,4},{2,5},{3, 7}};
Solution test;
cout<cout<cout<return 0;
}
返回 2，2，3

h*s2011-05-22 07:05

40 楼

第三题能不能这样解：
Brute force：假设时间每流动一个单位，就更新一下所有meeting和room的状态。
Optimization：我们发现时间可以流动的快一些，每次流动的单位数基于当前马上就要
结束的meeting和下一个马上就开始的meeting，算法如下:
1. 按start time排序
2. Go over the sorted list.
3. keep a minimum heap based on the end time.
4. the heap size is the needed number of room at any time.
TO(nlogn): for sorting and keeping heap.
SO(n): for the heap and maybe some sorting algorithm.
// heap is based on interval.endTime
int max = 0;
for ( Interval meeting : Sorted_List )
{
while ( true )
{
if ( heap.size() > 0 )
{
Interval meeting2 = heap.peek(); // first meeting to end
if ( meeting.startTime < meeting2.endTime )
{
// the new meeting will start before
// the first meeting to finish, need one more room
heap.add(meeting);
break;
}
else
{
// the first meeting can finish
// and no further meeting will start yet
head.removeTop();
}
} else
{
heap.add(meeting);
break;
}
}

max = Math.max(max, heap.size());
}
return max;

w*t2011-05-22 07:05

41 楼

minimum rooms:先对进入和退出的点排序 vector>，然后一遍扫描即
可。
关键点：位置相同的点，需要将退出的排在前面
bool comp(const pair &a, const pair &b) {
if (a.first == b.first) return a.second <= b.second; // Caution:
end node first
return a.first < b.first;
}
class Solution {
public:
// [start, end)
// O(NlogN)
// void GetMostIntersect(vector > &intervals, int &point,
int &intersectNum)
int GetMinimumRooms(vector > &intervals)
{
vector> nodes; // idx : enter/exit
for (auto &it : intervals) { // O(N)
nodes.push_back(make_pair(it.first, 1));
nodes.push_back(make_pair(it.second, 0));
}
sort(nodes.begin(), nodes.end(), comp); // O(N*logN)
int currNum = 0, minRooms = 0;
for (auto &nd : nodes) { // O(N)
if (1 == nd.second) ++currNum;
else --currNum;
minRooms = max(minRooms, currNum);
}
return minRooms;
}
};

w*t2011-05-22 07:05

42 楼

minimum rooms:先对进入和退出的点排序 vector>，然后一遍扫描即
可。
关键点：位置相同的点，需要将退出的排在前面
bool comp(const pair &a, const pair &b) {
if (a.first == b.first) return a.second <= b.second; // Caution:
end node first
return a.first < b.first;
}
class Solution {
public:
// [start, end)
// O(NlogN)
// void GetMostIntersect(vector > &intervals, int &point,
int &intersectNum)
int GetMinimumRooms(vector > &intervals)
{
vector> nodes; // idx : enter/exit
for (auto &it : intervals) { // O(N)
nodes.push_back(make_pair(it.first, 1));
nodes.push_back(make_pair(it.second, 0));
}
sort(nodes.begin(), nodes.end(), comp); // O(N*logN)
int currNum = 0, minRooms = 0;
for (auto &nd : nodes) { // O(N)
if (1 == nd.second) ++currNum;
else --currNum;
minRooms = max(minRooms, currNum);
}
return minRooms;
}
};

b*i2011-05-22 07:05

43 楼

首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
，最后的时间提问。
1. 一来就是一道简单题，翻转链表
// Reverse a Singly Linked List
// Example Input: A -> B -> C
// Example Output: C -> B -> A
他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部
分，所以很快就写完了。
2.第二题直接copy 题目，感觉跟leetcode上面的interval那题很相似，简单一点点。
// Given a array of pairs where each pair contains the start and end time of
a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False
同样的思路+复杂度。同样是变种题，还变简单了，很快写完。（主要是考比较器的
override吧）
3. follow up第二题
// 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
我看表还剩下10分钟，然后想了3min钟，面试官就说没时间了，要不你说说思路。然后
说了一下思路，面试官说OK。让我提问题。瞎问了一个问题。面试官还特别详细的解答
了。他说超了一点时，不过没关系。然后互相感谢了一下，客套了一下。就再见了。
第二天HR说下一轮Onsite了。
最后求大家祝福，希望能onsite好运~~ 祝大家都能拿到心仪的offer~

Y*o2011-05-22 07:05

44 楼

Bless! 祝早日拿到offer

r*e2011-05-22 07:05

45 楼

new grad 么？硕士or PhD

l*42011-05-22 07:05

46 楼

感谢分享

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

h*d2011-05-22 07:05

47 楼

谢谢面经！
第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
.first 如果不是 return false应该就行了
第三题得用dp
还是先按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

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

r*e2011-05-22 07:05

48 楼

用dp怎么做？能给出公式么？我感觉不是那么容易，不如divide conquer

1]

【在 h**d 的大作中提到】

: 谢谢面经！
: 第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
: .first 如果不是 return false应该就行了
: 第三题得用dp
: 还是先按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
:
: coding

r*e2011-05-22 07:05

49 楼

这个不行
举例
（1，3）（2，6），（4，5）
你的算法结果是3，肉眼判断结果是2.

1]

【在 h**d 的大作中提到】

: 谢谢面经！
: 第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
: .first 如果不是 return false应该就行了
: 第三题得用dp
: 还是先按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
:
: coding

s*p2011-05-22 07:05

50 楼

那个最小会议室的这样行吗？先按开始时间和结束时间排序，然后逐个对比，有点类似
merge sort 的merge 阶段。
public class Solution {
public int numOverLaps(List start, List end) {
if (start == null || start.size() == 0 || end == null || end.size()
== 0) {
return 0;
}

if (start.size() != end.size()) {
return 0;
}

Collections.sort(start);
Collections.sort(end);

int startP = 0;
int endP = 0;

int numActive = 0;
int numOverlap = 0;

while (startP < start.size() && endP < end.size()) {
if (start.get(startP) < end.get(endP)) {
numActive++;
numOverlap = Math.max(numOverlap, numActive);
startP++;
} else {
numActive--;
endP++;
}
}
return numOverlap;
}
public static void main(String[] args) {
Solution sol = new Solution();
List start = new ArrayList();
List end = new ArrayList();
start.add(1);
start.add(2);
start.add(5);
start.add(4);
end.add(3);
end.add(4);
end.add(6);
end.add(7);
int result = sol.numOverLaps(start, end);
System.out.println("Result is " + result);
}
}

s*p2011-05-22 07:05

51 楼

实际上DP 是这个题，
Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum.
一直不知道怎么解，搭车问一下哈

l*i2011-05-22 07:05

52 楼

prob 2:
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.

h*d2011-05-22 07:05

53 楼

有大牛在另一个帖子里给出答案了
摘录：
所有时间排序到一起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是
解。

)

【在 s*********p 的大作中提到】

: 那个最小会议室的这样行吗？先按开始时间和结束时间排序，然后逐个对比，有点类似
: merge sort 的merge 阶段。
: public class Solution {
: public int numOverLaps(List start, List end) {
: if (start == null || start.size() == 0 || end == null || end.size()
: == 0) {
: return 0;
: }
:
: if (start.size() != end.size()) {

m*12011-05-22 07:05

54 楼

mark

x*j2011-05-22 07:05

55 楼

同搭车问

【在 s*********p 的大作中提到】

: 实际上DP 是这个题，
: Given a set of n jobs with [start time, end time, cost] find a subset so
: that no 2 jobs overlap and the cost is maximum.
: 一直不知道怎么解，搭车问一下哈

y*22011-05-22 07:05

56 楼

第二题能解释一下解法吗
/ Given a array of pairs where each pair contains the start and end time of
a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False
另外，另外允许部分conflict吗？如果是(1, 4) (3, 5) ，是return False吗？

s*i2011-05-22 07:05

57 楼

第二题有没有可能O(n)？

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

C*M2011-05-22 07:05

58 楼

怎么觉得应该按照end time 排序，然后看interval.end[i]和interval.end[i-1] 有没
有overlapping，每重叠一次add一个room

l*42011-05-22 07:05

59 楼

第二题前面有人说了啊
“第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+
1]
.first 如果不是 return false应该就行了”

of

【在 y****2 的大作中提到】

: 第二题能解释一下解法吗
: / Given a array of pairs where each pair contains the start and end time of
: a meeting (as in int),
: // Determine if a single person can attend all the meetings
: // Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
: // Output: False
: 另外，另外允许部分conflict吗？如果是(1, 4) (3, 5) ，是return False吗？

z*b2011-05-22 07:05

60 楼

这个解法有个注意事项，如果interval 1的start time 和interval 2 的end time相等
，应该把 interval 2的 end time排在前面（ｉｎｃｒｅａｓｉｎｇ　ｏｒｄｅｒ）
不然像（２，　３），(3, 4)这样的可能返回2，实际应该返回1.

【在 l***i 的大作中提到】

: prob 2:
: 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.

b*i2011-05-22 07:05

61 楼

恩是的 MS new grad

【在 r*******e 的大作中提到】

: new grad 么？硕士or PhD

b*i2011-05-22 07:05

62 楼

HI
我觉得你第二题不大对哈
比如（1,2）（1,3）（2,4）（2,5）（3,7）

1]

【在 h**d 的大作中提到】

: 谢谢面经！
: 第二题就按pair.first sort一下然后从头扫到尾看每个pair[i].second<=pair[i+1]
: .first 如果不是 return false应该就行了
: 第三题得用dp
: 还是先按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
:
: coding

d*m2011-05-22 07:05

63 楼

多谢OP！！
Bless！

L*p2011-05-22 07:05

64 楼

没看懂，求贴？

【在 h**d 的大作中提到】

: 有大牛在另一个帖子里给出答案了
: 摘录：
: 所有时间排序到一起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是
: 解。
:
: )

h*02011-05-22 07:05

65 楼

为什么不对？展开来说说？

【在 b**********i 的大作中提到】

: HI
: 我觉得你第二题不大对哈
: 比如（1,2）（1,3）（2,4）（2,5）（3,7）
:
: 1]

w*n2011-05-22 07:05

66 楼

不错

m*a2011-05-22 07:05

67 楼

第三题
brute force 解法N R*ln(R) R meeting room number
#include
#include
using namespace std;
struct Interval{
int start;
int end;
};
bool comp(Interval a, Interval b){
return a.start}
class Solution{
public:
int meetingSchedule(vector interval){
sort(interval.begin(),interval.end(),comp);
vector rooms;
if (!interval.empty()){
rooms.push_back(interval[0].end);
}
for (int i=1;iint merged=false;
sort(rooms.begin(),rooms.end());
for (int j=rooms.size()-1;j>=0;j--){
if (interval[i].start>=rooms[j]) {
rooms[j]=interval[i].end;
merged=true;
break;
}
}
if (!merged){
rooms.push_back(interval[i].end);
}
}
return rooms.size();
}
};
int main()
{
vector interval={{2,3},{1,4},{3,4},{4, 5}};
vector interval2={{1,3},{2,6},{4, 5}};
vector interval3={{1,2},{1,3},{2,4},{2,5},{3, 7}};
Solution test;
cout<cout<cout<return 0;
}
返回 2，2，3

h*s2011-05-22 07:05

68 楼

第三题能不能这样解：
Brute force：假设时间每流动一个单位，就更新一下所有meeting和room的状态。
Optimization：我们发现时间可以流动的快一些，每次流动的单位数基于当前马上就要
结束的meeting和下一个马上就开始的meeting，算法如下:
1. 按start time排序
2. Go over the sorted list.
3. keep a minimum heap based on the end time.
4. the heap size is the needed number of room at any time.
TO(nlogn): for sorting and keeping heap.
SO(n): for the heap and maybe some sorting algorithm.
// heap is based on interval.endTime
int max = 0;
for ( Interval meeting : Sorted_List )
{
while ( true )
{
if ( heap.size() > 0 )
{
Interval meeting2 = heap.peek(); // first meeting to end
if ( meeting.startTime < meeting2.endTime )
{
// the new meeting will start before
// the first meeting to finish, need one more room
heap.add(meeting);
break;
}
else
{
// the first meeting can finish
// and no further meeting will start yet
head.removeTop();
}
} else
{
heap.add(meeting);
break;
}
}

max = Math.max(max, heap.size());
}
return max;

w*t2011-05-22 07:05

69 楼

minimum rooms:先对进入和退出的点排序 vector>，然后一遍扫描即
可。
关键点：位置相同的点，需要将退出的排在前面
bool comp(const pair &a, const pair &b) {
if (a.first == b.first) return a.second <= b.second; // Caution:
end node first
return a.first < b.first;
}
class Solution {
public:
// [start, end)
// O(NlogN)
// void GetMostIntersect(vector > &intervals, int &point,
int &intersectNum)
int GetMinimumRooms(vector > &intervals)
{
vector> nodes; // idx : enter/exit
for (auto &it : intervals) { // O(N)
nodes.push_back(make_pair(it.first, 1));
nodes.push_back(make_pair(it.second, 0));
}
sort(nodes.begin(), nodes.end(), comp); // O(N*logN)
int currNum = 0, minRooms = 0;
for (auto &nd : nodes) { // O(N)
if (1 == nd.second) ++currNum;
else --currNum;
minRooms = max(minRooms, currNum);
}
return minRooms;
}
};

x*82011-05-22 07:05

70 楼

public static int minRoom(List list) {
Comparator comparator = new Comparator() {
@Override
public int compare(Point o1, Point o2) {
return o1.y - o2.y;
}
};
Collections.sort(list, comparator);
int num = 0;
List res = new ArrayList<>();
for (int i = 1; i < list.size(); i++) {
int j = 0;
for (; j < res.size(); j++) {
if(res.get(j).y <= list.get(i).x){
res.set(j, list.get(i));
break;
}
}
if(j==res.size()){
res.add(list.get(i));
num++;
}
}
return num;
}

x*82011-05-22 07:05

71 楼

public static int minRoom(List list) {
Comparator comparator = new Comparator() {
@Override
public int compare(Point o1, Point o2) {
return o1.y - o2.y;
}
};
Collections.sort(list, comparator);
int num = 0;
List res = new ArrayList<>();
for (int i = 1; i < list.size(); i++) {
int j = 0;
for (; j < res.size(); j++) {
if(res.get(j).y <= list.get(i).x){
res.set(j, list.get(i));
break;
}
}
if(j==res.size()){
res.add(list.get(i));
num++;
}
}
return num;
}

l*u2011-05-22 07:05

72 楼

bless

coding

【在 b**********i 的大作中提到】

: 首先感谢帮我内推的哥们，谢谢你让我顺利拿到电话面试。
: 其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
: 说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
: ，最后的时间提问。
: 1. 一来就是一道简单题，翻转链表
: // Reverse a Singly Linked List
: // Example Input: A -> B -> C
: // Example Output: C -> B -> A
: 他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
: 题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部

s*m2011-05-22 07:05

73 楼

谢谢面经，祝LZ好运拿到offer!

x*u2011-05-22 07:05

74 楼

LZ的面经是去年的, 被人挖出来顶起了.
LZ offer 拿到了吗?

T*72011-05-22 07:05

75 楼

第三题跟 lintcode
Number of Airplanes in the Sky
一样的解法。
将会议的起始时间，和终止时间分别存为一个point(time, flag)， flag标示该point
该时间点会议是终止，还是开始。然后对这个point list进行排序（当两个point时间
相等是，默认point为会议终止的排在list前面）。这样最后再对list循环一遍，维护
一个最大的room count 即是结果。

r*d2011-05-22 07:05

76 楼

有个帖子好像讲了这个
https://hellosmallworld123.wordpress.com/2014/05/30/arranging-the-meeting-
room/

e*u2011-05-22 07:05

77 楼

祝好运...目测楼主这水平得多加把力.

【在 b**********i 的大作中提到】

: 恩是的 MS new grad