Redian新闻
>
收到EAD,大家觉得我这H-1B还用transfer吗? (转载)
avatar
收到EAD,大家觉得我这H-1B还用transfer吗? (转载)# Immigration - 落地生根
N*8
1
1. 这个算是老题了,就是给一个unsorted array算每个element有多少在右边等于或小
于自己的elements,比如:
input array = {1,3,2,4,5,4,2}
output array = {0,2,1,2,2,1,0}
比较常规的建树解法需要O(nlogn)时间+O(n)空间,有没有O(n)的时间解法,空间不限?
2. 算n个array的median
avatar
s*d
2
【 以下文字转载自 I485 讨论区 】
发信人: sleepingwind (起风), 信区: I485
标 题: 收到EAD,大家觉得我这H-1B还用transfer吗?
发信站: BBS 未名空间站 (Mon Nov 28 21:50:02 2011, 美东)
前些天觉得绿卡(或EAD)快有戏了,再加上公司的人事变动,开始找工作,出乎意料的
顺利,上周一拿到offer,但是连EAD都还没有,新公司答应给办H-1B premium tranfer
,利用长假期把材料准备好发给了律师,今天律师来回了几封信在准备申请的表格,可
是晚上回家收到EAD。老公的意思是H-1B premium tranfer接着办,不要用EAD上班,以
防万一绿卡被拒。他在什么地方就看到过用了EAD上班,绿卡被拒,不得不回国的事。
还有用了EAD,H-1B 是否就失效了呢?
大家帮我看看?多谢多谢。绿卡是老公申的EB2,140早批了。
avatar
p*2
3

限?
input array = {1,3,2,4,5,4,2}
output array = {0,2,1,2,2,1,0}
这个没看明白。

【在 N*****8 的大作中提到】
: 1. 这个算是老题了,就是给一个unsorted array算每个element有多少在右边等于或小
: 于自己的elements,比如:
: input array = {1,3,2,4,5,4,2}
: output array = {0,2,1,2,2,1,0}
: 比较常规的建树解法需要O(nlogn)时间+O(n)空间,有没有O(n)的时间解法,空间不限?
: 2. 算n个array的median

avatar
h*l
4
转h1b,反正不用你出钱

tranfer

【在 s**********d 的大作中提到】
: 【 以下文字转载自 I485 讨论区 】
: 发信人: sleepingwind (起风), 信区: I485
: 标 题: 收到EAD,大家觉得我这H-1B还用transfer吗?
: 发信站: BBS 未名空间站 (Mon Nov 28 21:50:02 2011, 美东)
: 前些天觉得绿卡(或EAD)快有戏了,再加上公司的人事变动,开始找工作,出乎意料的
: 顺利,上周一拿到offer,但是连EAD都还没有,新公司答应给办H-1B premium tranfer
: ,利用长假期把材料准备好发给了律师,今天律师来回了几封信在准备申请的表格,可
: 是晚上回家收到EAD。老公的意思是H-1B premium tranfer接着办,不要用EAD上班,以
: 防万一绿卡被拒。他在什么地方就看到过用了EAD上班,绿卡被拒,不得不回国的事。
: 还有用了EAD,H-1B 是否就失效了呢?

avatar
N*8
5
呵呵,二爷我还以为你肯定见过这题呢。
就是a[i]算一共有多少比自己小或等于的elements在a[i+1:n-1]的区间。

【在 p*****2 的大作中提到】
:
: 限?
: input array = {1,3,2,4,5,4,2}
: output array = {0,2,1,2,2,1,0}
: 这个没看明白。

avatar
k*e
6
suggest to do H1b transfer
avatar
p*2
7

不好意思。刚才晕了。去算大于或等于的了。这题没见过呀。我其实做题很少的。

【在 N*****8 的大作中提到】
: 呵呵,二爷我还以为你肯定见过这题呢。
: 就是a[i]算一共有多少比自己小或等于的elements在a[i+1:n-1]的区间。

avatar
N*8
8
版本有贴过这题,但是原帖中没有O(n)的解法。但是还是好奇,到底有没有O(n)的解法。
还有一道相似题就是inversion count了,就是给个array算在右边比自己大的元素个数
。就是mergesort的变形了,但是好像也没有O(n)的解法,同样空间不限。

【在 p*****2 的大作中提到】
:
: 不好意思。刚才晕了。去算大于或等于的了。这题没见过呀。我其实做题很少的。

