谷歌昂赛跪经

第一次发帖。

事出突然，工作室忽然倒闭，所以刷题的时间跟准备的时间都很少。之前被内推过，但是没去onsite，这次直接上回的对话继续onsite。

面的组是Google Cloud的Gsuites组。

第一题:

给类似 ab{1,2}c{4,5}的string input，括号内的都是变量，生成所有的可能output。
eg。 ab1c4, ab2c4, ab1c5, ab2c5

Process input之后BFS秒之。大哥看完直接说对了，然后讨论edge case， test case。

第二题:

给一堆point（x,y), 只能生成横

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

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

但是怎么想都没想出解法，大哥hint了两次才写出来，还写错了，超大的bug，然后就口述出正确解法。

估计凉了。。



补充内容 (2019-2-20 15:54):
妈呀第五题写错了！

a2cd4xk decode成 a2cd4kkkk. 就是Nx‘Char’的格式

第一题

1. public List<String> getStrings(String s) {
   
2.         List<String> ans = new LinkedList<>();
   
3.         LinkedList<String> q = new LinkedList<>();
   
4.         String[] a = s.split("[{}]");
   
5. 
   
6.         q.offer("");
   
7.         int size = q.size();
   
8.         int i = 0;
   
9.         while (i < a.length) {
   
10.             String p = q.poll();
    
11.             size--;
    
12.             String[] next = a[i].split(",");
    
13.             for (String n : next) {
    
14.                 q.offer(p + n);
    
15.             }
    
16.             if (size == 0) {
    
17.                 size = q.size();
    
18.                 i++;
    
19.             }
    
20.         }
    
21.         return q;
    
22.     }

复制代码

阿满 发表于 2019-2-20 12:33
请问第三题 路是直线吗？怎么定义把路堵住了？ 为什么merge interval 不行？

路线是直线。

如果使用merge interval的话，你没法保存merge之后的宽度，例如merge成一个梯形之后，要怎么去检测会否跟下一个block intersect，就需要保存之前所有的block，来做判定。

merge interval的前提是如果 interval[i]和interval[i+1]没有重叠，那么之后的interval必然没有重叠。这个前提在这里并无法实现。

有别人说应该用一个2D矩阵，把所有的block coord设置成1，然后找0的path。但是这个的worst case更惨。

doomdg 发表于 2019-2-20 15:47
因为这个input是alphanumeric的。

decoder唯一能分析的就是数字+x+符号这个特殊的case，只有这个case ...

”a2cd4xk decode成 a2cd4kkkk“ decode之后数字依旧在？
“这题我一看到就知道问题是 “a234xxxx” 这样的input” a234xxxx 的output应该是什么？

Could you give an example for round 3? Thanks.

请问第三题 路是直线吗？怎么定义把路堵住了？ 为什么merge interval 不行？

第五题能具体说一下吗？怎么展开？为什么2c不展开？“a2cd4xk” 展开 不应该是 “accdxxxxk”？

阿满 发表于 2019-2-20 13:01
第五题能具体说一下吗？怎么展开？为什么2c不展开？“a2cd4xk” 展开 不应该是 “accdxxxxk”？

因为这个input是alphanumeric的。

decoder唯一能分析的就是数字+x+符号这个特殊的case，只有这个case会展开。

doomdg 发表于 2019-2-20 15:51
路线是直线。

如果使用merge interval的话，你没法保存merge之后的宽度，例如merge成一个梯形之后，要 ...

是否有一个矩形重叠的长度刚好等于路的宽度？听起来好像是“line sweep algorithms” 的问题？

想请教第五题，为啥 a2c 为啥不展开成 acc 。

a234xxxx 是作为 encoder 输入吗？