请问周日的报纸通常长哪儿买呀 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

请问周日的报纸通常长哪儿买呀

请问周日的报纸通常长哪儿买呀# PennySaver - 省钱一族

v*d2010-10-11 07:10

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. 同样的一堆会议时间，返回最少需要多少间会议室.

s*y2010-10-11 07:10

2 楼

就是为了找找coupon,一般只买华人报纸，都不知道老美的报纸上那里买方便，除了书
店

l*a2010-10-11 07:10

3 楼

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), 开始时间和结束时间……判断是否可以只用一个会

d*12010-10-11 07:10

4 楼

cvs，RA，菜店。

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

: 就是为了找找coupon,一般只买华人报纸，都不知道老美的报纸上那里买方便，除了书
: 店

l*a2010-10-11 07:10

5 楼

full time or intern?
ＦＢ只面三轮？

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

g*n2010-10-11 07:10

6 楼

dollar tree，便宜

X*y2010-10-11 07:10

7 楼

多谢lz， median of integer stream的思路哪里有?

m*r2010-10-11 07:10

8 楼

cvs walgreen ra 菜点
还有自动卖的地方

l*a2010-10-11 07:10

9 楼

两个heap,一个最大堆，一个最小堆
两个size相同或差一
根据输入进行调整

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

: 多谢lz， median of integer stream的思路哪里有?

s*y2010-10-11 07:10

10 楼

thanks

v*d2010-10-11 07:10

11 楼

3比merge interval简单……
4如果按merge interval的思路写的话，要稍微复杂了一点

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

: 3/4不就是merge interval吗？
: 也算是李抠吧

v*d2010-10-11 07:10

12 楼

full time……master三轮，phd多一轮design

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

: full time or intern?
: ＦＢ只面三轮？

v*d2010-10-11 07:10

13 楼

http://www.ardendertat.com/2011/11/03/programming-interview-que

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

: 多谢lz， median of integer stream的思路哪里有?

l*a2010-10-11 07:10

14 楼

我的意思说就是个变形而已
当然判断比merge简单。。
４用dp当然也可以

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

: 3比merge interval简单……
: 4如果按merge interval的思路写的话，要稍微复杂了一点

v*d2010-10-11 07:10

15 楼

4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
++，遇到结束时间counter--……counter的最大值就是结果……

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

: 我的意思说就是个变形而已
: 当然判断比merge简单。。
: ４用dp当然也可以

f*e2010-10-11 07:10

16 楼

所有题都很简单。最后三题长得很像。

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

z*y2010-10-11 07:10

17 楼

多谢楼主分享
这架势应该是拿了好几个大offer吧
cong！

p*22010-10-11 07:10

18 楼

stream内存恐怕不够吧？

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

: 两个heap,一个最大堆，一个最小堆
: 两个size相同或差一
: 根据输入进行调整

f*e2010-10-11 07:10

19 楼

觉得用vectorized的balanced BST，顶多16G搞定。

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

:
: stream内存恐怕不够吧？

r*r2010-10-11 07:10

20 楼

第二题轮廓指的是什么？
第三题有O(n)的解吗？
第四题interval tree nlogn可以解吧。还有更好的方法吗

A*c2010-10-11 07:10

21 楼

Bless lz。请问什么时候面的？

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

r*r2010-10-11 07:10

22 楼

好想法，就像是line sweep。
第三个有O(n)的解嘛？

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

A*c2010-10-11 07:10

23 楼

sort based on start time， linear scan找相交。
和mege interval实际上是一样的。

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

: 好想法，就像是line sweep。
: 第三个有O(n)的解嘛？
:
: counter

r*r2010-10-11 07:10

24 楼

还是O(nlogn)
应该是极限了吧

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

: sort based on start time， linear scan找相交。
: 和mege interval实际上是一样的。

A*c2010-10-11 07:10

25 楼

haha, very good idea.

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

A*c2010-10-11 07:10

26 楼

我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
Any improvements?

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

: 还是O(nlogn)
: 应该是极限了吧

t*u2010-10-11 07:10

27 楼

第二题有O（n^2)的么

s*f2010-10-11 07:10

28 楼

在特定前提下可以. 既然是会议时间,可以假设最短开会时间为X,时间总跨度为y.设一
个初始全都是0,长度为y/x 的array.把会议时间一个一个set进去.可以是O(n).不过这
样的假设就把问题简单化了，失去了算法题的意义。

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

: 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
: Any improvements?

l*52010-10-11 07:10

29 楼

请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。

c*32010-10-11 07:10

30 楼

好极了，第3题就判断最大值是不是一了？

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

v*d2010-10-11 07:10

31 楼

那个链接我本来有的，但是现在点开以后，不知道为啥说，不存在了……你可以看看下
面这个
http://www.ardendertat.com/2011/11/03/programming-interview-que

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

: 请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。

v*d2010-10-11 07:10

32 楼

你可以这么做，也可以按merge interval的思路做……

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

: 好极了，第3题就判断最大值是不是一了？
:
: counter

p*22010-10-11 07:10

33 楼

第二题是skyline吗

t*72010-10-11 07:10

34 楼

谢谢分享

b*f2010-10-11 07:10

35 楼

Mark

p*32010-10-11 07:10

36 楼

