logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
郁闷，去微软面试，才回答一个问题就被赶出来了！
avatar
郁闷，去微软面试，才回答一个问题就被赶出来了！# Joke - 肚皮舞运动
b*7
1 楼
Desgin an algorithm to find whether a given sting is formed by the
Intealeaving of two given strings. 注意，原来的两个given strings的本身的
character的顺序不能变。
这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
advance both ptrs until they are different and then move one of them back.
The point is who is to be moved back? You cannot simply randomly choose one.
For example,
stringA: ABCEF...
string B: ABCA...
dst string : ABCABCEF....
那么，如果取B's ABCA 就错了。
哪位大侠能指教怎么
avatar
a*w
2 楼
amex怎么升cl？打电话？hard pull?
谢谢
avatar
g*n
3 楼
zz
avatar
w*o
4 楼
【 以下文字转载自 Seattle 讨论区 】
发信人: littlecute (村姑), 信区: Seattle
标 题: 郁闷，去微软面试，才回答一个问题就被赶出来了！
发信站: BBS 未名空间站 (Sat Nov 28 17:15:48 2009, 美东)
考官：Windows7专业版在中国大陆的零售价是多少？
我 ：5块
考官：出去，下一位。
从别的网站上看来的，还有一些也比较好笑！
郁闷,去移动面试,才回答了一个问题就被赶出来了!
教官:你的手机号码是多少?
我: 131XXXXXXXX
考官:出去,下一位.
我去GOOGLE面试，
问了一个问题就被赶了出来；
问：你是如何知道GOOGLE的？
答：摆渡。
我去麦当劳面试，
问了一个问题就被赶了出来；
问：你有何才艺？
答：（唱）有了肯德基，生活好滋味。
avatar
f*r
5 楼
这题要用suffix tree 或者suffix array. 然后求LCP判断一下就可以了

one.

【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
avatar
d*o
6 楼
登录后不能直接request吗？
avatar
r*g
7 楼
郁闷,去JOKE面试,才回答了一个问题就被赶出来了!
橙子:你笑话都在那看到的?
我: 菌斑。
橙子:出去,下一位.
avatar
j*j
8 楼
这种题目一般用backtracking
avatar
a*w
9 楼
哪里有？

【在 d***o 的大作中提到】
: 登录后不能直接request吗？
avatar
d*0
10 楼
考官：你最崇拜的企业家是谁？
我：Jobs大师。
考官：滚。

【在 w******o 的大作中提到】
: 【 以下文字转载自 Seattle 讨论区 】
: 发信人: littlecute (村姑), 信区: Seattle
: 标 题: 郁闷，去微软面试，才回答一个问题就被赶出来了！
: 发信站: BBS 未名空间站 (Sat Nov 28 17:15:48 2009, 美东)
: 考官：Windows7专业版在中国大陆的零售价是多少？
: 我 ：5块
: 考官：出去，下一位。
: 从别的网站上看来的，还有一些也比较好笑！
: 郁闷,去移动面试,才回答了一个问题就被赶出来了!
: 教官:你的手机号码是多少?
avatar
C*n
11 楼
能不能把那个例子再说明详细一点呢？
我没怎么看懂。

one.

【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
avatar
l*e
12 楼
去百事可乐公司面试，才回答一个问题就被赶出来了
考官：你现在心情怎么样：
我：雪碧，透心凉，心飞扬！
考官：出去，下一位！
avatar
g*y
13 楼
我们算法课作业题
用suffix当然是最好的
不会suffix的话，用DP有两种复杂度
一种是O(A.size * B.size * dist.size)
一种是O(dist.size^2)
avatar
t*e
14 楼
咋那么难？？？我都不会，好打击信心哦～～～～
avatar
b*7
15 楼
geniusxsy， 能否指教怎么用suffix tree或者suffix array做啊？
avatar
g*y
16 楼
呵呵，发现我说错了。这题用suffix tree好像不是很适合呢
就DP做吧

【在 b******7 的大作中提到】
: geniusxsy， 能否指教怎么用suffix tree或者suffix array做啊？
avatar
g*y
17 楼
你先给interleaving定义一下？
我做的算法课的作业题里面，interleaving的定义是，string的一个subsequence是A的
repeation，剩下的subsequence是B的repeation
repetion的定义是：
ABC的repetion就是ABCABCABC...ABC + '空/A/AB'

one.

【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
avatar
g*y
18 楼
一般是DP！backtracking的话，是指数复杂度了吧

【在 j*****j 的大作中提到】
: 这种题目一般用backtracking
avatar
C*n
19 楼
如果"取B' ABCA就错了"
这句话什么意思啊？
谁能说说看?

