一亩三分地论坛

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

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

Google Intern Interview

[复制链接] |试试Instant~ |关注本帖
fireisborn 发表于 2015-11-24 05:15:40 | 显示全部楼层 |阅读模式

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

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

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

x
Google interview

个人觉得题目还蛮简单的...但还是没把握住,简直太悲剧了...至少比很多地底的分享都简单许多,唉...接到 HR 电话时简直想一头碰壁...

第一个面我的是国人小哥,感觉亲近了一些,但是一开始我们的 google doc link 就对不起来让我有点囧,搞了一阵子之后小哥说不然你把 link 分享给我吧,然后才正式开始面试,题目如下:
有一串 edge pair list ,ex (1, 2), (2, 3) 代表 1->2, 2->3 ,然后需要我去算出有多少 bi-directional graph in the list … 嗯,我真的没见过这题,直接尝试解解看吧,一开始跟他说我可能会尝试用 topological sort 来解,但是小哥在此打住我,说尝试简单一点的解法,然后我提议用 python dict 来储存这些关係,然后再根据 key & value 这些关係来找出这个数目,然后我就绕进去了,现在想来简直就是悲剧的开始,这麽简单的题目被我搞得这麽复杂...总之写完第一个解法之后小哥提醒我有问题,我跑完自己的 test case 之后发现到我会重复算两次,然后最后改出一个 O(N^3) 的解法,后来就在跟小哥讨论 brute force 的解法跟一些实际状况之后,因为前面 technical issue 的时间就结束了,问建议的时候小哥有叫我 take care every detail of the questions first & familiar with one programmnig language,后面有些话听不是很清楚,因为接下来还有一面就先掰了.

