不用处方就能买contact网站 - 未名空间MITBBS历史存档

b*d2010-03-04 08:03

1 楼

有几个题，觉得有点意思。
1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
能有指向自己的edge。
2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
到至少一个duplicate，constant space，linear time。
3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
每条数据3个replica，无single point of failure，能自动修复replica上的failure
。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
结构，但我给的是p2p。

y*o2010-03-04 08:03

2 楼

以前有MM贴过一个不用处方就能买contact网站，忘记了，有哪个MM能一下吗？
谢谢

l*a2010-03-04 08:03

3 楼

不会图
array[array[i]] ...
什么叫single point of failure?

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

: 有几个题，觉得有点意思。
: 1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
: 能有指向自己的edge。
: 2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
: 到至少一个duplicate，constant space，linear time。
: 3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
: 每条数据3个replica，无single point of failure，能自动修复replica上的failure
: 。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
: 结构，但我给的是p2p。

m*z2010-03-04 08:03

4 楼

帮顶帮顶，我也想知道

N*N2010-03-04 08:03

5 楼

1 贴个别人的答案：
任何node的degree<=7
所以假设degree两两不同，那么 sum(Degree)=0+1+2..+6=35
但是这个和应该是edge数目的2倍，所以不应该是奇数

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

: 有几个题，觉得有点意思。
: 1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
: 能有指向自己的edge。
: 2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
: 到至少一个duplicate，constant space，linear time。
: 3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
: 每条数据3个replica，无single point of failure，能自动修复replica上的failure
: 。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
: 结构，但我给的是p2p。

x*o2010-03-04 08:03

6 楼

aalens.com
softlenseeye.com

l*c2010-03-04 08:03

7 楼

1. 要是没有两个有同样的degree，那么每个node至少要有1个degree，那么7个node，
最大的degree的那个node至少degree=7. 可是一个图里面每个node最多degree是6.
是这样的吗？

y*o2010-03-04 08:03

8 楼

谢谢！

N*N2010-03-04 08:03

9 楼

degree可以是0，不一定是connected graph

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

: 1. 要是没有两个有同样的degree，那么每个node至少要有1个degree，那么7个node，
: 最大的degree的那个node至少degree=7. 可是一个图里面每个node最多degree是6.
: 是这样的吗？

U*m2010-03-04 08:03

10 楼

多谢,老早就想要买了!!

l*c2010-03-04 08:03

11 楼

啊？我对图不了解。如果0也可以的话，
0+1+...+6 = odd
1+2+...+7 = odd， odd不可能，
这样理解应该可以了。

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

: degree可以是0，不一定是connected graph

p*y2010-03-04 08:03

12 楼

请问这两个网站可靠不？

g*y2010-03-04 08:03

13 楼

第二题，只能想到linear的算法。
def find_duplicates(array):
assert array

for i in range(len(array)):
assert 0 <= array[i] < len(array)
while i != array[i]:
if array[array[i]] == array[i]:
return array[i]
else:
array[array[i]], array[i] = array[i], array[array[i]]

return None

o*o2010-03-04 08:03

14 楼

同问：）谢谢

N*N2010-03-04 08:03

15 楼

是不是不允许self loop？
如果不允许，那么degree最高是6
如果允许的话，这样的edge让degree+2
http://en.wikipedia.org/wiki/Loop_(graph_theory)
最高degree是8，就可以有反例了。。
比如：
a b c d e f g
a
b 1
c 1 1
d 1 1 1
e 1 1 1 1
f 1 1 2 1
g 1 1 1 1 1 2
这样a到g的degree分别是 0 1 2 3 4 5 7 。。。。。

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

: 啊？我对图不了解。如果0也可以的话，
: 0+1+...+6 = odd
: 1+2+...+7 = odd， odd不可能，
: 这样理解应该可以了。

b*i2010-03-04 08:03

16 楼

mark

b*d2010-03-04 08:03

17 楼

~~~
忘了说，是的，不能指向self。

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

: 是不是不允许self loop？
: 如果不允许，那么degree最高是6
: 如果允许的话，这样的edge让degree+2
: http://en.wikipedia.org/wiki/Loop_(graph_theory)
: 最高degree是8，就可以有反例了。。
: 比如：
: a b c d e f g
: a
: b 1
: c 1 1

