一亩三分地论坛

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

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

狗狗12/11实习面经

[复制链接] |试试Instant~ |关注本帖
yingbich 发表于 2015-12-19 07:56:10 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 实习@Google - 内推 - 技术电面 |Pass其他

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

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

x
今天等了不耐烦了,心想跪就跪吧, 就发了一份催一下, 结果半小时后收到hr说过了。现在才敢贴面试题。 因为问题简单了一点怕被鄙视。。。两轮都是google research的人面的所以算法问的可能简单点。

第一轮, 国人大哥, 并且认识我phd导师(心中窃喜, 原来我导师那么有名)。 随便聊聊后,开始问第一题, tree的 in-order traversal 你会嘛? (再喜 ,认识我导师也不用那么放水吧)。 答: recursive 和 iterative 都可以你要哪个? recursive就行, 好瞬间结束。 warm-up结束, 然后问如果两棵树你怎么判断是不是有一样的中序遍历,答:分别扫一遍然后compare一次。 再问,如果一颗很大一颗很小会有神马问题。 答:浪费时间。 追问, 你该怎么办? 然后我突然就傻了, 死活写不好。大哥给hint说, 两颗一起recursive行不行。 行, 写完。 然后大哥让我跑个最简单例子,发现我的算法不对, 心想跪了。。。,已经半个小时过去了,这都答不出来。 大哥鼓励说恩这题不简单你再修改修改你recursive试试看。 死活还是失败。 最后还有10分钟不到了, 我脑抽终于好了, 说我们不写recursive了吧, 写iterative对应一一比较就好了。其实写完还超时了,大哥,让我快速跑下case和说下复杂度就结束了。

