logo
Redian新闻
>未名空间
>Biology - 生物学
>
一个faculty position的信息
avatar
一个faculty position的信息# Biology - 生物学
d*8
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)
avatar
b*y
2 楼
到中信交签证费，可以让其他人带着护照原件代交吗？
avatar
C*l
3 楼
具体难度在什么地方？
avatar
s*y
4 楼
University of Notre Dame,
Department of Biological Sciences
Title: Assistant Professor
Field: Developmental Biology
http://biology.nd.edu
b*****[email protected]
这个学校去年把我据了，不过今天突然给我来信，说他们面试的几个人都不理想，
最后谁都没招，所以今年要重新再招一次，问我还愿不愿意申请。
我本来想大义凛然给他们写封据信回去的。不过后来想想还是积点人品吧。
有意的同学去和他们联系吧。那个系还挺不错的。
avatar
h*0
5 楼
comfort...
继续加油吧
avatar
d*8
6 楼
复印件就可以了，ATM机上也可以，也可以到中信银行的网站用银联的卡交（不要用中
国银行的卡）。具体的要到使馆页面上去找。

【在 b******y 的大作中提到】
: 到中信交签证费，可以让其他人带着护照原件代交吗？
avatar
l*8
7 楼
这应该算私立名校了吧：）。

【在 s******y 的大作中提到】
: University of Notre Dame,
: Department of Biological Sciences
: Title: Assistant Professor
: Field: Developmental Biology
: http://biology.nd.edu
: b*****[email protected]
: 这个学校去年把我据了，不过今天突然给我来信，说他们面试的几个人都不理想，
: 最后谁都没招，所以今年要重新再招一次，问我还愿不愿意申请。
: 我本来想大义凛然给他们写封据信回去的。不过后来想想还是积点人品吧。
: 有意的同学去和他们联系吧。那个系还挺不错的。
avatar
g*y
8 楼
这个DP题不难的，多练一下，总结一下DP的思路吧
avatar
m*i
9 楼
hehe, 体育很牛。

【在 l*******8 的大作中提到】
: 这应该算私立名校了吧：）。
avatar
d*8
10 楼
就是比如一个pair <1, 5>
distance就是5
avatar
l*8
11 楼
football嘛：）。

【在 m*****i 的大作中提到】
: hehe, 体育很牛。
avatar
d*8
12 楼
每次被卡住都很紧张，一片空白。心理素质太差了...
又不知道跟他套什么话才能套出暗示

【在 g*******y 的大作中提到】
: 这个DP题不难的，多练一下，总结一下DP的思路吧
avatar
s*y
13 楼
他们家橄榄球貌似近年很烂呢，到处被人扁的样子。
不过学校排名还是很不错的。
校园貌似也很漂亮
有意找工作的同学不妨考虑一下。

【在 l*******8 的大作中提到】
: football嘛：）。
avatar
r*o
14 楼
distance(a,b)=(b-a+1)?

【在 d*******8 的大作中提到】
: 就是比如一个pair <1, 5>
: distance就是5
avatar
m*i
15 楼
再烂也比藤校强。

【在 s******y 的大作中提到】
: 他们家橄榄球貌似近年很烂呢，到处被人扁的样子。
: 不过学校排名还是很不错的。
: 校园貌似也很漂亮
: 有意找工作的同学不妨考虑一下。
avatar
d*8
16 楼
应该是4，就是b-a
用矩阵预算出distance是不是会快点，但是也不好排那个combination

【在 r****o 的大作中提到】
: distance(a,b)=(b-a+1)?
avatar
s*y
17 楼
倒。。。算你狠。。。

【在 m*****i 的大作中提到】
: 再烂也比藤校强。
avatar
r*o
18 楼
这个min distance是所有子集里面任意一个pair的distance的最小值吗？

【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
avatar
N*S
19 楼
足球名校阿，可惜方向不对口。。。

【在 s******y 的大作中提到】
: University of Notre Dame,
: Department of Biological Sciences
: Title: Assistant Professor
: Field: Developmental Biology
: http://biology.nd.edu
: b*****[email protected]d.edu
: 这个学校去年把我据了，不过今天突然给我来信，说他们面试的几个人都不理想，
: 最后谁都没招，所以今年要重新再招一次，问我还愿不愿意申请。
: 我本来想大义凛然给他们写封据信回去的。不过后来想想还是积点人品吧。
: 有意的同学去和他们联系吧。那个系还挺不错的。
avatar
d*8
20 楼
是的

