一亩三分地论坛

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

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

Google 电面

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

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

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

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

x
刚刚面完,分享经验攒人品。
interview 1 :.1point3acres缃
  面试官叫Jeremy Hoffman,美国人。
  介绍有趣的项目,针对项目问了些问题。
  code:
    1. input file,file中是一堆string,要求除去重复行并输出,A:map存每行,重复就skip;. 1point3acres.com/bbs
        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可以选择。
        combination的代码写完了,解释了很久才说懂他,后面处理的函数没有写完,说了思路写了些伪代码跟注释。

应该挂了,去吃点好的,晚上还得上课,大家加油。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| jpeng7 发表于 2016-11-30 07:26:31 | 显示全部楼层
关注一亩三分地微博:
Warald
catinclay 发表于 2016-11-30 06:13. 1point3acres.com/bbs
感觉应该是先求所有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
. more info on 1point3acres.com
补充内容 (2016-11-30 07:31):
我也說反了..
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| 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
. 1point 3acres 璁哄潧假设我们有三个button,我的combination求的结果是{{1,2,3},{1,2},{1,3},{2,3},{1},{2},{3}},但是其实还 ...

假设三个button
所有permutation:
123
132
213. more info on 1point3acres.com
231 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
312
321
. from: 1point3acres.com/bbs
所有'-'的插入法
000. Waral 鍗氬鏈夋洿澶氭枃绔,
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
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):. 1point3acres.com/bbs
如果是这样的话 用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):
. From 1point 3acres bbs
我用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,内容是
. Waral 鍗氬鏈夋洿澶氭枃绔,apple pen. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
pineapple pen. visit 1point3acres.com for more.
ang
penpineapple
apple pen
其中第一行跟最后一行是一样的,所以只需要输出第一行。不用care input file这个条件,可以只当是一个string数组
回复 支持 反对

使用道具 举报

zhangxi1994 发表于 2016-12-1 05:26:09 | 显示全部楼层
jpeng7 发表于 2016-11-30 12:13. 1point 3acres 璁哄潧
有一个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吗?
.1point3acres缃
对的,紫薯紫薯紫薯
回复 支持 反对

使用道具 举报

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

        public static  List<String>  buttonCombine(List<Integer> nums){. 1point 3acres 璁哄潧
             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());. From 1point 3acres bbs
            }
                if(level == size) return;
            for(int i=0; i<size; i++){
                        if(!used[i]){
                                used[i] = true;.1point3acres缃
                                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;. more info on 1point3acres.com
                        }
                }
        }
回复 支持 反对

使用道具 举报

阿童木 发表于 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);. From 1point 3acres bbs
  13.       path.erase(path.end() - 1);
  14.     }
  15.   }
  16. }. 1point 3acres 璁哄潧

  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 {. 1point3acres.com/bbs
  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) {. 1point3acres.com/bbs
  30.   if (i == n)
  31.     res.push_back(path);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.   else {
  33.     path += buttons[i];. more info on 1point3acres.com
  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[]) {
    . From 1point 3acres bbs
  39.   string buttons = "123";
  40.   int n = buttons.size();
  41.   vector<string> res;
  42.   vector<string> button_seq;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  43.   vector<string> button_select;
  44.   for (int len = 1; len <= n; len++). visit 1point3acres.com for more.
  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. }
复制代码
回复 支持 反对

使用道具 举报

onlinecco 发表于 2017-1-14 15:31:54 | 显示全部楼层
sumomoshinqi 发表于 2016-12-2 10:27
按按钮,先组合,再全排,然后插 '-'

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-25 09:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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