y*o2010-03-04 08:03

18 楼

我已经在softlenseeye.com上下订了，等货到了我来更新！

g*m2010-03-04 08:03

19 楼

1应该对任何图都成立吧，不局限于7 nodes
N nodes，所有点的degree要么0...N-2，要么1...N-1，只有N-1种可能，所以至少有两
个点度数相同。

d*t2010-03-04 08:03

20 楼

眼睛有散光，能用contact吗？

N*N2010-03-04 08:03

21 楼

对，只要是simple grapha
http://www.student.math.uwaterloo.ca/~math239/winter2008/t7sol.

【在 g***m 的大作中提到】

: 1应该对任何图都成立吧，不局限于7 nodes
: N nodes，所有点的degree要么0...N-2，要么1...N-1，只有N-1种可能，所以至少有两
: 个点度数相同。

h*y2010-03-04 08:03

22 楼

同问

g*y2010-03-04 08:03

23 楼

第二题，只能想到linear的算法。
def find_duplicates(array):
assert array

for i in range(len(array)):
assert 0 <= array[i] < len(array)
while i != array[i]:
if array[array[i]] == array[i]:
return array[i]
else:
array[array[i]], array[i] = array[i], array[array[i]]

return None

s*d2010-03-04 08:03

24 楼

有散光的，但不一定能fit你，一定要去验光试。

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

: 眼睛有散光，能用contact吗？

a*x2010-03-04 08:03

25 楼

第二题：
sum = SUM(array a)
rangeSum = sum from 0 to (n - 2)
sum - rangeSum = what we need
example: given [0, 3, 3, 2, 1]
we have sum = 9
rangeSum = (0 + 3) * 4 / 2 = 6
sum - rangeSum = 3
done

failure
worker

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

: 有几个题，觉得有点意思。
: 1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
: 能有指向自己的edge。
: 2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
: 到至少一个duplicate，constant space，linear time。
: 3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
: 每条数据3个replica，无single point of failure，能自动修复replica上的failure
: 。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
: 结构，但我给的是p2p。

S*y2010-03-04 08:03

26 楼

奇怪，这个网站我这里显示不存在。
期待mm的更新噢。

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

: 我已经在softlenseeye.com上下订了，等货到了我来更新！

l*a2010-03-04 08:03

27 楼

RE

【在 g***m 的大作中提到】

: 1应该对任何图都成立吧，不局限于7 nodes
: N nodes，所有点的degree要么0...N-2，要么1...N-1，只有N-1种可能，所以至少有两
: 个点度数相同。

y*o2010-03-04 08:03

28 楼

看一下日期，发帖那天3/4下的单，今天3/25收到货，三个星期这样，虽然慢点，不过
东西收到了，东西也完好。明天开始用，再上来汇报。

l*a2010-03-04 08:03

29 楼

It does not work on [1, 3, 3, 2, 2]
sum = 11
rangeSum = 6
sum - rangeSum = 5

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

: 第二题：
: sum = SUM(array a)
: rangeSum = sum from 0 to (n - 2)
: sum - rangeSum = what we need
: example: given [0, 3, 3, 2, 1]
: we have sum = 9
: rangeSum = (0 + 3) * 4 / 2 = 6
: sum - rangeSum = 3
: done
:

a*x2010-03-04 08:03

30 楼

好吧，我錯了

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

: It does not work on [1, 3, 3, 2, 2]
: sum = 11
: rangeSum = 6
: sum - rangeSum = 5

h*92010-03-04 08:03

31 楼

Yes, because degree 0 and degree 6 can not coexist in a graph with 7 nodes
without loops.

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

: 1. 要是没有两个有同样的degree，那么每个node至少要有1个degree，那么7个node，
: 最大的degree的那个node至少degree=7. 可是一个图里面每个node最多degree是6.
: 是这样的吗？

n*s2010-03-04 08:03

32 楼

failure
worker
第2个题目应该是在原数组上操作，只要一个额外的空间用来交换
一开始的时候有一个指针指向第1个元素，这个元素是几就把他跟几号位上数的互换
任何元素只可能跟他后面的互换，要是跟他前面的互换就说明有重复了

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

