推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2349|回复: 19
收起左侧

Google 电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚刚面完,分享经验攒人品。. From 1point 3acres bbs
interview 1 :. more info on 1point3acres.com
  面试官叫Jeremy Hoffman,美国人。
  介绍有趣的项目,针对项目问了些问题。
  code:
    1. input file,file中是一堆string,要求除去重复行并输出,A:map存每行,重复就skip;
        follow up:file非常大怎么办, A: trie树存. 鍥磋鎴戜滑@1point 3 acres
    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算重复,.1point3acres缃
        输出所有可能的按法。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        我感觉跟subset类似,所以用了recursion求所有可能的combination,然后对每个combination求剩下的button的combination,每次求combination都存进一种可能性,如此往复,直到没有button可以选择。
        combination的代码写完了,解释了很久才说懂他,后面处理的函数没有写完,说了思路写了些伪代码跟注释。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
应该挂了,去吃点好的,晚上还得上课,大家加油。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

xxxxx56789 发表于 2016-12-2 08:33:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
        第二题这样写不知道对不对. more info on 1point3acres.com

        public static  List<String>  buttonCombine(List<Integer> nums){
             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){
            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;. Waral 鍗氬鏈夋洿澶氭枃绔,
            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){. from: 1point3acres.com/bbs
                                        sb.append(nums.get(i)+"-");
                                        help(r,level+1, sb, used, nums);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        sb.delete(sb.length()-2, sb.length());
                                }.1point3acres缃
                                used[i] = false;
                        }
                }
        }
回复 支持 1 反对 0

使用道具 举报

catinclay 发表于 2016-11-30 06:13:18 | 显示全部楼层
关注一亩三分地微博:
Warald
感觉应该是先求所有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的问题呀

补充内容 (2016-11-30 07:30):
顺序无关的combination 就是所有combination下去作permutation

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

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:31:34 | 显示全部楼层
catinclay 发表于 2016-11-30 07:28
为什么面试官不建议这样作呀...感觉这样就能不用处理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. visit 1point3acres.com for more.
00-0
0-0-0

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

补充内容 (2016-11-30 07:36):
也就是.鏈枃鍘熷垱鑷1point3acres璁哄潧
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璁哄潧
321, 3-21, 32-1, 3-2-1
回复 支持 反对

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:36:10 | 显示全部楼层
catinclay 发表于 2016-11-30 07:33
假设三个button
所有permutation:
123

嗯不仅要permutation,还需要combination,因为可以不用到所有button,嗯,难道先求到所有的combination然后再分别求permutation?好像也可以。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-30 07:37:30 | 显示全部楼层
jpeng7 发表于 2016-11-30 07:36
嗯不仅要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):

但是这样比我那个方法直观简单多了……我那个还得在循环里面调用递归……哎。anyway,谢谢指教~
回复 支持 反对

使用道具 举报

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

补充内容 (2016-11-30 07:38):

我用backtracking求的combination,你的意思是?
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-30 07:51:41 | 显示全部楼层
jpeng7 发表于 2016-11-30 07:40. From 1point 3acres bbs
我用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那个不太明白是什么意思诶,,楼主能再详细说一下问题么?为什么是一行一行的存啊。。
. more info on 1point3acres.com
有一个input file,内容是
apple pen
pineapple pen
ang
penpineapple
apple pen
其中第一行跟最后一行是一样的,所以只需要输出第一行。不用care input file这个条件,可以只当是一个string数组
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| jpeng7 发表于 2016-12-1 07:13:54 | 显示全部楼层
zhangxi1994 发表于 2016-12-1 05:26
谢谢楼主!想再问一下,一个map的size比较小那道题,是问怎么实现hashmap吗?

对的,紫薯紫薯紫薯
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

sumomoshinqi 发表于 2016-12-2 10:27:17 | 显示全部楼层
按按钮,先组合,再全排,然后插 '-'
  1. #include <iostream>.1point3acres缃
  2. #include <string>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3. #include <vector>
  4. using namespace std; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5. . 1point3acres.com/bbs
  6. void CombButtons(string& buttons, int l, int r, int len,
  7.                  vector<string>& button_select, string path) {
  8.   if (path.size() == len)
  9.     button_select.push_back(path);
  10.   else {
  11.     for (int i = l; i <= r; i++) {
    -google 1point3acres
  12.       path += buttons[i];. 1point3acres.com/bbs
  13.       CombButtons(buttons, i + 1, r, len, button_select, path);
  14.       path.erase(path.end() - 1);
  15.     }. From 1point 3acres bbs
  16.   }
  17. }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18. . 鍥磋鎴戜滑@1point 3 acres
  19. void PermButtons(string& buttons, int l, int r, vector<string>& button_seq) {.1point3acres缃
  20.   if (l == r)
  21.     button_seq.push_back(buttons);
  22.   else {. 鍥磋鎴戜滑@1point 3 acres
  23.     for (int i = l; i <= r; i++) {
  24.       swap(buttons[i], buttons[l]);
  25.       PermButtons(buttons, l + 1, r, button_seq);
  26.       swap(buttons[i], buttons[l]);
  27.     }
  28.   }
  29. }

  30. void PressButtons(string buttons, int i, int n, vector<string>& res,
  31.                   string path) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  32.   if (i == n)
  33.     res.push_back(path);
  34.   else {
  35.     path += buttons[i];
  36.     PressButtons(buttons, i + 1, n, res, path);
  37.     if (i + 1 < n) PressButtons(buttons, i + 1, n, res, path + '-');
  38.   }
  39. }.1point3acres缃
  40. . From 1point 3acres bbs
  41. int main(int argc, char const* argv[]) {
  42.   string buttons = "123";
  43.   int n = buttons.size();
  44.   vector<string> res;
  45.   vector<string> button_seq;
  46.   vector<string> button_select;. visit 1point3acres.com for more.
  47.   for (int len = 1; len <= n; len++). From 1point 3acres bbs
  48.     CombButtons(buttons, 0, n - 1, len, button_select, "");
  49.   for (auto bs : button_select) PermButtons(bs, 0, bs.size() - 1, button_seq);
  50.   for (auto pb : button_seq) PressButtons(pb, 0, pb.size(), res, "");
  51.   for (auto r : res) cout << r << endl;
  52.   return 0;
  53. }
复制代码
回复 支持 反对

使用道具 举报

onlinecco 发表于 2017-1-14 15:31:54 | 显示全部楼层
sumomoshinqi 发表于 2016-12-2 10:27. 鍥磋鎴戜滑@1point 3 acres
按按钮,先组合,再全排,然后插 '-'

PermButtons写错了吧。。这样会少很多permutation的

补充内容 (2017-1-14 15:34):
看错了 看成i+1了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-28 13:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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