【在 r****o 的大作中提到】
: 这个min distance是所有子集里面任意一个pair的distance的最小值吗？
avatar
W*o
21 楼
是吗？我原来一个同事刚刚拿到他们系里的offer。8月份准备过去。我这同事8～9年的
薄厚。每天刻苦的不得了。4片一座的PNAS.我们领域小，冷门，出不了大文章，PNAS已
经很牛了。我就是看到他可怜的收入，（两个孩子），没有前途的千老生活，所以离开
了。终于人家拿到offer。真替他和他的家人高兴。
avatar
k*o
22 楼
我猜一个，假设是个数组A[1..n]，每次遇到第i个元素的时候，有两种可能
1）A[i]不被选中，那么结果同opt(i-1, k)
2）A[i]被选中，那么结果同opt(j, k-1) where jminimized (A[x] in opt(j, k-1))

【在 g*******y 的大作中提到】
: 这个DP题不难的，多练一下，总结一下DP的思路吧
avatar
s*y
23 楼
啊？不会吧？难道他们在耍我？可是这个有什么好耍的？
你同事申请的是developmental biology 的那个位置么？
他们系挺大的，似乎有不止一个opening, 另外一个好像是 Physiology。
会不会你的同事申请的是那个位置？

【在 W*****o 的大作中提到】
: 是吗？我原来一个同事刚刚拿到他们系里的offer。8月份准备过去。我这同事8～9年的
: 薄厚。每天刻苦的不得了。4片一座的PNAS.我们领域小，冷门，出不了大文章，PNAS已
: 经很牛了。我就是看到他可怜的收入，（两个孩子），没有前途的千老生活，所以离开
: 了。终于人家拿到offer。真替他和他的家人高兴。
avatar
k*o
24 楼
自己纠正一下
好像有点问题啊……
还需要再推敲

【在 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))
avatar
W*o
25 楼
不好意思没看仔细你说的是developmental biology，我同事应该是physiology.
avatar
r*o
26 楼
是不是子集不一定是连续的元素组成？

【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
avatar
n*w
27 楼
嗯。近几年的football太烂了。
Top 10里就数Stanford的football最强了。

【在 m*****i 的大作中提到】
: hehe, 体育很牛。
avatar
d*8
28 楼
对的， 不是均匀分布，可以很离散的
比如 1， 100， 111， 112， 113.
开始我妄图用2分做，直接被他这个例子给灭了。

【在 r****o 的大作中提到】
: 是不是子集不一定是连续的元素组成？
avatar
e*r
29 楼
Bilogy jobs:
http://jobguiding.com/science-jobs/biology.html

【在 s******y 的大作中提到】
: University of Notre Dame,
: Department of Biological Sciences
: Title: Assistant Professor
: Field: Developmental Biology
: http://biology.nd.edu
: b*****[email protected]
: 这个学校去年把我据了，不过今天突然给我来信，说他们面试的几个人都不理想，
: 最后谁都没招，所以今年要重新再招一次，问我还愿不愿意申请。
: 我本来想大义凛然给他们写封据信回去的。不过后来想想还是积点人品吧。
: 有意的同学去和他们联系吧。那个系还挺不错的。
avatar
t*t
30 楼
这到底啥意思: 子集每个数pair的Distance
最后20分钟讲个算法题目。
给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
每个数pair的Distance，使得这个min distance 最大化。
avatar
s*e
31 楼
http://entomology.ucdavis.edu/news/zainsyedtonotredame.html

【在 s******y 的大作中提到】
: University of Notre Dame,
: Department of Biological Sciences
: Title: Assistant Professor
: Field: Developmental Biology
: http://biology.nd.edu
: b*****[email protected]
: 这个学校去年把我据了，不过今天突然给我来信，说他们面试的几个人都不理想，
: 最后谁都没招，所以今年要重新再招一次，问我还愿不愿意申请。
: 我本来想大义凛然给他们写封据信回去的。不过后来想想还是积点人品吧。
: 有意的同学去和他们联系吧。那个系还挺不错的。
avatar
d*8
32 楼
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 最大化。
avatar
f*n
33 楼
UC davis原来的博士后？
现在澳大利亚元超级贵，你可以多多去欧洲东南亚旅游阿。

