一亩三分地论坛

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

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

[找工就业] google电面 10/7

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2015-10-8 05:36:55 | 显示全部楼层 |阅读模式

2015(10-12月)-[]EE硕士+<3个月短暂实习/全职 - 内推| 码农类全职@Googlefresh grad应届毕业生

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

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

x
下午刚面的google电面,狗屎运比较好,还比较简单。面试官迟到了10分钟,然后电话一直听不清,还重新打了一次。。。交流的时候一直在sorry。。
1. 有两个list,里面可能有重复的数, 返回两者相互的差集(在一个里面而不在另一个里面)
比如 A = [1,2,2,2,3,5] B = [1,2,3,6]
返回 A-B = [2, 2, 5]  B-A = [6]

我用两个hashtable分别存A, B的元素在其中出现的个数,比如tableA = {1:1, 2:3, 3:1, 5:1} tableB = {1:1, 2:1, 3:1, 6:1},然后找A-B就scan A然后看见一个在tableB里的元素就tableB里的value减一个,为0了就delete key,不在tableB里的元素就留下, 出来就是A-B。反过来再做一遍就是B-A
. visit 1point3acres.com for more.
然后写test case, 然后被问到了如果A= [[1,2], 3,4],有nested list怎么办,我说这样我的dictionary就没法用了。。因为list不能当key,会有key error的exception,然后问我怎么处理exception,表示没想到啥好的办法,就说如果有这种就把这种再map一次到一个可以当key的value上。。。

说完这个题已经只剩10分钟了,以为悲剧地只能做一道题了, 结果面试官说再来一题吧

2. 给一个wild card pattern,只含有 ‘0’ ‘1’ ‘?’,返回所有可能表示的string
比如
input: 1?01?00
output: [1001000, 1001100, 1101000, 1101100]
然后recursive很快搞定了,问面试官用不用考虑invalid input,他说不用,又说那你还是写一下怎么检查invalid吧,然后就很傻瓜的写了下扫一遍看是不是只有0,1,?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

面完感觉不是太好,2小时后recruiter就通知onsite了
写点面经攒RP

评分

3

查看全部评分

本帖被以下淘专辑推荐:

