v***d
发帖数: 42 | 1 前段时间面的，在板上学习了不少，多谢大家！
总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
说剩下的4道吧……
1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
论过，非常感谢！
2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
知道描述清楚了没有…这题没写代码，讲了下思路……
3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
议室满足所有会议.注意，(4,5), (5,6)……这个输入返回true……
4. 同样的一堆会议时间，返回最少需要多少间会议室. |
l*****a
发帖数: 14598 | 2 3/4不就是merge interval吗？
也算是李抠吧
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
l*****a
发帖数: 14598 | 3 full time or intern?
ＦＢ只面三轮？
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
X****y
发帖数: 33 | 4 多谢lz， median of integer stream的思路哪里有? |
l*****a
发帖数: 14598 | 5 两个heap,一个最大堆，一个最小堆
两个size相同或差一
根据输入进行调整
【在 X****y 的大作中提到】
: 多谢lz， median of integer stream的思路哪里有?
|
v***d
发帖数: 42 | 6 3比merge interval简单……
4如果按merge interval的思路写的话，要稍微复杂了一点
【在 l*****a 的大作中提到】
: 3/4不就是merge interval吗？
: 也算是李抠吧
|
v***d
发帖数: 42 | 7 full time……master三轮，phd多一轮design
【在 l*****a 的大作中提到】
: full time or intern?
: ＦＢ只面三轮？
|
v***d
发帖数: 42 | |
l*****a
发帖数: 14598 | 9 我的意思说就是个变形而已
当然判断比merge简单。。
４用dp当然也可以
【在 v***d 的大作中提到】
: 3比merge interval简单……
: 4如果按merge interval的思路写的话，要稍微复杂了一点
|
v***d
发帖数: 42 | 10 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
++，遇到结束时间counter--……counter的最大值就是结果……
【在 l*****a 的大作中提到】
: 我的意思说就是个变形而已
: 当然判断比merge简单。。
: ４用dp当然也可以
|
|
|
f*****e
发帖数: 2992 | 11 所有题都很简单。最后三题长得很像。
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
z*******y
发帖数: 578 | 12 多谢楼主分享
这架势应该是拿了好几个大offer吧
cong！ |
p*****2
发帖数: 21240 | 13
stream内存恐怕不够吧？
【在 l*****a 的大作中提到】
: 两个heap,一个最大堆，一个最小堆
: 两个size相同或差一
: 根据输入进行调整
|
f*****e
发帖数: 2992 | 14 觉得用vectorized的balanced BST，顶多16G搞定。
【在 p*****2 的大作中提到】
:
: stream内存恐怕不够吧？
|
r****r
发帖数: 54 | 15 第二题轮廓指的是什么？
第三题有O(n)的解吗？
第四题interval tree nlogn可以解吧。还有更好的方法吗 |
A*********c
发帖数: 430 | 16 Bless lz。请问什么时候面的？
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
r****r
发帖数: 54 | 17 好想法，就像是line sweep。
第三个有O(n)的解嘛？
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
A*********c
发帖数: 430 | 18 sort based on start time， linear scan找相交。
和mege interval实际上是一样的。
【在 r****r 的大作中提到】
: 好想法，就像是line sweep。
: 第三个有O(n)的解嘛？
:
: counter
|
r****r
发帖数: 54 | 19 还是O(nlogn)
应该是极限了吧
【在 A*********c 的大作中提到】
: sort based on start time， linear scan找相交。
: 和mege interval实际上是一样的。
|
A*********c
发帖数: 430 | 20 haha, very good idea.
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
|
|
A*********c
发帖数: 430 | 21 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
Any improvements?
【在 r****r 的大作中提到】
: 还是O(nlogn)
: 应该是极限了吧
|
t*****u
发帖数: 9 | |
s********f
发帖数: 510 | 23 在特定前提下可以. 既然是会议时间,可以假设最短开会时间为X,时间总跨度为y.设一
个初始全都是0,长度为y/x 的array.把会议时间一个一个set进去.可以是O(n).不过这
样的假设就把问题简单化了，失去了算法题的意义。
【在 A*********c 的大作中提到】
: 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
: Any improvements?
|
l********5
发帖数: 230 | 24 请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。 |
c******3
发帖数: 296 | 25 好极了，第3题就判断最大值是不是一了？
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
v***d
发帖数: 42 | 26 那个链接我本来有的，但是现在点开以后，不知道为啥说，不存在了……你可以看看下
面这个
http://www.ardendertat.com/2011/11/03/programming-interview-que
【在 l********5 的大作中提到】
: 请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。
|
v***d
发帖数: 42 | 27 你可以这么做，也可以按merge interval的思路做……
【在 c******3 的大作中提到】
: 好极了，第3题就判断最大值是不是一了？
:
: counter
|
p*******2
发帖数: 50 | |
t*********7
发帖数: 255 | |
b****f
发帖数: 138 | |
|
|
p*****3
发帖数: 488 | 31 第4题明明就是graph coloring problem
Overlap的meeting就是相邻点，考的是图 |
v***d
发帖数: 42 | 32 前段时间面的，在板上学习了不少，多谢大家！
总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
说剩下的4道吧……
1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
知道描述清楚了没有…这题没写代码，讲了下思路……
3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
议室满足所有会议.注意，(4,5), (5,6)……这个输入返回true……
4. 同样的一堆会议时间，返回最少需要多少间会议室. |
l*****a
发帖数: 14598 | 33 3/4不就是merge interval吗？
也算是李抠吧
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
l*****a
发帖数: 14598 | 34 full time or intern?
ＦＢ只面三轮？
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
X****y
发帖数: 33 | 35 多谢lz， median of integer stream的思路哪里有? |
l*****a
发帖数: 14598 | 36 两个heap,一个最大堆，一个最小堆
两个size相同或差一
根据输入进行调整
【在 X****y 的大作中提到】
: 多谢lz， median of integer stream的思路哪里有?
|
v***d
发帖数: 42 | 37 3比merge interval简单……
4如果按merge interval的思路写的话，要稍微复杂了一点
【在 l*****a 的大作中提到】
: 3/4不就是merge interval吗？
: 也算是李抠吧
|
v***d
发帖数: 42 | 38 full time……master三轮，phd多一轮design
【在 l*****a 的大作中提到】
: full time or intern?
: ＦＢ只面三轮？
|
v***d
发帖数: 42 | |
l*****a
发帖数: 14598 | 40 我的意思说就是个变形而已
当然判断比merge简单。。
４用dp当然也可以
【在 v***d 的大作中提到】
: 3比merge interval简单……
: 4如果按merge interval的思路写的话，要稍微复杂了一点
|
|
|
v***d
发帖数: 42 | 41 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
++，遇到结束时间counter--……counter的最大值就是结果……
【在 l*****a 的大作中提到】
: 我的意思说就是个变形而已
: 当然判断比merge简单。。
: ４用dp当然也可以
|
f*****e
发帖数: 2992 | 42 所有题都很简单。最后三题长得很像。
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
z*******y
发帖数: 578 | 43 多谢楼主分享
这架势应该是拿了好几个大offer吧
cong！ |
p*****2
发帖数: 21240 | 44
stream内存恐怕不够吧？
【在 l*****a 的大作中提到】
: 两个heap,一个最大堆，一个最小堆
: 两个size相同或差一
: 根据输入进行调整
|
f*****e
发帖数: 2992 | 45 觉得用vectorized的balanced BST，顶多16G搞定。
【在 p*****2 的大作中提到】
:
: stream内存恐怕不够吧？
|
r****r
发帖数: 54 | 46 第二题轮廓指的是什么？
第三题有O(n)的解吗？
第四题interval tree nlogn可以解吧。还有更好的方法吗 |
A*********c
发帖数: 430 | 47 Bless lz。请问什么时候面的？
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
r****r
发帖数: 54 | 48 好想法，就像是line sweep。
第三个有O(n)的解嘛？
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
A*********c
发帖数: 430 | 49 sort based on start time， linear scan找相交。
和mege interval实际上是一样的。
【在 r****r 的大作中提到】
: 好想法，就像是line sweep。
: 第三个有O(n)的解嘛？
:
: counter
|
r****r
发帖数: 54 | 50 还是O(nlogn)
应该是极限了吧
【在 A*********c 的大作中提到】
: sort based on start time， linear scan找相交。
: 和mege interval实际上是一样的。
|
|
|
A*********c
发帖数: 430 | 51 haha, very good idea.
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
A*********c
发帖数: 430 | 52 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
Any improvements?
【在 r****r 的大作中提到】
: 还是O(nlogn)
: 应该是极限了吧
|
t*****u
发帖数: 9 | |
s********f
发帖数: 510 | 54 在特定前提下可以. 既然是会议时间,可以假设最短开会时间为X,时间总跨度为y.设一
个初始全都是0,长度为y/x 的array.把会议时间一个一个set进去.可以是O(n).不过这
样的假设就把问题简单化了，失去了算法题的意义。
【在 A*********c 的大作中提到】
: 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
: Any improvements?
|
l********5
发帖数: 230 | 55 请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。 |
c******3
发帖数: 296 | 56 好极了，第3题就判断最大值是不是一了？
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
v***d
发帖数: 42 | 57 那个链接我本来有的，但是现在点开以后，不知道为啥说，不存在了……你可以看看下
面这个
http://www.ardendertat.com/2011/11/03/programming-interview-que
【在 l********5 的大作中提到】
: 请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。
|
v***d
发帖数: 42 | 58 你可以这么做，也可以按merge interval的思路做……
【在 c******3 的大作中提到】
: 好极了，第3题就判断最大值是不是一了？
:
: counter
|
p*******2
发帖数: 50 | |
t*********7
发帖数: 255 | |
|
|
b****f
发帖数: 138 | |
p*****3
发帖数: 488 | 62 第4题明明就是graph coloring problem
Overlap的meeting就是相邻点，考的是图 |
n*********u
发帖数: 34 | 63 能扩展说说 linear scan 找相交 怎么做吗？
【在 A*********c 的大作中提到】
: sort based on start time， linear scan找相交。
: 和mege interval实际上是一样的。
|
n*********u
发帖数: 34 | 64 不对吧， 如下case：
[1...................6]
[0....2] [3...4][5.....8]
counter
【在 v***d 的大作中提到】
: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……
|
R*******d
发帖数: 13640 | 65
【在 v***d 的大作中提到】
: 前段时间面的，在板上学习了不少，多谢大家！
: 总共电面一轮，onsite3轮……半轮问resume和project，2.5轮问代码……算上电面，
: 总共面了9道，其中5道是leetcode原题，这里就不说了，刷好leetcode是关键吖……说
: 说剩下的4道吧……
: 1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
: 论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
: 2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
: 可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
: 知道描述清楚了没有…这题没写代码，讲了下思路……
: 3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
|
v***d
发帖数: 42 | 66 这个例子里，counter最大值是2……
【在 n*********u 的大作中提到】
: 不对吧， 如下case：
: [1...................6]
: [0....2] [3...4][5.....8]
:
: counter
|
d******n
发帖数: 22 | 67 为什么是2？每个开始的时间都不一样，为什么会++
【在 v***d 的大作中提到】
: 这个例子里，counter最大值是2……
|
n*********u
发帖数: 34 | 68 哦，没注意是最大值。这个应该就是sweep line的实现吧： 把每个interval平铺在时
间轴上，竖线扫描遇到相交的最大值就是最少需要的meeting room#
假如用merge interval的思路，没看出按照starting time sort有什么帮助
【在 v***d 的大作中提到】
: 这个例子里，counter最大值是2……
|
f******n
发帖数: 279 | |