【在 W*****o 的大作中提到】
: 不好意思没看仔细你说的是developmental biology，我同事应该是physiology.
avatar
r*o
34 楼
可是不管K是多少， 我们都可以找出distance最小的一对数出来，让这个K数目的子集
包括这对数啊?
是不是我理解得不对？

【在 d*******8 的大作中提到】
: K数目的子集，有 K（k-1）/2的Pair，某个Pair有个distance, 里面最小的distance
: 是这个子集的 Min distance
: 开头我听成了mean distance,又废了几分钟。。
avatar
k*o
36 楼
是minmax吧……
应该是minimize the diameter of the set, I guess?

【在 r****o 的大作中提到】
: 可是不管K是多少， 我们都可以找出distance最小的一对数出来，让这个K数目的子集
: 包括这对数啊?
: 是不是我理解得不对？
avatar
W*o
37 楼
谢谢了。我现在还盼着澳元贬值呢。在美国存的那点美元全缩水了。缩的比我现在挣的
还多。：（

【在 f********n 的大作中提到】
: UC davis原来的博士后？
: 现在澳大利亚元超级贵，你可以多多去欧洲东南亚旅游阿。
avatar
r*o
38 楼
是我理解错题目了。

【在 k**o 的大作中提到】
: 是minmax吧……
: 应该是minimize the diameter of the set, I guess?
avatar
d*8
39 楼
但是最后要求是这个min distance 为最大的这样一个K子集。

【在 r****o 的大作中提到】
: 可是不管K是多少， 我们都可以找出distance最小的一对数出来，让这个K数目的子集
: 包括这对数啊?
: 是不是我理解得不对？
avatar
B*t
40 楼
Don't worry. Just move on!

【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
avatar
d*8
41 楼
手头的面试机会已经用光了。
找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
类文本文件啊。
我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。

【在 B*****t 的大作中提到】
: Don't worry. Just move on!
avatar
r*u
42 楼
hang on，苦练内功，你要做到小羊那样，google不招你就没天理了。

【在 d*******8 的大作中提到】
: 手头的面试机会已经用光了。
: 找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
: 也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
: 没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
: 类文本文件啊。
: 我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
: 看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
avatar
r*o
43 楼
那道DP题目谁能讲讲思路吗?

【在 r**u 的大作中提到】
: hang on，苦练内功，你要做到小羊那样，google不招你就没天理了。
avatar
x*y
44 楼
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
avatar
P*e
45 楼
comfort, maybe it is not as worse as you thought. good luck

【在 d*******8 的大作中提到】
: 手头的面试机会已经用光了。
: 找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
: 也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
: 没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
: 类文本文件啊。
: 我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
: 看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
avatar
d*8
46 楼
二分是不对的，因为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
avatar
d*8
47 楼
我觉得那个式子应该是对的，虽然复杂度是n^4

【在 r****o 的大作中提到】
: 那道DP题目谁能讲讲思路吗?
avatar
c*t
48 楼
失败是成功他妈,别难过！苦练内力吧！
avatar
c*t
49 楼
坚持是成功他爸，男人就是要坚持！
avatar
P*e
50 楼
非要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.
avatar
x*y
51 楼
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.
avatar
d*8
52 楼
对的，这个表达更简洁点，复杂度也是一样的。刚才没有仔细看，不好意思

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.
avatar
m*l
53 楼
我也是这样，特别是遇到听不懂的啊三，就开始胡言乱语。。。

【在 d*******8 的大作中提到】
: 每次被卡住都很紧张，一片空白。心理素质太差了...
: 又不知道跟他套什么话才能套出暗示
avatar
d*8
54 楼
应该是对的吧，果然是小强人，好牛。

min

