无语了，大人的 H-1B 签过，小孩的 H-4 被 check 了 38 天了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Visa - 签证

无语了，大人的 H-1B 签过，小孩的 H-4 被 check 了 38 天了

无语了，大人的 H-1B 签过，小孩的 H-4 被 check 了 38 天了# Visa - 签证

s*u2017-02-03 08:02

1 楼

发信人: shmu (shmu), 信区: FDU
标题: 追悼一位海归后自杀的复旦校友
发信站: BBS 未名空间站 (Sun Sep 30 07:25:46 2012, 美东)
近期参加校友的一个活动，得知一位熟知的校友离去的消息，非常感叹。
这位校友2001年辞去复旦大学讲师职务，自费赴美国留学，2008年获得Ph.D 后，作了
一年多薄厚，2009年于妻子离婚后，义无反顾的海归。前妻留在美国。
这位校友回国后先后干了四个单位。
第一：厦门大学
第二：桂林师范大学
第三：广东省预防医学科学院
第四；广东省湛江市疾病控制中心
四个单位均不理想，他觉得愧对前妻，愧对亲人，愧对自己的人生，选择自杀。
人生苦短，珍惜生命，珍惜生活，无论生活在哪儿，活出人生的精彩。

g*y2017-02-03 08:02

2 楼

Google » Algorithm
Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想知道这个是否有可能做到。我怎么觉得做到O(n^2)就没法提高了

b*02017-02-03 08:02

3 楼

弱弱的问一下，填ds160, U.S point of contact person里，父母在美国的联系人填本
人，那么那个“relaltionship to contact person"应该是什么呢？纠结在选项有”
relative", or "other"?谢谢拉！

z*y2017-02-03 08:02

4 楼

12 月 27 号面试，当时给了 221(g)，31 号回了资料，1 月 10 号我的 H-1B 下来了
，孩子和老婆的 H-4 就一直在 check。
小孩已经缺课 1 个多月了。几天催一回，都是模板回复。这种情况还有什么办法可想
？

s*u2017-02-03 08:02

5 楼

节哀
死亡对于死去的人
是种解脱
但对于亡故者有爱的人
却是永远的痛
所以只要这世界上还有爱你的人
请为他们好好活着
这话是对我自己说的

a*s2017-02-03 08:02

6 楼

Yes, I think:
Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
combination: the ith, jth and kth numbers (sorted from small to large).
You can essentially rule out 1/8 when you compare the required sum with that
of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
The total asymptotic cost is dominated by the sorting, which is O(NlgN).

up

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

: Google » Algorithm
: Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想知道这个是否有可能做到。我怎么觉得做到O(n^2)就没法提高了

b*32017-02-03 08:02

7 楼

relative

m*e2017-02-03 08:02

8 楼

都是看运气，也就是看vo心情，可以试试找单位律师催，就算是心理安慰吧

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

: 12 月 27 号面试，当时给了 221(g)，31 号回了资料，1 月 10 号我的 H-1B 下来了
: ，孩子和老婆的 H-4 就一直在 check。
: 小孩已经缺课 1 个多月了。几天催一回，都是模板回复。这种情况还有什么办法可想
: ？

p*n2017-02-03 08:02

9 楼

三年四个岗位，可知生命的艰难了。
RIP.

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

: 发信人: shmu (shmu), 信区: FDU
: 标题: 追悼一位海归后自杀的复旦校友
: 发信站: BBS 未名空间站 (Sun Sep 30 07:25:46 2012, 美东)
: 近期参加校友的一个活动，得知一位熟知的校友离去的消息，非常感叹。
: 这位校友2001年辞去复旦大学讲师职务，自费赴美国留学，2008年获得Ph.D 后，作了
: 一年多薄厚，2009年于妻子离婚后，义无反顾的海归。前妻留在美国。
: 这位校友回国后先后干了四个单位。
: 第一：厦门大学
: 第二：桂林师范大学
: 第三：广东省预防医学科学院

g*y2017-02-03 08:02

10 楼

好像是对的
挺好的方法啊，这么说来只要这个subset的元素个数是常数，都统一是nlogn的复杂度
不愧是传说中的牛人~

a
that

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

: Yes, I think:
: Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
: combination: the ith, jth and kth numbers (sorted from small to large).
: You can essentially rule out 1/8 when you compare the required sum with that
: of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
: The total asymptotic cost is dominated by the sorting, which is O(NlgN).
:
: up

