请教两个面试题 - 未名空间MITBBS历史存档

l*y2015-02-27 08:02

1 楼

都是glassdoor上看到的面经：
1. You have a number of meetings (with their start and end times). You need
to schedule them using the minimum number of rooms. Return the list of
meetings in every room.
似乎可以把会议按个插入各个房间中。只要某会议与现有所有已安排的会议室都有冲突
，就安排出新会议室。如果没有冲突，就任意插入现有会议室。但这样做似乎没办法保
证使用房间最小化。
2. Implement two functions that assign/release unique id's from a pool.
Memory usage should be minimized and the
assign/release should be fast, even under high contention.
似乎可以用一个hashset来维护所有可用id，但这样用的内存太多。还有别的什么办法
可以保证assign/release快速，但内存消耗少吗？

d*s2015-02-27 08:02

2 楼

1）第一题是NP吧，每个Meeting是个点，如果冲突就有边，然后要求indepent set
数目最少。
2）如果给的ID就是unique的，用单向链表？还是每次unique id要临时生成？那要跟
已经发出去了的check一下啊。

l*y2015-02-27 08:02

3 楼

那第一题只能暴力解？把所有可能的安排组合列出来，然后取使用会议室最少那个？
第二个面经上也只有说那个多，我猜是不是提前给定多个unique id，然后要管理发出
和收回。如果用链表的话用和hashset也是一样的吧，O(n)的空间和O(1)的时间

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

: 1）第一题是NP吧，每个Meeting是个点，如果冲突就有边，然后要求indepent set
: 数目最少。
: 2）如果给的ID就是unique的，用单向链表？还是每次unique id要临时生成？那要跟
: 已经发出去了的check一下啊。

w*d2015-02-27 08:02

4 楼

1. 看成scheduling问题变体：
1）找到最多的不重合meeting（scheduling问题，O(NlogN)），安排到room 1；
2）将已安排的meeting删除，如果还有剩余，重复1）且room数加1；
总体时间复杂度O(N^2*logN)。
2. 关键看看id是什么：如果是有限集合的字符串或者不连续int，用list；如果是有限
连续int，可以用bitmap；如果是无限连续int，那就一直current++吧，呵呵。

s*72015-02-27 08:02

5 楼

第一题，把start -> meeting, end -> meeting 建立map, 然后排序所有的时间点，
用greedy，维持一个list, list的size就是房间数，遇到一个start,就把相应的
meeting加进去，遇到end就remove，list的最大size就是最少房间数
我觉得不能再少房间了吧，有房间就用，不用肯定不是优化的

m*n2015-02-27 08:02

6 楼

其实第一题很简单，
假设每个meeting是[start, end] 的interval，先把输入meeting 按end排序,然后按楼
主的方法挨个插入room，不过要greedy，一定要插入符合条件的最后一个。
最后的结果一定是最少的。time complexity O(N^2)?

need

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

: 都是glassdoor上看到的面经：
: 1. You have a number of meetings (with their start and end times). You need
: to schedule them using the minimum number of rooms. Return the list of
: meetings in every room.
: 似乎可以把会议按个插入各个房间中。只要某会议与现有所有已安排的会议室都有冲突
: ，就安排出新会议室。如果没有冲突，就任意插入现有会议室。但这样做似乎没办法保
: 证使用房间最小化。
: 2. Implement two functions that assign/release unique id's from a pool.
: Memory usage should be minimized and the
: assign/release should be fast, even under high contention.

l*y2015-02-27 08:02

7 楼

请问这个scheduling具体是怎么操作的？有什么关键字可以google吗？是不是跟楼上有
一个帖子里说得那样，先对开始时间或者结束时间点做排序，然后进行插入？
第2个题有bitmap似乎也无法保证能在o(1)取出id吧？感觉如果每个bit代表一个id的话
，查找一个可以用的id也似乎需要把整个bitmap扫一遍才可以。

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

: 1. 看成scheduling问题变体：
: 1）找到最多的不重合meeting（scheduling问题，O(NlogN)），安排到room 1；
: 2）将已安排的meeting删除，如果还有剩余，重复1）且room数加1；
: 总体时间复杂度O(N^2*logN)。
: 2. 关键看看id是什么：如果是有限集合的字符串或者不连续int，用list；如果是有限
: 连续int，可以用bitmap；如果是无限连续int，那就一直current++吧，呵呵。

l*y2015-02-27 08:02

8 楼

