2B年年有，今年特别多 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

2B年年有，今年特别多

2B年年有，今年特别多# Joke - 肚皮舞运动

t*e2012-02-23 08:02

1 楼

Given an array of +ve and -ve integers, re-arrange it so that u have +ves on
one end and -ves on other,BUT RETAIN ORDER OF APPEARANCE..
for eg,
1,7,-5,9,-12,15
ans=
-5,-12,1,7,9,15
do it in O(n) without using any extra space.

S*92012-02-23 08:02

2 楼

现在在准备Eb1B RFE，deadline还有三星期。现在公司在不同部门有另外相同title 的
一个职位opening，我想申请。（注：新老板希望我去, 我已经决定申请这个工作。实
在收不了现老板了，才想转的。但新老板现在就要把这事定下来，不然就招别人了）有几个问题，想请教大家。
1. 对这个internal job transfer, 要申请H1B transfer吗？
2.这个job transfer对Eb1B的申请会有影响吗？
3. 如果有，是在递交job transfer 之前还是在递交job transfer 后对申请Eb1B有利。
4.实在不行的话，也可考虑放弃RFE,等job transfer 之后，在申请EB1B.
问题较多，也有点复杂。真诚求建议。多谢，想想在美国混下去，也真不容易啊。

G*o2012-02-23 08:02

3 楼

t*e2012-02-23 08:02

4 楼

我觉得明明有solution啊，就用quick sort的思想，大家看看对不对，还是我理解题目
有问题？
先扫一遍数组A[n]，知道有多少负数，假设有m个
把m视为pivot的位置，设两个指针，一个初始指向A[0], 另一个初始指向A[m]:
i=0, j=m
if A[i]>0 and A[j]<0, swap them
if A[i]<0,i++
if A[j]>0,j++
直到i=m-1 或j = n-1
这样就好了是O(n) time, O(1)space
对挖？

h*l2012-02-23 08:02

5 楼

有几个问题，想请教大家。
不用把，一个公司没关系
不清楚，可能有
利。

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

: 现在在准备Eb1B RFE，deadline还有三星期。现在公司在不同部门有另外相同title 的
: 一个职位opening，我想申请。（注：新老板希望我去, 我已经决定申请这个工作。实
: 在收不了现老板了，才想转的。但新老板现在就要把这事定下来，不然就招别人了）有几个问题，想请教大家。
: 1. 对这个internal job transfer, 要申请H1B transfer吗？
: 2.这个job transfer对Eb1B的申请会有影响吗？
: 3. 如果有，是在递交job transfer 之前还是在递交job transfer 后对申请Eb1B有利。
: 4.实在不行的话，也可考虑放弃RFE,等job transfer 之后，在申请EB1B.
: 问题较多，也有点复杂。真诚求建议。多谢，想想在美国混下去，也真不容易啊。

b*r2012-02-23 08:02

6 楼

p*22012-02-23 08:02

7 楼

这题不是讨论过没解吗？

g*32012-02-23 08:02

8 楼

试着回答：

有几个问题，想请教大家。
只要工作性质及专业是你现有H1B的性质，HR和international office不会需要你做H1b
transfer. 具体的例子是我老婆以前在学校里换不同的系（department),依然是原来
的H1b. 建议你最好和HR核实，这个工作转换他们认为是同意性质，不违背你现有的H1b.
这个转换并没有更换雇主 (同一个HR），所以不会影响你的申请，记住你的申请是基于
雇主的，这个雇主是你公司，不是你哪个特定的老板。
利。
如上，此问题不存在。
何必那么麻烦呢，都快成功了。
总结性发言：咨询你们的HR（或给你EB1b签字的部门---应该就是HR或者
international office)会得到最终的答案，否则网络上任何人的回答都可能不准确，
因为决定权在你们公司的主管部门。而不是移民局。

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

g*i2012-02-23 08:02

9 楼

......

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

l*82012-02-23 08:02

10 楼

RETAIN ORDER OF APPEARANCE

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

: 我觉得明明有solution啊，就用quick sort的思想，大家看看对不对，还是我理解题目
: 有问题？
: 先扫一遍数组A[n]，知道有多少负数，假设有m个
: 把m视为pivot的位置，设两个指针，一个初始指向A[0], 另一个初始指向A[m]:
: i=0, j=m
: if A[i]>0 and A[j]<0, swap them
: if A[i]<0,i++
: if A[j]>0,j++
: 直到i=m-1 或j = n-1
: 这样就好了是O(n) time, O(1)space