z*y2017-02-03 08:02

11 楼

后来周五给 B************[email protected] 发了封信周一就 issue 了，也不知道是不是
催的管用。

f*r2017-02-03 08:02

12 楼

不知道他这四个岗位都是什么职务？他为什么要换的这么频繁？对工资不满还是这些地
方的人际关系复杂？

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

: 三年四个岗位，可知生命的艰难了。
: RIP.

m*02017-02-03 08:02

13 楼

我是来膜拜的。

a
that

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

g*h2017-02-03 08:02

14 楼

你们上当了，这个ID一天到晚只在各版宣扬两件事：
1，反对海归
2，揭露海归造假
要么是奇葩，要么精神分裂不是一般的程度

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

: 不知道他这四个岗位都是什么职务？他为什么要换的这么频繁？对工资不满还是这些地
: 方的人际关系复杂？

Z*92017-02-03 08:02

15 楼

hi algorithmics,
有两个问题我不是很明白：
1. 每次去掉1/8后，剩下不是一个长方体，如何继续切分？
2. 如何保证选出来的i,j,k都两两不同？

a
that

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

f*r2017-02-03 08:02

16 楼

不是吧，这个ID居然还是版主，不像是一般的水军。

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

: 你们上当了，这个ID一天到晚只在各版宣扬两件事：
: 1，反对海归
: 2，揭露海归造假
: 要么是奇葩，要么精神分裂不是一般的程度

M*G2017-02-03 08:02

17 楼

f*r2017-02-03 08:02

18 楼

不是吧，这个ID居然还是版主，不像是一般的水军。

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

: 你们上当了，这个ID一天到晚只在各版宣扬两件事：
: 1，反对海归
: 2，揭露海归造假
: 要么是奇葩，要么精神分裂不是一般的程度

a*s2017-02-03 08:02

19 楼

1. After ruling out 1/8, you proceed by 7 subproblems each of scale N^3/8.
So
f(N^3) = 7*f(N^3/8)+O(1)
The total complexity is O(log_{8/7}N^3) = O(lgN)
2. Just forget about these cases :)

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

: hi algorithmics,
: 有两个问题我不是很明白：
: 1. 每次去掉1/8后，剩下不是一个长方体，如何继续切分？
: 2. 如何保证选出来的i,j,k都两两不同？
:
: a
: that

g*h2017-02-03 08:02

20 楼

水军的确不像，但你看看它的帖子，除了那两个主题没别的了吧，除了偶尔说说绿卡。
这得是啥样的发考题？

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

: 不是吧，这个ID居然还是版主，不像是一般的水军。

f*r2017-02-03 08:02

21 楼

f(N^3) = 7*f(N^3/8)+O(1)
=> f(N^3) = O(N^3*log_8^{7}, not O(logN^3)
x-sum problems have a lower performance bound Omega(n^ceil(x/2)) for
comparison based method. so low bound for 3-sum is O(n^2), maybe google wants you to prove this results.

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

: 1. After ruling out 1/8, you proceed by 7 subproblems each of scale N^3/8.
: So
: f(N^3) = 7*f(N^3/8)+O(1)
: The total complexity is O(log_{8/7}N^3) = O(lgN)
: 2. Just forget about these cases :)

m*h2017-02-03 08:02

22 楼

还是一个超级复旦黑
一直冒充自己是复旦校友
没见过这么不要脸的人

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

: 你们上当了，这个ID一天到晚只在各版宣扬两件事：
: 1，反对海归
: 2，揭露海归造假
: 要么是奇葩，要么精神分裂不是一般的程度

Z*92017-02-03 08:02

23 楼

ye...I think so too...
O(N^3*log_8{7})..

wants you to prove this results.

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

