一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2352|回复: 29
收起左侧

dropbox面经 (已挂T T)

[复制链接] |试试Instant~ |关注本帖
yvetterowe 发表于 2014-10-8 06:03:01 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Dropbox - 校园招聘会 - 校园招聘会 |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1. bool match(string pattern, string data)-google 1point3acres
样例是:
pattern = 'abba',    data = 'red blue blue red'        true
pattern = 'abba',    data = 'red blue yellow red'     false
pattern = 'aaaa',    data = 'red red red red'           true
pattern = 'abba',    data = red red red red'           false. from: 1point3acres.com/bbs

2. followup,去掉data中的空格怎么办
pattern = 'abba',    data = 'redbluebluered'        true. more info on 1point3acres.com
pattern = 'abba',    data = 'redblueyellowred'     false
pattern = 'aaaa',    data = 'redredredred'           true
pattern = 'abba',    data = redredredred'           false


第一题直接用hashmap很快写完。第二题我用recursion+memoization,写完了面试官举了两个不能通过的case,对应地修改了一下,他看了一眼改完的版本说没什么问题。。。
大概是第二题木有bugfree的所以挂了= =。。。. visit 1point3acres.com for more.

评分

3

查看全部评分

Interviwer 发表于 2014-10-8 15:36:15 | 显示全部楼层
思路应该差不多,楼主你是直接在纸上写的吗?这要是在纸上写,改来改去得乱成什么样啊
  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.     unordered_map<char, string>::iterator it;
  5.     it = lookup.find(pattern[0]); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  6.     if(it != lookup.end()) {
  7.         string word = it->second;. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.         if(data.size() < word.size() || data.substr(0, word.size()) != word) {
  9.             return false;
  10.         }else {. from: 1point3acres.com/bbs
  11.             return match2(pattern.substr(1), data.substr(word.size()), lookup, used);
  12.         }   . visit 1point3acres.com for more.
  13.     }else {
  14.         for(int len = 1; len <= data.size(); len ++) {
  15.             string new_word = data.substr(0, len);
  16.             if(used.find(new_word) != used.end()) {
  17.                 continue;                 . 1point3acres.com/bbs
  18.             }else {
  19.                 used.insert(new_word);
  20.                 lookup[pattern[0]] = new_word;
  21.                 if(match2(pattern.substr(1), data.substr(new_word.size()), lookup, used)) {
  22.                     return true;
  23.                 }           
  24.                 lookup.erase(pattern[0]);
  25.                 used.erase(new_word);
  26.             }   
  27.         }   . 1point3acres.com/bbs
  28.     }   

  29.     return false;
  30. }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。. 1point3acres.com/bbs
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 2 反对 0

使用道具 举报

readman 发表于 2014-10-8 07:45:27 | 显示全部楼层
第二题你怎么做的
回复 支持 反对

使用道具 举报

asdfg 发表于 2014-10-8 08:13:40 | 显示全部楼层
LZ是UIUC的啊?你是只面了周六一场还是周六周日两场?
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-8 09:00:57 | 显示全部楼层
第二题可以练一下DFS。C++ implementation。

void help(unordered_map<char, string> &info,
          unordered_set<string> &usedStr,
          const string &pattern, const string &data,.1point3acres缃
          int levelp, int leveld, bool &flag){

        int sizep = pattern.size();
        int sized = data.size();.鐣欏璁哄潧-涓浜-涓夊垎鍦
        if (levelp == sizep || leveld == sized){
                flag = (levelp == sizep && leveld == sized);
                return;
        }

        string temp("");.鐣欏璁哄潧-涓浜-涓夊垎鍦
        for (int i=levelp; i<sizep; i++){
                if (info.find(pattern) == info.end()){
                        for (int j=leveld; j<sized; j++){
. from: 1point3acres.com/bbs                                 temp += data[j];
                                if (usedStr.find(temp) != usedStr.end()) continue;. 鍥磋鎴戜滑@1point 3 acres
                                usedStr.insert(temp);
                                info[pattern] = temp;
                                help(info, usedStr, pattern, data, levelp+1, j+1, flag);. more info on 1point3acres.com
                                if (flag) return;
                                info.erase(pattern);
                                usedStr.erase(temp);
                        }
                } else {
                        for (int j=leveld; j<sized; j++){
                                temp += data[j];
                                if (info[pattern] != temp) continue;
                                help(info, usedStr, pattern, data, levelp+1, j+1, flag);
                                if (flag) return;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }
                }
        }
}


bool match(string pattern, string data){.1point3acres缃

        int p = pattern.size();. 1point3acres.com/bbs
        if (p <= 1) return true;

        unordered_map<char, string> info; // store (char, string) relation
        unordered_set<string> usedStr; // store used string to avoid that different chars correponds to same string
        bool flag = false;
        help(info, usedStr, pattern, data, 0, 0, flag);

        return flag;
}
-google 1point3acres

int main(){

        cout << match("abba", "redbluebluered") << endl;
        cout << match("abba", "redblueyellowred") << endl;
        cout << match("aaaa", "redredredred") << endl;
        cout << match("abba", "redredredred") << endl;
. From 1point 3acres bbs
        return 0;
}


补充内容 (2014-10-8 09:11):
help function中第一个for loop是多余的,只要分析当前levelp那层就行
回复 支持 反对

使用道具 举报