smile~~~~ 发表于 2015-10-8 08:44:32 | 显示全部楼层
又见紫风铃 发表于 2015-10-7 19:26
感觉应该不算DFS,DFS是朝着一个分支搜到头再换另一个的,我的code是这样的:
.1point3acres缃
我的想法跟lz类似,感觉就是recursive dfs啊。。。anyway,做是做出来了
  1. public class wildCard {
  2.         public static List<String> wildCard(String str) {. from: 1point3acres.com/bbs
  3.                 List<String> res = new ArrayList<String>();
  4.                 helper(res, str);
  5.                 return res;.1point3acres缃
  6.         }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.        
  8.         private static void helper(List<String> res, String str) {
  9.                 if (!str.contains("?")) {
  10.                         res.add(str);
  11.                         return;
  12.                 }
  13.                 String temp1 = str, temp2 = str;
  14.                 temp1 = temp1.replaceFirst("\\?", "0");. from: 1point3acres.com/bbs
  15.                 helper(res, temp1);. From 1point 3acres bbs
  16.                 temp2 = temp2.replaceFirst("\\?", "1");. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.                 helper(res, temp2);               
  18.         }
  19.        
  20.         public static void main(String[] args) {
  21.                 String str= "1100?01?";
  22.                 List<String> res = wildCard(str); // should be[11000010, 11000011, 11001010, 11001011]
  23.                 for (String s: res) {
  24.                         System.out.println(s);
  25.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.         }
  27. }
复制代码
回复 支持 2 反对 0

使用道具 举报

wxr.dal 发表于 2015-10-8 06:52:36 | 显示全部楼层
LZ 第二题没懂题……
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 06:54:34 | 显示全部楼层
wxr.dal 发表于 2015-10-8 06:52 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ 第二题没懂题……

就是?可能是 0 或者 1,然后写出所有可能组合。。。
回复 支持 反对

使用道具 举报

smile~~~~ 发表于 2015-10-8 07:52:46 | 显示全部楼层
lz第二问说的recursive是指的dfs吗?一直对dfs和recursion有点分不清。。。
回复 支持 反对

使用道具 举报

Guasisi 发表于 2015-10-8 08:17:15 | 显示全部楼层
楼主面的哪个组呀,我昨天面的到今天还没消息 ><
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 08:18:23 | 显示全部楼层
Guasisi 发表于 2015-10-8 08:17
楼主面的哪个组呀,我昨天面的到今天还没消息 >

google都是general的吧,木有是哪个组的诶
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 08:26:29 | 显示全部楼层
smile~~~~ 发表于 2015-10-8 07:52
lz第二问说的recursive是指的dfs吗?一直对dfs和recursion有点分不清。。。

感觉应该不算DFS,DFS是朝着一个分支搜到头再换另一个的,我的code是这样的:
  1. class Solution:
  2.     def wildCardPatterns(self, pattern):
  3.         if not pattern: return []
  4.         for ch in pattern:
  5.             if ch not in '01?':
  6.                 return []
  7.         return self.helper(pattern)

  8.     def helper(self, pattern):
  9.         if not pattern: return []. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.         temp = ''
  11.         i = 0.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.         result = []
  13.         while i < len(pattern):
  14.             if pattern[i] != '?':
  15.                 temp += pattern[i]
  16.                 i += 1
  17.             else:
  18.                 break
  19.         # if no question mark
  20.         if i == len(pattern):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.             return [temp]

  22.         remain = self.helper(pattern[i+1:]).鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.         for res in remain:
  24.             result.append(temp + '0' + res)
  25.             result.append(temp + '1' + res)

  26.         return result
复制代码
回复 支持 反对

使用道具 举报

gnijuohz 发表于 2015-10-8 08:45:25 | 显示全部楼层
楼主。。。空格难道都要自己敲么。能配置tab让它成四个空格么
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 08:47:22 | 显示全部楼层
gnijuohz 发表于 2015-10-8 08:45
楼主。。。空格难道都要自己敲么。能配置tab让它成四个空格么

你说google doc里写代码么。。。我试着找了下没找到。。默认tab貌似是六个空格,然后我面试就还是用tab,虽然这样缩进太多了看起来挺丑的。。不过在google doc里写代码觉得怎么写都不好看= =
回复 支持 反对

使用道具 举报

smile~~~~ 发表于 2015-10-8 08:48:13 | 显示全部楼层
gnijuohz 发表于 2015-10-7 19:45
楼主。。。空格难道都要自己敲么。能配置tab让它成四个空格么

对呀 同问!我用google doc敲代码的时候用tab 是6个空格,看着真别扭!
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 08:49:43 | 显示全部楼层
smile~~~~ 发表于 2015-10-8 08:44
我的想法跟lz类似,感觉就是recursive dfs啊。。。anyway,做是做出来了

你这确实是DFS吧,取0 然后recursive这之后所有的,然后取1再recursive这之后所有的, anyway,挺简单的怎么做都行。。。
回复 支持 反对

使用道具 举报

smile~~~~ 发表于 2015-10-8 08:51:03 | 显示全部楼层
又见紫风铃 发表于 2015-10-7 19:49
你这确实是DFS吧,取0 然后recursive这之后所有的,然后取1再recursive这之后所有的, anyway,挺简单的 ...

好的~祝lz onsite顺利!
回复 支持 反对

使用道具 举报

gnijuohz 发表于 2015-10-8 08:56:51 | 显示全部楼层
嗯啊。。。假如我也能有电面的话,也直接用tab了~话说MV给了电面但想留在加拿大,所以重投了Google加拿大。。。祝lz onsite顺利!
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 09:08:43 | 显示全部楼层
smile~~~~ 发表于 2015-10-8 08:51
好的~祝lz onsite顺利!

谢谢!~~~
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-10-8 09:09:40 | 显示全部楼层
gnijuohz 发表于 2015-10-8 08:56
嗯啊。。。假如我也能有电面的话,也直接用tab了~话说MV给了电面但想留在加拿大,所以重投了Google加拿大 ...

谢谢!突然发现今年初找实习的时候我还回复过你的Python刷题号召帖哈哈
回复 支持 反对

使用道具 举报

myllm 发表于 2015-10-8 12:15:40 | 显示全部楼层
紫风铃有fb了吗?
回复 支持 反对

使用道具 举报

hutianyu 发表于 2015-10-8 12:50:04 | 显示全部楼层
新手来支持一下,攒人品,需要发帖求助T。T
回复 支持 反对

使用道具 举报

wxr.dal 发表于 2015-10-8 12:53:22 | 显示全部楼层
  1. import java.util.*;

  2. public class test {

  3.        
  4.     public static List<String> wildCard(String str) {
  5. //            if(str == null) {
  6. //                    return res;
  7. //            }
  8.         List<String> res = new ArrayList<String>();. 1point 3acres 璁哄潧
  9.             if(str == null) {
  10.                     return res;
  11.             }
  12.             . 1point 3acres 璁哄潧
  13.         helper(res, str, 0);
  14.         return res;
  15.     }

  16.     private static void helper(List<String> res, String str, int start) {
  17.         if (!str.contains("?")) {
  18.                 res.add(str);
  19.                 return;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20.         }
  21. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.         for(int i = start; i < str.length(); i++){
  23.                 if(str.charAt(i) == '?'){
  24.                         String str2 = str.substring(0, i) + "0" +str.substring(i + 1);
  25.                         String str3 = str.substring(0, i) + "1" +str.substring(i + 1);
  26.                         helper(res, str2, i + 1);
  27.                         helper(res, str3, i + 1);
  28.                 }
  29.         }
  30.                
  31. }. visit 1point3acres.com for more.
  32.         public static void main(String[] args) {. 1point 3acres 璁哄潧
  33.                
  34.         String str= "1100?01?";.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.         List<String> res = wildCard(str); // should be[11000010, 11000011, 11001010, 11001011]
  36.         for (String s: res) {
  37.                 System.out.println(s);
  38.         }. visit 1point3acres.com for more.
  39.         }

  40. }
复制代码
replaceFirst还是要从0开始遍历吧。这样算不算改进一点点
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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