dropbox面经 （已挂T T)

1. bool match(string pattern, string data)
样例是：
pattern = 'abba',    data = 'red blue blue red'        true
pattern = 'abba',    data = 'red blue yellow red'     false
pa

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我用recursion+memoization，写完了面试官举了两个不能通过的case，对应地修改了一下，他看了一眼改完的版本说没什么问题。。。
大概是第二题木有bugfree的所以挂了= =。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题你怎么做的

LZ是UIUC的啊？你是只面了周六一场还是周六周日两场？

kuyen 发表于 2014-10-8 09:00
第二题可以练一下DFS。C++ implementation。

void help(unordered_map &info,

dfs找字符串, 不如dfs插空格

为啥这么快就知道挂了？

readman 发表于 2014-10-8 07:45
第二题你怎么做的

lz代码又长又丑。。求指点...

1. bool helper(string pattern, string data, unordered_map<char, string>& dict, unordered_set<string>& exist_words) {
   
2.     if (pattern.size() == 1) {
   
3.         if (data == dict[pattern[0]]) {
   
4.             return true;
   
5.         } else {
   
6.             return false;
   
7.         }
   
8.     }
   
9.    
   
10.     char matched_pattern = pattern[0];
    
11.     bool pattern_exist = dict.find(matched_pattern) != dict.end();
    
12.    
    
13.     if (pattern_exist) {
    
14.         if (dict[matched_pattern] !=
    
15.             data.substr(0, dict[matched_pattern].size())) {
    
16.             return false;
    
17.         }
    
18.     }
    
19.    
    
20.     string sub_pattern = pattern.substr(1, pattern.size() + 1);
    
21.    
    
22.     for (int i = 1; i <= data.size(); ++i) {
    
23.         string matched_data = data.substr(0,i);
    
24.         if (!pattern_exist && exist_words.find(matched_data) != exist_words.end()) {
    
25.             continue;
    
26.         } else if (pattern_exist && dict[matched_pattern] != matched_data) {
    
27.             continue;
    
28.         }
    
29.         
    
30.         string sub_data = data.substr(i,data.size() + 1);
    
31.         
    
32.         if (!pattern_exist) {
    
33.             dict[matched_pattern] = matched_data;
    
34.             exist_words.insert(matched_data);
    
35.         }
    
36.         
    
37.         if (helper(sub_pattern, sub_data, dict, exist_words)) {
    
38.             return true;
    
39.         }
    
40.         
    
41.         if (!pattern_exist) {
    
42.             dict.erase(matched_pattern);
    
43.             exist_words.erase(matched_data);
    
44.         }
    
45.     }
    
46. }
    
47. 
    
48. bool match(string pattern, string data) {
    
49.     unordered_map<char, string> dict;
    
50.     unordered_set<string> exist_words;
    
51.     return helper(pattern, data, dict, exist_words);
    
52. }

复制代码

asdfg 发表于 2014-10-8 08:13
LZ是UIUC的啊？你是只面了周六一场还是周六周日两场？

周六就挂了。。没有收到通知去参加周日的。。。

tbu 发表于 2014-10-8 10:12
为啥这么快就知道挂了？

如果过了当天会收到通知参加第二天第二轮。。

yvetterowe 发表于 2014-10-7 20:31
周六就挂了。。没有收到通知去参加周日的。。。

我面了周日的到现在还没消息……也是出了个bug被举了反例才改对，看来有点不妙……