: 有几个题，觉得有点意思。
: 1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
: 能有指向自己的edge。
: 2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
: 到至少一个duplicate，constant space，linear time。
: 3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
: 每条数据3个replica，无single point of failure，能自动修复replica上的failure
: 。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
: 结构，但我给的是p2p。

p*e2010-03-04 08:03

33 楼

Node的degree只能是0到6，如果没有0，那么7个node的degrees必定有两个相同的。
如果有一个是0，剩下的6个node中如果有0 degree，那么相同degree的node找到, 0
degree，如果没有0 degree, 6个degree分到1-5中，必定有两个相同

e*e2010-03-04 08:03

34 楼

public int findDuplicate(int[] a) {
if ( a == null || a.length < 2 )
return -1;

for ( int i = 0; i < a.length; i++ ) {
if ( a[i] == i )
continue;
else if ( a[a[i]] == a[i] || a[i] < i )
return a[i];
else {
int tmp = a[i];
a[i] = a[a[i]];
a[tmp] = tmp;
i--;
}
}

return -1;
}

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

:
: failure
: worker
: 第2个题目应该是在原数组上操作，只要一个额外的空间用来交换
: 一开始的时候有一个指针指向第1个元素，这个元素是几就把他跟几号位上数的互换
: 任何元素只可能跟他后面的互换，要是跟他前面的互换就说明有重复了

w*o2010-03-04 08:03

35 楼

因为有i--,不能保证在循环a.length次之前结束，试试{4，0，1，2，3}，要loop9次。

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

:
: public int findDuplicate(int[] a) {
: if ( a == null || a.length < 2 )
: return -1;
:
: for ( int i = 0; i < a.length; i++ ) {
: if ( a[i] == i )
: continue;
: else if ( a[a[i]] == a[i] || a[i] < i )
: return a[i];

w*o2010-03-04 08:03

36 楼

可以借用Counting Sort的思想，但是标准的Counting Sort要用O（n)的空间。稍改一
下，可以借用已有的Array的空间。也就是a[i] = x * n + y; x 是i在Array里出现的
次数，而y是原来的a[i]的值。
假设没有overflow:
public int findDuplicate(int[] a) {
if ( a == null || a.length < 2 )
return -1;

int n = a.length;
for(int i = 0; i < n; i++) {
int x = a[i] % n;
int y = a[x] / n;
if (y > 0)
return x;
else
a[x] += n;
}
return -1;
}
保证在n次loop内结束。而且可以很容易恢复到原数组。

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

: 有几个题，觉得有点意思。
: 1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
: 能有指向自己的edge。
: 2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
: 到至少一个duplicate，constant space，linear time。
: 3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
: 每条数据3个replica，无single point of failure，能自动修复replica上的failure
: 。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
: 结构，但我给的是p2p。

e*e2010-03-04 08:03

37 楼

That's quite a piece of work. Good job.

【在 w***o 的大作中提到】

: 可以借用Counting Sort的思想，但是标准的Counting Sort要用O（n)的空间。稍改一
: 下，可以借用已有的Array的空间。也就是a[i] = x * n + y; x 是i在Array里出现的
: 次数，而y是原来的a[i]的值。
: 假设没有overflow:
: public int findDuplicate(int[] a) {
: if ( a == null || a.length < 2 )
: return -1;
:
: int n = a.length;
: for(int i = 0; i < n; i++) {

w*o2010-03-04 08:03

38 楼

谢谢。
其实还可以再好一点。用+n有overflow的危险如果n很大的话。
可以用negative来表示该数已出现过。不过要考虑0的情况，因为 0 = -0。

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

: That's quite a piece of work. Good job.

f*42010-03-04 08:03

39 楼

题3的failure-fix 是接口get/put的切换么, 还是生成一份新的冗余呢?

failure
worker

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

: 有几个题，觉得有点意思。
: 1. 证明任意一个7个node的无向graph，至少两个node拥有同样的degree。每个node不
: 能有指向自己的edge。
: 2. 一个array，size n，里面的数都属于range[0, n-1]，有unknown的duplicates，找
: 到至少一个duplicate，constant space，linear time。
: 3. 设计一个persistence系统对外提供get（key）， put（key，value）的功能，要求
: 每条数据3个replica，无single point of failure，能自动修复replica上的failure
: 。基本是distributed system的课堂讨论题。可以是p2p结构，也可以是server-worker
: 结构，但我给的是p2p。