第二轮, 反正不是国人和烙印。 上来啥也么有聊开做题。 crossproduct: 就是给 {“ab”,“c"} {"de"}{"eg", "f"} 返回出{“abdeeg",”abdef","cdeeg","cdef"}就是把每个set的元素练到后面所有set的element前面。具体点假设有3个set分别有M,N,K个元素那么最终就返回MNK个元素的一个set. 两两一做加for loop 搞定。 第二题, 问给一排不等关系式比如 a>b, f>c, b>e这样的, 然后给你两个元素 比如 a,e问他们是否存在 不等关系。 建立graph, 然后BFS/DFS即可。 其中问了很多假设比如会不会存在a>b, b>a情况, 给的元素会不会没有出现过神马的。 假设都不回的话, 就是一个有向无回路图。 然后我自作聪明说, 哈因为无回路不需要再来一个set或者变量来记录有没有访问过,因为算法一定会结束。 面试官想了想说, 恩对的, 但算法复杂度会怎么样。 O(V) 或O(E)? 看用BFS还是DFS。 面试官想了想说 I don't think so。心想完了又要跪了。面试官耐心给了一个例子,才反应出来即使无环还是会exponential的复杂度出现的。结束后问我有问题吗?我就随口问了一句你们工业届做deep learning东西啊, 目前数学理论保证那么差,你们care嘛?然后他突然说话停不下来了,超了10多分钟说。其实我英文不好没有听懂太多,反正大意就是 good question, 我们非常需要数学。


大概就这样吧,反正面试我犯了很多错误,也算是运气比较好才过了。 可能当中的交流也是非常重要的。犯错不怕, 能体现出你能从错误中快速更正和学习还是能弥补回来的。
.鐣欏璁哄潧-涓浜-涓夊垎鍦

求team match!!!


鏉ユ簮涓浜.涓夊垎鍦拌鍧.

.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

pleaaa 发表于 2015-12-21 13:51:29 | 显示全部楼层
谢谢,很有用的信息
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-12 12:43:02 | 显示全部楼层
写了下第二轮第二题
  1. public class CrossproductString {

  2.         public static void main(String[] args) {
  3.                 List<List<String>> lists = new ArrayList<List<String>>();. 1point 3acres 璁哄潧
  4.                 lists.add(Arrays.asList("ab", "c"));
  5.                 lists.add(Arrays.asList("de"));
  6.                 lists.add(Arrays.asList("eg", "f"));. from: 1point3acres.com/bbs
  7.                 List<String> res = getCrossproductStrings(lists);
  8.                 for (String s : res) {
  9.                         System.out.println(s);
  10.                 }
  11.         }
  12.         public static List<String> getCrossproductStrings(List<List<String>> lists) {
  13.                 if (lists == null || lists.size() == 0) {
  14.                         return new ArrayList<String>();
  15.                 }
  16.                 List<String> list = lists.get(0);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17.                 for (int i = 1; i < lists.size(); i++) {
  18.                         list = getProduct(list, lists.get(i));
  19.                 }
  20.                 return list;
  21.         }

  22.         private static List<String> getProduct(List<String> list1, List<String> list2) {
  23.                 List<String> res = new ArrayList<String>();
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.                 for (int i = 0; i < list1.size(); i++) {
  25.                         for (int j = 0; j < list2.size(); j++) {
  26.                                 res.add(list1.get(i) + list2.get(j));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.                         }
  28.                 }. 1point 3acres 璁哄潧
  29.                 return res;
  30.         }
  31. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-12 23:03:42 | 显示全部楼层
为什么图的那题不是O(V )呢?如有加了visited,应该都只会被访问一次啊
  1. public class Inequality {.鏈枃鍘熷垱鑷1point3acres璁哄潧

  2.         static class Pair {
  3.                 char large;. from: 1point3acres.com/bbs
  4.                 char small;
  5.                 public Pair(char a , char b) {
  6.                         large = a;
  7.                         small = b;
  8.                 }
  9.         }

  10.         public static int hasInequalityRelationship(Pair[] pairs, char a, char b) throws Exception {
  11.                 if (pairs == null || pairs.length == 0) {. 1point 3acres 璁哄潧
  12.                         return 0;
  13.                 }
  14.                 if (a == b) {
  15.                         return 0;
  16.                 }. 1point 3acres 璁哄潧
  17.                 HashMap<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
  18.                 for (Pair pair : pairs) {.1point3acres缃
  19.                         if (!map.containsKey(pair.large)) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                                 map.put(pair.large, new HashSet<Character>());
  21.                         }
  22.                         map.get(pair.large).add(pair.small);
  23.                 }
  24.                 boolean val1 = dfs(map, a, b, new HashSet<Character>());
  25.                 boolean val2 = dfs(map, b, a, new HashSet<Character>());
  26.                 if (val1) {
  27.                         return 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.                 } else if (val2) {
  29.                         return -1;
  30.                 } else {
  31.                         return 0;
  32.                 }
  33.         }
  34. . 1point 3acres 璁哄潧
  35.         private static boolean dfs(HashMap<Character, Set<Character>> map, char a, char b, HashSet<Character> visited) throws Exception {
  36.                 if (a == b) {
  37.                         return true;
  38.                 }
  39.                 if (visited.contains(a)) {
  40.                         throw new Exception("Has Loop");
  41.                 }
  42.                 if (!map.containsKey(a)) {
  43.                         return false;
  44.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  45.                 visited.add(a);
  46.                 for (char c : map.get(a)) {
  47.                         if (dfs(map, c, b, visited)) {
  48.                                 return true;
  49.                         }
  50.                 }.1point3acres缃
  51.                 return false;
  52.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  53.        
  54.         public static void main(String[] args) throws Exception {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  55.                 Pair[] pairs = {new Pair('a', 'b'), new Pair('f', 'c'), new Pair('b', 'e')};
  56.                 System.out.println(hasInequalityRelationship(pairs, 'a', 'e'));
  57.                 System.out.println(hasInequalityRelationship(pairs, 'e', 'a'));
  58.                 System.out.println(hasInequalityRelationship(pairs, 'f', 'a'));
  59.         }
  60. }
复制代码


回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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