印度人的的确写得比我们好 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

印度人的的确写得比我们好

印度人的的确写得比我们好# Biology - 生物学

x*n2011-11-17 08:11

1 楼

不才想请教两道很常见的面试题
（1）给定array a1,a2,...,an,b1,b2,...,bn，将其变成a1,b1,a2,b2,...,an,bn的
形式
知道有个O(n)解，不过水平比较低，理解起来是在有困难，CareerCup上给了一个
O(nlogn)
的解，不过自己尝试总不能对，希望大牛们指教
（2）另外就是也很常见的在rotated 的sorted的数组里找一个元素的题，是用Binary
search实
现的，但是对于有重复元素的数组就会有错，不知道是不是就不能处理这种情况。
多谢了

a*w2011-11-17 08:11

2 楼

【以下文字转载自 ebiz 讨论区】
发信人: alpenglow (且听风雨), 信区: ebiz
标题: MS 太不靠谱了刚发布一个病毒更新把 chrome给杀了赶紧又发布了一个又救回来了
发信站: BBS 未名空间站 (Fri Sep 30 13:36:07 2011, 美东)
。。。。。。。。。。。。。

s*y2011-11-17 08:11

3 楼

这几天在看博士后的申请，几个印度来的人写的申请，有条有理，重点突出，
而且紧扣广告的要求，确实让人叹服，值得让我们中国人学习。

h*e2011-11-17 08:11

4 楼

O(n)的你就别管了，没有必要。
O(nlogn)的思想是分治。把X=a1,a2...an,b1,b2...bn看作四段A1,A2,B1,B2。假设要求
的置换是F(X), 那么F(X)=F(A1,B1),F(A2,B2), 也就是说，把A2和B1交换，然后递归。
Binary
可以证明，有重复元素的时候，基于比较的算法有O(n)的下界。具体怎么证明你可以想
想。

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

: 不才想请教两道很常见的面试题
: （1）给定array a1,a2,...,an,b1,b2,...,bn，将其变成a1,b1,a2,b2,...,an,bn的
: 形式
: 知道有个O(n)解，不过水平比较低，理解起来是在有困难，CareerCup上给了一个
: O(nlogn)
: 的解，不过自己尝试总不能对，希望大牛们指教
: （2）另外就是也很常见的在rotated 的sorted的数组里找一个元素的题，是用Binary
: search实
: 现的，但是对于有重复元素的数组就会有错，不知道是不是就不能处理这种情况。
: 多谢了

m*i2011-11-17 08:11

5 楼

post some , let us study study?

i*e2011-11-17 08:11

6 楼

第二题的解答你可以参考这里：
http://ihas1337code.blogspot.com/2010/04/searching-element-in-rotated-array.html
要边看解答边思考，然后自己再写代码，写完后再看解答里面的代码。

Binary

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

K*S2011-11-17 08:11

7 楼

I turned down a lot of such resumes a couple of years ago. The reason I gave
to HR person was that those candidates match every key word / skill we
asked for which is nearly impossible. hehe
Another obvious explanation I gave HR was that whenever an instrument skill
is required, those guys only mention mfr name instead of the specific
instrument model name.

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

: 这几天在看博士后的申请，几个印度来的人写的申请，有条有理，重点突出，
: 而且紧扣广告的要求，确实让人叹服，值得让我们中国人学习。

m*g2011-11-17 08:11

8 楼

第二题，有重复的确实没办法

s*y2011-11-17 08:11

9 楼

呵呵，你收到的那些写得也太拙劣了。
我收到的这几个明显是高手，他们写的就是从不同的角度来说为什么他们的经验和经历使得他们适合来做我的项目。看的我几乎被说动了。但是后来一看发表文章的记录就让我晕过去了。其中写得最好的那个，发了将近10片文章，没有一片是一作，全部是挂在中间打酱油的。

gave
skill

【在 K******S 的大作中提到】

: I turned down a lot of such resumes a couple of years ago. The reason I gave
: to HR person was that those candidates match every key word / skill we
: asked for which is nearly impossible. hehe
: Another obvious explanation I gave HR was that whenever an instrument skill
: is required, those guys only mention mfr name instead of the specific
: instrument model name.

i*e2011-11-17 08:11

10 楼

有重复的就没办法。
你想一下，binary search 返回找到的值就只有一个，有重复的也只能返回其中一个的
位置。
如果你想找所有重复的位置，那就另当别论，完全是不同的问题了。。。

s*y2011-11-17 08:11

11 楼

抱歉啊，不能贴，否则会有法律问题

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

: post some , let us study study?

x*n2011-11-17 08:11

12 楼

谢谢大侠，我知道分治的方法，但是自己实现总实现不好，主要是在如何分段上出问题
，对于奇数和偶
数长度的分段好像要不同处理，但我的代码始终有Bug，对某个长度的行，对另一个长
度就不行了，很沮
丧。还希望有经验的大牛们指点一二。

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

:
: O(n)的你就别管了，没有必要。
: O(nlogn)的思想是分治。把X=a1,a2...an,b1,b2...bn看作四段A1,A2,B1,B2。假设要求
: 的置换是F(X), 那么F(X)=F(A1,B1),F(A2,B2), 也就是说，把A2和B1交换，然后递归。
: Binary
: 可以证明，有重复元素的时候，基于比较的算法有O(n)的下界。具体怎么证明你可以想
: 想。

d*22011-11-17 08:11

13 楼

只要是印度人，一律不予考虑。

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

: 这几天在看博士后的申请，几个印度来的人写的申请，有条有理，重点突出，
: 而且紧扣广告的要求，确实让人叹服，值得让我们中国人学习。

