Dropbox的online coding exercise - 未名空间MITBBS历史存档

Dropbox的online coding exercise# JobHunting - 待字闺中

g*a2014-10-29 07:10

1 楼

Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
请教有没有什么好的思路？
Given a pattern and a string input - find if the string follows the same
pattern and return 0 or 1.
Examples:
1) Pattern : "abab", input: "redblueredblue" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

s*r2014-10-29 07:10

2 楼

一个星期前面过原题，用DFS做。
注意有可能会有这样的case:
"abab" input "redredredred" should return false
我当时用hashset存已经map过的pattern.

的,

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

: Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
: 请教有没有什么好的思路？
: Given a pattern and a string input - find if the string follows the same
: pattern and return 0 or 1.
: Examples:
: 1) Pattern : "abab", input: "redblueredblue" should return 1.
: 2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
: 3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

g*a2014-10-29 07:10

3 楼

多谢！
请问DFS是穷举法的意思么？
比如对于第一个pattern“a”的话遍历所有可能的子串长度？然后一直recursion，里
面加一个hashset的参数存当前出现过的所有pattern？
这样可以过test么？

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

: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,

s*r2014-10-29 07:10

4 楼

是的，有点像穷举法的感觉。
我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
上自己测试通过。
如果真的出这道题，你就不用那么紧张。
另外loghit那道也要准备，非常高频。
加油。

n*s2014-10-29 07:10

5 楼

题目不是很清楚，
如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？

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

: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,

e*i2014-10-29 07:10

6 楼

who can post a solution for the pattern matching problem. I have no clue.

s*l2014-10-29 07:10

7 楼

请问那个loghit啊
能给个link 或者说说题吗？

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

: 是的，有点像穷举法的感觉。
: 我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
: 上自己测试通过。
: 如果真的出这道题，你就不用那么紧张。
: 另外loghit那道也要准备，非常高频。
: 加油。

g*a2014-10-29 07:10

8 楼

Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
请教有没有什么好的思路？
Given a pattern and a string input - find if the string follows the same
pattern and return 0 or 1.
Examples:
1) Pattern : "abab", input: "redblueredblue" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

s*r2014-10-29 07:10

9 楼

一个星期前面过原题，用DFS做。
注意有可能会有这样的case:
"abab" input "redredredred" should return false
我当时用hashset存已经map过的pattern.

的,

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

: Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
: 请教有没有什么好的思路？
: Given a pattern and a string input - find if the string follows the same
: pattern and return 0 or 1.
: Examples:
: 1) Pattern : "abab", input: "redblueredblue" should return 1.
: 2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
: 3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

g*a2014-10-29 07:10

10 楼

多谢！
请问DFS是穷举法的意思么？
比如对于第一个pattern“a”的话遍历所有可能的子串长度？然后一直recursion，里
面加一个hashset的参数存当前出现过的所有pattern？
这样可以过test么？

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

: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,

s*r2014-10-29 07:10

11 楼

是的，有点像穷举法的感觉。
我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
上自己测试通过。
如果真的出这道题，你就不用那么紧张。
另外loghit那道也要准备，非常高频。
加油。

n*s2014-10-29 07:10

12 楼

题目不是很清楚，
如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？

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

: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,

e*i2014-10-29 07:10

13 楼

who can post a solution for the pattern matching problem. I have no clue.

s*l2014-10-29 07:10

14 楼

请问那个loghit啊
能给个link 或者说说题吗？

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

: 是的，有点像穷举法的感觉。
: 我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
: 上自己测试通过。
: 如果真的出这道题，你就不用那么紧张。
: 另外loghit那道也要准备，非常高频。
: 加油。

g*y2014-10-29 07:10

15 楼

嗯，出题人没想好。全解此题貌似要用到compiler技术。

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

: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？

g*a2014-10-29 07:10

16 楼

那个例子貌似不合适，应该是输出1，
不过楼主的意思很明确，就是不同的pattern不能map到相同的string
比如pattern “abba” 对应 string “xxxx”就不行。

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

: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？

E*c2014-10-29 07:10

17 楼

难道是这个？
http://www.mitbbs.com/article_t/JobHunting/32549839.html

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

: 请问那个loghit啊
: 能给个link 或者说说题吗？

b*72014-10-29 07:10

18 楼

只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
那位大牛能给个多项式复杂度的算法吗?

w*i2014-10-29 07:10

19 楼

让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.
boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set visited) {
if (start1 == str.length() || start2 == pattern.length) {
return start1 == str.length() && start2 == pattern.length;
}
char ch = pattern[start2++];
if (map.containsKey(ch)) {
在map里找到对应单词
if(str能够从start1开始取到这个单词）
return dfs(str, start1 + 下个单词长度,
pattern, start2, map, visited);
} else {
for (int end = start1 + 1; end <= str.length(); ++end) {
让nextWord为start1和end之间的substring,
if(nextWord在visited中) continue;
map.put(ch, nextWord);
visited.add(nextWord);
if (haveWordPattern(str, end, pattern, start2, map, visited)
) {
return true;
}
map.remove(ch);
visited.remove(nextWord);
}
return false;
}
其实里面还可以加点剪枝代码，不过大概就是这样了。

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

: 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
: 那位大牛能给个多项式复杂度的算法吗?

m*g2014-10-29 07:10

20 楼

看来刷题得多啊。

g*y2014-10-29 07:10

21 楼

嗯，出题人没想好。全解此题貌似要用到compiler技术。

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

: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？

g*a2014-10-29 07:10

22 楼

那个例子貌似不合适，应该是输出1，
不过楼主的意思很明确，就是不同的pattern不能map到相同的string
比如pattern “abba” 对应 string “xxxx”就不行。

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

: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？

E*c2014-10-29 07:10

23 楼

难道是这个？
http://www.mitbbs.com/article_t/JobHunting/32549839.html

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

: 请问那个loghit啊
: 能给个link 或者说说题吗？

b*72014-10-29 07:10

24 楼

只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
那位大牛能给个多项式复杂度的算法吗?

w*i2014-10-29 07:10

25 楼

让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.
boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set visited) {
if (start1 == str.length() || start2 == pattern.length) {
return start1 == str.length() && start2 == pattern.length;
}
char ch = pattern[start2++];
if (map.containsKey(ch)) {
在map里找到对应单词
if(str能够从start1开始取到这个单词）
return dfs(str, start1 + 下个单词长度,
pattern, start2, map, visited);
} else {
for (int end = start1 + 1; end <= str.length(); ++end) {
让nextWord为start1和end之间的substring,
if(nextWord在visited中) continue;
map.put(ch, nextWord);
visited.add(nextWord);
if (haveWordPattern(str, end, pattern, start2, map, visited)
) {
return true;
}
map.remove(ch);
visited.remove(nextWord);
}
return false;
}
其实里面还可以加点剪枝代码，不过大概就是这样了。

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

: 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
: 那位大牛能给个多项式复杂度的算法吗?

m*g2014-10-29 07:10

26 楼

看来刷题得多啊。

h*n2014-10-29 07:10

27 楼

这个应该是true的，re|dred|re|dred

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

: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,