EAD approve之后多久能收到卡 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

EAD approve之后多久能收到卡

EAD approve之后多久能收到卡# EB23 - 劳工卡

w*a2015-06-01 07:06

1 楼

"10分钟前面经"系列的第三弹，这次是F家电二面。
不用大家Bless了，这次必挂了。就问了一道技术题。
Word breaking
// How many spaces can we add to a word such that:
// All subwords can be found within a given dictionary
// fireman
// fire man -> 2 words
// fir em an -> 3 words
/* DICT
a
an
em
fir
fire
ire
ma
man
*/
这题以前没做过，我当时想这个看上去就是个典型DP题。
但是没做过不敢妄为就想先用回溯先做个解出来再跟他讨论DP。
然后回溯做法出了个bug被他指出来，然后卡壳了好一会。最后DP也没做成。面试时间
一共三十分钟左右。就因为卡了会壳估计面试官都没兴趣让我再用别的解法做了。。
而且中途还有个，我循环用i和j被他指出来了。我正常变量命名都还行，就是循环我一
直喜欢用i，以后连循环我都不敢用i了。大家吸取教训。
给大家个教训吧。没做过的题千万别慌。写出代码了自己一定要多用几个test测测，自
己发现了bug跟他发现了bug完全是两个数量级的悲剧。
Move on了，还有一家G，继续准备。

x*02015-06-01 07:06

2 楼

老板催的急。有谁share一下时间？多谢。

M*52015-06-01 07:06

3 楼

需要找出所有的组合还是只需要找出一个即可？
Bless G家面试。。。

y*02015-06-01 07:06

4 楼

1周左右。

f*x2015-06-01 07:06

5 楼

bless G

f*x2015-06-01 07:06

6 楼

现在从RD开始多久Approve

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

: 1周左右。

w*a2015-06-01 07:06

7 楼

找出substring最多的一组。

y*02015-06-01 07:06

8 楼

2-3个月。

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

: 现在从RD开始多久Approve

w*a2015-06-01 07:06

9 楼

不需要枚举出来，给个数量就行。

y*02015-06-01 07:06

10 楼

2-3个月。

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

: 现在从RD开始多久Approve

w*x2015-06-01 07:06

11 楼

DP经典题，递归也可以吧

x*02015-06-01 07:06

12 楼

我的不到两个月就approve了。

w*a2015-06-01 07:06

13 楼

刚看了用memoization做.
递归肯定可以，但是毕竟效率低。更重要的是我出BUG被指出来还卡壳了。。

j*p2015-06-01 07:06

14 楼

我家的批了三个礼拜才收到卡，还是我做了SR的结果

a*82015-06-01 07:06

15 楼

bless G, 顺便mark题，
和 leetcode Substring with Concatenation of All Words有点像，

a*o2015-06-01 07:06

16 楼

我昨晚收到approval notice, 为什么卡不是一起来的呢？

w*a2015-06-01 07:06

17 楼

刚看了用memoization做.
递归肯定可以，但是毕竟效率低。更重要的是我出BUG被指出来还卡壳了。。

a*o2015-06-01 07:06

18 楼

具体啥bug?

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

: 刚看了用memoization做.
: 递归肯定可以，但是毕竟效率低。更重要的是我出BUG被指出来还卡壳了。。

w*a2015-06-01 07:06

19 楼

刚看了用memoization做.
递归肯定可以，但是毕竟效率低。更重要的是我出BUG被指出来还卡壳了。。

a*o2015-06-01 07:06

20 楼

看了一下楼主一面的很牛啊,为啥f家还要二面呢?
我记得面得好,一面就行了呀,还是记错了?

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

