G家电面，已挂 - 未名空间MITBBS历史存档

w*r2013-11-04 08:11

1 楼

【以下文字转载自 Notice 讨论区】
发信人: deliver (自动发信系统), 信区:
标题: winderwater 解封 I8888 在 ebiz 版
发信站: BBS 未名空间站自动发信系统 (Mon May 10 02:10:16 2010)
【此篇文章是由自动发信系统所张贴】
寄信人: deliver
标题: [通知]
发信站: BBS 未名空间站 (Mon May 10 02:10:16 2010)
来源: 65.10.
您被 ebiz 版版主 winderwater 解除封禁

a*e2013-11-04 08:11

2 楼

面试官有东南亚口音
第一题是leetcode原题，大数+1
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
他让想算法，给出伪码。我说最简单的方法就是S1和S2先合并，然后再和S3合并，以此
类推。
他说可以，那写一下伪码吧。我写的时候发现case太多，结果没有写完。今天收听到
消息，说挂了。

z*82013-11-04 08:11

3 楼

第二题不能用额外空间吗？
不得不赞一下G的面试，总是有新题涌出

a*m2013-11-04 08:11

4 楼

第二题这样行吗：
一个数组， index 为单位时间
各个 speaker 的各个时段volume都累加到这个数组
最后对数组按音量分段

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

d*x2013-11-04 08:11

5 楼

should be...
not that hard...

【在 z*********8 的大作中提到】

: 第二题不能用额外空间吗？
: 不得不赞一下G的面试，总是有新题涌出

d*x2013-11-04 08:11

6 楼

no. you need to make it better 'discreted' so it will lead you to the
segment tree solution.
otherwise, consider a interval like [1, INT_MAX]

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

: 第二题这样行吗：
: 一个数组， index 为单位时间
: 各个 speaker 的各个时段volume都累加到这个数组
: 最后对数组按音量分段

h*y2013-11-04 08:11

7 楼

这个不是新题了吧, EPI上的原题,
可以divide and conquer
也可以先排序, 从左往右scan, 同时maintain一个BST
两种都是nlog(n)

【在 z*********8 的大作中提到】

: 第二题不能用额外空间吗？
: 不得不赞一下G的面试，总是有新题涌出

e*s2013-11-04 08:11

8 楼

什么是EPI？

h*y2013-11-04 08:11

9 楼

elements of programming interview

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

: 什么是EPI？

n*e2013-11-04 08:11

10 楼

能具体说说是leetcode的哪道题吗？不太明白“大数+1”的意思。

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

e*s2013-11-04 08:11

11 楼

就是考了大数

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

: 能具体说说是leetcode的哪道题吗？不太明白“大数+1”的意思。

n*e2013-11-04 08:11

12 楼

能给个leetcode 大数题的连接吗？
做了leetcode这么久，还不知道哪道题是大数。。。。

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

: 就是考了大数

v*n2013-11-04 08:11

13 楼

能不能展开说说，或者给个链接？
谢谢。

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

: 这个不是新题了吧, EPI上的原题,
: 可以divide and conquer
: 也可以先排序, 从左往右scan, 同时maintain一个BST
: 两种都是nlog(n)

s*u2013-11-04 08:11

14 楼

颜色那题么，好像看着有点差别。

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

: 这个不是新题了吧, EPI上的原题,
: 可以divide and conquer
: 也可以先排序, 从左往右scan, 同时maintain一个BST
: 两种都是nlog(n)

d*x2013-11-04 08:11

15 楼

the basic idea is the same. convert each segment into 2 events, sort and
maintain some states

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

: 颜色那题么，好像看着有点差别。

r*n2013-11-04 08:11

16 楼

去leetcode 搜 plus one那道题

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

: 能给个leetcode 大数题的连接吗？
: 做了leetcode这么久，还不知道哪道题是大数。。。。

D*d2013-11-04 08:11

17 楼

第二道是 interval 相加，O(nlgn)
具体做法是:
用 map 将所有端点排序, 其中右端的 volume 为负值，然后扫描 map
一遍即可.

n*e2013-11-04 08:11

18 楼