avatar
l*8
9
第一个题目, 如果有general 的O(n)的时间解法,那么就代表有general的O(n)时间排
序算法了。 所以我觉得在一般情况下, 没有O(n)的时间解法。

限?

【在 N*****8 的大作中提到】
: 1. 这个算是老题了,就是给一个unsorted array算每个element有多少在右边等于或小
: 于自己的elements,比如:
: input array = {1,3,2,4,5,4,2}
: output array = {0,2,1,2,2,1,0}
: 比较常规的建树解法需要O(nlogn)时间+O(n)空间,有没有O(n)的时间解法,空间不限?
: 2. 算n个array的median

avatar
t*7
10
第一题应该没有O(n)的搞法吧...第二题倒是有O(n)的搞法,好像是一篇高端论文...
nlgn的搞法应该是median of medians algo...同求熟悉这个算法的大神指点.
avatar
p*2
11
第一题nlogn的解法就是先建一个BST, 然后再从后往前走一遍。每到一个element,就
search一下BST,然后大于等于他的node都+1, 然后看他自己的node的counter是多少就
行了?
avatar
l*8
12
我觉得可以在BST的每个node里面存上子树的节点总数

【在 p*****2 的大作中提到】
: 第一题nlogn的解法就是先建一个BST, 然后再从后往前走一遍。每到一个element,就
: search一下BST,然后大于等于他的node都+1, 然后看他自己的node的counter是多少就
: 行了?

avatar
p*2
13

就是这个意思。但是一次都存不行吧?还是得按照从右往左的顺序吧?
或者用最后一个element做root,但是不能保证balanced。

【在 l*********8 的大作中提到】
: 我觉得可以在BST的每个node里面存上子树的节点总数
avatar
l*8
14
从root到destination node的path上的所有节点的右子树的node count加起来,应该可
以吧?

【在 p*****2 的大作中提到】
:
: 就是这个意思。但是一次都存不行吧?还是得按照从右往左的顺序吧?
: 或者用最后一个element做root,但是不能保证balanced。

avatar
N*8
15
从右往左扫数组,然后建AVL/RB tree(普通的BST不能保证logn时间),右边的分支需要
把root的个数加上然后加一,左边的不需要。
然后再扫数组,从左往右,每次node都减一。

【在 p*****2 的大作中提到】
: 第一题nlogn的解法就是先建一个BST, 然后再从后往前走一遍。每到一个element,就
: search一下BST,然后大于等于他的node都+1, 然后看他自己的node的counter是多少就
: 行了?

avatar
N*8
16
嗯,你的说法有道理。

【在 l*********8 的大作中提到】
: 第一个题目, 如果有general 的O(n)的时间解法,那么就代表有general的O(n)时间排
: 序算法了。 所以我觉得在一般情况下, 没有O(n)的时间解法。
:
: 限?

avatar
N*8
17
先求n个array自己的median,然后再在这个n个median中求median,这个median就是整
个n个数组的median,毛想想好像对,有简单的数学证明吗?

【在 t*********7 的大作中提到】
: 第一题应该没有O(n)的搞法吧...第二题倒是有O(n)的搞法,好像是一篇高端论文...
: nlgn的搞法应该是median of medians algo...同求熟悉这个算法的大神指点.

avatar
p*2
18

是这样。我的意思是面试写的时候应该怎么建tree呢?

【在 l*********8 的大作中提到】
: 从root到destination node的path上的所有节点的右子树的node count加起来,应该可
: 以吧?

avatar
N*8
19
可能更多的是讲思路吧,顺便把AVL/RB里面的关键算法也考了,突然觉得这个题一举两
得啊。
avatar
r*g
21
这个不对吧。。例子:
1 2 100
3 4 50
median应该是3.5啊

【在 N*****8 的大作中提到】
: 先求n个array自己的median,然后再在这个n个median中求median,这个median就是整
: 个n个数组的median,毛想想好像对,有简单的数学证明吗?

avatar
h*f
22
BST不一定能在为O(n)内建成,因为可能要重新balance.
TopCoder的讨论中提到用merge sort. 应该可以ensure为O(nlogn) with O(n) space.
avatar
h*f
23
Counter example:
1 2 3=>median 2
4 5 6=>median 5
1 5 5=>median 5
median of 2 5 5 = 5
actual median of all 3 arrays = 4

【在 N*****8 的大作中提到】
: 先求n个array自己的median,然后再在这个n个median中求median,这个median就是整
: 个n个数组的median,毛想想好像对,有简单的数学证明吗?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。