l****p
发帖数: 397 | 1 先是问还有几年毕业，确定面试的是实习。然后开始在白板上做题。
第一题：找出二维平面上相互重叠的长方形。我先给出个O(n^2)的算法。要求我优化成
O(n)。一再提示可以多用空间，还是没解出来
第二题：找出柱型图中最大的长方形。觉得可以用动态规划，但还是没解出来 |
s*******e
发帖数: 1630 | 2 第一题中长方形是正放的还是可以是旋转的？输入是什么数据结构？ |
l*n
发帖数: 529 | 3 如此黑你啊，且不说第二题是最难的面试题之一，第一题根本就没有o(n)解法吧。
http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
http://stackoverflow.com/questions/4542892/possible-interview-q
怎么着也得要o(nlogn)吧。
【在 l****p 的大作中提到】
: 先是问还有几年毕业，确定面试的是实习。然后开始在白板上做题。
: 第一题：找出二维平面上相互重叠的长方形。我先给出个O(n^2)的算法。要求我优化成
: O(n)。一再提示可以多用空间，还是没解出来
: 第二题：找出柱型图中最大的长方形。觉得可以用动态规划，但还是没解出来
|
g*********e
发帖数: 14401 | |
z*********8
发帖数: 2070 | |
l*n
发帖数: 529 | 6 第一次见的话，都会比较confuse，都会试图搞个优于O(n^2)的解法，即使O(n^2)都不
是显而易见。
【在 z*********8 的大作中提到】
: 第二题还是满常见的吧
: 当然没见过的话是不可能当场写出来的。 能写出来的也不会去微软
|
l****p
发帖数: 397 | 7 正放
Input: (x00, y00, x01, y01), (x10, y10, x11, y11), ...
each rectangle is represented by its top-left and bottom-right coordinates.
【在 s*******e 的大作中提到】
: 第一题中长方形是正放的还是可以是旋转的？输入是什么数据结构？
|
s********u
发帖数: 1109 | |
l****p
发帖数: 397 | 9 Really? That adds to my bad impression about the interviewer.
The interviewer was really impatient. Although he didn't say it, his face
was saying like "hey, you are a PhD in CS, how come you couldn't work out
such simple questions?"
【在 l*n 的大作中提到】
: 如此黑你啊，且不说第二题是最难的面试题之一，第一题根本就没有o(n)解法吧。
: http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
: http://stackoverflow.com/questions/4542892/possible-interview-q
: 怎么着也得要o(nlogn)吧。
|
l****p
发帖数: 397 | 10 No, latino
【在 g*********e 的大作中提到】
: 对方是阿三吗？
|
|
|
l****p
发帖数: 397 | 11 For the first question, I worked out an O(nlogn) solution in the interview
actually, but he insisted an O(n)...
【在 l*n 的大作中提到】
: 如此黑你啊，且不说第二题是最难的面试题之一，第一题根本就没有o(n)解法吧。
: http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
: http://stackoverflow.com/questions/4542892/possible-interview-q
: 怎么着也得要o(nlogn)吧。
|
t******n
发帖数: 19 | 12 第一题我肯定当场想不出O(n) 的算法的. hehe
第二题,如果用DP, 应该是O(n^2)的. 有点像最大1子矩阵那个题. 如果不知道用递增
stack的话, 肯定是想不出O(n)算法的.
这个interviewer是挺黑的. 两个题都不容易, 尤其第一题还要O(n)的算法.
【在 l****p 的大作中提到】
: 先是问还有几年毕业，确定面试的是实习。然后开始在白板上做题。
: 第一题：找出二维平面上相互重叠的长方形。我先给出个O(n^2)的算法。要求我优化成
: O(n)。一再提示可以多用空间，还是没解出来
: 第二题：找出柱型图中最大的长方形。觉得可以用动态规划，但还是没解出来
|
l*n
发帖数: 529 | 13 呃，莫非你现在有能O(n)搞定的高见？
【在 t******n 的大作中提到】
: 第一题我肯定当场想不出O(n) 的算法的. hehe
: 第二题,如果用DP, 应该是O(n^2)的. 有点像最大1子矩阵那个题. 如果不知道用递增
: stack的话, 肯定是想不出O(n)算法的.
: 这个interviewer是挺黑的. 两个题都不容易, 尤其第一题还要O(n)的算法.
|
h****y
发帖数: 137 | 14 微软来我们这campus interview就是给个超简单的hash table题就叫onsite了
【在 l****p 的大作中提到】
: 先是问还有几年毕业，确定面试的是实习。然后开始在白板上做题。
: 第一题：找出二维平面上相互重叠的长方形。我先给出个O(n^2)的算法。要求我优化成
: O(n)。一再提示可以多用空间，还是没解出来
: 第二题：找出柱型图中最大的长方形。觉得可以用动态规划，但还是没解出来
|
e*******8
发帖数: 94 | 15 第一题没有O(n)的解法吧：别说二维的，就是一维的（检查给定的一堆线段中
overlap的线段）也没有。一维的问题可以reduce成uniqueness的问题，
uniqueness在comparison model下至少也要o(n log n).
而且我觉得这个问题本身就有问题啊：比如最坏的情况下，可能输入的rectangle两两
相overlap，那样的话怎么都要\Omega(n^2)的时间复杂度呀。觉得最好也就能达到O(n
log n + k)了（k是实际overlap的rectangle pair的个数）
【在 l****p 的大作中提到】
: For the first question, I worked out an O(nlogn) solution in the interview
: actually, but he insisted an O(n)...
|
c********p
发帖数: 1969 | |
l*n
发帖数: 529 | 17 严重怀疑interviewer以为有个什么nb的hash函数能帮你判断overlapping。
~~~good point.
【在 e*******8 的大作中提到】
: 第一题没有O(n)的解法吧：别说二维的，就是一维的（检查给定的一堆线段中
: overlap的线段）也没有。一维的问题可以reduce成uniqueness的问题，
: uniqueness在comparison model下至少也要o(n log n).
: 而且我觉得这个问题本身就有问题啊：比如最坏的情况下，可能输入的rectangle两两
: 相overlap，那样的话怎么都要\Omega(n^2)的时间复杂度呀。觉得最好也就能达到O(n
: log n + k)了（k是实际overlap的rectangle pair的个数）
|
M*********r
发帖数: 70 | 18 第一题能介绍下nlog(n)怎么做吗？或者给个link也可以。多谢了！ |
l****p
发帖数: 397 | 19 If you could identify overlapping intervals in one dimension, then you could
first get the overlapping intervals in x and y axis, and find rectangles
that overlap on both their x and y axis.
Finding overlapping intervals in one dimension requires O(nlogn), according
to the stackoverflow link posted above http://stackoverflow.com/questions/4542892/possible-interview-question-how-to-find-all-overlapping-intervals/9775727#9775727
Intersecting two sets can be done in O(n) with the help of hashing. So
overall is O(nlogn).
Just an idea of the top of my head.
【在 M*********r 的大作中提到】
: 第一题能介绍下nlog(n)怎么做吗？或者给个link也可以。多谢了！
|
l****p
发帖数: 397 | 20 Just got an email from the recruiter that I passed the interview, and am
invited to on-site one.
Never interview with MS before, but I guess this is their style: have a
crappy interviewer asking freaking questions to make you feel bad, and then
let you pass... |
s****n
发帖数: 147 | |
M*********r
发帖数: 70 | 22 懂了，多谢。
楼主加油！Good luck！
could
according
【在 l****p 的大作中提到】
: If you could identify overlapping intervals in one dimension, then you could
: first get the overlapping intervals in x and y axis, and find rectangles
: that overlap on both their x and y axis.
: Finding overlapping intervals in one dimension requires O(nlogn), according
: to the stackoverflow link posted above http://stackoverflow.com/questions/4542892/possible-interview-question-how-to-find-all-overlapping-intervals/9775727#9775727
: Intersecting two sets can be done in O(n) with the help of hashing. So
: overall is O(nlogn).
: Just an idea of the top of my head.
|
