dropbox面经 （已挂T T)

asdfg 发表于 2014-10-8 10:36
我面了周日的到现在还没消息……也是出了个bug被举了反例才改对，看来有点不妙……

我觉得我的还很有可能是代码不够精简。。。anyway, good luck!

楼主有G的return offer吗

女神来了

set可以不用，可以传index减少copy
有很多branch可以减少。
据trow说，这种提出来就行，写代码写出来费时间

补充内容 (2014-10-9 12:04):
linkedin一直没消息，hr说现在人多。你呢

思路应该差不多，楼主你是直接在纸上写的吗？这要是在纸上写，改来改去得乱成什么样啊

1. bool match(string pattern, string data, unordered_map<char, string> &lookup, unordered_set<string> &used) {
   
2.     if(pattern.size() == 0 && data.size() == 0)     return true;
   
3.     if(pattern.size() == 0 || data.size() == 0)     return false;
   
4. 
   
5.     unordered_map<char, string>::iterator it;
   
6.     it = lookup.find(pattern[0]);
   
7. 
   
8.     if(it != lookup.end()) {
   
9.         string word = it->second;
   
10.         if(data.size() < word.size() || data.substr(0, word.size()) != word) {
    
11.             return false;
    
12.         }else {
    
13.             return match2(pattern.substr(1), data.substr(word.size()), lookup, used);
    
14.         }   
    
15.     }else {
    
16.         for(int len = 1; len <= data.size(); len ++) {
    
17.             string new_word = data.substr(0, len);
    
18.             if(used.find(new_word) != used.end()) {
    
19.                 continue;                 
    
20.             }else {
    
21.                 used.insert(new_word);
    
22.                 lookup[pattern[0]] = new_word;
    
23.                 if(match2(pattern.substr(1), data.substr(new_word.size()), lookup, used)) {
    
24.                     return true;
    
25.                 }           
    
26.                 lookup.erase(pattern[0]);
    
27.                 used.erase(new_word);
    
28.             }   
    
29.         }   
    
30.     }   
    
31. 
    
32.     return false;
    
33. }
    

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

dropbox的面试题还是挺有意思的，我的思路就是dfs，不过这个题要在短时间内一次写完不容易啊。求指教。。

1. boolean isMatch = false;
   
2.         HashMap<Character, String> dict = new HashMap<Character,String>();
   
3.         public boolean match2(String pattern, String data){
   
4.                 if (pattern.length() == 0 && data.length() == 0)
   
5.                         return true;
   
6.                 if (pattern.length() == 0 || data.length() == 0)
   
7.                         return false;
   
8.                 HashMap<Character, String> map = new HashMap<Character, String>();
   
9.                 dfs(pattern,data,map,'a');
   
10.                 return isMatch;
    
11.         }
    
12.         public void dfs(String pattern, String data, HashMap<Character, String> map,char max){
    
13.                 if (pattern.length() == 0){
    
14.                         if (data.length() == 0){
    
15.                                 dict = new HashMap<Character,String>(map);
    
16.                                 isMatch = true;
    
17.                         }
    
18.                         return;
    
19.                 }
    
20.                 int i;
    
21.                 String str;
    
22.                 // match first, then do the recursion
    
23.                 if (map.containsKey(pattern.charAt(0))){
    
24.                         str = map.get(pattern.charAt(0));
    
25.                         if (str.length() > data.length() || !str.equals(data.substring(0, str.length())))
    
26.                                 return;
    
27.                         dfs(pattern.substring(1),data.substring(str.length()),map,max);
    
28.                 }
    
29.                 else{
    
30.                         for (i=1;i<data.length()-pattern.length()+2;i++){
    
31.                                 str = data.substring(0,i);
    
32.                                 map.put(max, str);
    
33.                                 dfs(pattern.substring(1),data.substring(i),map,(char)(max+1));
    
34.                                 map.remove(max);
    
35.                         }
    
36.                 }
    
37.         }

复制代码

请问第二题直接动归可以做吗？

1. static boolean match(int i, int j, String p, String s, Map<Character, String> map) {
   
2.                 int len1 = p.length(), len2 = s.length();
   
3. 
   
4.                 if (i == len1) {
   
5.                         if (j == len2)
   
6.                                 return true;
   
7.                         else
   
8.                                 return false;
   
9.                 } else if (j >= len2)
   
10.                         return false;
    
11. 
    
12.                 char c = p.charAt(i);
    
13.                 if (map.containsKey(c)) {
    
14.                         String val = map.get(c);
    
15.                         int len = val.length();
    
16.                         if (j + len <= len2 && s.substring(j, j + len).equals(val)) {
    
17.                                 if (match(i + 1, j + len, p, s, map)) {
    
18.                                         return true;
    
19.                                 }
    
20.                         } else {
    
21.                                 return false;
    
22.                         }
    
23.                 } else {// no such key, k=end
    
24.                         for (int k = j; k < len2; ++k) {
    
25.                                 String str = s.substring(j, k + 1);// possible word
    
26.                                 map.put(c, str);
    
27.                                 if (match(i + 1, k + 1, p, s, map)) {
    
28.                                         return true;
    
29.                                 } else {
    
30.                                         map.remove(c);
    
31.                                 }
    
32. 
    
33.                         }
    
34. 
    
35.                 }
    
36.                 return false;
    
37.         }

复制代码

思路都差不多

刚提交了代码。做法是dfs + 剪枝。

shinichish 发表于 2014-11-5 04:36
请问第二题直接动归可以做吗？

我一开始尝试用dp，面试官提示说太复杂然后我就用dfs了。。。如果能写出来应该也行吧