: "10分钟前面经"系列的第三弹，这次是F家电二面。
: 不用大家Bless了，这次必挂了。就问了一道技术题。
: Word breaking
: // How many spaces can we add to a word such that:
: // All subwords can be found within a given dictionary
: // fireman
: // fire man -> 2 words
: // fir em an -> 3 words
: /* DICT
: a

d*y2015-06-01 07:06

21 楼

int numofword(string& S)
{
unordered_set dict;
dict.insert(string("a"));
dict.insert(string("an"));
dict.insert(string("em"));
dict.insert(string("fir"));
dict.insert(string("fire"));
dict.insert(string("ire"));
dict.insert(string("ma"));
dict.insert(string("man"));
vector vNumW(S.size()+1,-1);
vNumW[0]=0;
for(int i=1;i<=S.size();++i){
for(int j=i-1;j>=0;--j){
if(dict.count(S.substr(j,i-j)))
vNumW[i] = max(vNumW[i],vNumW[j]+1);
}
}
return vNumW[S.size()];
}
为什么循环的时候不能用i,j?

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

w*a2015-06-01 07:06

22 楼

面试官感觉变量命名不好。

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

: int numofword(string& S)
: {
: unordered_set dict;
: dict.insert(string("a"));
: dict.insert(string("an"));
: dict.insert(string("em"));
: dict.insert(string("fir"));
: dict.insert(string("fire"));
: dict.insert(string("ire"));
: dict.insert(string("ma"));

M*52015-06-01 07:06

23 楼

int combCount(std::string& str, std::set& dict){
if( str.length()==0 )
return 1;

int count = 0;
for(int i=1; i<=str.length(); i++){
std::string first = str.substr(0,i);
if( i==str.length() ){
if( dict.find(first)==dict.end() )
return -1;
else
return 1;
}
if( dict.find(sub)!=dict.end() ){
std::string remaining = str.substr(i);
int sub_count = combCount(remaining, dict);
if( sub_count!=-1 )
count += sub_count;
}
}

if(count==0)
return -1;
return count;
}
这样写行不行？

d*e2015-06-01 07:06

24 楼

def break_words(line, sol, result):
if not line:
result.append(sol[:])
else:
for i in xrange(len(line)):
if in_dict(line[:i+1]):
sol.append(line[:i+1])
break_words(line[i+1:], sol, result)
sol.pop()

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

H*s2015-06-01 07:06

25 楼

循环用 i 为啥不可以啊？几乎所有人都这样写啊。

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

j*y2015-06-01 07:06

26 楼

bless
是要返回最少的所需的space 还是返回最多的单词数?
我这个是返回最少的所需的 space
int numberSpaceNeed(string s, unordered_set & dict)
{
int n = s.length();
int dp[n][n];
for(int i = 0; i < n ; ++i)
{
if(dict.find(s.substr(i, 1) != dict.end()))
{
dp[i][i] = 0;
}
else
{
dp[i][i] = n;
}
}
for(int k = 2; k <= n; ++k) // k is the length of substr
for(int i = 0; i <= n - k; ++i)
{
dp[i][i + k - 1] = n;
if(dict.find(s.substr(i, k) != dict.end()))
{
dp[i][i + k - 1] = 0;
continue;
}
for(int j = i + 1; j < i + k - 1; ++j)
{
dp[i][i + k - 1] = min(dp[i][i + k - 1], dp[
i][j] + dp[j + 1][i + k - 1] + 1);
}
}
return dp[0][n - 1];
}

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

w*x2015-06-01 07:06

27 楼

为什么用二维数组？

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

: bless
: 是要返回最少的所需的space 还是返回最多的单词数?
: 我这个是返回最少的所需的 space
: int numberSpaceNeed(string s, unordered_set & dict)
: {
: int n = s.length();
: int dp[n][n];
: for(int i = 0; i < n ; ++i)
: {
: if(dict.find(s.substr(i, 1) != dict.end()))

j*y2015-06-01 07:06

28 楼

dp 阿， dp[i][j] 表示 break s[i,...,j] 所需的 space

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

:
: 为什么用二维数组？

l*h2015-06-01 07:06

29 楼

求dp的状态方程怎么写？

s*s2015-06-01 07:06

30 楼

lz加油！我猜如果f还像去年一样大招人的话，你还是有机会的！

S*02015-06-01 07:06

31 楼

不对吧

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

: dp 阿， dp[i][j] 表示 break s[i,...,j] 所需的 space

j*y2015-06-01 07:06

32 楼

这个问题是求需要插入的最少的 space的数目吗？

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

:
: 不对吧

l*b2015-06-01 07:06

33 楼

先bless，再看！

l*82015-06-01 07:06

34 楼

我也觉得用一维数组就够了。

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

: dp 阿， dp[i][j] 表示 break s[i,...,j] 所需的 space

M*52015-06-01 07:06

35 楼

我求的是所有可能的space组合。。。

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

: 这个问题是求需要插入的最少的 space的数目吗？

j*y2015-06-01 07:06

36 楼

我的理解是如果用一维数组的话
dp[i] 表示 break s[0,...,i] 所需的 space 是吧？

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

: 我也觉得用一维数组就够了。

j*y2015-06-01 07:06

37 楼

应该不是所有 space的组合

【在 M********5 的大作中提到】

: 我求的是所有可能的space组合。。。

j*y2015-06-01 07:06

38 楼

也不好说 :)

应该不是所有 space的组合

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

: 应该不是所有 space的组合

w*x2015-06-01 07:06

39 楼

一维数组

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

: 也不好说 :)
:
: 应该不是所有 space的组合

l*82015-06-01 07:06

40 楼

是的

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

: 我的理解是如果用一维数组的话
: dp[i] 表示 break s[0,...,i] 所需的 space 是吧？

j*y2015-06-01 07:06

41 楼

想了一下，一维数组确实够了 :)
int numberSpaceNeed(string s, unordered_set & dict)
{
int n = s.length();
int dp[n];
if(dict.find(s.substr(0, 1)) != dict.end())
{
dp[0] = 0;
}
else
{
dp[0] = n;
}
for(int i = 1; i < n; ++i)
{
if(dict.find(s.substr(0, i + 1)) != dict.end())
{
dp[i] = 0;
}
else
{
dp[i] = n;
for(int j = 0; j < i; ++j)
{
if(dict.find(s.substr(j + 1, i - j)) != dict
.end())
{
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
}
return dp[n - 1];
}

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

: 我也觉得用一维数组就够了。

l*82015-06-01 07:06

42 楼

dp[i] = min(dp[i], dp[j] + 1);
为什么用min?

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

: 想了一下，一维数组确实够了 :)
: int numberSpaceNeed(string s, unordered_set & dict)
: {
: int n = s.length();
: int dp[n];
: if(dict.find(s.substr(0, 1)) != dict.end())
: {
: dp[0] = 0;
: }
: else

w*a2015-06-01 07:06

43 楼

感谢楼上的bless
我是根本没想到电面就开始考DP题，DP题我做了不超过10题。所以拿道题我也没敢用DP
做。怕写错，就用递归做了。给你们看看我做的吧。最后代码没啥问题，我刚刚跑了几
个测试都过了。
void maxSubwords(int subs, string& str, map& dict,int id, int &
maxNumber){
if(id == str.size()){
maxNumber = max(subs,maxNumber);
return;
}
for(int subStrBegin = id; subStrBegin < str.size(); subStrBegin ++){
bool canContinue = false;
for(int subStrEnd = subStrBegin ; subStrEnd < str.size(); subStrEnd
++){
string substring = str.substr(subStrBegin ,subStrEnd-subStrBegin
+1);
if(subStrEnd maxSubwords(subs+1,str,dict,subStrEnd+1,maxNumber);
canContinue = true;
}
}
if(!canContinue) break;
}
}

f*e2015-06-01 07:06

44 楼

facebook肯定看复杂度的，recursive效率太低，burtal force应该不难吧。
不过这题有比较经典的O(N)算法。

DP

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

: 感谢楼上的bless
: 我是根本没想到电面就开始考DP题，DP题我做了不超过10题。所以拿道题我也没敢用DP
: 做。怕写错，就用递归做了。给你们看看我做的吧。最后代码没啥问题，我刚刚跑了几
: 个测试都过了。
: void maxSubwords(int subs, string& str, map& dict,int id, int &
: maxNumber){
: if(id == str.size()){
: maxNumber = max(subs,maxNumber);
: return;
: }

p*22015-06-01 07:06

45 楼

我好像在blog里写过一次。分析了几种变形。
http://blog.sina.com.cn/s/blog_b9285de20101hrg7.html

j*y2015-06-01 07:06

46 楼

比如算 dp[4]， n = 100
先初始化 dp[4] = 100, 这个数字表示没办法 break s[0,...,4]
j = 0, 表示 break s[0,...,4]成 s[0] 和 s[1,...,4]
这时候如果 s[1,...,4]是一个单词的话，
那么 dp[4] = min(dp[4], dp[0] + 1)
j = 1, 表示 break s[0,...,4]成 s[0,...,1] 和 s[2,...,4]
这时候如果 s[2,...,4]是一个单词的话，那么 dp[4] = min(dp[4], dp[1] + 1)
j = 2,...
j = 3,...

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

: dp[i] = min(dp[i], dp[j] + 1);
: 为什么用min?

w*a2015-06-01 07:06

47 楼

谁能想到他们电面就开始DP。。。

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

: facebook肯定看复杂度的，recursive效率太低，burtal force应该不难吧。
: 不过这题有比较经典的O(N)算法。
:
: DP

M*52015-06-01 07:06

48 楼

anything is possible
你也可能不会想到面Graph里面的shortest path的，所以做好准备确实是最关键的。。。
anyway, Big Bless for your Google interview!

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

: 谁能想到他们电面就开始DP。。。

w*a2015-06-01 07:06

49 楼

我也不知道。。反正他给我指出让我改了
代码洁癖吧

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

: 循环用 i 为啥不可以啊？几乎所有人都这样写啊。

w*a2015-06-01 07:06

50 楼

是啊归根结底还是准备不充分

。。

【在 M********5 的大作中提到】

: anything is possible
: 你也可能不会想到面Graph里面的shortest path的，所以做好准备确实是最关键的。。。
: anyway, Big Bless for your Google interview!

b*w2015-06-01 07:06

51 楼

新新手问一下：啥是DP?

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

: DP经典题，递归也可以吧

l*82015-06-01 07:06

52 楼

谢谢解释。我把题目理解为：把字符串分成尽量多的单词了。。。。

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

: 比如算 dp[4]， n = 100
: 先初始化 dp[4] = 100, 这个数字表示没办法 break s[0,...,4]
: j = 0, 表示 break s[0,...,4]成 s[0] 和 s[1,...,4]
: 这时候如果 s[1,...,4]是一个单词的话，
: 那么 dp[4] = min(dp[4], dp[0] + 1)
: j = 1, 表示 break s[0,...,4]成 s[0,...,1] 和 s[2,...,4]
: 这时候如果 s[2,...,4]是一个单词的话，那么 dp[4] = min(dp[4], dp[1] + 1)
: j = 2,...
: j = 3,...

w*a2015-06-01 07:06

53 楼

就是一个循环的判断，我没注意到。。

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

: 具体啥bug?

z*82015-06-01 07:06

54 楼

新手弱弱的回你，dynamic programming，动态规划。。

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

: 新新手问一下：啥是DP?

b*w2015-06-01 07:06

55 楼

谢了。知道了这个，我也应该从新新手升级到新手了

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

: 新手弱弱的回你，dynamic programming，动态规划。。

P*b2015-06-01 07:06

56 楼

我在觉得这道题递归比DP要难呢

【在 M********5 的大作中提到】

: int combCount(std::string& str, std::set& dict){
: if( str.length()==0 )
: return 1;
:
: int count = 0;
: for(int i=1; i<=str.length(); i++){
: std::string first = str.substr(0,i);
: if( i==str.length() ){
: if( dict.find(first)==dict.end() )
: return -1;

l*a2015-06-01 07:06

57 楼

这题不就是这个意思吗？

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

: 谢谢解释。我把题目理解为：把字符串分成尽量多的单词了。。。。

s*02015-06-01 07:06

58 楼

bless g

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

c*t2015-06-01 07:06

59 楼

我觉得你理解的对，应该用max

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

: 谢谢解释。我把题目理解为：把字符串分成尽量多的单词了。。。。

c*t2015-06-01 07:06

60 楼

够简洁，不懂c++,但目测好像过不了test case "bafireman"

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

w*a2015-06-01 07:06

61 楼

DP思路对了就很简单了，代码好写啊。
递归考编码功底，我就出了BUG了。虽然后来改对了但是面试官肯定不开心了。
我现在吸取经验了，考功底的题，一定要实现把所有的测试用例都写好。代码写完了挨
个测试，都通过了再跟面试官说it's ok。这次就是吃的这个亏。

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

: 我在觉得这道题递归比DP要难呢

b*e2015-06-01 07:06

62 楼

lz说了这个题有个前提是 All subwords can be found within a given dictionary，
否则的话就复杂了吧。

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

: 够简洁，不懂c++,但目测好像过不了test case "bafireman"

d*x2015-06-01 07:06

63 楼

用递归的dp啊。。

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

: DP思路对了就很简单了，代码好写啊。
: 递归考编码功底，我就出了BUG了。虽然后来改对了但是面试官肯定不开心了。
: 我现在吸取经验了，考功底的题，一定要实现把所有的测试用例都写好。代码写完了挨
: 个测试，都通过了再跟面试官说it's ok。这次就是吃的这个亏。

c*t2015-06-01 07:06

64 楼

哦，这样啊，其实也不复杂，加个判断if(i==0)....就可以了

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

: lz说了这个题有个前提是 All subwords can be found within a given dictionary，
: 否则的话就复杂了吧。

j*22015-06-01 07:06

65 楼

这题跟cc150的17.14几乎一样吧？只不过17.14是求令非法字符最少的分法，这个是求
令合法单词数最多的分法，只要小小改动就行。递归DP。循环DP不行吧？

e*s2015-06-01 07:06

66 楼

这题他是要随意一个分法，还是有要求（分出最少的词或分出最多的词）
下面是一个递归写法，DFS找到第一个分法
public static String segmentStringRecursive(String s, Set dict){
if(dict.contains(s)) return s;
int len = s.length();
for(int i = 1; i < len; i++)
{
String prefix = s.substring(0, i);
if(dict.contains(prefix))
{
String suffix = s.substring(i);
String segSuffix = segmentStringRecursive(suffix, dict);
if(segSuffix != null)
return prefix + " " + segSuffix;
}
}
return null;
}

w*a2015-06-01 07:06

67 楼

求分出最多的。

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

: 这题他是要随意一个分法，还是有要求（分出最少的词或分出最多的词）
: 下面是一个递归写法，DFS找到第一个分法
: public static String segmentStringRecursive(String s, Set dict){
: if(dict.contains(s)) return s;
: int len = s.length();
: for(int i = 1; i < len; i++)
: {
: String prefix = s.substring(0, i);
: if(dict.contains(prefix))
: {