one.

【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
avatar
C*n
20 楼
能不能说说DP的思路阿？

【在 g*******y 的大作中提到】
: 一般是DP！backtracking的话，是指数复杂度了吧
avatar
b*e
21 楼
Typical DP.
Consider a rectangle network of m*n, where m is the length of a and n
is the length of b. Label the rows using characters in string a and
cols using characters in string b. For your example:
\ a b c e f
a . . . . .
b . . . . .
c . . . . .
a . . . . .
All that you need to do is to find a path from the top left corner to
the bottom right corner. This at most requires you to examine m*n
states, which gives you m*n time complexity.
avatar
C*n
22 楼
what does the element [i][j] means?

【在 b***e 的大作中提到】
: Typical DP.
: Consider a rectangle network of m*n, where m is the length of a and n
: is the length of b. Label the rows using characters in string a and
: cols using characters in string b. For your example:
: \ a b c e f
: a . . . . .
: b . . . . .
: c . . . . .
: a . . . . .
: All that you need to do is to find a path from the top left corner to
avatar
b*e
23 楼
Good question, but bad for you not to think.
Assume top left is (0, 0), then element[i][j] is a boolean which means
whether there is a path from (0, 0) to (i, j) that covers the first i+j
characters in the target.

【在 C**********n 的大作中提到】
: what does the element [i][j] means?
avatar
g*y
24 楼
In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j]

【在 C**********n 的大作中提到】
: what does the element [i][j] means?
avatar
g*y
25 楼
in case of A string B string are repetion of small size string A' and B'
there's an DP algorithm that takes O(string.size * A'.size * B'.size)
so in cases where sizes of A' B' are very small, this algorithm will be much
better.

【在 b***e 的大作中提到】
: Typical DP.
: Consider a rectangle network of m*n, where m is the length of a and n
: is the length of b. Label the rows using characters in string a and
: cols using characters in string b. For your example:
: \ a b c e f
: a . . . . .
: b . . . . .
: c . . . . .
: a . . . . .
: All that you need to do is to find a path from the top left corner to
avatar
b*e
26 楼
// I don't see why I didn't explain enough, or, you didn't understand
enough?
"A path from (0, 0) to (i, j)" is not a bit different from "an
interleaving of A[1...i] and B[1...j]".

is an interleaving of A[1...i] and B[1...j]

【在 g*******y 的大作中提到】
: In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j]
avatar
C*n
27 楼
那也就是说，
不用看什么从[0][0]到[M][N]有什么路径，而是直接看[M][N]=1就可以了把？

an interleaving of A[1...i] and B[1...j]

【在 g*******y 的大作中提到】
: In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j]
avatar
g*y
28 楼
呵呵，不好意思，我回帖子的时候你还没发解释，等我吃了顿饭回来把回帖发了才发现
你已经解释了。。。

【在 b***e 的大作中提到】
: // I don't see why I didn't explain enough, or, you didn't understand
: enough?
: "A path from (0, 0) to (i, j)" is not a bit different from "an
: interleaving of A[1...i] and B[1...j]".
:
: is an interleaving of A[1...i] and B[1...j]
avatar
g*y
29 楼
看[1][str.size-1] || [2][str.size-2] ||...|| [str.size-1][1]
看辅对角线

