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...
相关阅读
博导昨天姐姐算是明白为什么一部分女人会剩下来 (转载)放心吧。。。（zz）童言无忌啊，哈哈成龙广告代言遭恶搞 “DUANG”成网络热词这里藏龙卧虎，求教一个打结图解。FBI：全美50州均有IS支持者 反恐形势重于911头夹住了！Re: 想知道色戒里汤唯和梁朝伟是真做的么 (转载)新 图不响，再亲一口（zz）军版现在用term上有问题，翻不了页冷笑话只因是羊年，夫妻不愿生宝宝（转载） (转载)看黑白掐架，体会白人的战斗素养 (转载)猫老的日常 -- 健身冷笑话的构成是什么？这个图怎么样 (转载)互联网算utility了如果不下跪，那头猪是不是还不会当晚被宰
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。