.1point3acres缃虽然我觉得我没做出最佳解,但整体的交流还是不错,不过最后还是跪了,后来发现根本就不用想得这麽复杂,只要确认有没有前后互换的 pair 就好了,只能说一开始自己把题目想得太难了,然后也没有一次写出 bug free 的 code,以及有些条件没有先确认好,只能说自己实力真的还是远远不够啊(叹
. from: 1point3acres.com/bbs
第二个面我的是一个三姐,感觉英文不是很好,话非常少,只好我一直讲话,为了保持跟他的互动我常常问他说 does this make sense to you? 之类的问题,还好他给的题目蛮简单的,就是两个字串比对,然后找出多出来的那一个字元,先写了一个 sorted 版本的,然后三姐追问 unsorted 怎麽解,我讲了时间换空间,空间换时间的两套方法,看他希望我做哪一个,然后他要求再做一个空间换时间的解法,写完之后讨论一下,发现有点 bug,很快地改完,然后又聊了很多特殊的 test case ,分别检讨了之前提过的几个解法可能会有哪些问题,最后发现最后一版的解法是最好的,皆大欢喜之下结束

几点检讨:
1. 遇到新题不要紧张很重要,一定要先确认好许多的 input 条件,以及事先提出时间复杂度,往越简单的地方想越好,不要把自己绕进去了
2. 觉得遇到印度人也不需要特别紧张,有时他们只是不太想讲话而已,保持跟面试官互动还是很重要的,不要一直埋头写题目

唉,反正去不成了...发出来给大家见笑,经验分享,求 RP & 大米

评分

3

查看全部评分

JEC726 发表于 2015-12-5 02:26:49 | 显示全部楼层
话说第一题题目是说找双向图么?怎么感觉楼主的描述是找双向边。。。
回复 支持 1 反对 0

使用道具 举报

cherylshang 发表于 2015-11-24 05:29:14 | 显示全部楼层
请问LZ你是什么时候面的?刚接到的结果嘛
回复 支持 反对

使用道具 举报

红色鲱鱼 发表于 2015-11-24 05:46:20 | 显示全部楼层
想问一下第一题的输入是以哪一种数据结构输入的。
回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2015-11-24 07:04:46 | 显示全部楼层
cherylshang 发表于 2015-11-24 05:29
请问LZ你是什么时候面的?刚接到的结果嘛

上禮拜一面的,剛剛接到結果
回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2015-11-24 07:05:32 | 显示全部楼层
红色鲱鱼 发表于 2015-11-24 05:46
想问一下第一题的输入是以哪一种数据结构输入的。

我是用 python 面的,面試官給的是 tuple list
回复 支持 反对

使用道具 举报

xixiaoxi 发表于 2015-11-24 09:21:29 | 显示全部楼层
第一题我觉得idea和2 sum差不多,用一个set去存需要找的部分,如果input是(1,2),就存(2,1)。对每个input去查set.contains(input),如果true,count+1

第二题就是先sort再找(time and space:O(nlgn)&O(1))或者用hashmap(O(n)&O(n))  . visit 1point3acres.com for more.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不知道对不对
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-4 12:56:17 | 显示全部楼层
xixiaoxi 发表于 2015-11-24 09:21
第一题我觉得idea和2 sum差不多,用一个set去存需要找的部分,如果input是(1,2),就存(2,1)。对每个input去 ...
. 1point3acres.com/bbs
请问这个bi-directional graph in the list就是指两个node相互指向对方,还是找环呢?
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-12-4 13:39:49 | 显示全部楼层
xixiaoxi 发表于 2015-11-24 09:21
第一题我觉得idea和2 sum差不多,用一个set去存需要找的部分,如果input是(1,2),就存(2,1)。对每个input去 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一次听说双向图,其实就是2 sum。谷歌的题目真的是不难,但是却又让你没见过。
回复 支持 反对

使用道具 举报

xiaohl0913 发表于 2015-12-4 15:40:37 | 显示全部楼层
第一题他是说有几个无向的conencted component吗?比如 1->2, 2->1, 2->3, 3->2算一个吗? 然后1->2, 2->1, 3->4, 4->3算两个?
回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2015-12-4 21:27:08 | 显示全部楼层
xiaohl0913 发表于 2015-12-4 15:40
第一题他是说有几个无向的conencted component吗?比如 1->2, 2->1, 2->3, 3->2算一个吗? 然后1->2, 2->1, ...
. more info on 1point3acres.com
你兩個例子都是算兩個喔~
回复 支持 反对

使用道具 举报

 楼主| fireisborn 发表于 2015-12-4 21:28:21 | 显示全部楼层
我把我自己寫的 python code 貼上來好了,這應該是正確的,大家可以跑跑看. 鍥磋鎴戜滑@1point 3 acres

  1. class Solution(object):
  2.     '''
  3.     TC: O(N)
  4.     SC: O(N)
  5.     '''
  6.     def count_bi_direct(self, edges):
  7.         edge_dict = {}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.         count = 0
  9.         for edge in edges:
  10.             if edge_dict.get((edge[1], edge[0])) is not None:.1point3acres缃
  11.                 count += 1. 1point3acres.com/bbs
  12.             else:
  13.                 edge_dict[edge] = 1
  14.         return count
    . from: 1point3acres.com/bbs

  15.     '''
  16.     TC: O(N ^ 2)
  17.     SC: O(1)
  18.     '''
  19.     def count_bi_direct_brute_force(self, edges):
  20.         count = 0
  21.         edges = list(set(edges)) # remove the repeated edges
  22.         for i in xrange(len(edges)):. From 1point 3acres bbs
  23.             for j in xrange(i, len(edges)):
  24.                 if edges[i][1] == edges[j][0] and edges[j][1] == edges[i][0]:-google 1point3acres
  25.                     count += 1
  26.         return count
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 02:06:14 | 显示全部楼层
fireisborn 发表于 2015-12-4 21:28
我把我自己寫的 python code 貼上來好了,這應該是正確的,大家可以跑跑看

楼主这时间复杂度是O(n^2)吧,用hashmap, or hashset,可以减少到O(n)吧?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 02:16:07 | 显示全部楼层
写了下code,欢迎指教
  1. public class BidirectionalGraph {. more info on 1point3acres.com
  2.        
  3.         public static void main(String[] args) {
  4.                 int[][] edges = {{1, 2}, {2, 1}, {1, 3}, {3, 1}};
  5.                 int res = countBidirectionalGraph(edges);
  6.                 System.out.println(res);
  7.         }
  8.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.         public static int countBidirectionalGraph(int[][] edges) {
  10.                 if (edges == null || edges.length == 0 || edges[0].length == 0) {
  11.                         return 0;
  12.                 }
  13.                 HashSet<String> set = new HashSet<String>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.                 int count = 0;. 1point3acres.com/bbs
  15.                 for (int[] edge : edges) {
  16.                         if (set.contains(edge[1] + "" + edge[0])) {
  17.                                 count++;
  18.                         }
  19.                         set.add(edge[0] + "" + edge[1]);
  20.                 }
  21.                 . 1point 3acres 璁哄潧
  22.                 return count;.1point3acres缃
  23.         }
  24. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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