【在 C**********n 的大作中提到】
: 那也就是说，
: 不用看什么从[0][0]到[M][N]有什么路径，而是直接看[M][N]=1就可以了把？
:
: an interleaving of A[1...i] and B[1...j]
avatar
k*k
30 楼
/* a simple brute force sol.
similar to the sol. of another m$ problem:
matching a*?b with adxefb
*/
int isInterleaving(char* a, char* b, char* c,
int ai, int bi, int ci){
printf("entry info: %d, %d, %d,\n", ai, bi, ci);
if (a[0]=='\0' && b[0]=='\0' && c[0]=='\0')
return 1;
if (b[0]=='\0' && a[0]=='\0' && c[0]!='\0')
return 0;

int tmp1=0; int tmp2=0;
if (a[0]!='\0' && a[0]==c[0]){
tmp1 = isInterleaving(a+1, b, c+1,
ai+1, bi, ci+1);

}
if (tmp
avatar
g*y
31 楼
I think you are likely to fail the interview if you do something like this...

【在 k*k 的大作中提到】
: /* a simple brute force sol.
: similar to the sol. of another m$ problem:
: matching a*?b with adxefb
: */
: int isInterleaving(char* a, char* b, char* c,
: int ai, int bi, int ci){
: printf("entry info: %d, %d, %d,\n", ai, bi, ci);
: if (a[0]=='\0' && b[0]=='\0' && c[0]=='\0')
: return 1;
: if (b[0]=='\0' && a[0]=='\0' && c[0]!='\0')
avatar
k*k
32 楼
如果可能，您是否可以贴个 DP 的implementation.
先谢了。
avatar
k*k
33 楼
@geniusxsy; thanks,
//my dp solution.
int isInterleavingdp(char* a, char* b, char* str, int alen, int blen){
int i, j;
int m[alen+1][blen+1];
memset(m, 0, (alen+1)*(blen+1)*sizeof(int));

for(i=0; iif (a[i]==str[i])
m[i+1][0]=1;
else
break;
}
for(j=0; jif (b[j] == str[j])
m[0][j+1]=1;
else
break;
}
for(i=1; i<=alen; i++){
for(j=1; j<=blen; j++){
int r1 = (m[i-1][j]>0) && a[i-1]==str[i+j-1];
int r2
avatar
g*y
34 楼
use bool m[][] to save space.
or even better,
you compute the matrix line by line in 次对角线 direction, this way you'll
need only O(N) space.

【在 k*k 的大作中提到】
: @geniusxsy; thanks,
: //my dp solution.
: int isInterleavingdp(char* a, char* b, char* str, int alen, int blen){
: int i, j;
: int m[alen+1][blen+1];
: memset(m, 0, (alen+1)*(blen+1)*sizeof(int));
:
: for(i=0; i: if (a[i]==str[i])
: m[i+1][0]=1;
avatar
b*7
35 楼
感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！
avatar
b*7
36 楼
感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！
avatar
b*7
37 楼
感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！
avatar
b*7
38 楼
感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！
avatar
k*k
39 楼
hi, geniusxsy
i am not quite get the "次对角线 direction" idea.
if possible, could you kindly elaborate... such as give me an simple example.
char* a="ab";
char* b="de";
char* c="adbe";
thank u so much.
avatar
b*7
40 楼
感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！
avatar
b*7
41 楼
感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！
avatar
b*7
42 楼
感谢大家，我也想了想，blaze的答案确实对，另外B(m,n)==1 应该就能说明true
avatar
b*7
43 楼
感谢大家，我也想了想，blaze的答案确实对，另外B(m,n)==1 应该就能说明true
avatar
b*e
44 楼
Are you a robot? LOL

【在 b******7 的大作中提到】
: 感谢大家，我也想了想，blaze的答案确实对，另外B(m,n)==1 应该就能说明true
avatar
b*e
45 楼
Roughly:
for (int s = 0; s < m+n; s++) {
for (int i = 0; i < s; i++) {
int j = s - i;
element[i][j] =
(element[i-1][j] && a[i] = t[s]) ||
(element[i][j-1] && b[j] = t[s]);
}
}
where s identifies a diagonal.

【在 k*k 的大作中提到】
: @geniusxsy; thanks,
: //my dp solution.
: int isInterleavingdp(char* a, char* b, char* str, int alen, int blen){
: int i, j;
: int m[alen+1][blen+1];
: memset(m, 0, (alen+1)*(blen+1)*sizeof(int));
:
: for(i=0; i: if (a[i]==str[i])
: m[i+1][0]=1;
avatar
s*x
46 楼
做一个NFA接受(A+B)^*，然后看这个NFA是不是接受你给的那个字符串。就是复杂度不
小。

one.

【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
avatar
P*f
47 楼
baseline的解法就是dp了.O(MN)
当然在实际中可以根据输入先算一些hash值,提高amortized performance

one.

【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
相关阅读
mitbbs的web界面有问题方舟子老婆竟然叫刘菊花？各位知道繁体“和气”的反面看上去像什么字么？ (转载)特此发贴感谢大家。钱包掉进公厕马桶里， 算是吉照吗？ (转载)Re: 胡海清和温如春，你要哪个？ (转载)搞笑吧 BAC upgraded by BAC (转载)谁给编的舞蹈，简直太太太牛P了_ciros.fr 爆笑视频新加坡一公司不懂华人民俗 派“4元”红包员工脸黑：）国外惊现被通缉哥，苍天啊，大地啊我们在大学就是这样吃火锅的 哎。。。。年底了，活不下去了，贱卖贱卖 (转载)非诚勿扰出现休斯敦40岁处男WSN (转载)有没有同学用过这个药？创意 ～～～ （zz）：）就在马上要下班之际，竟然看到这样的一句成语。csboy2007 20min内奔脸奔自己：）玩得好high啊：）：）职业装真的很重要 超级玛丽脱了衣服竟是这个样子
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。