【在 P*******e 的大作中提到】
: 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
: distance，知道有k-1个distance在vector里面，这样结果也对吧？
avatar
n*r
55 楼
第二题按照你的思路的话，每次往set里面加i，j两个数？k是奇数呢？
感觉应该每次只加一个数，dp的公式还要复杂

Min(

【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
avatar
r*o
56 楼
请问为什么是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里面，这样结果也对吧？
avatar
n*r
57 楼
试试看这个例子
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里面，这样结果也对吧？
avatar
r*o
58 楼
请问distance vector是不是n个元素两两之间的距离，也就是说要算O(n^2)次？

min

【在 P*******e 的大作中提到】
: 非要DP么？你排序之后maintain一个distance vector，然后merge interval with min
: distance，知道有k-1个distance在vector里面，这样结果也对吧？
avatar
n*r
59 楼
排序过后，对某个被选中的元素，只要算和它相邻的两个被选中的元素的距离就可以了
，和其他距离肯定更大，对题目没有影响
是O(n)

【在 r****o 的大作中提到】
: 请问distance vector是不是n个元素两两之间的距离，也就是说要算O(n^2)次？
:
: min
avatar
d*8
60 楼
是的，那个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(
avatar
n*r
61 楼
恩，这个应该对了，和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)}
avatar
g*y
62 楼
复杂度还可以再降一个维度

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)}
avatar
g*y
63 楼
事实上，还可以进一步优化，我觉得可以做到 n*k*logn

【在 g*******y 的大作中提到】
: 复杂度还可以再降一个维度
:
: 1,i,end)}
avatar
d*8
64 楼
求赐教，logn的话就要Divide&conquer了，每次怎么分呢？

【在 g*******y 的大作中提到】
: 事实上，还可以进一步优化，我觉得可以做到 n*k*logn
avatar
n*r
65 楼
xnxky给的方法就是吧

【在 d*******8 的大作中提到】
: 求赐教，logn的话就要Divide&conquer了，每次怎么分呢？
avatar
g*y
66 楼
不是div conq
你先做到 n^2*k的时间复杂度，再考虑怎么做n->logn加速

【在 d*******8 的大作中提到】
: 求赐教，logn的话就要Divide&conquer了，每次怎么分呢？
avatar
d*8
67 楼
但是他的方法里i是从l遍历到r的，
第一个i的selection不能马上确定的吧...

【在 n******r 的大作中提到】
: xnxky给的方法就是吧
avatar
n*r
68 楼
一分为二以后两边都可以递归啊

【在 d*******8 的大作中提到】
: 但是他的方法里i是从l遍历到r的，
: 第一个i的selection不能马上确定的吧...
avatar
d*8
69 楼
两分是不对呀，因为你不确定中间那个是不是在最后的Set里...

【在 n******r 的大作中提到】
: 一分为二以后两边都可以递归啊
avatar
d*8
70 楼
原来那个DP难道不是n*k吗？每次scan n个item, DP是K次。

【在 g*******y 的大作中提到】
: 不是div conq
: 你先做到 n^2*k的时间复杂度，再考虑怎么做n->logn加速
avatar
d*8
71 楼
错了，是n^2*k.

【在 d*******8 的大作中提到】
: 原来那个DP难道不是n*k吗？每次scan n个item, DP是K次。
avatar
d*8
72 楼
忘记加上那个求Max的复杂度了。
再好好想想

【在 g*******y 的大作中提到】
: 不是div conq
: 你先做到 n^2*k的时间复杂度，再考虑怎么做n->logn加速
avatar
g*y
73 楼
嗯，我看错了，你的那个是n^n^k的
不过你完全不需要把end作为f()的parameter
那么怎么在这个基础上再做一个log加速？

【在 d*******8 的大作中提到】
: 错了，是n^2*k.
avatar
g*y
74 楼
建议你不要在f()的参数里面写一个end，这个东西让我差点误以为你的复杂度是k*n^3
你自己可以看到，你的end这个参数自始至终都没有变过

【在 d*******8 的大作中提到】
: 忘记加上那个求Max的复杂度了。
: 再好好想想
avatar
d*8
75 楼
对的，是不要end的
是的，是没有变，因为一开始想的是两个头都要变的，后来发现不用的。