多谢，知道了！
plus one和大数相加没有什么关系啊

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

: 去leetcode 搜 plus one那道题

w*e2013-11-04 08:11

19 楼

第二题:
1.先找出最小最大的时间值,设置一个数组,每个element代表一个单位时间内的max vol
2.填满这个数组
3,扫描这个数组,当值跳变的时候,就增加一个时间段
这道题目如果follow leetcode上merge interval的思路,肯定会非常麻烦
复杂度是O(mn)，n是S的个数，m是时间段的长度

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

d*x2013-11-04 08:11

20 楼

S1: {[0, 222233333], vol=1};

vol

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

: 第二题:
: 1.先找出最小最大的时间值,设置一个数组,每个element代表一个单位时间内的max vol
: 2.填满这个数组
: 3,扫描这个数组,当值跳变的时候,就增加一个时间段
: 这道题目如果follow leetcode上merge interval的思路,肯定会非常麻烦
: 复杂度是O(mn)，n是S的个数，m是时间段的长度

w*e2013-11-04 08:11

21 楼

if coding in interviews, start from the simplest cases. Then, at least, you
can finish the coding. Then tell the interviewers the cases your codes
cannot cover and try to optimize it.
if you tell them a very complicate algorithm which covers a lot of cases,
you will get into a trap and cannot finish the codes. Then the result will
be a rejection.

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

: S1: {[0, 222233333], vol=1};
:
: vol

d*x2013-11-04 08:11

22 楼

but not one that unacceptable. :)

you

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

: if coding in interviews, start from the simplest cases. Then, at least, you
: can finish the coding. Then tell the interviewers the cases your codes
: cannot cover and try to optimize it.
: if you tell them a very complicate algorithm which covers a lot of cases,
: you will get into a trap and cannot finish the codes. Then the result will
: be a rejection.

g*e2013-11-04 08:11

23 楼

第二题就是skyline problem吧

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

f*x2013-11-04 08:11

24 楼

第二题
每次取出每个队列的head，然后提取区间（分隔最前端可以确定的几轮and保留剩下的
区间），直到某个head的区间用完，取入其head的下一个
这思路和merge n sorted list一个感觉，变成merge n sorted interval了
貌似可行

f*x2013-11-04 08:11

25 楼

自己仔细想了想，实现起来还是很麻烦，但是感觉依然可行
大牛快给点建议

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

: 第二题
: 每次取出每个队列的head，然后提取区间（分隔最前端可以确定的几轮and保留剩下的
: 区间），直到某个head的区间用完，取入其head的下一个
: 这思路和merge n sorted list一个感觉，变成merge n sorted interval了
: 貌似可行

w*e2013-11-04 08:11

26 楼