x*n2011-11-17 08:11

14 楼

多谢了，我会看看

array.html

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

: 第二题的解答你可以参考这里：
: http://ihas1337code.blogspot.com/2010/04/searching-element-in-rotated-array.html
: 要边看解答边思考，然后自己再写代码，写完后再看解答里面的代码。
:
: Binary

F*e2011-11-17 08:11

15 楼

老美的教育确实很看重书面和口头表达能力，阿三们也是吸取了这一点的精华。
带过一个老美本科生，教了两个月做miniprep，人走了逢年过节还给我发个email问候
一声，顺便附上大段赞美景仰之词，让人看得心里舒服之极啊，呵呵。

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

: 这几天在看博士后的申请，几个印度来的人写的申请，有条有理，重点突出，
: 而且紧扣广告的要求，确实让人叹服，值得让我们中国人学习。

x*n2011-11-17 08:11

16 楼

不是，我不是希望找到所有重复的元素，只是有重复的时候，我判断舍去某一段的逻辑
可能有问题，会
miss

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

: 有重复的就没办法。
: 你想一下，binary search 返回找到的值就只有一个，有重复的也只能返回其中一个的
: 位置。
: 如果你想找所有重复的位置，那就另当别论，完全是不同的问题了。。。

y*82011-11-17 08:11

17 楼

Only count their publications.

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

: 这几天在看博士后的申请，几个印度来的人写的申请，有条有理，重点突出，
: 而且紧扣广告的要求，确实让人叹服，值得让我们中国人学习。

r*o2011-11-17 08:11

18 楼

这个我也没搞定。感觉好像只有2^N个元素才好用分治。有谁已经搞定了通用的分治算
法吗?

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

: 谢谢大侠，我知道分治的方法，但是自己实现总实现不好，主要是在如何分段上出问题
: ，对于奇数和偶
: 数长度的分段好像要不同处理，但我的代码始终有Bug，对某个长度的行，对另一个长
: 度就不行了，很沮
: 丧。还希望有经验的大牛们指点一二。

c*72011-11-17 08:11

19 楼

This is a great post for knowing the activating PI on the board... LoL!!

d*n2011-11-17 08:11

20 楼

Try this:
// Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
algorithm to change
// this array to a1, b1, a2, b2, ..., an, bn.
void Swap(int *A, int i, int j)
{
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
};
void SwitchOddEven(int *A, int start, int end)
{
if (start >= end)
return;
int mid = (start+end)/2;

// when start = 1, end =4
// then mid = 2, we want left = 2 too, that's why the
// following "+1"
int left = (start + mid + 1

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

: 这个我也没搞定。感觉好像只有2^N个元素才好用分治。有谁已经搞定了通用的分治算
: 法吗?

g*02011-11-17 08:11

21 楼

难道不是９９％印度人的申请信都是dear sir／madam开头的么

x*n2011-11-17 08:11

22 楼

cool! 没想到这个简洁，多谢大牛指点。

an

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

: Try this:
: // Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
: algorithm to change
: // this array to a1, b1, a2, b2, ..., an, bn.
: void Swap(int *A, int i, int j)
: {
: A[i] ^= A[j];
: A[j] ^= A[i];
: A[i] ^= A[j];
: };

v*s2011-11-17 08:11

23 楼

我问组里的印度人要过他们写的申请信，都写的超级长啊，经常还附有对自己paper的
大段综述，这玩艺有人看吗？

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

: 这几天在看博士后的申请，几个印度来的人写的申请，有条有理，重点突出，
: 而且紧扣广告的要求，确实让人叹服，值得让我们中国人学习。

h*62011-11-17 08:11

24 楼

第一题是完美洗牌问题，可以参考这里的解答：
http://webhome.cs.uvic.ca/~jellis/perfect.html
如果限定O(n)时间，则in place空间没有办法完成，至少需要O(log n)的额外空间。
另：楼上durbin的方法虽然不需要额外空间，但需要O(n logn)的时间。

m*i2011-11-17 08:11

25 楼

I'm looking for postdog position, but few would even reply. I think my
writing must suck that much! sigh~

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

: 抱歉啊，不能贴，否则会有法律问题

O*e2011-11-17 08:11

26 楼

发了什么文章，从哪里来，始终是最重要的因素。你把信和简历写那么长，说不定
很多人一看就烦了。

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

: I'm looking for postdog position, but few would even reply. I think my
: writing must suck that much! sigh~

K*S2011-11-17 08:11

27 楼

not only PIs screen resumes. ...

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

: This is a great post for knowing the activating PI on the board... LoL!!

m*i2011-11-17 08:11

28 楼

you can say that because you are a NIU. My records is not good so what I can
work on is to make interest and proposal persuasive. BTW, not long.

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

: 发了什么文章，从哪里来，始终是最重要的因素。你把信和简历写那么长，说不定
: 很多人一看就烦了。

s*y2011-11-17 08:11

29 楼

不要写那么长。但是对自己的文章写一些综述是必须的，就像印度人那样，得吹一吹
自己的成就。
另，我觉得你可能碰到了那种比较傻的印度人：）
（印度也是一个大国，应该也有傻的吧？）

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

: 我问组里的印度人要过他们写的申请信，都写的超级长啊，经常还附有对自己paper的
: 大段综述，这玩艺有人看吗？

s*y2011-11-17 08:11

30 楼

You mean active PI?
There are many, many, many of them here :)
Just that they usually hide it very well. Hehe

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

: This is a great post for knowing the activating PI on the board... LoL!!