【在 g*******y 的大作中提到】
: 建议你不要在f()的参数里面写一个end，这个东西让我差点误以为你的复杂度是k*n^3
: 你自己可以看到，你的end这个参数自始至终都没有变过
avatar
B*t
76 楼
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)}
avatar
d*8
77 楼
我还是没想明白， 这个复杂度， DP是不是n*k,算Max那个不是乘上n的复杂度，
还是n*k+n吧，搞糊涂了。

【在 g*******y 的大作中提到】
: 嗯，我看错了，你的那个是n^n^k的
: 不过你完全不需要把end作为f()的parameter
: 那么怎么在这个基础上再做一个log加速？
avatar
g*y
78 楼
correct！

【在 B*****t 的大作中提到】
: this is right！在head到end之间进行二分，还可以降低复杂度了。
: 注意到dist(head, i): and f(k-1, i, end)>=f(k-1, j, end) for i
avatar
B*t
79 楼
不用着急，车到山前必有路！
简历茫无目的的随便投好像也不好，建议联系一下hunter。
可以到linkedin上去找找，很多hunter的review都很不错。
good luck！

【在 d*******8 的大作中提到】
: 手头的面试机会已经用光了。
: 找工作一个多月了，除了这三家公司外，其余的连个电面的都没有，
: 也发了很多简历给小公司，一听说外国人+Ph.D+之前无industry经验（我一个intern都
: 没做过），直接就没反应了。还有极个别的发数据文件包让我干民工活，写脚本解析各
: 类文本文件啊。
: 我吭哧吭哧写个半天的程序，给发过去后就什么回应都没有了。
: 看来暑假毕业无望了，是不是要继续赖在学校了。但是实在不想混在学校浪费时间了。
avatar
r*o
80 楼
不好意思我没看太明白，
你的大概意思是不是跟下面差不多？
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)}
avatar
d*8
81 楼
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
avatar
d*8
82 楼
E关于求这个复杂度， 求验证下，以前算法课学的都忘记了。
DP中的States这里应该是logn^k 用了两分的话，
加上外面那个算Max的，应该还是要算的。是n*logn^k.

【在 d*******8 的大作中提到】
: 我还是没想明白， 这个复杂度， DP是不是n*k,算Max那个不是乘上n的复杂度，
: 还是n*k+n吧，搞糊涂了。
avatar
d*8
83 楼
谢谢，可能找工作还没真正用心吧，总报着侥幸心理
反正对工作期望不高，有个Offer就行了。
linkedin中是搜到hunter就加好友发消息吗？之前都没怎么试过。

【在 B*****t 的大作中提到】
: 不用着急，车到山前必有路！
: 简历茫无目的的随便投好像也不好，建议联系一下hunter。
: 可以到linkedin上去找找，很多hunter的review都很不错。
: good luck！
avatar
r*o
84 楼
大侠们能不能看看我的想法对不对。

【在 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]))}
avatar
d*8
85 楼
这个应该对的，你这个从尾部开始scan的

【在 r****o 的大作中提到】
: 大侠们能不能看看我的想法对不对。
avatar
B*t
86 楼
我比较土，不会用linkedin，这个方法是同学告诉我的。
不过我近来在dice，monster上投简历，很多hunter都会给你搭讪。把他们的名字搞过
来后，然后到linkined上search。好的hunter都用linkedin，而且reviews不错，你可
以参考一下，决定是穷追猛打，还是急流勇退。

【在 d*******8 的大作中提到】
: 谢谢，可能找工作还没真正用心吧，总报着侥幸心理
: 反正对工作期望不高，有个Offer就行了。
: linkedin中是搜到hunter就加好友发消息吗？之前都没怎么试过。
avatar
r*o
87 楼
我这个是从左到右scan的啊。
还有，你说的那个二分在这里怎么用啊？

【在 d*******8 的大作中提到】
: 这个应该对的，你这个从尾部开始scan的
avatar
r*o
88 楼
还想问一下，这个DP算法都是算出最优值，但是怎么输出那些数字呢?
有什么好办法没有?

【在 d*******8 的大作中提到】
: 这个应该对的，你这个从尾部开始scan的
avatar
d*8
89 楼
看BlueAnt的那个帖子