typdef struct {
int start, end;
int vol;
} Interval;
vector > findMaxVol(vector > &S) {
int n = S.size();
vector > ret;
if(n==0) return ret;
if(n==1) return S[0];
vector index(n, 0);
int start=S[0][0].start, end=S[0][0].end;
int max_vol = 0;
for(int i=0; iif(start>S[i][0].start) start = S[i][0].start;
}
int finish_cnt = 0;
while(finish_cntfor(int i=0; iif(index[i]index[i]++;
if(index[i]==S[i].size()) finish_cnt++;
}
if(index[i]>=S[i].size()) continue;
if(S[i][index[i]].endif(max_vol}
Interval ntvl;
ntvl.start = start;
ntvl.end = end;
ntvl.vo;l = max_vol;
ret.push_back(ntvl);
max_vol = 0;
start = end;
end = INT_MAX;
}
return ret;
}

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

: S1: {[0, 222233333], vol=1};
:
: vol

n*e2013-11-04 08:11

27 楼

Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。

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

:
: 第二题就是skyline problem吧

a*e2013-11-04 08:11

28 楼

本来是这么想的。
写的时候想写两个speaker的case，但即使是这样也比merge interval复杂很多，于是
就挂了。。。

you

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

: if coding in interviews, start from the simplest cases. Then, at least, you
: can finish the coding. Then tell the interviewers the cases your codes
: cannot cover and try to optimize it.
: if you tell them a very complicate algorithm which covers a lot of cases,
: you will get into a trap and cannot finish the codes. Then the result will
: be a rejection.

g*e2013-11-04 08:11

29 楼

。
multiset用来做maxheap貌似不错！
不知道heap在stil里标准的data structure是什么

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

: Exactly
: Skyline 的解法貌似是（没记错的话）：
: 把所有的turning points 放在一起，根据coordination从小到大sort 。
: struct turnpoint {
: int ptr; //coordinate;
: bool startOrEnd;
: int volume
: }
: 再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
: volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。

n*e2013-11-04 08:11

30 楼

C++ STL 里面有：
std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
很少用到

f*p2013-11-04 08:11

31 楼

不是accumulated volume是max volume.
不过赞思路，学习。

map

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

: 第二道是 interval 相加，O(nlgn)
: 具体做法是:
: 用 map 将所有端点排序, 其中右端的 volume 为负值，然后扫描 map
: 一遍即可.

z*n2013-11-04 08:11

32 楼

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

: the basic idea is the same. convert each segment into 2 events, sort and
: maintain some states

d*n2013-11-04 08:11

33 楼

这个不work，不信找个输入走一遍

。

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

: Exactly
: Skyline 的解法貌似是（没记错的话）：
: 把所有的turning points 放在一起，根据coordination从小到大sort 。
: struct turnpoint {
: int ptr; //coordinate;
: bool startOrEnd;
: int volume
: }
: 再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
: volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。

l*n2013-11-04 08:11

34 楼

即便不work，也应该是你来走一遍来说明如何简单的输入都不work。
何况，该solution works。虽然很多地方拿skyline problem做divide & conquer的例
子，但那样并不意味着别的思路就行不通。

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

: 这个不work，不信找个输入走一遍
:
: 。

c*p2013-11-04 08:11

35 楼

mark

a*e2013-11-04 08:11

36 楼

面试官有东南亚口音
第一题是leetcode原题，大数+1
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
他让想算法，给出伪码。我说最简单的方法就是S1和S2先合并，然后再和S3合并，以此
类推。
他说可以，那写一下伪码吧。我写的时候发现case太多，结果没有写完。今天收听到
消息，说挂了。

z*82013-11-04 08:11

37 楼

第二题不能用额外空间吗？
不得不赞一下G的面试，总是有新题涌出

a*m2013-11-04 08:11

38 楼

第二题这样行吗：
一个数组， index 为单位时间
各个 speaker 的各个时段volume都累加到这个数组
最后对数组按音量分段

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

d*x2013-11-04 08:11

39 楼

should be...
not that hard...

【在 z*********8 的大作中提到】

: 第二题不能用额外空间吗？
: 不得不赞一下G的面试，总是有新题涌出

d*x2013-11-04 08:11

40 楼

no. you need to make it better 'discreted' so it will lead you to the
segment tree solution.
otherwise, consider a interval like [1, INT_MAX]

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

: 第二题这样行吗：
: 一个数组， index 为单位时间
: 各个 speaker 的各个时段volume都累加到这个数组
: 最后对数组按音量分段

h*y2013-11-04 08:11

41 楼

这个不是新题了吧, EPI上的原题,
可以divide and conquer
也可以先排序, 从左往右scan, 同时maintain一个BST
两种都是nlog(n)

【在 z*********8 的大作中提到】

: 第二题不能用额外空间吗？
: 不得不赞一下G的面试，总是有新题涌出

e*s2013-11-04 08:11

42 楼

什么是EPI？

h*y2013-11-04 08:11

43 楼

elements of programming interview

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

: 什么是EPI？

n*e2013-11-04 08:11

44 楼

能具体说说是leetcode的哪道题吗？不太明白“大数+1”的意思。

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

e*s2013-11-04 08:11

45 楼

就是考了大数

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

: 能具体说说是leetcode的哪道题吗？不太明白“大数+1”的意思。

n*e2013-11-04 08:11

46 楼

能给个leetcode 大数题的连接吗？
做了leetcode这么久，还不知道哪道题是大数。。。。

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

: 就是考了大数

v*n2013-11-04 08:11

47 楼

能不能展开说说，或者给个链接？
谢谢。

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

: 这个不是新题了吧, EPI上的原题,
: 可以divide and conquer
: 也可以先排序, 从左往右scan, 同时maintain一个BST
: 两种都是nlog(n)

s*u2013-11-04 08:11

48 楼

颜色那题么，好像看着有点差别。

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

: 这个不是新题了吧, EPI上的原题,
: 可以divide and conquer
: 也可以先排序, 从左往右scan, 同时maintain一个BST
: 两种都是nlog(n)

d*x2013-11-04 08:11

49 楼

the basic idea is the same. convert each segment into 2 events, sort and
maintain some states

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

: 颜色那题么，好像看着有点差别。

r*n2013-11-04 08:11

50 楼

去leetcode 搜 plus one那道题

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

: 能给个leetcode 大数题的连接吗？
: 做了leetcode这么久，还不知道哪道题是大数。。。。

D*d2013-11-04 08:11

51 楼

第二道是 interval 相加，O(nlgn)
具体做法是:
用 map 将所有端点排序, 其中右端的 volume 为负值，然后扫描 map
一遍即可.

n*e2013-11-04 08:11

52 楼

多谢，知道了！
plus one和大数相加没有什么关系啊

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

: 去leetcode 搜 plus one那道题

w*e2013-11-04 08:11

53 楼

第二题:
1.先找出最小最大的时间值,设置一个数组,每个element代表一个单位时间内的max vol
2.填满这个数组
3,扫描这个数组,当值跳变的时候,就增加一个时间段
这道题目如果follow leetcode上merge interval的思路,肯定会非常麻烦
复杂度是O(mn)，n是S的个数，m是时间段的长度

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

d*x2013-11-04 08:11

54 楼

S1: {[0, 222233333], vol=1};

vol

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

: 第二题:
: 1.先找出最小最大的时间值,设置一个数组,每个element代表一个单位时间内的max vol
: 2.填满这个数组
: 3,扫描这个数组,当值跳变的时候,就增加一个时间段
: 这道题目如果follow leetcode上merge interval的思路,肯定会非常麻烦
: 复杂度是O(mn)，n是S的个数，m是时间段的长度

w*e2013-11-04 08:11

55 楼

if coding in interviews, start from the simplest cases. Then, at least, you
can finish the coding. Then tell the interviewers the cases your codes
cannot cover and try to optimize it.
if you tell them a very complicate algorithm which covers a lot of cases,
you will get into a trap and cannot finish the codes. Then the result will
be a rejection.

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

: S1: {[0, 222233333], vol=1};
:
: vol

d*x2013-11-04 08:11

56 楼

but not one that unacceptable. :)

you

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

: if coding in interviews, start from the simplest cases. Then, at least, you
: can finish the coding. Then tell the interviewers the cases your codes
: cannot cover and try to optimize it.
: if you tell them a very complicate algorithm which covers a lot of cases,
: you will get into a trap and cannot finish the codes. Then the result will
: be a rejection.

g*e2013-11-04 08:11

57 楼

第二题就是skyline problem吧

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

f*x2013-11-04 08:11

58 楼

第二题
每次取出每个队列的head，然后提取区间（分隔最前端可以确定的几轮and保留剩下的
区间），直到某个head的区间用完，取入其head的下一个
这思路和merge n sorted list一个感觉，变成merge n sorted interval了
貌似可行

f*x2013-11-04 08:11

59 楼

自己仔细想了想，实现起来还是很麻烦，但是感觉依然可行
大牛快给点建议

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

: 第二题
: 每次取出每个队列的head，然后提取区间（分隔最前端可以确定的几轮and保留剩下的
: 区间），直到某个head的区间用完，取入其head的下一个
: 这思路和merge n sorted list一个感觉，变成merge n sorted interval了
: 貌似可行

w*e2013-11-04 08:11

60 楼

typdef struct {
int start, end;
int vol;
} Interval;
vector > findMaxVol(vector > &S) {
int n = S.size();
vector > ret;
if(n==0) return ret;
if(n==1) return S[0];
vector index(n, 0);
int start=S[0][0].start, end=S[0][0].end;
int max_vol = 0;
for(int i=0; iif(start>S[i][0].start) start = S[i][0].start;
}
int finish_cnt = 0;
while(finish_cntfor(int i=0; iif(index[i]index[i]++;
if(index[i]==S[i].size()) finish_cnt++;
}
if(index[i]>=S[i].size()) continue;
if(S[i][index[i]].endif(max_vol}
Interval ntvl;
ntvl.start = start;
ntvl.end = end;
ntvl.vo;l = max_vol;
ret.push_back(ntvl);
max_vol = 0;
start = end;
end = INT_MAX;
}
return ret;
}

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

: S1: {[0, 222233333], vol=1};
:
: vol

n*e2013-11-04 08:11

61 楼

Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。

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

:
: 第二题就是skyline problem吧

a*e2013-11-04 08:11

62 楼

本来是这么想的。
写的时候想写两个speaker的case，但即使是这样也比merge interval复杂很多，于是
就挂了。。。

you

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

: if coding in interviews, start from the simplest cases. Then, at least, you
: can finish the coding. Then tell the interviewers the cases your codes
: cannot cover and try to optimize it.
: if you tell them a very complicate algorithm which covers a lot of cases,
: you will get into a trap and cannot finish the codes. Then the result will
: be a rejection.

g*e2013-11-04 08:11

63 楼

。
multiset用来做maxheap貌似不错！
不知道heap在stil里标准的data structure是什么

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

: Exactly
: Skyline 的解法貌似是（没记错的话）：
: 把所有的turning points 放在一起，根据coordination从小到大sort 。
: struct turnpoint {
: int ptr; //coordinate;
: bool startOrEnd;
: int volume
: }
: 再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
: volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。

n*e2013-11-04 08:11

64 楼

C++ STL 里面有：
std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
很少用到

f*p2013-11-04 08:11

65 楼

不是accumulated volume是max volume.
不过赞思路，学习。

map

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

: 第二道是 interval 相加，O(nlgn)
: 具体做法是:
: 用 map 将所有端点排序, 其中右端的 volume 为负值，然后扫描 map
: 一遍即可.

z*n2013-11-04 08:11

66 楼

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

: the basic idea is the same. convert each segment into 2 events, sort and
: maintain some states

d*n2013-11-04 08:11

67 楼

这个不work，不信找个输入走一遍

。

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

: Exactly
: Skyline 的解法貌似是（没记错的话）：
: 把所有的turning points 放在一起，根据coordination从小到大sort 。
: struct turnpoint {
: int ptr; //coordinate;
: bool startOrEnd;
: int volume
: }
: 再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
: volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。

l*n2013-11-04 08:11

68 楼

即便不work，也应该是你来走一遍来说明如何简单的输入都不work。
何况，该solution works。虽然很多地方拿skyline problem做divide & conquer的例
子，但那样并不意味着别的思路就行不通。

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

: 这个不work，不信找个输入走一遍
:
: 。

c*p2013-11-04 08:11

69 楼

mark

n*e2013-11-04 08:11

70 楼

mark

c*n2013-11-04 08:11

71 楼

又看到喇叭的题了，不就是 skyline 么？那可是 lc 难等级的，怎么弄到店面了？

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

: 面试官有东南亚口音
: 第一题是leetcode原题，大数+1
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

l*s2013-11-04 08:11

72 楼

好题

i*s2013-11-04 08:11

73 楼

电面这么出题没意思，基本就是写报告可以看自己心情。

a*n2013-11-04 08:11

74 楼

pat

p*g2013-11-04 08:11

75 楼

这题满难的, 就算要写代码也不少, 我的思路就是每组按begin sort.
然后s1和s2合并, 出的新结果要和s3合并
合并时要以相同的begin为一组, 然后找最小的end,找到最小的end后, 可以找到这组最
大的voice,然后把这组的begin都更新为最小end+1, 然后再找下面一组

j*02013-11-04 08:11

76 楼

I have a solution here: https://github.com/jasonzhang2022/algorithm/blob/
master/src/main/java/jason/algorithm/practice/VoiceMixer.java
But it takes me at least 2 hours.