Google 电面

刚刚面完，分享经验攒人品。
interview 1 ：
  面试官叫Jeremy Hoffman，美国人。
  介绍有趣的项目，针对项目问了些问题。
  code：
    1. input file，file中是一堆string，要求除去重复行并输出，A：map存每行，重复就

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ton可以选择。
        combination的代码写完了，解释了很久才说懂他，后面处理的函数没有写完，说了思路写了些伪代码跟注释。

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

        第二题这样写不知道对不对

        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;
            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;
                        }
                }
        }

按按钮，先组合，再全排，然后插 '-'

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
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++) {
    
12.       path += buttons[i];
    
13.       CombButtons(buttons, i + 1, r, len, button_select, path);
    
14.       path.erase(path.end() - 1);
    
15.     }
    
16.   }
    
17. }
    
18. 
    
19. void PermButtons(string& buttons, int l, int r, vector<string>& button_seq) {
    
20.   if (l == r)
    
21.     button_seq.push_back(buttons);
    
22.   else {
    
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. 
    
31. void PressButtons(string buttons, int i, int n, vector<string>& res,
    
32.                   string path) {
    
33.   if (i == n)
    
34.     res.push_back(path);
    
35.   else {
    
36.     path += buttons[i];
    
37.     PressButtons(buttons, i + 1, n, res, path);
    
38.     if (i + 1 < n) PressButtons(buttons, i + 1, n, res, path + '-');
    
39.   }
    
40. }
    
41. 
    
42. int main(int argc, char const* argv[]) {
    
43.   string buttons = "123";
    
44.   int n = buttons.size();
    
45.   vector<string> res;
    
46.   vector<string> button_seq;
    
47.   vector<string> button_select;
    
48.   for (int len = 1; len <= n; len++)
    
49.     CombButtons(buttons, 0, n - 1, len, button_select, "");
    
50.   for (auto bs : button_select) PermButtons(bs, 0, bs.size() - 1, button_seq);
    
51.   for (auto pb : button_seq) PressButtons(pb, 0, pb.size(), res, "");
    
52.   for (auto r : res) cout << r << endl;
    
53.   return 0;
    
54. }
    

复制代码

感觉应该是先求所有permutation, 然后再输出所有往中间插入'-'的方法

catinclay 发表于 2016-11-30 06:13
感觉应该是先求所有permutation, 然后再输出所有往中间插入'-'的方法

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

catinclay 发表于 2016-11-30 06:13
感觉应该是先求所有permutation, 然后再输出所有往中间插入'-'的方法

说反了，我做的是顺序无关的，怎么求顺序相关呀？就是 既能得到321，又能有123

jpeng7 发表于 2016-11-30 07:26
我一开始也是这么做的，但是被面试官建议不这样做，因为我当时写的求combination是顺序有关的，不太好处 ...

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

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

补充内容 (2016-11-30 07:31):
我也說反了..

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}啊等等的，这个我不会怎么求。

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
321, 3-21, 32-1, 3-2-1

catinclay 发表于 2016-11-30 07:33
假设三个button
所有permutation:
123

嗯不仅要permutation，还需要combination，因为可以不用到所有button，嗯，难道先求到所有的combination然后再分别求permutation？好像也可以。

jpeng7 发表于 2016-11-30 07:36
嗯不仅要permutation，还需要combination，因为可以不用到所有button，嗯，难道先求到所有的combination ...

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

补充内容 (2016-11-30 07:38):
如果是这样的话 用back-tracking好像会比较快

catinclay 发表于 2016-11-30 07:37
恩 先combination再permutation, 挺麻烦的 以为全部的button都要用到

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

但是这样比我那个方法直观简单多了……我那个还得在循环里面调用递归……哎。anyway，谢谢指教～