: f(N^3) = 7*f(N^3/8)+O(1)
: => f(N^3) = O(N^3*log_8^{7}, not O(logN^3)
: x-sum problems have a lower performance bound Omega(n^ceil(x/2)) for
: comparison based method. so low bound for 3-sum is O(n^2), maybe google wants you to prove this results.

v*y2017-02-03 08:02

24 楼

给个名字吧

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

a*s2017-02-03 08:02

25 楼

.... yeah, I realized I was wrong on the analysis part, and ruling out a corner isn't enough, hmm~~~

wants you to prove this results.

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

S*e2017-02-03 08:02

26 楼

If this is true,it is too sick!!

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

: 还是一个超级复旦黑
: 一直冒充自己是复旦校友
: 没见过这么不要脸的人

b*e2017-02-03 08:02

27 楼

Problematic. It is even hard to get the sum of 2 (for a sorted list) in
log(n). The minimum is O(n). I see your recursion is wrong. It should
be something like:
T(n) = 7 * T(n/2)

for a
that

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

s*u2017-02-03 08:02

28 楼

个人隐私重要啊。还是要尊重校友和他在美国的前妻。

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

: 给个名字吧

a*h2017-02-03 08:02

29 楼

Sorry, I never saw this in the book.
Could anyone explain how to get this O(N^3*log_8{7})
from f(N^3) = 7*f(N^3/8)+O(1)?
And what is the underscore after log?

d*a2017-02-03 08:02

30 楼

Rest in peace...

f*r2017-02-03 08:02

31 楼

google master theorem or refer to Introduction to algorithms

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

: Sorry, I never saw this in the book.
: Could anyone explain how to get this O(N^3*log_8{7})
: from f(N^3) = 7*f(N^3/8)+O(1)?
: And what is the underscore after log?

a*h2017-02-03 08:02

32 楼

Then what's the underscore? log_8{7}

f*r2017-02-03 08:02

33 楼

base-8 logorithm of 7

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

: Then what's the underscore? log_8{7}

g*y2017-02-03 08:02

34 楼

I was thinking about the same flaw in algorithmics' solution. But I was not
courageous enough be to believe algorithmics was wrong. Hehe
By the way, where do you see a proof for Omega(n^ceil(x/2))? I might have
seen it somewhere for the Subset Sum NPC, but didn't know for sure.

wants you to prove this results.

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

f*r2017-02-03 08:02

35 楼

http://cjtcs.cs.uchicago.edu/articles/1999/8/cj99-08.pdf

not

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

: I was thinking about the same flaw in algorithmics' solution. But I was not
: courageous enough be to believe algorithmics was wrong. Hehe
: By the way, where do you see a proof for Omega(n^ceil(x/2))? I might have
: seen it somewhere for the Subset Sum NPC, but didn't know for sure.
:
: wants you to prove this results.

w*p2017-02-03 08:02

36 楼

本来觉得我的算法在nlgn和n^2之间，没在意
看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
得懂
assuming T=16
list after sorted
1, 2, 3, 6, 7, 8, 9
1. 简化问题。如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the las

s*e2017-02-03 08:02

37 楼

4)的"otherwise fail"不对吧。

return

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

: 本来觉得我的算法在nlgn和n^2之间，没在意
: 看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
: 得懂
: assuming T=16
: list after sorted
: 1, 2, 3, 6, 7, 8, 9
: 1. 简化问题。如果只考虑sum of 2 elements in an array equals to value T
: 1)sort array
: 2)use two points point to start and end of the list....
: find the 2 elements in O(n)

l*g2017-02-03 08:02

38 楼

我觉得otherwise是对的阿,因为这个index不可能比number index大,如果这样就不可能
存在三个数的和是T了.这是1.
关键在于这个程序中开始从end取数, 然后做binarysearch, 也就是说对于array中1/3n
的数进行循环吧. 然后循环是binarysearch对于>2/3n的数来做的.还有一个递归.这个
复杂度能满足要求吗?

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

: 4)的"otherwise fail"不对吧。
:
: return

d*n2017-02-03 08:02

39 楼

3-sum hard one, O( n ^ 2)
1) sort O ( n lg n)
2) for each i, we check whether 2 item can sum up to T-a[i] ( O ( n ^ 2))
so total O ( n ^ 2 )

History
sum up

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

w*p2017-02-03 08:02

40 楼

楼上的link 好像说最好可以到n^(3/2)
2）是可以优化的，因为是sorted list. 不过考虑的case有点多，懒得想了

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

: 3-sum hard one, O( n ^ 2)
: 1) sort O ( n lg n)
: 2) for each i, we check whether 2 item can sum up to T-a[i] ( O ( n ^ 2))
: so total O ( n ^ 2 )
:
: History
: sum up

w*p2017-02-03 08:02

41 楼

1. 简化问题。如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the last 3 number , otherwise return
false;
2) pick up number from the end of the array,
Num=array[len-i-1]=9; i=0, numberIndex=le

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

a*s2017-02-03 08:02

42 楼

Mine was very wrong, blush///

not

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