s*******n
发帖数: 97 | 1 今天开始准备amazon面试：
第一题：给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集每个
数pair的Distance，使得这个min distance 最大化。
没思路 | l*****a
发帖数: 14598 | 2 AMZN基本不会考这种题
【在 s*******n 的大作中提到】
: 今天开始准备amazon面试：
: 第一题：给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集每个
: 数pair的Distance，使得这个min distance 最大化。
: 没思路
| s*********d
发帖数: 2406 | 3 我on-site 就是靠的这题
我解了最简单的。就是一个一个求距离。
interviewer 很不满意。但是没时间了
应该用DP | p*****2
发帖数: 21240 | 4 能不能给个例子呢'没太明白
★ Sent from iPhone App: iReader Mitbbs Lite 7.39 | q******8
发帖数: 848 | | m**a
发帖数: 139 | 6 是这个意思吧：
1， 3,5,6,9,。 k=3的话 取 1,5,9，因为他们之间的最小距离是4，这个4是所有取
3个数的情况下最大的。（如果取1,3，5，的话，最小距离就是2）。
如果dp的话，k 增加到4，好像还是要扫描剩下的数字加到1,5,9里面，最后取一个最优
的。有可能增加到4的时候需要拿掉1,5,9中的一个吗？ | p*****2
发帖数: 21240 | 7 我现在能想到的就是greedy的做法，不知道有没有问题。
先把两两的distance放到一个矩阵。再一个一个有把最短distance的数字从矩阵中mark
，直到剩k个数字。
这样就是n^2logn 的复杂度 | e***s
发帖数: 799 | 8 DP好像不行，可能我想的是错的。
因为K=4的答案不是建立在K=3时的答案上面，就是说K=4的时候不应该是1，5，9中插入
一个剩下的数。
反例：
1,3,7,9,13,16,21,25,38
K=3
1,21,38
K=4
1,13,25,38
【在 m**a 的大作中提到】
: 是这个意思吧：
: 1， 3,5,6,9,。 k=3的话 取 1,5,9，因为他们之间的最小距离是4，这个4是所有取
: 3个数的情况下最大的。（如果取1,3，5，的话，最小距离就是2）。
: 如果dp的话，k 增加到4，好像还是要扫描剩下的数字加到1,5,9里面，最后取一个最优
: 的。有可能增加到4的时候需要拿掉1,5,9中的一个吗？
| j*******g
发帖数: 4 | 9 How about this:
sorting + binary search
O(mlogm + mlog(n/k))
??? | G**********s
发帖数: 70 | 10 if(k>1) & 如果 M 不是很大，
counting sort O(n),
然后 依次正向(from smallest key)取一个key
if(
iterative直到k个,O(k)
O(n+k)就是了吧？ | s*******n
发帖数: 97 | 11 太忙了，才过来看看，网上看到一个DP答案，好像挺有道理：
F（k, head, end) = Max ( for ((i in [head, end-k+1]),j in [i+k-1,end]) Min(
distanc(head,i),distance(j,end), F(k-1,i,j) )) |
|