第4题明明就是graph coloring problem
Overlap的meeting就是相邻点，考的是图

v*d2010-10-11 07:10

37 楼

前段时间面的，在板上学习了不少，多谢大家！
总共电面一轮，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*a2010-10-11 07:10

38 楼

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*a2010-10-11 07:10

39 楼

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*y2010-10-11 07:10

40 楼

多谢lz， median of integer stream的思路哪里有?

l*a2010-10-11 07:10

41 楼

两个heap,一个最大堆，一个最小堆
两个size相同或差一
根据输入进行调整

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

: 多谢lz， median of integer stream的思路哪里有?

v*d2010-10-11 07:10

42 楼

3比merge interval简单……
4如果按merge interval的思路写的话，要稍微复杂了一点

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

: 3/4不就是merge interval吗？
: 也算是李抠吧

v*d2010-10-11 07:10

43 楼

full time……master三轮，phd多一轮design

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

: full time or intern?
: ＦＢ只面三轮？

v*d2010-10-11 07:10

44 楼

http://www.ardendertat.com/2011/11/03/programming-interview-que

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

: 多谢lz， median of integer stream的思路哪里有?

l*a2010-10-11 07:10

45 楼

我的意思说就是个变形而已
当然判断比merge简单。。
４用dp当然也可以

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

: 3比merge interval简单……
: 4如果按merge interval的思路写的话，要稍微复杂了一点

v*d2010-10-11 07:10

46 楼

: 我的意思说就是个变形而已
: 当然判断比merge简单。。
: ４用dp当然也可以

f*e2010-10-11 07:10

47 楼

所有题都很简单。最后三题长得很像。

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

z*y2010-10-11 07:10

48 楼

多谢楼主分享
这架势应该是拿了好几个大offer吧
cong！

p*22010-10-11 07:10

49 楼

stream内存恐怕不够吧？

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

: 两个heap,一个最大堆，一个最小堆
: 两个size相同或差一
: 根据输入进行调整

f*e2010-10-11 07:10

50 楼

觉得用vectorized的balanced BST，顶多16G搞定。

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

:
: stream内存恐怕不够吧？

r*r2010-10-11 07:10

51 楼

第二题轮廓指的是什么？
第三题有O(n)的解吗？
第四题interval tree nlogn可以解吧。还有更好的方法吗

A*c2010-10-11 07:10

52 楼

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*r2010-10-11 07:10

53 楼

好想法，就像是line sweep。
第三个有O(n)的解嘛？

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

A*c2010-10-11 07:10

54 楼

sort based on start time， linear scan找相交。
和mege interval实际上是一样的。

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

: 好想法，就像是line sweep。
: 第三个有O(n)的解嘛？
:
: counter

r*r2010-10-11 07:10

55 楼

还是O(nlogn)
应该是极限了吧

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

: sort based on start time， linear scan找相交。
: 和mege interval实际上是一样的。

A*c2010-10-11 07:10

56 楼

haha, very good idea.

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

A*c2010-10-11 07:10

57 楼

我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
Any improvements?

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

: 还是O(nlogn)
: 应该是极限了吧

t*u2010-10-11 07:10

58 楼

第二题有O（n^2)的么

s*f2010-10-11 07:10

59 楼

: 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
: Any improvements?

l*52010-10-11 07:10

60 楼

请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。

c*32010-10-11 07:10

61 楼

好极了，第3题就判断最大值是不是一了？

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

v*d2010-10-11 07:10

62 楼

: 请问那个讨论median的帖子谁能帮着贴一下，，，找不到了。。

v*d2010-10-11 07:10

63 楼

你可以这么做，也可以按merge interval的思路做……

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

: 好极了，第3题就判断最大值是不是一了？
:
: counter

p*22010-10-11 07:10

64 楼

第二题是skyline吗

t*72010-10-11 07:10

65 楼

谢谢分享

b*f2010-10-11 07:10

66 楼

Mark

p*32010-10-11 07:10

67 楼

第4题明明就是graph coloring problem
Overlap的meeting就是相邻点，考的是图

n*u2010-10-11 07:10

68 楼

能扩展说说 linear scan 找相交怎么做吗？

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

: sort based on start time， linear scan找相交。
: 和mege interval实际上是一样的。

n*u2010-10-11 07:10

69 楼

不对吧，如下case：
[1...................6]
[0....2] [3...4][5.....8]

counter

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

: 4的话可以把时间段拆成时间点，然后对所有时间点排序……如果遇到开始时间counter
: ++，遇到结束时间counter--……counter的最大值就是结果……

R*d2010-10-11 07:10

70 楼

【在 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*d2010-10-11 07:10

71 楼

这个例子里，counter最大值是2……

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

: 不对吧，如下case：
: [1...................6]
: [0....2] [3...4][5.....8]
:
: counter

d*n2010-10-11 07:10

72 楼

为什么是2？每个开始的时间都不一样，为什么会++

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

: 这个例子里，counter最大值是2……

n*u2010-10-11 07:10

73 楼

哦，没注意是最大值。这个应该就是sweep line的实现吧：把每个interval平铺在时
间轴上，竖线扫描遇到相交的最大值就是最少需要的meeting room#
假如用merge interval的思路，没看出按照starting time sort有什么帮助

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

: 这个例子里，counter最大值是2……