d*******8
发帖数: 785 | 1 继上周Amazon Onsite被一个三哥灭了
这次电面又被国人灭了。
具体过程是这样
前25分钟聊Research...
（真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
接下来二叉树遍历编程题，
inorder的非递归。
几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
最后20分钟讲个算法题目。
给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
每个数pair的Distance，使得这个min distance 最大化。
题目解释了半天..就剩10分想了。。
先Sort 数组，取 头尾做最初两个元素，然后K-2中做DP，但是DP我方向想错了
用f(k-1) 到f (k)，虽然知道也不对，但是一下子卡住了。
这位国人大哥也不给我提示，到了最后结束了跟我讲 从左到右 扫描做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) |
h********0
发帖数: 440 | |
g*******y
发帖数: 1930 | 3 这个DP题不难的，多练一下，总结一下DP的思路吧 |
d*******8
发帖数: 785 | 4 就是比如一个pair <1, 5>
distance就是5 |
d*******8
发帖数: 785 | 5 每次被卡住都很紧张，一片空白。心理素质太差了...
又不知道跟他套什么话才能套出暗示
【在 g*******y 的大作中提到】
: 这个DP题不难的，多练一下，总结一下DP的思路吧
|
r****o
发帖数: 1950 | 6 distance(a,b)=(b-a+1)?
【在 d*******8 的大作中提到】
: 就是比如一个pair <1, 5>
: distance就是5
|
d*******8
发帖数: 785 | 7 应该是4，就是b-a
用矩阵预算出distance是不是会快点，但是也不好排那个combination
【在 r****o 的大作中提到】
: distance(a,b)=(b-a+1)?
|
r****o
发帖数: 1950 | 8 这个min distance是所有子集里面任意一个pair的distance的最小值吗？
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
d*******8
发帖数: 785 | 9 是的
【在 r****o 的大作中提到】
: 这个min distance是所有子集里面任意一个pair的distance的最小值吗？
|
k**o
发帖数: 3006 | 10 我猜一个，假设是个数组A[1..n]，每次遇到第i个元素的时候，有两种可能
1）A[i]不被选中，那么结果同opt(i-1, k)
2）A[i]被选中，那么结果同opt(j, k-1) where j
minimized (A[x] in opt(j, k-1))
【在 g*******y 的大作中提到】
: 这个DP题不难的，多练一下，总结一下DP的思路吧
|
|
|
k**o
发帖数: 3006 | 11 自己纠正一下
好像有点问题啊……
还需要再推敲
【在 k**o 的大作中提到】
: 我猜一个，假设是个数组A[1..n]，每次遇到第i个元素的时候，有两种可能
: 1）A[i]不被选中，那么结果同opt(i-1, k)
: 2）A[i]被选中，那么结果同opt(j, k-1) where j: minimized (A[x] in opt(j, k-1))
|
r****o
发帖数: 1950 | 12 是不是子集不一定是连续的元素组成？
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
d*******8
发帖数: 785 | 13 对的， 不是均匀分布，可以很离散的
比如 1， 100， 111， 112， 113.
开始我妄图用2分做，直接被他这个例子给灭了。
【在 r****o 的大作中提到】
: 是不是子集不一定是连续的元素组成？
|
t******t
发帖数: 2404 | 14 这到底啥意思: 子集每个数pair的Distance
最后20分钟讲个算法题目。
给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
每个数pair的Distance，使得这个min distance 最大化。 |
d*******8
发帖数: 785 | 15 K数目的子集，有 K（k-1）/2的Pair，某个Pair有个distance, 里面最小的distance
是这个子集的 Min distance
开头我听成了mean distance,又废了几分钟。。
【在 t******t 的大作中提到】
: 这到底啥意思: 子集每个数pair的Distance
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
: 每个数pair的Distance，使得这个min distance 最大化。
|
r****o
发帖数: 1950 | 16 可是不管K是多少， 我们都可以找出distance最小的一对数出来，让这个K数目的子集
包括这对数啊?
是不是我理解得不对？
【在 d*******8 的大作中提到】
: K数目的子集，有 K（k-1）/2的Pair，某个Pair有个distance, 里面最小的distance
: 是这个子集的 Min distance
: 开头我听成了mean distance,又废了几分钟。。
|
k**o
发帖数: 3006 | 17 是minmax吧……
应该是minimize the diameter of the set, I guess?
【在 r****o 的大作中提到】
: 可是不管K是多少， 我们都可以找出distance最小的一对数出来，让这个K数目的子集
: 包括这对数啊?
: 是不是我理解得不对？
|
r****o
发帖数: 1950 | 18 是我理解错题目了。
【在 k**o 的大作中提到】
: 是minmax吧……
: 应该是minimize the diameter of the set, I guess?
|
d*******8
发帖数: 785 | 19 但是最后要求是这个min distance 为最大的这样一个K子集。
【在 r****o 的大作中提到】
: 可是不管K是多少， 我们都可以找出distance最小的一对数出来，让这个K数目的子集
: 包括这对数啊?
: 是不是我理解得不对？
|
B*****t
发帖数: 335 | 20 Don't worry. Just move on!
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
|
|
d*******8
发帖数: 785 | 21 手头的面试机会已经用光了。
找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
类文本文件啊。
我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
【在 B*****t 的大作中提到】
: Don't worry. Just move on!
|
r**u
发帖数: 1567 | 22 hang on，苦练内功，你要做到小羊那样，google不招你就没天理了。
【在 d*******8 的大作中提到】
: 手头的面试机会已经用光了。
: 找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
: 也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
: 没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
: 类文本文件啊。
: 我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
: 看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
|
r****o
发帖数: 1950 | 23 那道DP题目谁能讲讲思路吗?
【在 r**u 的大作中提到】
: hang on，苦练内功，你要做到小羊那样，google不招你就没天理了。
|
x***y
发帖数: 633 | 24 For the last problem, after sorting, if we select one number, the array is
divided into 2 parts, and consider taking numbers from each part. So, the dp
is
f(k, l, r) =max_{l<=i<=r, 0<=p<=k-1}
{min(f(p+1, l, i), f(k-p, i, r))};
with some boundary conditions if r-l+1 |
P*******e
发帖数: 1353 | 25 comfort, maybe it is not as worse as you thought. good luck
【在 d*******8 的大作中提到】
: 手头的面试机会已经用光了。
: 找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
: 也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
: 没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
: 类文本文件啊。
: 我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
: 看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
|
d*******8
发帖数: 785 | 26 二分是不对的，因为DP中K-1到K的子集里可能每个元素都不一样。
dp
, r)= min distance of any two adjacent numbers.
【在 x***y 的大作中提到】
: For the last problem, after sorting, if we select one number, the array is
: divided into 2 parts, and consider taking numbers from each part. So, the dp
: is
: f(k, l, r) =max_{l<=i<=r, 0<=p<=k-1}
: {min(f(p+1, l, i), f(k-p, i, r))};
: with some boundary conditions if r-l+1
|
d*******8
发帖数: 785 | 27 我觉得那个式子应该是对的，虽然复杂度是n^4
【在 r****o 的大作中提到】
: 那道DP题目谁能讲讲思路吗?
|
c********t
发帖数: 1756 | |
c********t
发帖数: 1756 | |
P*******e
发帖数: 1353 | 30 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
distance，知道有k-1个distance在vector里面，这样结果也对吧？
【在 d*******8 的大作中提到】
: 二分是不对的，因为DP中K-1到K的子集里可能每个元素都不一样。
:
: dp
: , r)= min distance of any two adjacent numbers.
|
|
|
x***y
发帖数: 633 | 31 This is not divide and conquer...The idea is that suppose that if the number A[i
] is selected, then we have to select p numbers from A[1:i] and q numbers
from A[i:M]
such that p+q=k+1 as i must be selected in both sub arrays.
We calculate the value for each A[i] 1<=i<=M, select the max one.
【在 d*******8 的大作中提到】
: 二分是不对的，因为DP中K-1到K的子集里可能每个元素都不一样。
:
: dp
: , r)= min distance of any two adjacent numbers.
|
d*******8
发帖数: 785 | 32 对的，这个表达更简洁点，复杂度也是一样的。刚才没有仔细看，不好意思
number A[i
【在 x***y 的大作中提到】
: This is not divide and conquer...The idea is that suppose that if the number A[i
: ] is selected, then we have to select p numbers from A[1:i] and q numbers
: from A[i:M]
: such that p+q=k+1 as i must be selected in both sub arrays.
: We calculate the value for each A[i] 1<=i<=M, select the max one.
|
m********l
发帖数: 190 | 33 我也是这样，特别是遇到听不懂的啊三，就开始胡言乱语。。。
【在 d*******8 的大作中提到】
: 每次被卡住都很紧张，一片空白。心理素质太差了...
: 又不知道跟他套什么话才能套出暗示
|
d*******8
发帖数: 785 | 34 应该是对的吧，果然是小强人，好牛。
min
【在 P*******e 的大作中提到】
: 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
: distance，知道有k-1个distance在vector里面，这样结果也对吧？
|
n******r
发帖数: 1247 | 35 第二题按照你的思路的话，每次往set里面加i，j两个数？k是奇数呢？
感觉应该每次只加一个数，dp的公式还要复杂
Min(
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
r****o
发帖数: 1950 | 36 请问为什么是merge interval with min distance啊？
是不是应该merge interval with max distance，这样min distance最大。
min
【在 P*******e 的大作中提到】
: 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
: distance，知道有k-1个distance在vector里面，这样结果也对吧？
|
n******r
发帖数: 1247 | 37 试试看这个例子
1 2 3 4 5 7 9 10 k=4
最优解应该是
1 4 7 10
如果一直merge最小的distance，最后可能算出来
1 5 7 10
min
【在 P*******e 的大作中提到】
: 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
: distance，知道有k-1个distance在vector里面，这样结果也对吧？
|
r****o
发帖数: 1950 | 38 请问distance vector是不是n个元素两两之间的距离，也就是说要算O(n^2)次？
min
【在 P*******e 的大作中提到】
: 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
: distance，知道有k-1个distance在vector里面，这样结果也对吧？
|
n******r
发帖数: 1247 | 39 排序过后，对某个被选中的元素，只要算和它相邻的两个被选中的元素的距离就可以了
，和其他距离肯定更大，对题目没有影响
是O(n)
【在 r****o 的大作中提到】
: 请问distance vector是不是n个元素两两之间的距离，也就是说要算O(n^2)次？
:
: min
|
d*******8
发帖数: 785 | 40 是的，那个j可以不用的，
f(k,head,end) = max_{for i in head+1, end-k}min{dis(head,i), f(k-1,i,end)}
【在 n******r 的大作中提到】
: 第二题按照你的思路的话，每次往set里面加i，j两个数？k是奇数呢？
: 感觉应该每次只加一个数，dp的公式还要复杂
:
: Min(
|
|
|
n******r
发帖数: 1247 | 41 恩，这个应该对了，和xnxky的一样，更简洁
【在 d*******8 的大作中提到】
: 是的，那个j可以不用的，
: f(k,head,end) = max_{for i in head+1, end-k}min{dis(head,i), f(k-1,i,end)}
|
g*******y
发帖数: 1930 | 42 复杂度还可以再降一个维度
1,i,end)}
【在 d*******8 的大作中提到】
: 是的，那个j可以不用的，
: f(k,head,end) = max_{for i in head+1, end-k}min{dis(head,i), f(k-1,i,end)}
|
g*******y
发帖数: 1930 | 43 事实上，还可以进一步优化，我觉得可以做到 n*k*logn
【在 g*******y 的大作中提到】
: 复杂度还可以再降一个维度
:
: 1,i,end)}
|
d*******8
发帖数: 785 | 44 求赐教，logn的话就要Divide&conquer了，每次怎么分呢？
【在 g*******y 的大作中提到】
: 事实上，还可以进一步优化，我觉得可以做到 n*k*logn
|
n******r
发帖数: 1247 | 45 xnxky给的方法就是吧
【在 d*******8 的大作中提到】
: 求赐教，logn的话就要Divide&conquer了，每次怎么分呢？
|
g*******y
发帖数: 1930 | 46 不是div conq
你先做到 n^2*k的时间复杂度，再考虑怎么做n->logn加速
【在 d*******8 的大作中提到】
: 求赐教，logn的话就要Divide&conquer了，每次怎么分呢？
|
d*******8
发帖数: 785 | 47 但是他的方法里i是从l遍历到r的，
第一个i的selection不能马上确定的吧...
【在 n******r 的大作中提到】
: xnxky给的方法就是吧
|
n******r
发帖数: 1247 | 48 一分为二以后两边都可以递归啊
【在 d*******8 的大作中提到】
: 但是他的方法里i是从l遍历到r的，
: 第一个i的selection不能马上确定的吧...
|
d*******8
发帖数: 785 | 49 两分是不对呀，因为你不确定中间那个是不是在最后的Set里...
【在 n******r 的大作中提到】
: 一分为二以后两边都可以递归啊
|
d*******8
发帖数: 785 | 50 原来那个DP难道不是n*k吗？每次scan n个item, DP是K次。
【在 g*******y 的大作中提到】
: 不是div conq
: 你先做到 n^2*k的时间复杂度，再考虑怎么做n->logn加速
|
|
|
d*******8
发帖数: 785 | 51 错了，是n^2*k.
【在 d*******8 的大作中提到】
: 原来那个DP难道不是n*k吗？每次scan n个item, DP是K次。
|
d*******8
发帖数: 785 | 52 忘记加上那个求Max的复杂度了。
再好好想想
【在 g*******y 的大作中提到】
: 不是div conq
: 你先做到 n^2*k的时间复杂度，再考虑怎么做n->logn加速
|
g*******y
发帖数: 1930 | 53 嗯，我看错了，你的那个是n^n^k的
不过你完全不需要把end作为f()的parameter
那么怎么在这个基础上再做一个log加速？
【在 d*******8 的大作中提到】
: 错了，是n^2*k.
|
g*******y
发帖数: 1930 | 54 建议你不要在f()的参数里面写一个end，这个东西让我差点误以为你的复杂度是k*n^3
你自己可以看到，你的end这个参数自始至终都没有变过
【在 d*******8 的大作中提到】
: 忘记加上那个求Max的复杂度了。
: 再好好想想
|
d*******8
发帖数: 785 | 55 对的，是不要end的
是的，是没有变，因为一开始想的是两个头都要变的，后来发现不用的。
【在 g*******y 的大作中提到】
: 建议你不要在f()的参数里面写一个end，这个东西让我差点误以为你的复杂度是k*n^3
: 你自己可以看到，你的end这个参数自始至终都没有变过
|
B*****t
发帖数: 335 | 56 this is right！在head到end之间进行二分，还可以降低复杂度了。
注意到dist(head, i)
and f(k-1, i, end)>=f(k-1, j, end) for i
【在 d*******8 的大作中提到】
: 是的，那个j可以不用的，
: f(k,head,end) = max_{for i in head+1, end-k}min{dis(head,i), f(k-1,i,end)}
|
d*******8
发帖数: 785 | 57 我还是没想明白， 这个复杂度， DP是不是n*k,算Max那个不是乘上n的复杂度，
还是n*k+n吧，搞糊涂了。
【在 g*******y 的大作中提到】
: 嗯，我看错了，你的那个是n^n^k的
: 不过你完全不需要把end作为f()的parameter
: 那么怎么在这个基础上再做一个log加速？
|
g*******y
发帖数: 1930 | 58 correct！
【在 B*****t 的大作中提到】
: this is right！在head到end之间进行二分，还可以降低复杂度了。
: 注意到dist(head, i): and f(k-1, i, end)>=f(k-1, j, end) for i
|
B*****t
发帖数: 335 | 59 不用着急，车到山前必有路！
简历茫无目的的随便投好像也不好，建议联系一下hunter。
可以到linkedin上去找找，很多hunter的review都很不错。
good luck！
【在 d*******8 的大作中提到】
: 手头的面试机会已经用光了。
: 找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
: 也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
: 没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
: 类文本文件啊。
: 我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
: 看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
|
r****o
发帖数: 1950 | 60 不好意思我没看太明白，
你的大概意思是不是跟下面差不多？
A(i,j)表示前i个元素里面，可以找出j大小的子集的min pair distance的最大值。
A(i,j)=Max_{k=j-1...i-1}{ Min{A(k,j-1),dist(a[k], a[i]))}
【在 d*******8 的大作中提到】
: 是的，那个j可以不用的，
: f(k,head,end) = max_{for i in head+1, end-k}min{dis(head,i), f(k-1,i,end)}
|
|
|
d*******8
发帖数: 785 | 61 Bingbo，就是要求dist(head,i) 和 f(k-1,i,end)靠近相等，这个想法好。
【在 B*****t 的大作中提到】
: this is right！在head到end之间进行二分，还可以降低复杂度了。
: 注意到dist(head, i): and f(k-1, i, end)>=f(k-1, j, end) for i
|
d*******8
发帖数: 785 | 62 E关于求这个复杂度， 求验证下，以前算法课学的都忘记了。
DP中的States这里应该是logn^k 用了两分的话，
加上外面那个算Max的，应该还是要算的。是n*logn^k.
【在 d*******8 的大作中提到】
: 我还是没想明白， 这个复杂度， DP是不是n*k,算Max那个不是乘上n的复杂度，
: 还是n*k+n吧，搞糊涂了。
|
d*******8
发帖数: 785 | 63 谢谢，可能找工作还没真正用心吧，总报着侥幸心理
反正对工作期望不高，有个Offer就行了。
linkedin中是搜到hunter就加好友发消息吗？之前都没怎么试过。
【在 B*****t 的大作中提到】
: 不用着急，车到山前必有路！
: 简历茫无目的的随便投好像也不好，建议联系一下hunter。
: 可以到linkedin上去找找，很多hunter的review都很不错。
: good luck！
|
r****o
发帖数: 1950 | 64 大侠们能不能看看我的想法对不对。
【在 r****o 的大作中提到】
: 不好意思我没看太明白，
: 你的大概意思是不是跟下面差不多？
: A(i,j)表示前i个元素里面，可以找出j大小的子集的min pair distance的最大值。
: A(i,j)=Max_{k=j-1...i-1}{ Min{A(k,j-1),dist(a[k], a[i]))}
|
d*******8
发帖数: 785 | 65 这个应该对的，你这个从尾部开始scan的
【在 r****o 的大作中提到】
: 大侠们能不能看看我的想法对不对。
|
B*****t
发帖数: 335 | 66 我比较土，不会用linkedin，这个方法是同学告诉我的。
不过我近来在dice，monster上投简历，很多hunter都会给你搭讪。把他们的名字搞过
来后，然后到linkined上search。好的hunter都用linkedin，而且reviews不错，你可
以参考一下，决定是穷追猛打，还是急流勇退。
【在 d*******8 的大作中提到】
: 谢谢，可能找工作还没真正用心吧，总报着侥幸心理
: 反正对工作期望不高，有个Offer就行了。
: linkedin中是搜到hunter就加好友发消息吗？之前都没怎么试过。
|
r****o
发帖数: 1950 | 67 我这个是从左到右scan的啊。
还有，你说的那个二分在这里怎么用啊？
【在 d*******8 的大作中提到】
: 这个应该对的，你这个从尾部开始scan的
|
r****o
发帖数: 1950 | 68 还想问一下，这个DP算法都是算出最优值，但是怎么输出那些数字呢?
有什么好办法没有?
【在 d*******8 的大作中提到】
: 这个应该对的，你这个从尾部开始scan的
|
d*******8
发帖数: 785 | 69 看BlueAnt的那个帖子
【在 r****o 的大作中提到】
: 我这个是从左到右scan的啊。
: 还有，你说的那个二分在这里怎么用啊？
|
d*******8
发帖数: 785 | 70 明白了，我现在先LinkedIn的Profile开始弄弄，都是空白的。唉，太懒了。
【在 B*****t 的大作中提到】
: 我比较土，不会用linkedin，这个方法是同学告诉我的。
: 不过我近来在dice，monster上投简历，很多hunter都会给你搭讪。把他们的名字搞过
: 来后，然后到linkined上search。好的hunter都用linkedin，而且reviews不错，你可
: 以参考一下，决定是穷追猛打，还是急流勇退。
|
|
|
r****o
发帖数: 1950 | 71 能不能说说为什么靠近相等比较好啊？
【在 d*******8 的大作中提到】
: Bingbo，就是要求dist(head,i) 和 f(k-1,i,end)靠近相等，这个想法好。
|
d*******8
发帖数: 785 | 72 因为i 从左到右移的时候，dis(head,i) 肯定是相等或增加的
f(k-1,i,end）是相等或减少的
如果要使这两个中的最小值最大化的话
比如 我取 i = n/2, 如果dis(head,i) > f(k-1,i)
这个极优值必然在 [1,i]之间，所以在前半部分找
直到 [head,end] end-head = 1的时候，比较这两个Case就好了
【在 r****o 的大作中提到】
: 能不能说说为什么靠近相等比较好啊？
|
B*****t
发帖数: 335 | 73 最后分析一下复杂度吧
DP方程f(k,a,b) = max{{for a
每算一个状态点f(k,a,b)用O(log(b-a)), 一共有O(k*n*n)个这样的点，复杂度
O(n*n*klogn)
【在 d*******8 的大作中提到】
: E关于求这个复杂度， 求验证下，以前算法课学的都忘记了。
: DP中的States这里应该是logn^k 用了两分的话，
: 加上外面那个算Max的，应该还是要算的。是n*logn^k.
|
d*******8
发帖数: 785 | 74 恩，终于搞明白了，DP是用bottom up算复杂度的所以每个状态点只要求一次。
多谢
【在 B*****t 的大作中提到】
: 最后分析一下复杂度吧
: DP方程f(k,a,b) = max{{for a: 每算一个状态点f(k,a,b)用O(log(b-a)), 一共有O(k*n*n)个这样的点，复杂度
: O(n*n*klogn)
|
r****o
发帖数: 1950 | 75 明白了，多谢多谢！
【在 d*******8 的大作中提到】
: 因为i 从左到右移的时候，dis(head,i) 肯定是相等或增加的
: f(k-1,i,end）是相等或减少的
: 如果要使这两个中的最小值最大化的话
: 比如 我取 i = n/2, 如果dis(head,i) > f(k-1,i)
: 这个极优值必然在 [1,i]之间，所以在前半部分找
: 直到 [head,end] end-head = 1的时候，比较这两个Case就好了
|
r****o
发帖数: 1950 | 76 不是可以降到2维吗？
最后复杂度可以到O(n*k*logn)吧。
【在 B*****t 的大作中提到】
: 最后分析一下复杂度吧
: DP方程f(k,a,b) = max{{for a: 每算一个状态点f(k,a,b)用O(log(b-a)), 一共有O(k*n*n)个这样的点，复杂度
: O(n*n*klogn)
|
B*****t
发帖数: 335 | 77 Thanks for pointing out！更正一下！
DP方程f(k,a,b) = max{...}
b点是不动点，这道题里面b永远等于n，一共有O(k*n)个这样的状态点，复杂度O(k*n*
logn)
【在 r****o 的大作中提到】
: 不是可以降到2维吗？
: 最后复杂度可以到O(n*k*logn)吧。
|
s*****e
发帖数: 36 | 78 Hi, is there some method other than DP?
For example, compute distance of each pair (i,j) first and then sort these
pair distances (increasing order). Then starting from the end, count how
many numbers have been selected until K numbers are selected. And then the
distance of the last selected pair is the max one.
How do you guys think out of using DP? If I am given this question in a
phone interview, I will have no idea ya.
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
g*****e
发帖数: 282 | 79 牛人们的dp不太看得懂。这个subset到底是M里任意k个数，还是array里连续k个。如果
是任意k个不是npc？
【在 B*****t 的大作中提到】
: Thanks for pointing out！更正一下！
: DP方程f(k,a,b) = max{...}
: b点是不动点，这道题里面b永远等于n，一共有O(k*n)个这样的状态点，复杂度O(k*n*
: logn)
|
s******n
发帖数: 21 | |
|
|
s******5
发帖数: 673 | 81
I phone interviewed with people from google research group as well. That
dude keeps saying "fine and that is good" when I was trying to polish my
code.
But it turned out I got a rejection after 2 hours.
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
g****n
发帖数: 431 | 82 这个题不能用DP，因为不具备DP的性质。比如对于k长度的子集，最优解是ans(i, j, k
)，那么去掉
最优解中的一个元素后，剩下的k-1个元素并不是在(i,j)范围里子集长度为k-1的最优
解。虽然你可以
遍历去掉哪个元素，但只要不具备这个性质，用DP做就是错的。 |
A*H
发帖数: 127 | 83 minmax 之类的题目都可以用二分思想来作，比如那个linear partition问题 |
j********x
发帖数: 2330 | 84 路过瞻仰一下版大。。。
dist(A[x], A[i]) is
【在 k**o 的大作中提到】
: 我猜一个，假设是个数组A[1..n]，每次遇到第i个元素的时候，有两种可能
: 1）A[i]不被选中，那么结果同opt(i-1, k)
: 2）A[i]被选中，那么结果同opt(j, k-1) where j: minimized (A[x] in opt(j, k-1))
|
V*****i
发帖数: 92 | 85 This is not right, you have to make sure that all K(K-1)/2 pairs are
selected, which is not a easy task itself.
【在 s*****e 的大作中提到】
: Hi, is there some method other than DP?
: For example, compute distance of each pair (i,j) first and then sort these
: pair distances (increasing order). Then starting from the end, count how
: many numbers have been selected until K numbers are selected. And then the
: distance of the last selected pair is the max one.
: How do you guys think out of using DP? If I am given this question in a
: phone interview, I will have no idea ya.
|
s*******e
发帖数: 93 | 86 大概一个月之前的一个帖子很相似
http://www.mitbbs.com/article_t1/JobHunting/31717591_0_1.html
感觉这两道题会其中一道另外一道也就不难了。
所以lesson就是mit上的题都要仔细看，弄明白。我看到这个帖子之后也是反应了很久
才想到怎么做，估计面试的情况下是也会fail的。看来看mit的效率还有待提高。。
多谢楼主分享。learned a lot from this post and the discussions |
c*****n
发帖数: 96 | 87 先对数组排序（升序），
1）首先考虑最简单的情况： |K| = M, 原数组即为答案。
2）再考虑 |K| = M -1：即需要在原数组中去掉一个元素。我们可以对数组中相邻的两
个元素的差值排序: = a[i+1] - a[i]. 假设 是最小值，那么要去掉
的元素是:
a[j] : if a[j] - a[j-1] <= a[j+2] - a[j+1]
a[j+1] : if a[j+2] - a[j+1] < a[j] - a[j-1]
边界条件： if j == 0, then select a[j+1]
if j+1 == M-1 then select a[j]
假设a[i]是要去掉的元素， 在数组中去掉啊a[i]， 得到集合T（M-1）
3） |K| = M - 2: 可以归纳为在 T(M-1) 中找 M-2个数的子集， 从而可以用 step 2
的方法求得。 以此类推可以得到任意子集的解 |
V*****i
发帖数: 92 | 88 This is not correct. For example M = 5, K = 3 and the number is {1, 5, 6, 8,
11}. Obviously, the subset is {1, 6,
11}. But according to your solution, you will delete 6 first.
【在 c*****n 的大作中提到】
: 先对数组排序（升序），
: 1）首先考虑最简单的情况： |K| = M, 原数组即为答案。
: 2）再考虑 |K| = M -1：即需要在原数组中去掉一个元素。我们可以对数组中相邻的两
: 个元素的差值排序: = a[i+1] - a[i]. 假设 是最小值，那么要去掉
: 的元素是:
: a[j] : if a[j] - a[j-1] <= a[j+2] - a[j+1]
: a[j+1] : if a[j+2] - a[j+1] < a[j] - a[j-1]
:
: 边界条件： if j == 0, then select a[j+1]
: if j+1 == M-1 then select a[j]
|
j*******a
发帖数: 61 | 89 Based on dawenxi88 and Kyro's idea, my more detailed pseudo code is:
Assume input is a[].
//return a set (array) storing the indices of the
//elements having max min distance.
int* GetMaxMinDistanceSet(int* a, int k)
{
Set returnedSet; // the final set of indices to return.
int maxMinDistance=INT_MIN; // store the max min distance.
for(int i=k-2; i
{
//compute opt(i,k-1) to be reused in later iterations.
//List GetCombinations(array, end, n) returns the combinations
//of n elements in array ending at "end". For example, if array =
// [1,2,3, 4], end=2, n=2, this function returns the indice
// sets: {0,1},{0,2}{1,2}.
foreach(Set s in GetCombinations(a, k-2, k-1))
{
//MinDistancesOfK_1 is the array to store
//min distances for sets having k-1 elements.
MinDistancesOfK_1[s] = GetMinDistance(s);
}
//compute min distance
if(i>k-2)
{
Set returnCandidate;
int localMin=MAX_INT;
foreach(Set s in GetCombinations(a, i-1, k-1))
{
if(localMin
{
localMin= min(localMin);
returnCandidate = s + a[i];
}
foreach(int t in s)
{
localMin= min(localMin, distance(a[i], a[t]);
}
}
//update max min distance
if(maxMinDistance
{
maxMinDistance=localMin;
returnedSet = returnCandidate
}
}
}
return returnedSet;
}
【在 k**o 的大作中提到】
: 我猜一个，假设是个数组A[1..n]，每次遇到第i个元素的时候，有两种可能
: 1）A[i]不被选中，那么结果同opt(i-1, k)
: 2）A[i]被选中，那么结果同opt(j, k-1) where j: minimized (A[x] in opt(j, k-1))
|
j*******a
发帖数: 61 | 90 Based on dawenxi88 and Kyro's idea, my more detailed pseudo code is:
Assume input is a[].
//return a set (array) storing the indices of the
//elements having max min distance.
int* GetMaxMinDistanceSet(int* a, int k)
{
Set returnedSet; // the final set of indices to return.
int maxMinDistance=INT_MIN; // store the max min distance.
for(int i=k-2; i
{
//compute opt(i,k-1) to be reused in later iterations.
//List GetCombinations(array, end, n) returns the combinations
//of n elements in array ending at "end". For example, if array =
// [1,2,3, 4], end=2, n=2, this function returns the indice
// sets: {0,1},{0,2}{1,2}.
foreach(Set s in GetCombinations(a, k-2, k-1))
{
//MinDistancesOfK_1 is the array to store
//min distances for sets having k-1 elements.
MinDistancesOfK_1[s] = GetMinDistance(s);
}
//compute min distance
if(i>k-2)
{
Set returnCandidate;
int localMin=MAX_INT;
foreach(Set s in GetCombinations(a, i-1, k-1))
{
if(localMin
{
localMin= min(localMin);
returnCandidate = s union i;
}
foreach(int t in s)
{
localMin= min(localMin, distance(a[i], a[t]);
}
}
//update max min distance
if(maxMinDistance
{
maxMinDistance=localMin;
returnedSet = returnCandidate
}
}
}
return returnedSet;
} |
|
|
j*******a
发帖数: 61 | 91 Based on dawenxi88 and Kyro's idea, my more detailed pseudo code is:
Assume input is a[].
//return a set (array) storing the indices of the
//elements having max min distance.
int* GetMaxMinDistanceSet(int* a, int k)
{
Set returnedSet; // the final set of indices to return.
int maxMinDistance=INT_MIN; // store the max min distance.
for(int i=k-2; i
{
//compute opt(i,k-1) to be reused in later iterations.
//List GetCombinations(array, end, n) returns the combinations
//of n elements in array ending at "end". For example, if array =
// [1,2,3, 4], end=2, n=2, this function returns the indice
// sets: {0,1},{0,2}{1,2}.
foreach(Set s in GetCombinations(a, k-2, k-1))
{
//MinDistancesOfK_1 is the array to store
//min distances for sets having k-1 elements.
MinDistancesOfK_1[s] = GetMinDistance(s);
}
//compute min distance
if(i>k-2)
{
Set returnCandidate;
int localMin=MAX_INT;
foreach(Set s in GetCombinations(a, i-1, k-1))
{
if(localMin
{
localMin= min(localMin);
returnCandidate = s union i;
}
foreach(int t in s)
{
localMin= min(localMin, distance(a[i], a[t]);
}
}
//update max min distance
if(maxMinDistance
{
maxMinDistance=localMin;
returnedSet = returnCandidate
}
}
}
return returnedSet;
} |
h***o
发帖数: 2321 | 92 too hard for an interview question
【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
|