readman 发表于 2014-10-8 09:01:56 | 显示全部楼层
kuyen 发表于 2014-10-8 09:00
.鐣欏璁哄潧-涓浜-涓夊垎鍦第二题可以练一下DFS。C++ implementation。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
void help(unordered_map &info,

dfs找字符串, 不如dfs插空格
回复 支持 反对

使用道具 举报

tbu 发表于 2014-10-8 10:12:38 | 显示全部楼层
为啥这么快就知道挂了?
回复 支持 反对

使用道具 举报

 楼主| yvetterowe 发表于 2014-10-8 10:30:29 | 显示全部楼层
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();. From 1point 3acres bbs
  12.    
  13.     if (pattern_exist) {
  14.         if (dict[matched_pattern] !=
  15.             data.substr(0, dict[matched_pattern].size())) {
  16.             return false;
  17.         }. 1point3acres.com/bbs
  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) {. more info on 1point3acres.com
  33.             dict[matched_pattern] = matched_data;
  34.             exist_words.insert(matched_data);. From 1point 3acres bbs
  35.         }
  36.         . 鍥磋鎴戜滑@1point 3 acres
  37.         if (helper(sub_pattern, sub_data, dict, exist_words)) {
  38.             return true;
  39.         }. 1point 3acres 璁哄潧
  40.         
  41.         if (!pattern_exist) {
  42.             dict.erase(matched_pattern);
  43.             exist_words.erase(matched_data);
  44.         }
    . From 1point 3acres bbs
  45.     }
  46. }
  47. . 鍥磋鎴戜滑@1point 3 acres
  48. bool match(string pattern, string data) {
  49.     unordered_map<char, string> dict;
  50.     unordered_set<string> exist_words;. From 1point 3acres bbs
  51.     return helper(pattern, data, dict, exist_words);
  52. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| yvetterowe 发表于 2014-10-8 10:31:24 | 显示全部楼层
asdfg 发表于 2014-10-8 08:13
LZ是UIUC的啊?你是只面了周六一场还是周六周日两场?

周六就挂了。。没有收到通知去参加周日的。。。
回复 支持 反对

使用道具 举报

 楼主| yvetterowe 发表于 2014-10-8 10:32:12 | 显示全部楼层
tbu 发表于 2014-10-8 10:12
为啥这么快就知道挂了?

如果过了当天会收到通知参加第二天第二轮。。
回复 支持 反对

使用道具 举报

asdfg 发表于 2014-10-8 10:36:58 | 显示全部楼层
yvetterowe 发表于 2014-10-7 20:31
周六就挂了。。没有收到通知去参加周日的。。。

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

使用道具 举报

 楼主| yvetterowe 发表于 2014-10-8 10:43:39 | 显示全部楼层
asdfg 发表于 2014-10-8 10:36
我面了周日的到现在还没消息……也是出了个bug被举了反例才改对,看来有点不妙……

我觉得我的还很有可能是代码不够精简。。。anyway, good luck!
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-10-8 10:45:08 | 显示全部楼层
楼主有G的return offer吗
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-8 12:10:15 | 显示全部楼层
set可以不用,可以传index减少copy
有很多branch可以减少。
据trow说,这种提出来就行,写代码写出来费时间

补充内容 (2014-10-9 12:04):
linkedin一直没消息,hr说现在人多。你呢
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2014-10-10 07:55:06 | 显示全部楼层
dropbox的面试题还是挺有意思的,我的思路就是dfs,不过这个题要在短时间内一次写完不容易啊。求指教。。
  1. boolean isMatch = false;
  2.         HashMap<Character, String> dict = new HashMap<Character,String>();. more info on 1point3acres.com
  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>();. 1point 3acres 璁哄潧
  9.                 dfs(pattern,data,map,'a');
  10.                 return isMatch;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.         }
  12.         public void dfs(String pattern, String data, HashMap<Character, String> map,char max){. Waral 鍗氬鏈夋洿澶氭枃绔,
  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
    . visit 1point3acres.com for more.
  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.         }
复制代码
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-11-5 04:36:07 | 显示全部楼层
请问第二题直接动归可以做吗?
回复 支持 反对

使用道具 举报

sailorconan 发表于 2014-11-5 07:04:59 | 显示全部楼层
  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. . visit 1point3acres.com for more.
  4.                 if (i == len1) {
  5.                         if (j == len2)
  6.                                 return true;
  7.                         else
  8.                                 return false;. From 1point 3acres bbs
  9.                 } else if (j >= len2)
  10.                         return false;. 鍥磋鎴戜滑@1point 3 acres

  11.                 char c = p.charAt(i);
  12.                 if (map.containsKey(c)) {
  13.                         String val = map.get(c);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.                         int len = val.length();
  15.                         if (j + len <= len2 && s.substring(j, j + len).equals(val)) {. 1point3acres.com/bbs
  16.                                 if (match(i + 1, j + len, p, s, map)) {
  17.                                         return true;
  18.                                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                         } else {
  20.                                 return false;. 1point3acres.com/bbs
  21.                         }
  22.                 } else {// no such key, k=end
  23.                         for (int k = j; k < len2; ++k) {
  24.                                 String str = s.substring(j, k + 1);// possible word. 1point3acres.com/bbs
  25.                                 map.put(c, str);
  26.                                 if (match(i + 1, k + 1, p, s, map)) {
  27.                                         return true;
  28.                                 } else {
  29.                                         map.remove(c);
  30.                                 }

  31.                         }
  32. . more info on 1point3acres.com
  33.                 }
  34.                 return false;
  35.         }
复制代码
思路都差不多
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-11-5 15:34:27 | 显示全部楼层
刚提交了代码。做法是dfs + 剪枝。
回复 支持 反对

使用道具 举报

 楼主| yvetterowe 发表于 2014-11-5 23:44:25 | 显示全部楼层
shinichish 发表于 2014-11-5 04:36
请问第二题直接动归可以做吗?

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 23:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表