s*******n
发帖数: 97 | 1 Design a system to store heap on multiple machines ? What is avg number of
machines accessed per operation and number of elements stored in a machine ?
First greater number in an array. Given a large array of positive integers,
for an arbitrary integer A, we want to know the first integer in the array
which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80
Given an N-by-N array of black (1) and white (0) pixels, find the |
h*******e
发帖数: 1377 | |
g*******y
发帖数: 1930 | 3 注意题目不是找largest square，所以不是DP。
这个题目讨论过的。
我个人觉得，如果事先没做过任何题目，面试的时候要想到O(N^2)解是相当难的
【在 h*******e 的大作中提到】
: 3 是DP吧
|
m*****f
发帖数: 1243 | 4 第二题怎么做?
原数组既然无序, 扫描一遍都要O(n)阿, 怎么能在O(logn)内找到呢? |
h*******e
发帖数: 1377 | 5 一般面的时候就得写算法吧,我感觉10-15分钟把算法白板写出来而且不错需要相当的训
练了.
【在 g*******y 的大作中提到】
: 注意题目不是找largest square，所以不是DP。
: 这个题目讨论过的。
: 我个人觉得，如果事先没做过任何题目，面试的时候要想到O(N^2)解是相当难的
|
c*********n
发帖数: 1057 | 6 能给点解题的思路么？或者square的DP解法
【在 g*******y 的大作中提到】
: 注意题目不是找largest square，所以不是DP。
: 这个题目讨论过的。
: 我个人觉得，如果事先没做过任何题目，面试的时候要想到O(N^2)解是相当难的
|
r**u
发帖数: 1567 | 7 co-ask.
【在 c*********n 的大作中提到】
: 能给点解题的思路么？或者square的DP解法
|
k***e
发帖数: 556 | 8 i think there are some conditions missing in prob 1 and prob 2
for 2, just think that I give out a number to check for first larger than
him in the array and I intentionally pick a number much larger than all the
array entries, then how could you give out the answer without checking
everyone of the array?
machine ?
,
example
【在 s*******n 的大作中提到】
: Design a system to store heap on multiple machines ? What is avg number of
: machines accessed per operation and number of elements stored in a machine ?
: First greater number in an array. Given a large array of positive integers,
: for an arbitrary integer A, we want to know the first integer in the array
: which is greater than or equal A . O(logn) solution required
: ex [2, 10,5,6,80]
: input : 6 output : 10
: input :20 output : 80
: Given an N-by-N array of black (1) and white (0) pixels, find the
|
c*****o
发帖数: 178 | 9 我觉得就是square，也不能是DP吧？k = f(k-1) f是什么？
【在 g*******y 的大作中提到】
: 注意题目不是找largest square，所以不是DP。
: 这个题目讨论过的。
: 我个人觉得，如果事先没做过任何题目，面试的时候要想到O(N^2)解是相当难的
|
k*i
发帖数: 220 | 10 只会一个 O(N^3)的...
【在 g*******y 的大作中提到】
: 注意题目不是找largest square，所以不是DP。
: 这个题目讨论过的。
: 我个人觉得，如果事先没做过任何题目，面试的时候要想到O(N^2)解是相当难的
|
|
|
b****j
发帖数: 78 | 11 Square:
二维的DP，对每个元素记录以它为右下角的最大的SQUARE的边长L
L[x][y] = min(L[x-1][y], L[x][y-1], L[x-1][y-1]) + 1 对于1的点
L[x][y] = 0 对于0的点
注意边界条件
Non-Square:
可以转化为Historgram做
【在 c*****o 的大作中提到】
: 我觉得就是square，也不能是DP吧？k = f(k-1) f是什么？
|
g*******y
发帖数: 1930 | 12 correct!
【在 b****j 的大作中提到】
: Square:
: 二维的DP，对每个元素记录以它为右下角的最大的SQUARE的边长L
: L[x][y] = min(L[x-1][y], L[x][y-1], L[x-1][y-1]) + 1 对于1的点
: L[x][y] = 0 对于0的点
: 注意边界条件
: Non-Square:
: 可以转化为Historgram做
|
X****r
发帖数: 3557 | 13 For problem 2, assume pre-processing is allowed.
the
【在 k***e 的大作中提到】
: i think there are some conditions missing in prob 1 and prob 2
: for 2, just think that I give out a number to check for first larger than
: him in the array and I intentionally pick a number much larger than all the
: array entries, then how could you give out the answer without checking
: everyone of the array?
:
: machine ?
: ,
: example
|
k***e
发帖数: 556 | 14 that makes sense
then define b[i]=max{a[1]...a[i]}, b[i] is increasing.
for given x, to find the first a[j] that a[j]>x,
do binary search of b and find index k such that b[k]<=x
then k+1 is the guy we want for x
【在 X****r 的大作中提到】
: For problem 2, assume pre-processing is allowed.
:
: the
|
m*******y
发帖数: 68 | 15 很弱的继续问，什么是Histogram，到底应该这么做？
【在 b****j 的大作中提到】
: Square:
: 二维的DP，对每个元素记录以它为右下角的最大的SQUARE的边长L
: L[x][y] = min(L[x-1][y], L[x][y-1], L[x-1][y-1]) + 1 对于1的点
: L[x][y] = 0 对于0的点
: 注意边界条件
: Non-Square:
: 可以转化为Historgram做
|
b****j
发帖数: 78 | 16 careercup上搜索histogram
【在 m*******y 的大作中提到】
: 很弱的继续问，什么是Histogram，到底应该这么做？
|
a********a
发帖数: 219 | 17 没读明白第三题，谁给解说一下？
【在 g*******y 的大作中提到】
: 注意题目不是找largest square，所以不是DP。
: 这个题目讨论过的。
: 我个人觉得，如果事先没做过任何题目，面试的时候要想到O(N^2)解是相当难的
|
m*******y
发帖数: 68 | 18 The search lead to this page:
http://www.careercup.com/question?id=198686
This seems to be about the problem of "finding the largest rectangle in a
histogram", which is a well-known ACM Programming Contest problem:
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html
Then I still cannot see how this matrix problem can be reduced to this
problem. More hints please
【在 b****j 的大作中提到】
: careercup上搜索histogram
|
c*********n
发帖数: 1057 | 19 楼住出来把题目说完整点吧
【在 m*****f 的大作中提到】
: 第二题怎么做?
: 原数组既然无序, 扫描一遍都要O(n)阿, 怎么能在O(logn)内找到呢?
|
b****j
发帖数: 78 | 20 for all rectangles (x1, y1) - (x2, y2), when y2 is fixed, you can apply the
historgram algorithm to find the one with maximized area.
【在 m*******y 的大作中提到】
: The search lead to this page:
: http://www.careercup.com/question?id=198686
: This seems to be about the problem of "finding the largest rectangle in a
: histogram", which is a well-known ACM Programming Contest problem:
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html
: Then I still cannot see how this matrix problem can be reduced to this
: problem. More hints please
|
|
|
t********e
发帖数: 25 | 21 Any one know
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1
0 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0
0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0
求内部是0，外部是1的 square 或 rectangle 应该怎么解 ？ |
r**u
发帖数: 1567 | 22 这第一题，就是弄个monitor machine，然后每个machine上搞个heap，如果要popMax，
每个machine把自己的max报给monitor，然后monitor比一下然后告诉最大的那个machie
popMAX and healify。如果要insert，就找heap size最小的machineinsert。对不？
machine ?
,
example
【在 s*******n 的大作中提到】
: Design a system to store heap on multiple machines ? What is avg number of
: machines accessed per operation and number of elements stored in a machine ?
: First greater number in an array. Given a large array of positive integers,
: for an arbitrary integer A, we want to know the first integer in the array
: which is greater than or equal A . O(logn) solution required
: ex [2, 10,5,6,80]
: input : 6 output : 10
: input :20 output : 80
: Given an N-by-N array of black (1) and white (0) pixels, find the
|
c****p
发帖数: 32 | 23 图像处理中有个简单方法叫object filling，就是横着填一遍，每两个1之间就加1，竖
着再一遍，这样你下面的就成了：
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1
0 1 0 1 1 1 1 0
0 1 0 1 1 1 1 0
0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0
竖着来一次
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1
0 1 0 1 2 2 1 0
0 1 0 1 2 2 1 0
0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0
2对应的就是你要找的。
因为只有上下有1的才会变为2，所以即便有缺口如下图，也没有关系
0 0 1 0 1 0
1 1 1 0 0 0
1 1 1 1 1 1
1 0 1 1 1 1
1 1 1 0 0 1
【在 t********e 的大作中提到】
: Any one know
: 0 0 0 0 0 0 0 0
: 0 0 0 1 1 1 1 1
: 0 1 0 1 0 0 1 0
: 0 1 0 1 0 0 1 0
: 0 0 0 1 1 1 1 0
: 0 0 0 0 0 0 0 0
: 求内部是0，外部是1的 square 或 rectangle 应该怎么解 ？
|
H*M
发帖数: 1268 | 24 错的吧？你第3/4行，第三列的两个0怎么没变加1?
【在 c****p 的大作中提到】
: 图像处理中有个简单方法叫object filling，就是横着填一遍，每两个1之间就加1，竖
: 着再一遍，这样你下面的就成了：
: 0 0 0 0 0 0 0 0
: 0 0 0 1 1 1 1 1
: 0 1 0 1 1 1 1 0
: 0 1 0 1 1 1 1 0
: 0 0 0 1 1 1 1 0
: 0 0 0 0 0 0 0 0
: 竖着来一次
: 0 0 0 0 0 0 0 0
|
c****p
发帖数: 32 | 25 忘了加了:D
加上正好证明啊，因为上下都没有，那两个就一直是1。
【在 H*M 的大作中提到】
: 错的吧？你第3/4行，第三列的两个0怎么没变加1?
|
H*M
发帖数: 1268 | 26 你说的不清楚
什么叫两个1之间加1？ 原来是1你加还是不加？
你过第一遍的时候没加，第二遍就加了
【在 c****p 的大作中提到】
: 忘了加了:D
: 加上正好证明啊，因为上下都没有，那两个就一直是1。
|
g*******y
发帖数: 1930 | 27 呵呵，这个方法我以前看到过，好像可以用来确定一个任意闭合路径的内部和外部
【在 c****p 的大作中提到】
: 图像处理中有个简单方法叫object filling，就是横着填一遍，每两个1之间就加1，竖
: 着再一遍，这样你下面的就成了：
: 0 0 0 0 0 0 0 0
: 0 0 0 1 1 1 1 1
: 0 1 0 1 1 1 1 0
: 0 1 0 1 1 1 1 0
: 0 0 0 1 1 1 1 0
: 0 0 0 0 0 0 0 0
: 竖着来一次
: 0 0 0 0 0 0 0 0
|
H*M
发帖数: 1268 | 28 你说他算法是对的啊？能不能准确描述下？我看op写的不是很清晰啊
【在 g*******y 的大作中提到】
: 呵呵，这个方法我以前看到过，好像可以用来确定一个任意闭合路径的内部和外部
|
g*******y
发帖数: 1930 | 29 他的思想就是从每个1出发，往四个方向走，每走过一个格子0，在该格子留下一个印记
，直到碰见一个格子1就停止。
这样，一个格子0如果上下左右都被格子1包围的话，那么格子1应该有4个印记
然后过滤一遍，只留下所有有4个印记的格子，然后找一个最大的rect/sq就容易了(其
实就是若干个isolated图形，找rect/square)
【在 H*M 的大作中提到】
: 你说他算法是对的啊？能不能准确描述下？我看op写的不是很清晰啊
|
H*M
发帖数: 1268 | 30 如果角的4个是0也符合吧
但是不满足题目要求阿
【在 g*******y 的大作中提到】
: 他的思想就是从每个1出发，往四个方向走，每走过一个格子0，在该格子留下一个印记
: ，直到碰见一个格子1就停止。
: 这样，一个格子0如果上下左右都被格子1包围的话，那么格子1应该有4个印记
: 然后过滤一遍，只留下所有有4个印记的格子，然后找一个最大的rect/sq就容易了(其
: 实就是若干个isolated图形，找rect/square)
|
|
|
t********e
发帖数: 25 | 31 那这个怎么办，填满了不是矩形哦。对于下面这个不存在....
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0
0 0 0 1 0 0 1 0
0 0 0 1 0 0 0 1
0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 |