【在 r****o 的大作中提到】
: 我这个是从左到右scan的啊。
: 还有，你说的那个二分在这里怎么用啊？
avatar
d*8
90 楼
明白了，我现在先LinkedIn的Profile开始弄弄，都是空白的。唉，太懒了。

【在 B*****t 的大作中提到】
: 我比较土，不会用linkedin，这个方法是同学告诉我的。
: 不过我近来在dice，monster上投简历，很多hunter都会给你搭讪。把他们的名字搞过
: 来后，然后到linkined上search。好的hunter都用linkedin，而且reviews不错，你可
: 以参考一下，决定是穷追猛打，还是急流勇退。
avatar
r*o
91 楼
能不能说说为什么靠近相等比较好啊？

【在 d*******8 的大作中提到】
: Bingbo，就是要求dist(head,i) 和 f(k-1,i,end)靠近相等，这个想法好。
avatar
d*8
92 楼
因为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 的大作中提到】
: 能不能说说为什么靠近相等比较好啊？
avatar
B*t
93 楼
最后分析一下复杂度吧
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.
avatar
d*8
94 楼
恩，终于搞明白了，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)
avatar
r*o
95 楼
明白了，多谢多谢！

【在 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就好了
avatar
r*o
96 楼
不是可以降到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)
avatar
B*t
97 楼
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)吧。
avatar
s*e
98 楼
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个大小的子集，这个子集
avatar
g*e
99 楼
牛人们的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)
avatar
s*n
100 楼
电面问这样的题 实在是太不厚道了
avatar
s*5
101 楼

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个大小的子集，这个子集
avatar
g*n
102 楼
这个题不能用DP，因为不具备DP的性质。比如对于k长度的子集，最优解是ans(i, j, k
)，那么去掉
最优解中的一个元素后，剩下的k-1个元素并不是在(i,j)范围里子集长度为k-1的最优
解。虽然你可以
遍历去掉哪个元素，但只要不具备这个性质，用DP做就是错的。
avatar
A*H
103 楼
minmax 之类的题目都可以用二分思想来作，比如那个linear partition问题
avatar
j*x
104 楼
路过瞻仰一下版大。。。

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))
avatar
V*i
105 楼
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.
avatar
s*e
106 楼
大概一个月之前的一个帖子很相似
http://www.mitbbs.com/article_t1/JobHunting/31717591_0_1.html
感觉这两道题会其中一道另外一道也就不难了。
所以lesson就是mit上的题都要仔细看，弄明白。我看到这个帖子之后也是反应了很久
才想到怎么做，估计面试的情况下是也会fail的。看来看mit的效率还有待提高。。
多谢楼主分享。learned a lot from this post and the discussions
avatar
c*n
107 楼
先对数组排序（升序），
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
的方法求得。 以此类推可以得到任意子集的解
avatar
V*i
108 楼
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]
avatar
j*a
109 楼
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))
avatar
j*a
110 楼
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;
}
avatar
j*a
111 楼
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;
}
avatar
h*o
112 楼
too hard for an interview question

【在 d*******8 的大作中提到】
: 继上周Amazon Onsite被一个三哥灭了
: 这次电面又被国人灭了。
: 具体过程是这样
: 前25分钟聊Research...
: （真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
: 接下来二叉树遍历编程题，
: inorder的非递归。
: 几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
: 最后20分钟讲个算法题目。
: 给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
相关阅读
文献求助，包子感谢！拿了postdoc fellowship 可以换实验室吗聘请par time 博士后科研人员Re: 老板们有什么资格要求忠诚度？ (转载)关于中国PI招人版上好像对我们这些中国PI不友好？做biology的看不起做测序、bioinfo和结构的？求助质谱操作视频做发考题的是不是压力太大，会用婚外情来解压？ (转载)bl3 lab 招technician生物学词典 请教牛人们一根筋与智障仅仅一步之遥[转]DOD,DARPA的经费看来要涨文革斗教授的制度是该大力引进迷弟 (转载)“中西部博士后”大哥的女儿是名校毕业，还有全bioinformatics的基本要求转载 NIH或将在今年削减20%预算求推荐neurodegeneration/regeneration labepisomal plasmid isolation求文献一篇，万分感激！
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。