Eb 5 投资移民最新通过率 (2012年11月） (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Immigration - 落地生根

Eb 5 投资移民最新通过率 (2012年11月） (转载)

Eb 5 投资移民最新通过率 (2012年11月） (转载)# Immigration - 落地生根

h*22012-11-27 08:11

1 楼

昨天电面，两道题不算难，求好运~~
1. Given a sorted array of floats, find the index of the number closest to x:
Example: {1.2, 2.5, 9.3} x = 5, return 1
2. Of the pairs of words in the dictionary that have no letters in common,
find one that maximizes the product of the words' lengths.
cat
dog
feed
pull
space
pair = word1, word2
length = word1.size() * word2.size()

w*n2012-11-27 08:11

2 楼

【以下文字转载自 Eb5 俱乐部】
发信人: windben (不戒), 信区: Eb5
标题: Eb 5 投资移民最新通过率 (2012年11月）
发信站: BBS 未名空间站 (Tue Nov 27 17:43:32 2012, 美东)
Eb5 投资移民，自2011年起骤然升温。根据移民局今年7月的数据统计，截止2012财年
第三季度，Eb5 第一步临时绿卡I-526的申请，从2010年1955件增加至2011年的3805件
，2012财年前3 季度更是收到4156件申请，比两年前整年的申请数量增加了1倍。增
加的大部分案件来自中国的申请人。第二步申请永久绿卡I-829的申请从2010年的768件
，增加至2011年的2345件，2012年前3季度骤减为546件。
究其原因，我们认为Eb5 的“hot”，无不与加拿大移民政策的改动息息相关。本来
，由于社会福利政策优越，加拿大一直是国人考虑移民的首选国家。2011年加拿大移民
政策收紧，资金门槛提高，名额大幅度减少，很多人因此放弃考虑加拿大，把目光
转向美国。 Eb5 作为要求条件较少的移民方式，成为越来越多富裕人士的选择。
尽管Eb5申请数量剧增，但第一步I-526申请的通过率有所下降。 2010年I-526申请的
通过率为89%， 2011年为81%， 2012年前3季度则是79%，三年降低10%。观察第二步
永久绿卡I-829申请的通过率，情形却相反。 2010年I-829申请的通过率为89%，2011
年升高至96%， 2012年前3季度则是94%，三年来I-829的批准率呈上升态势。分析原
因， 2011以来Eb5申请的基数大增，相对的，通过率有所下降；另一方面，着急申请
的人中，不乏对项目选择欠缺审慎调查的情况，因此，选择的投资项目或区域中心达
不到移民法对Eb5的要求，导致移民局的拒绝。相比之下， I-829申请通过率的升高，
说明前两年申请人数较少的时候，大家选择项目或区域中心更加慎重。

g*e2012-11-27 08:11

3 楼

第二题有什么好方法？

x:

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

: 昨天电面，两道题不算难，求好运~~
: 1. Given a sorted array of floats, find the index of the number closest to x:
: Example: {1.2, 2.5, 9.3} x = 5, return 1
: 2. Of the pairs of words in the dictionary that have no letters in common,
: find one that maximizes the product of the words' lengths.
: cat
: dog
: feed
: pull
: space

d*02012-11-27 08:11

4 楼

why not
cat* feed

x:

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

i*r2012-11-27 08:11

5 楼

Using a maximal heap for length of words?
I guess no common in letters does not matter, right?

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

: 第二题有什么好方法？
:
: x:

B*g2012-11-27 08:11

6 楼

ee ?

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

: why not
: cat* feed
:
: x:

f*n2012-11-27 08:11

7 楼

mark

J*n2012-11-27 08:11

8 楼

应该是pull * space吧？
最直观的话应该两层loop，然后问题转换成找 common letter of two words. 记录max
length, word1, word2.
至于找common，应该好多方法，可以new int[] 来记录字符出现次数，或者hashSet 判
断contains char.
复杂度这样看应该是O(n^3).
我这样对不对？有没有好的方法呢？

f*n2012-11-27 08:11

9 楼

mark

i*r2012-11-27 08:11

10 楼

Why we need to compute common letters?
I did not understand the orignal problem well. The answer should be the two
words with 1st and 2nd maximal length, am I right?

max

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

: 应该是pull * space吧？
: 最直观的话应该两层loop，然后问题转换成找 common letter of two words. 记录max
: length, word1, word2.
: 至于找common，应该好多方法，可以new int[] 来记录字符出现次数，或者hashSet 判
: 断contains char.
: 复杂度这样看应该是O(n^3).
: 我这样对不对？有没有好的方法呢？

s*72012-11-27 08:11

11 楼

brute force solution to compare each pair, complexity should be O(n^2*26)= O
(n^2), assumption all word are lower case.
public static int largestProduct(String[] s)
{
int[][] c=new int[s.length][26];
int max=1;
for (int i=0; i{
for (int j=0; ja']=1;
}
for (int i=0; i{
j: for (int j=i+1; j{
for (int k=0; k<26; k++)
{
if(c[i][k]+c[j][k]==2) continue j;
}
max=Math.max(max,s[i].length()*s[j].length());
}
}
return max;
}

max

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

l*i2012-11-27 08:11

12 楼

pull和space有common p吧

max

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

J*n2012-11-27 08:11

13 楼

额，是的，眼花了..

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

: pull和space有common p吧
:
: max

J*n2012-11-27 08:11

14 楼

恩， maximum 应该是26，我弄错了，算下来还是O(n^2)

O
-'

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

: brute force solution to compare each pair, complexity should be O(n^2*26)= O
: (n^2), assumption all word are lower case.
: public static int largestProduct(String[] s)
: {
: int[][] c=new int[s.length][26];
: int max=1;
: for (int i=0; i: {
: for (int j=0; j: a']=1;

l*a2012-11-27 08:11

15 楼

我想这么做
1) sort the string array in descending by length
2) start from the beginning.
a[i]a[j] (initial a[0]a[1])should be the biggest, check whether they have
common character, if they don't have, 版主
otherwise , a[i+1]a[j],a[i]a[j+1]插入heap,
找到大的,判断是否有common character, 有的话继续.
###注意插入过程中可能有已出现过的，需要排除，a[i]a[i]的情况也该排除

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

: 第二题有什么好方法？
:
: x:

l*82012-11-27 08:11

16 楼

a[i]a[j]是什么？

have

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

: 我想这么做
: 1) sort the string array in descending by length
: 2) start from the beginning.
: a[i]a[j] (initial a[0]a[1])should be the biggest, check whether they have
: common character, if they don't have, 版主
: otherwise , a[i+1]a[j],a[i]a[j+1]插入heap,
: 找到大的,判断是否有common character, 有的话继续.
: ###注意插入过程中可能有已出现过的，需要排除，a[i]a[i]的情况也该排除

l*a2012-11-27 08:11

17 楼

排序结束后的两个单词啊
index i
index j

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

: a[i]a[j]是什么？
:
: have

l*82012-11-27 08:11

18 楼

if they don't have, 版主
是什么意思呢？

have

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

l*a2012-11-27 08:11

19 楼

版主是done,
hehe

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

: if they don't have, 版主
: 是什么意思呢？
:
: have

l*82012-11-27 08:11

20 楼

呵呵，你这个算法还是O(n^2)吧？（n是单词个数）

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

: 版主是done,
: hehe

d*s2012-11-27 08:11

21 楼

想了想可以这样：
hash unique letter sequence and length
比如pipe 是 ip - 4，如此遍历一遍更新最大值
然后把所有的m个length, m所以复杂度是O(n+m) = O(n)

b*t2012-11-27 08:11

22 楼

举个例子？

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

: 想了想可以这样：
: hash unique letter sequence and length
: 比如pipe 是 ip - 4，如此遍历一遍更新最大值
: 然后把所有的m个length, m: 所以复杂度是O(n+m) = O(n)

l*a2012-11-27 08:11

23 楼

pipe 是 ip - 4
这是什么意思？看不懂

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

: 想了想可以这样：
: hash unique letter sequence and length
: 比如pipe 是 ip - 4，如此遍历一遍更新最大值
: 然后把所有的m个length, m: 所以复杂度是O(n+m) = O(n)

d*s2012-11-27 08:11

24 楼

对不起上面想错了我再想想

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

: pipe 是 ip - 4
: 这是什么意思？看不懂

g*e2012-11-27 08:11

25 楼

反正我是想不出比n^2更好的解法

h*d2012-11-27 08:11

26 楼

Good luck!

x:

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

l*r2012-11-27 08:11

27 楼

我觉得你的思路很好，可以简化问题。

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

: 对不起上面想错了我再想想

l*a2012-11-27 08:11

28 楼

展开说说,好吗

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

: 我觉得你的思路很好，可以简化问题。

l*r2012-11-27 08:11

29 楼

我就说说我在他基础上想的，可能错得离谱，轻拍。
扫描所有的词，每个词先sort字母，然后去掉duplicate的字母，得到简化版 see ->
es
简化版做key，简化版对应word做value，放入 HashMap,
同时track当前扫到的最长length.
每扫到一个新词，如果简化版已在Hashmap中，新词更长的话，value变成新词。否之
skip。
当然这样可能时间复杂度也不理想。

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

: 展开说说,好吗

w*n2012-11-27 08:11

30 楼

想到一个算法，可以优化，但还是n^2：
1. 对于每一个词，创建一个整数标签。标签前6位表示词的长度，后26位表示出现某个
字符与否。比如：如果词中有c，那么第3比特就是1，否则为0.
2. 对这些整数标签排序。所得数组记为A
3.
let n be the size of A
let furthest = n;
let cmax = 0;
for(int i = 0; i < furthest; i++)
{
for(int j = i + 1; j < furthest; j++)
{
if(A[i] and A[j] do not share bits in the last 26 bits)
{
cmax = max(cmax, product of the first 6 bits of A[i], A[j]);
furthest = j;
break;
}
}
}
return cmax;
此法前两步是nlogn。最后一步理论上还是n^2.可是实际情况下由于furthest的限制，
恐怕会比Brute force 快得多。
实在想不出来还能怎么优化。。。

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

: 第二题有什么好方法？
:
: x:

w*s2012-11-27 08:11

31 楼

第一题，实际上就是二分查找插入的位置k，选择k的两边2个元素比较一下，哪个接近
返回哪个的位置。
int find_min_distance(float* a, int n, int b, int e)
{
if (e < b)
{
float f1 = abs(a[e] - n);
float f2 = abs(a[b] - n);
return f1 < f2 ? e : b;
}
int m = (b + e) / 2;
if (a[m] < n)
{
return find_min_distance(a, n, b + 1, e);
}
else if (a[m] > n)
{
return find_min_distance(a, n, b, m - 1);
}
else
{
return m;
}
}

x:

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

w*s2012-11-27 08:11

32 楼

第二题用trie?前缀树？

x:

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

b*g2012-11-27 08:11

33 楼

我觉得原题的意思是考虑一对单词不要有common letter，不考虑单词本身是否有重复
的letter，所以feed和pull是valid pair.
int maximalProductPairedWordLens(string strs[], int n) {
if (n < 2) return 0;
int maxProduct = 0;
vector > table(n,vector(26,false));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (int)strs[i].size(); ++j) {
table[i][strs[i][j]-'a'] = true;
}
}
for (int i = 0; i < n-1; ++i) {
for (int j = i+1; j < n; ++j) {
bool hasCommonLetter = false;
for (int k = 0; k < 26; ++k) {
if (table[i][k] && table[j][k]) {
hasCommonLetter = true;
break;
}
}
if (!hasCommonLetter)
maxProduct = max(maxProduct,(int)(strs[i].size()*strs[j].
size()));
}
}
return maxProduct;
}

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

: 我就说说我在他基础上想的，可能错得离谱，轻拍。
: 扫描所有的词，每个词先sort字母，然后去掉duplicate的字母，得到简化版 see ->
: es
: 简化版做key，简化版对应word做value，放入 HashMap,
: 同时track当前扫到的最长length.
: 每扫到一个新词，如果简化版已在Hashmap中，新词更长的话，value变成新词。否之
: skip。
: 当然这样可能时间复杂度也不理想。

l*u2012-11-27 08:11

34 楼

bless

x:

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

h*22012-11-27 08:11

35 楼

我刚开始写的是N^2地解法，后来他说可以稍微改进了下
我就说可以先把每个单词处理下，用map记录出现的字母（其实遍历单词的话还是要n^2
的），说了以后他貌似还比较满意，感觉他没想要我写出太高级地方法来｀～

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

: 第二题有什么好方法？
:
: x:

h*22012-11-27 08:11

36 楼

喔喔，哈哈
word1 word2 仅仅是指代两个单词，没有序号的意思哈
表达不清，不好意思

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

: why not
: cat* feed
:
: x:

h*22012-11-27 08:11

37 楼

我刚开始写的是N^2遍历单词的解法，后来他说可以稍微改进了下
我就说可以先把每个单词处理下，用map记录出现的字母（其实遍历单词的话还是要n^2
的），说了以后他貌似还比较满意，感觉他没想要我写出太高级地方法来｀～

max

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

m*k2012-11-27 08:11

38 楼

1. compute each word's binary representation in 26 bits and save as an int,
for example, "a" becomes 10000...., which is 1*2^25
"abc" becomes 1110000.... , which is 7 * 2^23
2. construct a Hashmap by
scan the words in the dictionary, if key already exists, update the word if
it is longer.
result=[maximum,"",""];
3. with all the keys in the map,
for (key1 in map.keys):
for (key2 in map.keys):
if (key1 & key2 ==0):
x = word1.length()*words.length()
if (x> result[0]):
result=[x, word1, word2]
return result;

l*a2012-11-27 08:11

39 楼

能说说你预处理的作用吗？

if

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

: 1. compute each word's binary representation in 26 bits and save as an int,
: for example, "a" becomes 10000...., which is 1*2^25
: "abc" becomes 1110000.... , which is 7 * 2^23
: 2. construct a Hashmap by
: scan the words in the dictionary, if key already exists, update the word if
: it is longer.
: result=[maximum,"",""];
: 3. with all the keys in the map,
: for (key1 in map.keys):
: for (key2 in map.keys):

p*o2012-11-27 08:11

40 楼

随手写了个第一感觉的笨办法
In [28]: words = ['cat','dog','feed','pull','space']
In [29]: ws = [(len(w),set(w)) for w in
...: sorted(words, key=len, reverse=True)]
In [30]: n = len(words)
In [31]: ws
Out[31]:
[(5, {'a', 'c', 'e', 'p', 's'}),
(4, {'d', 'e', 'f'}),
(4, {'l', 'p', 'u'}),
(3, {'a', 'c', 't'}),
(3, {'d', 'g', 'o'})]
In [32]: maxprod = -1
...: for i in range(n-1):
...: wi = ws[i]
...: if wi[0] * ws[i+1][0] < maxprod:
...: break
...: for wj in ws[i+1:]:
...: prod = wi[0] * wj[0]
...: if prod < maxprod:
...: break
...: elif wi[1] & wj[1]:
...: continue
...: else:
...: maxprod = prod
...: break
...: print(maxprod)
...:
16

p*o2012-11-27 08:11

41 楼

开26bits的话，不适用于latin-1甚至unicode字符的情况

if

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

b*g2012-11-27 08:11

42 楼

N * LogN 解法
class StrCompare
{
public:
bool operator()( const string& str1, const string& str2 ) const
{
return str1.size() > str2.size();
}
};
class PairFinder
{
public:
void init()
{
m_nProductSize = 0;
}

size_t getProduct() const { return m_nProductSize; }
pair getPair() const { return make_pair( m_csFirst, m_
csSecond ); }

void compute( vector& vctStr )
{
init();
if( vctStr.size() < 2 ) return;

StrCompare compare;
sort( vctStr.begin(), vctStr.end(), compare );

unsigned int nRunningMask = (unsigned int)-1;
vector vctMask;
size_t i = 0;
for( ; i{
nRunningMask &= getMask( vctStr[i] );
if( !nRunningMask ) break;
vctMask.push_back( nRunningMask );
}

for( ; i{
long nIndex = searchIndex( getMask( vctStr[i] ), vctMask );
if( nIndex == -1 ) continue;
size_t nProductSize = vctStr[i].size() * vctStr[nIndex].size();
if( nProductSize > m_nProductSize )
{
m_nProductSize = nProductSize;
m_csFirst = vctStr[nIndex];
m_csSecond = vctStr[i];
}
}

}

private:
size_t m_nProductSize;
string m_csFirst;
string m_csSecond;

unsigned int getMask( const string& str ) const
{
unsigned int nMask = 0;
for( size_t i=0; i{
assert( str[i] >= 'a' && str[i] <= 'z' );
nMask |= 1 << (str[i] - 'a');
}
return nMask;
}

long searchIndex( unsigned int nMask, const vector&
vctMask ) const
{
long lo = 0, hi = vctMask.size()-1;
while( lo < hi )
{
long mid = (lo + hi )/2;
if( (vctMask[mid] & nMask) == 0 )
hi = mid;
else
lo = mid+1;
}

if( (vctMask[lo] & nMask) == 0 ) return lo;
else return -1;
}
};
int main(int argc, const char * argv[])
{
PairFinder finder;
const char* ppsz[] = {"cat", "dog", "feed", "pull", "space"};
vector vctStr( ppsz, ppsz+5 );
finder.compute( vctStr );
cout << finder.getProduct() << 't' << finder.getPair().first
<< 't' << finder.getPair().second << endl;
}

x:

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

i*r2012-11-27 08:11

43 楼

Any explanation?

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

: N * LogN 解法
: class StrCompare
: {
: public:
: bool operator()( const string& str1, const string& str2 ) const
: {
: return str1.size() > str2.size();
: }
: };
: class PairFinder

l*82012-11-27 08:11

44 楼

binary search 不成立吧？

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

: N * LogN 解法
: class StrCompare
: {
: public:
: bool operator()( const string& str1, const string& str2 ) const
: {
: return str1.size() > str2.size();
: }
: };
: class PairFinder

m*k2012-11-27 08:11

45 楼

不好意思，表达不清，第一步就是解释第二步时怎么把一个单词存入map中。

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

: 能说说你预处理的作用吗？
:
: if

p*d2012-11-27 08:11

46 楼

For input {"yxxxx", "yxxx", "xxxz", "yz", "y", "z"}, your code returns 8 for
"xxxz" and "yz", which is clearly a wrong answer.
You can do a binary search on the running intersection of letters, but you
cannot guarantee there is no shared letters between two words A and B, even
when the running intersection at A does not share any letter with B, just as
in the case of "xxxz" and "yz" where the running intersection at "xxxz" is
"xxx" which shares no letters with "yz".

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

: N * LogN 解法
: class StrCompare
: {
: public:
: bool operator()( const string& str1, const string& str2 ) const
: {
: return str1.size() > str2.size();
: }
: };
: class PairFinder

P*92012-11-27 08:11

47 楼

多谢！楼主好运！