我开始的想法比较类似。我的想发是按照开始时间排序，然后逐个插入。如果发现现有
的room里都有重叠，就开一个新room。如果没有重叠，就插入其中一个没有出现重叠的
会议室。但这样可以永远保证使用的房间最少吗？好像一时半会想不出什么反例。但似
乎感觉这个问题是combinatorial optimization, 不像是一个polynomial time的问题。

【在 m*****n 的大作中提到】

: 其实第一题很简单，
: 假设每个meeting是[start, end] 的interval，先把输入meeting 按end排序,然后按楼
: 主的方法挨个插入room，不过要greedy，一定要插入符合条件的最后一个。
: 最后的结果一定是最少的。time complexity O(N^2)?
:
: need

h*c2015-02-27 08:02

9 楼

第一题类似fb问过
我lol答，可以预先设定时间的granularity
比如三个会议
[1 2 3]
[3 4 5]
[6 7]
用hashmap 来detect collision，没有下文。

need

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

: 都是glassdoor上看到的面经：
: 1. You have a number of meetings (with their start and end times). You need
: to schedule them using the minimum number of rooms. Return the list of
: meetings in every room.
: 似乎可以把会议按个插入各个房间中。只要某会议与现有所有已安排的会议室都有冲突
: ，就安排出新会议室。如果没有冲突，就任意插入现有会议室。但这样做似乎没办法保
: 证使用房间最小化。
: 2. Implement two functions that assign/release unique id's from a pool.
: Memory usage should be minimized and the
: assign/release should be fast, even under high contention.

h*c2015-02-27 08:02

10 楼

第二题可以超卖吗？
SIMPLE

h*c2015-02-27 08:02

11 楼

第二题可以这样，有一个Abelian group atomic 的计数器，
所有的thread拿同一个compressed stream，同时读加计数器
拿回去之后每个客端自己回解压缩，用计数器值取自己那一段做id
这样contention will be greatly pain relieved.
MIT license.

...

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

: 我开始的想法比较类似。我的想发是按照开始时间排序，然后逐个插入。如果发现现有
: 的room里都有重叠，就开一个新room。如果没有重叠，就插入其中一个没有出现重叠的
: 会议室。但这样可以永远保证使用的房间最少吗？好像一时半会想不出什么反例。但似
: 乎感觉这个问题是combinatorial optimization, 不像是一个polynomial time的问题。

b*n2015-02-27 08:02

12 楼

我来回答下第一题：
先放等式：
需要的房间数 = meeting overlap 涉及meeting数量最大的meeting数
可能以上公式比较抽象，举两个例子
Example #1
Meeting #A， start 1:00, end 3:00
Meeting #B， start 2:00，end 4:00
Meeting #C， start 3:00，end 5:00
在Example #1 中，需要的meeting room 数是2，因为这三个meeting的overlap部分最
多只涉及到2个meeting
Example #2
Meeting #A， start 1:00, end 3:00
Meeting #B， start 2:00，end 4:00
Meeting #C， start 2:00，end 5:00
在Example #2 中，需要的meeting room 数是3，因为第三个meeting时间提前了，
overlap部分最多涉及到3个meeting
所以算法如下：
1.按照starting time给meeting排序（nlog（n））
2.iterate the meeting array,用一个counter 和 min heap 计算已经开始的meeting
和结束的meeting，得到的是overlap涉及的meeting数量（nlog（n））
3.在此过程中记下counter的最大值，此值即为所需meeting room的最大值
个人想法，有什么不对的地方请指正

need

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

: 都是glassdoor上看到的面经：
: 1. You have a number of meetings (with their start and end times). You need
: to schedule them using the minimum number of rooms. Return the list of
: meetings in every room.
: 似乎可以把会议按个插入各个房间中。只要某会议与现有所有已安排的会议室都有冲突
: ，就安排出新会议室。如果没有冲突，就任意插入现有会议室。但这样做似乎没办法保
: 证使用房间最小化。
: 2. Implement two functions that assign/release unique id's from a pool.
: Memory usage should be minimized and the
: assign/release should be fast, even under high contention.

C*t2015-02-27 08:02

13 楼

Greedy adding new meeting. Either add to a current room, or set a new room
for this meeting. O(n^2) time.
def findRoom( A):
A.sort(key = lambda x:x[0])
res = [[A[0]]]
for i in range(1,len(A)):
for j in range(len(res)):
if res[j][-1][-1] <= A[i][0]:
res[j].append(A[i])
break
if j == len(res) - 1:
res.append([A[i]])
return res

