一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
jpeng7 发表于 2016-11-30 06:04:33 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚面完,分享经验攒人品。
interview 1 :
  面试官叫Jeremy Hoffman,美国人。
  介绍有趣的项目,针对项目问了些问题。
  code:. 1point 3acres 璁哄潧
    1. input file,file中是一堆string,要求除去重复行并输出,A:map存每行,重复就skip;
        follow up:file非常大怎么办, A: trie树存
    2. 如果一个map的size非常小,怎么implement,我用了链表,写得不太对;
interview 2 :
  面试官叫Shumin Yang,台湾人。.鐣欏璁哄潧-涓浜-涓夊垎鍦
  没有问项目,直接code。
  code:
    1. 给一堆button 1 2 3 4 5 , 可以按很多次,但是不能有重复,每次按的button可以是多个button的组合,like 1-23-4,

        1-23-4 跟 1-32-4不算重复,1-23-34算重复,
        输出所有可能的按法。
        我感觉跟subset类似,所以用了recursion求所有可能的combination,然后对每个combination求剩下的button的combination,每次求combination都存进一种可能性,如此往复,直到没有button可以选择。
. From 1point 3acres bbs        combination的代码写完了,解释了很久才说懂他,后面处理的函数没有写完,说了思路写了些伪代码跟注释。
. Waral 鍗氬鏈夋洿澶氭枃绔,
应该挂了,去吃点好的,晚上还得上课,大家加油。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

catinclay 发表于 2016-11-30 06:13:18 | 显示全部楼层
感觉应该是先求所有permutation, 然后再输出所有往中间插入'-'的方法
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:26:31 | 显示全部楼层
catinclay 发表于 2016-11-30 06:13
感觉应该是先求所有permutation, 然后再输出所有往中间插入'-'的方法

我一开始也是这么做的,但是被面试官建议不这样做,因为我当时写的求combination是顺序有关的,不太好处理duplicate,求问怎么得到顺序无关的combination呀?
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:27:28 | 显示全部楼层
catinclay 发表于 2016-11-30 06:13
感觉应该是先求所有permutation, 然后再输出所有往中间插入'-'的方法

说反了,我做的是顺序无关的,怎么求顺序相关呀?就是 既能得到321,又能有123
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-30 07:28:33 | 显示全部楼层
jpeng7 发表于 2016-11-30 07:26
我一开始也是这么做的,但是被面试官建议不这样做,因为我当时写的求combination是顺序有关的,不太好处 ...

为什么面试官不建议这样作呀...感觉这样就能不用处理duplicate的问题呀-google 1point3acres

补充内容 (2016-11-30 07:30):
顺序无关的combination 就是所有combination下去作permutation. visit 1point3acres.com for more.

补充内容 (2016-11-30 07:31):
我也說反了..
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:31:34 | 显示全部楼层
catinclay 发表于 2016-11-30 07:28. more info on 1point3acres.com
为什么面试官不建议这样作呀...感觉这样就能不用处理duplicate的问题呀

假设我们有三个button,我的combination求的结果是{{1,2,3},{1,2},{1,3},{2,3},{1},{2},{3}},但是其实还要有{3,2,1},{3,1,2}啊等等的,这个我不会怎么求。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-30 07:33:53 | 显示全部楼层
jpeng7 发表于 2016-11-30 07:31
假设我们有三个button,我的combination求的结果是{{1,2,3},{1,2},{1,3},{2,3},{1},{2},{3}},但是其实还 ...

假设三个button
所有permutation:
123
132
213
231
312
321

所有'-'的插入法
000
0-00
00-0
0-0-0

把这4种插入法跟上面6种permutation全部交叉产生结果就会是所有的方法

补充内容 (2016-11-30 07:36):
也就是
123, 1-23, 12-3, 1-2-3
132, 1-32, 13-2, 1-3-2
213, 2-13, 21-3, 2-1-3
231, 2-31, 23-1, 2-3-1
312, 3-12, 31-2, 3-1-2. 1point3acres.com/bbs
321, 3-21, 32-1, 3-2-1
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:36:10 | 显示全部楼层
catinclay 发表于 2016-11-30 07:33
假设三个button. from: 1point3acres.com/bbs
所有permutation:
123
-google 1point3acres
嗯不仅要permutation,还需要combination,因为可以不用到所有button,嗯,难道先求到所有的combination然后再分别求permutation?好像也可以。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-30 07:37:30 | 显示全部楼层
jpeng7 发表于 2016-11-30 07:36.1point3acres缃
嗯不仅要permutation,还需要combination,因为可以不用到所有button,嗯,难道先求到所有的combination ...

恩 先combination再permutation, 挺麻烦的 以为全部的button都要用到

补充内容 (2016-11-30 07:38):.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果是这样的话 用back-tracking好像会比较快
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:39:47 | 显示全部楼层
catinclay 发表于 2016-11-30 07:37
恩 先combination再permutation, 挺麻烦的 以为全部的button都要用到

补充内容 (2016-11-30 07:38):
-google 1point3acres
但是这样比我那个方法直观简单多了……我那个还得在循环里面调用递归……哎。anyway,谢谢指教~
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:40:38 | 显示全部楼层
catinclay 发表于 2016-11-30 07:37 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
恩 先combination再permutation, 挺麻烦的 以为全部的button都要用到. 1point3acres.com/bbs