S*92012-02-23 08:02

11 楼

非常感谢你的回复。工作性质是从R/D department 转到manufacturing department in
the same product area. 不知对H1B和Eb1B会有何影响？
提一下，新老板也同意润色job description,使其包含更多R/D描述；他也支持R/D in
his department.

H1b
H1b.

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

: 试着回答：
:
: 有几个问题，想请教大家。
: 只要工作性质及专业是你现有H1B的性质，HR和international office不会需要你做H1b
: transfer. 具体的例子是我老婆以前在学校里换不同的系（department),依然是原来
: 的H1b. 建议你最好和HR核实，这个工作转换他们认为是同意性质，不违背你现有的H1b.
: 这个转换并没有更换雇主 (同一个HR），所以不会影响你的申请，记住你的申请是基于
: 雇主的，这个雇主是你公司，不是你哪个特定的老板。
: 利。
: 如上，此问题不存在。

r*e2012-02-23 08:02

12 楼

铐,太2

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

k*r2012-02-23 08:02

13 楼

如果interview时碰到这样无解的题，怎么"说服"interviewer这是无解的呢？
要是interviewer拒绝说出他心目中的答案，但就是坚持有解，那咋办？

g*32012-02-23 08:02

14 楼

正如我说的，你一定要让新老板和支持你绿卡的HR,还有管理你H1B的International
Office几个部门synchronize这个case. 这个让你新老板明白，他一定能帮你搞定的。
这个基本上是一个顺水推舟的事情, 对谁都没伤害。所以我估计，比较容易办。

in
in

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

: 非常感谢你的回复。工作性质是从R/D department 转到manufacturing department in
: the same product area. 不知对H1B和Eb1B会有何影响？
: 提一下，新老板也同意润色job description,使其包含更多R/D描述；他也支持R/D in
: his department.
:
: H1b
: H1b.

p*22012-02-23 08:02

15 楼

估计出这题就是想搞掉你。怎么对付听语文老师的吧。

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

: 如果interview时碰到这样无解的题，怎么"说服"interviewer这是无解的呢？
: 要是interviewer拒绝说出他心目中的答案，但就是坚持有解，那咋办？

j*a2012-02-23 08:02

16 楼

以前的老政策是同学校不同系里转的不需要重新办理H1B,
现在的新政策是系里面转老板的不需要换H1B,但是,在不同的系之间转的就要转H1B,我
家的几个月前刚转过!

y*u2012-02-23 08:02

17 楼

别，俺的烂招就成功了一次，上周onsite就没成功
这东西见仁见智，反正interview嘛，不要放在心上就好
面完了还得move on

【在 p*****2 的大作中提到】

:
: 估计出这题就是想搞掉你。怎么对付听语文老师的吧。

c*p2012-02-23 08:02

18 楼

这算是面霸么？

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

: 别，俺的烂招就成功了一次，上周onsite就没成功
: 这东西见仁见智，反正interview嘛，不要放在心上就好
: 面完了还得move on

y*u2012-02-23 08:02

19 楼

我过去3年好像就面了5个公司左右

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

: 这算是面霸么？

c*p2012-02-23 08:02

20 楼

AGMFL全面过了么。。。

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

: 我过去3年好像就面了5个公司左右

p*22012-02-23 08:02

21 楼

把M换成T吧。

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

: AGMFL全面过了么。。。

t*e2012-02-23 08:02

22 楼

什么意思啊，就是order都不变？就是什么也不能做咯？

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

: RETAIN ORDER OF APPEARANCE

c*p2012-02-23 08:02

23 楼

太牛了。。。

【在 p*****2 的大作中提到】

:
: 把M换成T吧。

c*p2012-02-23 08:02

24 楼

稳定排序

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

: 什么意思啊，就是order都不变？就是什么也不能做咯？

l*a2012-02-23 08:02

25 楼

跟我有一拼
热门的不敢申，不热门的不屑于申

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

: 我过去3年好像就面了5个公司左右

p*22012-02-23 08:02

26 楼

俩大牛

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

: 跟我有一拼
: 热门的不敢申，不热门的不屑于申

h*g2012-02-23 08:02

27 楼

再某些特定情况下有解，假定k0个负数，k1个正数，
如果k=min｛k0，k1｝，那么存在O(n+k^2)的算法，所以只要k=O(sqrt(n))就有O(n)算
法。

f*n2012-02-23 08:02

28 楼

怎么做到O(n+K^2)?
我只能想到O(kn)的算法啊，就是假设负数少，就从最后面往前一个个找负数慢慢挪。
。。

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

: 再某些特定情况下有解，假定k0个负数，k1个正数，
: 如果k=min｛k0，k1｝，那么存在O(n+k^2)的算法，所以只要k=O(sqrt(n))就有O(n)算
: 法。

h*g2012-02-23 08:02

29 楼

是呀，就是从后面向前挪，先把最后一个同倒数第二个挪到一起，然后再把二个同倒数
第三个挪一起，就这样一直下去直到遇到第一个负数，然后再把所有的负数都挪到最左
边就可以了。

f*n2012-02-23 08:02

30 楼

这个复杂度不是O(k^2)吧。
每次挪一个负数到前一个负数你可能要走一段距离，这段距离的上限是n，不是k吧？两
个负数的距离跟k没必然关系。

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

: 是呀，就是从后面向前挪，先把最后一个同倒数第二个挪到一起，然后再把二个同倒数
: 第三个挪一起，就这样一直下去直到遇到第一个负数，然后再把所有的负数都挪到最左
: 边就可以了。

h*g2012-02-23 08:02

31 楼

先考虑如下基本问题：
假定一个数组前N个数是正数，后M个数是负数，如何把M个负数全部移到头部，N个正数
全部移到尾部，同时不改变正数与负数的相对次序？
其实用 N+M 次交换操作就可解决上面问题。因为每次移动一个负数时，你不需要只向
前移一位，而是可以－次移很多位。
比如你有：
３２５－１－２
你可以把２与－１交换，５与－２交换得到：
３－１－２２５
再把３与－１交换
－１３－２２５
再把３与－２交换得到
－１－２３２５
于是移位完成，用了４次交换
于是当 M 能整除 N 时，用上面的办法其实只交换N次就可以完成了，当M不能整除N时
，你也可以用数学归纳法证明只要M+N次交换就够了。
那么现在你再回过头来看我的算法，就会发现它所需的总操作数最多是：
(l(k-1, k)+1)+(l(k-2,k-1)+2)+(l(k-3, k-2)+3)+...(l(1, 2)+k-1)+(l(0, 1)+k)
其中l(i-1, i)表示第i-1个负数和第i个负数之间所含的正数的个数,
所有的l(i-1, i) 1<=i<=k 的和最多是 N,
所以共需要O(N+k^2) 次交换操作.

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

: 这个复杂度不是O(k^2)吧。
: 每次挪一个负数到前一个负数你可能要走一段距离，这段距离的上限是n，不是k吧？两
: 个负数的距离跟k没必然关系。

t*e2012-02-23 08:02

32 楼

这题不需要排序啊……或者你是指先出现的负（正）数必须在后出现的负（正）数之前？

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

: 稳定排序

t*e2012-02-23 08:02

33 楼

望大牛明示……什么叫RETAIN ORDER OF APPEARANCE啊？

【在 p*****2 的大作中提到】

: 这题不是讨论过没解吗？

f*n2012-02-23 08:02

34 楼

谢谢你这么耐烦讲解啊。不过这里还是有疑问，就是你好像没计算你寻找应该移的位置
的开销啊。我不是很确定你这里是怎么决定移到哪里的，应该也有不止一种做法，但我
想到的最直接的，就是找前一个负数，然后移到前一个负数的后面。这个开销本身可以
up to (n-k)吧。
举个例子，
3 2 -8 5 -1 -2
我会第一步把-1 -2 移到 -5的后面吧。但是你怎么知道-1前面的负数在哪里呢？没有
额外的内存来建个表的话，你就得从-1往前找，这个操作的开销最大是k1 (正数的个数
)。
也许你有更巧妙的方法来查找但是我没有理解对。

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

: 先考虑如下基本问题：
: 假定一个数组前N个数是正数，后M个数是负数，如何把M个负数全部移到头部，N个正数
: 全部移到尾部，同时不改变正数与负数的相对次序？
: 其实用 N+M 次交换操作就可解决上面问题。因为每次移动一个负数时，你不需要只向
: 前移一位，而是可以－次移很多位。
: 比如你有：
: ３２５－１－２
: 你可以把２与－１交换，５与－２交换得到：
: ３－１－２２５
: 再把３与－１交换

h*g2012-02-23 08:02

35 楼

不客气, 你不需要建表去存储负数的位置，只需一个变量，扫一遍数组，找出最后一个
负数的位置，用该变量存储这个位置, 用O（N）时间。
然后从这个位置往后一个一个的查，查到下一个负数就是倒数第二个负数，然后用我提
到的方法把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出
发往后找下一个负数，。。。然后重复这一过程。
问题的关键是你从最后一个负数的位置开始向后查找，永远不需要再向前移动，而是一
直向后移，碰到下一个负数停一下，等操作完毕后继续向后移寻找下一个负数，所以最
后累计所用的时间也是O（N）。

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

: 谢谢你这么耐烦讲解啊。不过这里还是有疑问，就是你好像没计算你寻找应该移的位置
: 的开销啊。我不是很确定你这里是怎么决定移到哪里的，应该也有不止一种做法，但我
: 想到的最直接的，就是找前一个负数，然后移到前一个负数的后面。这个开销本身可以
: up to (n-k)吧。
: 举个例子，
: 3 2 -8 5 -1 -2
: 我会第一步把-1 -2 移到 -5的后面吧。但是你怎么知道-1前面的负数在哪里呢？没有
: 额外的内存来建个表的话，你就得从-1往前找，这个操作的开销最大是k1 (正数的个数
: )。
: 也许你有更巧妙的方法来查找但是我没有理解对。

f*n2012-02-23 08:02

36 楼

把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出
---->把最后一个负数移到到倒数第二个负数紧接下来的位置，这个过程的开销不是O(1
)，是O(n)吧？因为不能用额外的存储，你只能暂时存一个负数，然后把两个负数之间
的所有数一个个挪位置，直到想要的位置空出来？
Maybe I'm missing something again.. :-)

h*g2012-02-23 08:02

37 楼

你应该把目光集中到累积分析上面，不要只注重一个操作所需的时间，而是所有操作所
需的时间的和。对单个操作来讲当然是O（N），但是如果把它们求和就还是O（N），因
为你从后向前操作，永远不用回头，所以操作的时间累积不会超过O（N）。
你也可以试着搜索amortized analysis，看看相关几个问题的经典分析。记得Cormen的
算法书上也有专门一章讲这个的。

(1

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

: 把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出
: ---->把最后一个负数移到到倒数第二个负数紧接下来的位置，这个过程的开销不是O(1
: )，是O(n)吧？因为不能用额外的存储，你只能暂时存一个负数，然后把两个负数之间
: 的所有数一个个挪位置，直到想要的位置空出来？
: Maybe I'm missing something again.. :-)

f*n2012-02-23 08:02

38 楼

我明白你的意思，但我觉得加起来是O(N*k1), k1是正数的个数。
想一个简单的worst case，所有正数在一边负数在一边，每一个正数都需要从一边挪到
另一边，而且只能一个位置一个位置的挪，这本身就是O(k1^2)，对吧？ amortize后不
会是O(N)啊

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

: 你应该把目光集中到累积分析上面，不要只注重一个操作所需的时间，而是所有操作所
: 需的时间的和。对单个操作来讲当然是O（N），但是如果把它们求和就还是O（N），因
: 为你从后向前操作，永远不用回头，所以操作的时间累积不会超过O（N）。
: 你也可以试着搜索amortized analysis，看看相关几个问题的经典分析。记得Cormen的
: 算法书上也有专门一章讲这个的。
:
: (1

v*c2012-02-23 08:02

39 楼

要解是有解的，不过都比较复杂
做const space algo的人找简单算法找了二十多年也没找到，估计很难了
真要有人想研究这个问题，我给个reference吧
主要是两个idea
1. for blocks A and B, BA=reverse(reverse(A)reverse(B))
2. pack small int into a word
"Stable minimum space partitioning in linear time"
by Jyrki Katajainen and Tomi Pasanen
BIT Numerical Mathematics, 1992

on

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

: Given an array of +ve and -ve integers, re-arrange it so that u have +ves on
: one end and -ves on other,BUT RETAIN ORDER OF APPEARANCE..
: for eg,
: 1,7,-5,9,-12,15
: ans=
: -5,-12,1,7,9,15
: do it in O(n) without using any extra space.

t*e2012-02-23 08:02

40 楼

好吧想明白了就是这个要求
我在2楼给的算法不对，是因为结果会是 -5,-12,1,9,7,15，和正确答案不一致

前？

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

: 这题不需要排序啊……或者你是指先出现的负（正）数必须在后出现的负（正）数之前？