s*32015-02-27 08:02

14 楼

Second this.

room

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

: Greedy adding new meeting. Either add to a current room, or set a new room
: for this meeting. O(n^2) time.
: def findRoom( A):
: A.sort(key = lambda x:x[0])
: res = [[A[0]]]
: for i in range(1,len(A)):
: for j in range(len(res)):
: if res[j][-1][-1] <= A[i][0]:
: res[j].append(A[i])
: break

c*e2015-02-27 08:02

15 楼

第一题就是经典的 greedy 算法，类似于任务分配到机器，以会议的结束时间排序，
有冲突就加一个房间，会议结束就把房间释放出来。

need

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

: 都是glassdoor上看到的面经：
: 1. You have a number of meetings (with their start and end times). You need
: to schedule them using the minimum number of rooms. Return the list of
: meetings in every room.
: 似乎可以把会议按个插入各个房间中。只要某会议与现有所有已安排的会议室都有冲突
: ，就安排出新会议室。如果没有冲突，就任意插入现有会议室。但这样做似乎没办法保
: 证使用房间最小化。
: 2. Implement two functions that assign/release unique id's from a pool.
: Memory usage should be minimized and the
: assign/release should be fast, even under high contention.

l*y2015-02-27 08:02

16 楼

感谢大家的解答。根据bigonotation的分析，似乎应该用o(n^2)的greedy办法插入就可
以了。因为如果有某一个会议安排无法插入到目前已有的房间，那就说明overlapping
的数量是超过了现有房间的总量，所以必须重新开新会议室。反之，如果不需要新的会
议室，那必然目前已有的房间里，可以把会议插进去

w*o2015-02-27 08:02

17 楼

正解.

overlapping

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

: 感谢大家的解答。根据bigonotation的分析，似乎应该用o(n^2)的greedy办法插入就可
: 以了。因为如果有某一个会议安排无法插入到目前已有的房间，那就说明overlapping
: 的数量是超过了现有房间的总量，所以必须重新开新会议室。反之，如果不需要新的会
: 议室，那必然目前已有的房间里，可以把会议插进去

b*n2015-02-27 08:02

18 楼

大家真的看懂我的答案了吗？感觉大家都没看懂，好桑心！
可能是我语言表达能力太差，我的意思是这题有nlog（n）的解法啊！
帖code
import headq
def scheduleMeeting(self, meetings):
meetings.sort(key = lambda x: x[0])
heap = []
cnt = 0
max_cnt = 0
for i in range(len(meetings)):
while heap and heap[0]<=meetings[i][0]:
heapq.heappop(heap)
cnt -= 1
cnt += 1
max_cnt = max(max_cnt, cnt)
heapq.heappush(heap, meetings[i][1])
return max_cnt
test case #1 [[2,4], [3,5],[4,6]]
output ： 2
test case #2 [[2,4], [3,5],[3,6]]
output ： 3
nlog（n）

overlapping

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

: 感谢大家的解答。根据bigonotation的分析，似乎应该用o(n^2)的greedy办法插入就可
: 以了。因为如果有某一个会议安排无法插入到目前已有的房间，那就说明overlapping
: 的数量是超过了现有房间的总量，所以必须重新开新会议室。反之，如果不需要新的会
: 议室，那必然目前已有的房间里，可以把会议插进去

b*g2015-02-27 08:02

19 楼

Initialization:
1. Given a list of meetings with each meeting represented by (meeting
id, start time, end time)
2. Convert each meeting (meeting id, start time, end time) into 2 tuples
meeting tuple (time, end type, meeting id). Sort all start and end meeting
tuples by time.
3. Initial a meeting number counter. If a new meeting room is needed,
the the next meeting room id is the counter value.
4. Initialize a hash map {meeting id: room id} to record which room uses
which id.
5. Initialize a list to garbage collect used meeting room.
Processing:
for each meeting tuple (time, start type or end type, meeting id) in the
sorted meeting tuples:
if the tuple type is start type:
if the meeting id garbage collection list is not empty:
room id = pop the front of the list;
else:
room id = room counter++
store (meeting id, room id) in hash map
else the tuple type is end type:
room id = meeting id in hash map
push room id into garbage collection list

After processing:
the room counter is the max number of room needed to arrange all
meetings.
the hash map contains the room id for each meeting
Time Complexity nlog(n)
need