a********3
发帖数: 228 | 1 对方是印度人，俺在电话里听印度英语还是有那么点困难，有两个问题让人家重复了几次，不知道会不会减印象分。。。
1. Given an image and a query rectangle, calculate the average intensity within the rectangle. (coding)
If we have one millions of queries in one minute, how can we do the queries faster and use less space?
他push了我三次想不同优化的方法。第一次我想了一个减少时间的算法。第二次我说用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次他提示我有只占O(N^2)空间的cache，问我怎么实现。
2. To find a minimum number in an unsorted array, we need to compare min with each number and update min if necessary. Calculat |
h*t
发帖数: 505 | 2 不是，也有一两周才有下一轮的
【在 a********3 的大作中提到】
: 对方是印度人，俺在电话里听印度英语还是有那么点困难，有两个问题让人家重复了几次，不知道会不会减印象分。。。
: 1. Given an image and a query rectangle, calculate the average intensity within the rectangle. (coding)
: If we have one millions of queries in one minute, how can we do the queries faster and use less space?
: 他push了我三次想不同优化的方法。第一次我想了一个减少时间的算法。第二次我说用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次他提示我有只占O(N^2)空间的cache，问我怎么实现。
: 2. To find a minimum number in an unsorted array, we need to compare min with each number and update min if necessary. Calculat
|
a********3
发帖数: 228 | 3 谢谢回答，我是申intern，一次电面就是两轮technical interview。
【在 h*t 的大作中提到】
: 不是，也有一两周才有下一轮的
|
m*******i
发帖数: 370 | 4 能不能贡献一下题目啊？多谢！
【在 a********3 的大作中提到】
: 谢谢回答，我是申intern，一次电面就是两轮technical interview。
|
a********3
发帖数: 228 | 5 等晚上我写吧，现在实验室都是偷偷上bbs的。都是从一道简单题目开始，然后说如果
查询数据量很大怎么办，让你不断的优化时空复杂度。
【在 m*******i 的大作中提到】
: 能不能贡献一下题目啊？多谢！
|
m*****f
发帖数: 1243 | 6 这个不一定把， 看recruiter了
【在 a********3 的大作中提到】
: 等晚上我写吧，现在实验室都是偷偷上bbs的。都是从一道简单题目开始，然后说如果
: 查询数据量很大怎么办，让你不断的优化时空复杂度。
|
r****o
发帖数: 1950 | 7 第一题的intensity是什么意思啊？
几次，不知道会不会减印象分。。。
within the rectangle. (coding)
queries faster and use less space?
用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次
他提示我有只占O(N^2)空间的cache，问我怎么实现。
with each number and update min if necessary. Calculate the expected number
of times you need to update min. Explain how you calculate it.
【在 a********3 的大作中提到】
: 对方是印度人，俺在电话里听印度英语还是有那么点困难，有两个问题让人家重复了几次，不知道会不会减印象分。。。
: 1. Given an image and a query rectangle, calculate the average intensity within the rectangle. (coding)
: If we have one millions of queries in one minute, how can we do the queries faster and use less space?
: 他push了我三次想不同优化的方法。第一次我想了一个减少时间的算法。第二次我说用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次他提示我有只占O(N^2)空间的cache，问我怎么实现。
: 2. To find a minimum number in an unsorted array, we need to compare min with each number and update min if necessary. Calculat
|
B*****t
发帖数: 335 | 8 k>2时， O(N*logk)并不是最好的solution |
w******k
发帖数: 917 | 9 两个45分钟就三道题么?
【在 a********3 的大作中提到】
: 谢谢回答，我是申intern，一次电面就是两轮technical interview。
|
c****s
发帖数: 241 | 10 我感觉计算了distance之后，维持一个k大小的heap。这样可以做到O(nlogk)。
应该不会有更快的了吧？您老还有什么更好的方法？
【在 B*****t 的大作中提到】
: k>2时， O(N*logk)并不是最好的solution
|
|
|
B*****t
发帖数: 335 | 11 可以做到只比较N+logN+loglogN+...(一共有k项）次， 当k接近N/2时，显然要比nlogk
的算法快， 缺点是可能要多一点儿的空间， 不过也不一定。
【在 c****s 的大作中提到】
: 我感觉计算了distance之后，维持一个k大小的heap。这样可以做到O(nlogk)。
: 应该不会有更快的了吧？您老还有什么更好的方法？
|
l*******t
发帖数: 642 | 12 compute the distance of each point to the given point, O(N),
find k-th distance, O(N),
find all distances less than the k-th distance, O(N).
【在 c****s 的大作中提到】
: 我感觉计算了distance之后，维持一个k大小的heap。这样可以做到O(nlogk)。
: 应该不会有更快的了吧？您老还有什么更好的方法？
|
c**********e
发帖数: 2007 | 13
with each number and update min if necessary. Calculate the expected number
of times you need to update min. Explain how you calculate it.
1/2 + 1/3 + ... + 1/n.
【在 a********3 的大作中提到】
: 等晚上我写吧，现在实验室都是偷偷上bbs的。都是从一道简单题目开始，然后说如果
: 查询数据量很大怎么办，让你不断的优化时空复杂度。
|
G**********s
发帖数: 70 | |
r****o
发帖数: 1950 | 15 第1题的intensity是什么意思啊？
第2题有谁算出答案吗？
几次，不知道会不会减印象分。。。
within the rectangle. (coding)
queries faster and use less space?
用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次
他提示我有只占O(N^2)空间的cache，问我怎么实现。
with each number and update min if necessary. Calculate the expected number
of times you need to update min. Explain how you calculate it.
【在 a********3 的大作中提到】
: 对方是印度人，俺在电话里听印度英语还是有那么点困难，有两个问题让人家重复了几次，不知道会不会减印象分。。。
: 1. Given an image and a query rectangle, calculate the average intensity within the rectangle. (coding)
: If we have one millions of queries in one minute, how can we do the queries faster and use less space?
: 他push了我三次想不同优化的方法。第一次我想了一个减少时间的算法。第二次我说用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次他提示我有只占O(N^2)空间的cache，问我怎么实现。
: 2. To find a minimum number in an unsorted array, we need to compare min with each number and update min if necessary. Calculat
|
f*******5
发帖数: 52 | 16 第二题有个做法不知道对不对：
求update次数的数学期望。当第一个数为min时，update次数0；当第一个数为倒数第i小的
数时，update次数i-1。倒数第i小的数作为第一个数概率为(n-1)!/n!=1/n。
所以update次数数学期望是 Sum_i{(i-1)*1/n}=n*(n-1)/2/n=(n-1)/2
number
【在 r****o 的大作中提到】
: 第1题的intensity是什么意思啊？
: 第2题有谁算出答案吗？
:
: 几次，不知道会不会减印象分。。。
: within the rectangle. (coding)
: queries faster and use less space?
: 用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次
: 他提示我有只占O(N^2)空间的cache，问我怎么实现。
: with each number and update min if necessary. Calculate the expected number
: of times you need to update min. Explain how you calculate it.
|
l******x
发帖数: 163 | 17 给个第二题我的想法，大家讨论下
let Xi = 1 if a update of min needed at A[i], w.p. Pr{ith comparision
invloves a update of min}
= 0 if no update of min needed
Pr{ith comparision invloves a update of min} = Pr{ith number is the min of A
[1...i]} = 1/i
E[X] = sum Xi = 1 + 1/2 + ... + 1/n
number
【在 r****o 的大作中提到】
: 第1题的intensity是什么意思啊？
: 第2题有谁算出答案吗？
:
: 几次，不知道会不会减印象分。。。
: within the rectangle. (coding)
: queries faster and use less space?
: 用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次
: 他提示我有只占O(N^2)空间的cache，问我怎么实现。
: with each number and update min if necessary. Calculate the expected number
: of times you need to update min. Explain how you calculate it.
|
B*****t
发帖数: 335 | 18 想复杂了。第i个数与min比较进行update的概率是1/2, 总共有n-1次比较， answer is
(n-1)/2
i小的
【在 f*******5 的大作中提到】
: 第二题有个做法不知道对不对：
: 求update次数的数学期望。当第一个数为min时，update次数0；当第一个数为倒数第i小的
: 数时，update次数i-1。倒数第i小的数作为第一个数概率为(n-1)!/n!=1/n。
: 所以update次数数学期望是 Sum_i{(i-1)*1/n}=n*(n-1)/2/n=(n-1)/2
:
: number
|
B*****t
发帖数: 335 | 19
几次，不知道会不会减印象分。。。
within the rectangle. (coding)
queries faster and use less space?
用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次
他提示我有只占O(N^2)空间的cache，问我怎么实现。
这个题用一个O(N^2)空间存储到原点的total intensity， 用DP加加减减一下再除以面
积就是 average intensity。 BWY， 图像处理中的典型处理方法
【在 a********3 的大作中提到】
: 对方是印度人，俺在电话里听印度英语还是有那么点困难，有两个问题让人家重复了几次，不知道会不会减印象分。。。
: 1. Given an image and a query rectangle, calculate the average intensity within the rectangle. (coding)
: If we have one millions of queries in one minute, how can we do the queries faster and use less space?
: 他push了我三次想不同优化的方法。第一次我想了一个减少时间的算法。第二次我说用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次他提示我有只占O(N^2)空间的cache，问我怎么实现。
: 2. To find a minimum number in an unsorted array, we need to compare min with each number and update min if necessary. Calculat
|
r****o
发帖数: 1950 | 20 请问为什么第i个数与min比较进行update的概率是1/2啊？
is
【在 B*****t 的大作中提到】
: 想复杂了。第i个数与min比较进行update的概率是1/2, 总共有n-1次比较， answer is
: (n-1)/2
:
: i小的
|
|
|
o*******7
发帖数: 13 | 21
how?
【在 l*******t 的大作中提到】
: compute the distance of each point to the given point, O(N),
: find k-th distance, O(N),
: find all distances less than the k-th distance, O(N).
|
l*******t
发帖数: 642 | 22 CLRS, Chapter 9.3
【在 o*******7 的大作中提到】
:
: how?
|
r****o
发帖数: 1950 | 23 这个方法理论上是O(n),但是我觉得实现起来很麻烦啊。如果面试的时候说这个是不是
不太好？
【在 l*******t 的大作中提到】
: CLRS, Chapter 9.3
|
U********o
发帖数: 132 | 24 thanks
【在 l*******t 的大作中提到】
: CLRS, Chapter 9.3
|
l*******t
发帖数: 642 | 25 You are right. You can just mention that it could be done in O(N) and make
it your showtime.
【在 r****o 的大作中提到】
: 这个方法理论上是O(n),但是我觉得实现起来很麻烦啊。如果面试的时候说这个是不是
: 不太好？
|
g*******y
发帖数: 1930 | 26 我怎么觉得你理解的题目的意思跟我理解的不一样呢？我觉得调和级数的解是对的呢
对了，有个假定，处理第一个数的时候，假定是要算1次update
很容易验证调和级数的解是正确的，试试3个数的情况：
123 update次数:1
132 update次数:1
213 update次数:2
231 update次数:2
312 update次数:2
321 update次数:3
平均: 11/6 = 1 + 1/2 + 1/3
is
【在 B*****t 的大作中提到】
: 想复杂了。第i个数与min比较进行update的概率是1/2, 总共有n-1次比较， answer is
: (n-1)/2
:
: i小的
|
e********c
发帖数: 66 | 27 It is not that complicated to explain. See wikipedia.
http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements
【在 l*******t 的大作中提到】
: You are right. You can just mention that it could be done in O(N) and make
: it your showtime.
|
B*****t
发帖数: 335 | 28 恩，按你这样理解题意的话，结果应该是调和级数，我想interviewer要的应该是这个
结果。
【在 g*******y 的大作中提到】
: 我怎么觉得你理解的题目的意思跟我理解的不一样呢？我觉得调和级数的解是对的呢
: 对了，有个假定，处理第一个数的时候，假定是要算1次update
: 很容易验证调和级数的解是正确的，试试3个数的情况：
: 123 update次数:1
: 132 update次数:1
: 213 update次数:2
: 231 update次数:2
: 312 update次数:2
: 321 update次数:3
: 平均: 11/6 = 1 + 1/2 + 1/3
|
B*****t
发帖数: 335 | 29 题意理解有误，结果应该是调和级数
【在 r****o 的大作中提到】
: 请问为什么第i个数与min比较进行update的概率是1/2啊？
:
: is
|
P****i
发帖数: 1362 | 30 调和级数是对的
【在 B*****t 的大作中提到】
: 题意理解有误，结果应该是调和级数
|
|
|
B*****t
发帖数: 335 | 31 对于给定的k<
个并不能保证前者O(N)的常数项一定小于小于后者的吧？尤其是在最坏的情况下
【在 l*******t 的大作中提到】
: compute the distance of each point to the given point, O(N),
: find k-th distance, O(N),
: find all distances less than the k-th distance, O(N).
|
U********o
发帖数: 132 | 32 nod
【在 B*****t 的大作中提到】
: 题意理解有误，结果应该是调和级数
|
a********3
发帖数: 228 | 33 您真牛，我要早点有人给我讲就好了。我对image processing的knowledge几乎为0，所
以当他让我算intensity时，我就问他intensity是啥玩意
【在 B*****t 的大作中提到】
: 对于给定的k<: 个并不能保证前者O(N)的常数项一定小于小于后者的吧？尤其是在最坏的情况下
|
r****o
发帖数: 1950 | 34 什么是intensity啊？
【在 a********3 的大作中提到】
: 您真牛，我要早点有人给我讲就好了。我对image processing的knowledge几乎为0，所
: 以当他让我算intensity时，我就问他intensity是啥玩意
|
a********3
发帖数: 228 | 35 一个image就相当于一个matrix，matrix的每一个cell都有一个intensity值，用通俗的
话讲就是算一个大matrix里一个小矩形matrix的average value。
我也是问了他好几分钟才搞明白，问题其实简单，就是优化的算法如果以前没接触不容
易想到。
【在 r****o 的大作中提到】
: 什么是intensity啊？
|
w******k
发帖数: 917 | 36 喜欢你的泥称
祝福
【在 a********3 的大作中提到】
: 一个image就相当于一个matrix，matrix的每一个cell都有一个intensity值，用通俗的
: 话讲就是算一个大matrix里一个小矩形matrix的average value。
: 我也是问了他好几分钟才搞明白，问题其实简单，就是优化的算法如果以前没接触不容
: 易想到。
|
a********3
发帖数: 228 | 37 我答的不是调和级数，可是面试官没有纠正我啊。我答的是\sum_i{n-i/n}，就是到第i
个数后面需要更新min的概率是n-i/n，assume第一个数设置为min不算update。
【在 P****i 的大作中提到】
: 调和级数是对的
|
a********3
发帖数: 228 | 38 谢谢，我是找intern，面试前没怎么复习，找不到以后正式找工作还要好好复习。
【在 w******k 的大作中提到】
: 喜欢你的泥称
: 祝福
|
g*****u
发帖数: 298 | 39 这不就是调和级数么？
第i
【在 a********3 的大作中提到】
: 我答的不是调和级数，可是面试官没有纠正我啊。我答的是\sum_i{n-i/n}，就是到第i
: 个数后面需要更新min的概率是n-i/n，assume第一个数设置为min不算update。
|
P**********0
发帖数: 412 | |