补充内容 (2016-11-30 07:38):
. Waral 鍗氬鏈夋洿澶氭枃绔,
我用backtracking求的combination,你的意思是?
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-30 07:51:41 | 显示全部楼层
jpeng7 发表于 2016-11-30 07:40.鐣欏璁哄潧-涓浜-涓夊垎鍦
我用backtracking求的combination,你的意思是?

其实应该都差不多啦...
no more idea
回复 支持 反对

使用道具 举报

zhangxi1994 发表于 2016-11-30 11:22:54 | 显示全部楼层
第一题file那个不太明白是什么意思诶,,楼主能再详细说一下问题么?为什么是一行一行的存啊。。
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 12:13:59 | 显示全部楼层
zhangxi1994 发表于 2016-11-30 11:22
第一题file那个不太明白是什么意思诶,,楼主能再详细说一下问题么?为什么是一行一行的存啊。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
有一个input file,内容是
apple pen
pineapple pen. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
ang-google 1point3acres
penpineapple
apple pen
其中第一行跟最后一行是一样的,所以只需要输出第一行。不用care input file这个条件,可以只当是一个string数组
回复 支持 反对

使用道具 举报

zhangxi1994 发表于 2016-12-1 05:26:09 | 显示全部楼层
jpeng7 发表于 2016-11-30 12:13-google 1point3acres
有一个input file,内容是
apple pen
pineapple pen

谢谢楼主!想再问一下,一个map的size比较小那道题,是问怎么实现hashmap吗?
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-12-1 07:13:54 | 显示全部楼层
zhangxi1994 发表于 2016-12-1 05:26. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
谢谢楼主!想再问一下,一个map的size比较小那道题,是问怎么实现hashmap吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对的,紫薯紫薯紫薯
回复 支持 反对

使用道具 举报

xxxxx56789 发表于 2016-12-2 08:33:21 | 显示全部楼层
        第二题这样写不知道对不对

        public static  List<String>  buttonCombine(List<Integer> nums){.鏈枃鍘熷垱鑷1point3acres璁哄潧
             List<String> re = new ArrayList<String>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
             boolean[] used = new boolean[nums.size()];
             help(re,0, new StringBuilder(), used, nums);
             return re;
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
       
        public static void help( List<String> r,int level, StringBuilder sb, boolean[] used, List<Integer> nums){. more info on 1point3acres.com
            int size = nums.size();
            if(sb.length()!=0 && sb.charAt(sb.length()-1)!='-'){
                    StringBuilder newsb = new StringBuilder(sb);
                    r.add(newsb.toString());
            }
                if(level == size) return;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            for(int i=0; i<size; i++){
                        if(!used[i]){
                                used[i] = true;
                                sb.append(nums.get(i));
                                help(r,level+1, sb, used, nums);
                                sb.deleteCharAt(sb.length()-1);
                                if(level!=size-1){
                                        sb.append(nums.get(i)+"-");
                                        help(r,level+1, sb, used, nums);
                                        sb.delete(sb.length()-2, sb.length());
                                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                used[i] = false;
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
        }
回复 支持 反对

使用道具 举报

阿童木 发表于 2016-12-2 08:45:25 | 显示全部楼层
jpeng7 发表于 2016-11-30 15:13
对的,紫薯紫薯紫薯

hashmap的那个题楼主现在知道怎么做了吗?
回复 支持 反对

使用道具 举报

sumomoshinqi 发表于 2016-12-2 10:27:17 | 显示全部楼层
按按钮,先组合,再全排,然后插 '-'
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;

  5. void CombButtons(string& buttons, int l, int r, int len,
  6.                  vector<string>& button_select, string path) {
  7.   if (path.size() == len)
  8.     button_select.push_back(path);
  9.   else {
  10.     for (int i = l; i <= r; i++) {
  11.       path += buttons[i];
  12.       CombButtons(buttons, i + 1, r, len, button_select, path);
  13.       path.erase(path.end() - 1);
  14.     }
  15.   }
  16. }. From 1point 3acres bbs

  17. void PermButtons(string& buttons, int l, int r, vector<string>& button_seq) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.   if (l == r)
  19.     button_seq.push_back(buttons);
  20.   else {
  21.     for (int i = l; i <= r; i++) {
  22.       swap(buttons[i], buttons[l]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.       PermButtons(buttons, l + 1, r, button_seq);
  24.       swap(buttons[i], buttons[l]);
  25.     }
  26.   }
  27. }

  28. void PressButtons(string buttons, int i, int n, vector<string>& res,
  29.                   string path) {
  30.   if (i == n)
  31.     res.push_back(path);
  32.   else {
  33.     path += buttons[i];
  34.     PressButtons(buttons, i + 1, n, res, path);
  35.     if (i + 1 < n) PressButtons(buttons, i + 1, n, res, path + '-');
  36.   }
  37. }

  38. int main(int argc, char const* argv[]) {
  39.   string buttons = "123";
  40.   int n = buttons.size();
  41.   vector<string> res;. from: 1point3acres.com/bbs
  42.   vector<string> button_seq;
  43.   vector<string> button_select;
  44.   for (int len = 1; len <= n; len++)
  45.     CombButtons(buttons, 0, n - 1, len, button_select, "");
  46.   for (auto bs : button_select) PermButtons(bs, 0, bs.size() - 1, button_seq);
  47.   for (auto pb : button_seq) PressButtons(pb, 0, pb.size(), res, ""); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  48.   for (auto r : res) cout << r << endl;
  49.   return 0;
  50. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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