一亩三分地论坛

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

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

google onsite面经

[复制链接] |试试Instant~ |关注本帖
宝贝忆彼岸 发表于 2016-1-8 10:10:35 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
接了offer有一段时间了,然后天天吃,喝,玩,乐,颓废了一阵,今天把onsite面经写出来,给google面经题库里再加几道目前正在等选组,希望后面一切顺利. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
当天我的面试官好像是迟到了,和我一个building里等待的同学一个一个被叫走,就剩我一个了。后来HR过来先领我逛了一下campus,着重去了一个restroom->我是说休息室不是卫生间,让我玩了一个好像是3D的google map,重点就是强调google很cool,对员工很好,我就一路附和下去,内心OS是:能不能别讲了,我好紧张,能不能先让我去面试。。。。


下面是干货
**************************************************分割线***********************************************************
.1point3acres缃
第一轮:
美国大叔,一个股票的stream,每个时间点(timeline)都有股票的更新,实现两个function:
1.给一个timeline,删掉当前点的股票
2.给你一个timeline让你求出历史股票数据的最大值和最小值
我使用heap和hashmap做的
.1point3acres缃
第二轮:
国人姐姐
1.给一个linkedList,返回倒数第n个node,这个题我已开始竟然说先把链表反转,真想一巴掌拍死自己。。。。有时候真的紧张会大脑短路
2.给一个complete tree,返回最后一个level的叶子(用二分的思路)
剩下的时间讨论了下类似于unique tree的题,没写code

午饭是内推我的前辈带我去吃的,因为比较紧张,所以并没有留意是不是好吃,好像还行吧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第三轮:
俄罗斯姐姐带了一个shadow白人小哥,这个小哥全程红脸,不知道是紧张还是本身就自带腮红
一个matrix,里面的每一格是白色或者黑色,已知黑色的block都是conntected的,让求matrix里的黑色格子的上下左右四个边界。我当时说DFS遍历,过程中记录四个边界,她说有没有better solution,然后提示我说如果是一个一维的你会怎么做,然后我就想到了二分。。。
这一轮有一个比较trick的follow up,我硬是想了快20分钟,就是在找左右边界的时候我用了两个function,面试官问我能否把这两个合成一个,然后中间提示我说这个board里面只有黑白两个颜色,让我往颜色的方面考虑,可惜直到最后我也没想出做法。。。。最后她说ok, it looks...nice....good luck...然后我觉得我一定是没戏了
回家的路上想到了,其实很简单,你们先自己想想

第四轮 都是leetcode
国人小哥
1.string to integer
2.excel sheet column title
第二题我也是刷了很多遍,但是现场写居然写了好久才写出来,后面10分钟小哥让我证明为啥我的解法是正确的,可惜最后还是没能领会他的意思,但是从结果来看,这个小哥应该是帮了我一把的,很感谢
*********************************************************************************************************************
下面依然是水货君
1.google onsite整体感觉很好,每个面试官都很亲切,整个过程很像是你和面试官一起讨论把题目解出来的
2.拿到题目,可以先说brute force的解法,在进行优化,如果卡住了可以主动问面试官要一下hint
3.我面试的白板和我想象中的不一样,有点小,并且是高度大于宽度的,所以我总是写了擦,擦了写
4.比起bug free,面试官更看重你的思路,还有你对数据结构和算法是不是能够灵活应用

5.中国同胞出题都更加偏向leetcode,而且都很给力,你懂得



6.找工作的这段期间真的很难熬,而且愿意给我面试的公司又很少(google算是我第二个onsite),我记得拿到offer的前几天真的觉得压力好大,跟朋友打电话哭来着。。。我想每个人大概都一样吧,找到工作前都有一段苦逼成狗的岁月,所有事情都是自己一个人撑,所有情绪都是自己一个人知道,但是,请坚持,再坚持一下。。。

最后,求选组顺利啊


补充内容 (2016-1-8 12:35):. 鍥磋鎴戜滑@1point 3 acres
complete tree那道题是返回最后一个level的最后一个叶子

评分

7

查看全部评分

bobzhang2004 发表于 2016-1-14 04:35:11 | 显示全部楼层
多谢楼主,写了写complete tree last leaf的code
  1. public class CompleteTreeLastLeaf {
  2.         static class TreeNode {
  3.                 TreeNode left, right;
  4.                 int val;. more info on 1point3acres.com

  5.                 public TreeNode(int v) {
  6.                         val = v;.1point3acres缃
  7.                 }
  8.         }
  9. . 1point 3acres 璁哄潧
  10.         public static TreeNode findCompleteTreeLastLeaf(TreeNode root) {
  11.                 if (root == null) {
  12.                         return null;
  13.                 }
  14.                 if (root.left == null && root.right == null) {
  15.                         return root;
  16.                 }
  17.                 if (root.left != null && root.right == null) {
  18.                         return root.left;-google 1point3acres
  19.                 }. more info on 1point3acres.com
  20.                 int left = countLeft(root.left);. 1point 3acres 璁哄潧
  21.                 int right = countLeft(root.right);
  22.                 if (left == right) {
  23.                         return findCompleteTreeLastLeaf(root.right);
  24.                 } else {
    -google 1point3acres
  25.                         return findCompleteTreeLastLeaf(root.left);
  26.                 }
  27.         }

  28.         private static int countLeft(TreeNode left) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.                 if (left == null) {. more info on 1point3acres.com
  30.                         return 0;
  31.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  32.                 return countLeft(left.left) + 1;
    . visit 1point3acres.com for more.
  33.         }

  34. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.         public static void main(String[] args) {
  36.                 TreeNode root = new TreeNode(1);
  37.                 System.out.println(findCompleteTreeLastLeaf(root).val);. Waral 鍗氬鏈夋洿澶氭枃绔,
  38.                 root.left = new TreeNode(2);
  39.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  40.                 root.right = new TreeNode(3);. 1point3acres.com/bbs
  41.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  42.                 root.left.left = new TreeNode(4);
  43.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  44.         }
  45. }
复制代码
回复 支持 0 反对 2

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:35:06 | 显示全部楼层
zjuzqh 发表于 2016-1-8 11:24
恭喜楼主拿到了Offer.然后有几点不清楚要问下楼主。1.第一题题目意思看不大懂,是给一个序列(时间点,股票 ...

1.第一题可以这么想,就是stream序列里有一个object,object包含时间点和股票的价格,让求当前历史数据里股票的最大值和最小值,然后给一个时间点,删除时间点上的股票,然后最大值和最小值可能就要更新了,因为删除的时间点上的可能就是之前的最大值或最小值。我的做法就是把历史股票全部都放在一个max heap里,然后删除的时候,把删除的股票放在map里,然后看max heap的root是否在被删除的map里,如果在就把这个点从heap里删除,这样找最大值,最小值同理。
2.complete tree这题怪我没有说清楚,是返回最后一个level的最后一个叶子,就是先找左右两个树的最左边一个分支的深度,如果两个深度一样,就说明这个要找的叶子在右树,否则在左树这样。。
3.是的,二分就是比如说输入给你一个(3,4)说明位置(3,4)这个格子的点是黑色的,然后我们按列做二分,看从0到4得中间那一列也就是第2列,遍历第二列看第二列有没有黑色的点,如果没有,说明第二列左边也没有黑色的点,因为前面说过,黑色的格子是全部connected的,也就是说,左边的边界在第二列的右边这样,按照这个规律二分
语言表达能力有限,不知道说清楚了没
回复 支持 1 反对 0

使用道具 举报

lotustree86 发表于 2016-1-11 17:58:46 | 显示全部楼层
按照楼主的思路用JAVA写了一下第一题 stock price。Delete : O(1). Add: O(logn). GetMax/Min: O(1) if top item is not deleted. O(nlogn) worst case if all prices are deleted.

看到楼上讨论的一个问题是,delete 时直接从heap里删除,而不是存在hashmap里。这种方式的问题是delete item in heap 操作只有在你确切知道这个item的位置的时候,i.e. index in the backed up array,才是logn,其它情况是O(N)。在JAVA的PriorityQueue, remove是O(N)。除非你自己实现楼上提到的indexed heap。

另一种方案使用BST,可以实现Delete: o(logn), add: O(logn), getMax/Min: O(1),但是其实这两种方案是没有本质区别的,BST内存上反而会多占,而且Performance上,BST由于data locality其实不如heap。
这两种方案我都实现了。. Waral 鍗氬鏈夋洿澶氭枃绔,

  1. public class StockStreaming {
  2.     // heap + hashmap. more info on 1point3acres.com
  3.     // hashmap keeps all delted nodes
  4.     // when get max, keep polling hte heap until the max item is not deleted.
  5.     PriorityQueue<StockPrice> minHeap = new PriorityQueue<>();
  6.     PriorityQueue<StockPrice> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b.price, a.price)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.     Set<Integer> deletedSet = new HashSet<>();
  8. . From 1point 3acres bbs
  9.     // O(1)
  10.     public void deleteStockPrice(int time) {. from: 1point3acres.com/bbs
  11.         deletedSet.add(time);
  12.     }

  13.     // O(logn)
  14.     public void addStockPrice(StockPrice sp) {
  15.         minHeap.add(sp);
  16.         maxHeap.add(sp);
  17.     }

  18.     // O(1) for not deleted max, worst case O(nlogn). i.e. all items are deleted if the max is deleted
  19.     public int getMax() {
    . 1point3acres.com/bbs
  20.         while(!maxHeap.isEmpty() && deletedSet.contains(maxHeap.peek().time))
  21.             maxHeap.poll();. visit 1point3acres.com for more.
  22.         return maxHeap.isEmpty() ? -1 : maxHeap.peek().price;
  23.     }

  24.     public int getMin() {
  25.         while(!minHeap.isEmpty() && deletedSet.contains(minHeap.peek().time))
  26.             minHeap.poll();
  27.         return minHeap.isEmpty() ? -1 :  minHeap.peek().price;
  28.     }

  29. . From 1point 3acres bbs
  30.     // Method two, using a single BST tree to keep track of max/min
  31.     SortedSet<StockPrice> sortedPrice = new TreeSet<>();
  32.     Map<Integer, StockPrice> prices = new HashMap<Integer, StockPrice>();
  33.     int maxPrice = -1;
  34.     int minPrice = Integer.MAX_VALUE;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  35.     // O(logn)
  36.     public void deleteStockPrice2(int time) {
  37.         StockPrice sp = prices.get(time);
  38.         sortedPrice.remove(prices.get(time));
  39.         if(sortedPrice.isEmpty())
  40.         {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.             maxPrice = -1;
  42.             minPrice = Integer.MAX_VALUE;
  43.         }

  44.         if(sp.price == maxPrice)
  45.             maxPrice = sortedPrice.last().price;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.         if(sp.price == minPrice)
  47.             minPrice = sortedPrice.first().price;
  48.     }

  49.     // O(logn). from: 1point3acres.com/bbs
  50.     public void addStockPrice2(StockPrice sp){. From 1point 3acres bbs
  51.         prices.put(sp.time, sp);
  52.         sortedPrice.add(sp);
  53.         if(maxPrice < sp.price)
  54.             maxPrice = sp.price;
  55.         if(minPrice > sp.price)
  56.             minPrice = sp.price;
  57.     }

  58.     // O(1)
  59.     public int getMax2() {
  60.         return maxPrice;
  61.     }. visit 1point3acres.com for more.
  62. . from: 1point3acres.com/bbs
  63.     // O(1)
  64.     public int getMin2() {
  65.         return minPrice;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  66.     }
    . 鍥磋鎴戜滑@1point 3 acres

  67.     public static class StockPrice implements Comparable<StockPrice>{
  68.         final int time;
  69.         final int price;. visit 1point3acres.com for more.
  70.         public StockPrice(int time, int price) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  71.             this.time = time;. Waral 鍗氬鏈夋洿澶氭枃绔,
  72.             this.price = price;
  73.         }. from: 1point3acres.com/bbs
  74. -google 1point3acres
  75.         @Override
  76.         public int hashCode() {
  77.             return this.time * 51 + price;
  78.         }
  79. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  80.         @Override
  81.         public boolean equals(Object other) {
  82.             if(other == null) return false;-google 1point3acres
  83.             if(this.getClass() != other.getClass()) return false;
  84.             StockPrice b = (StockPrice) other;
  85.             return this.price == b.price && this.time == b.time;
  86.         }. 1point 3acres 璁哄潧

  87.         @Override. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  88.         public int compareTo(StockPrice other) {
  89.             int ret = Integer.compare(this.price, other.price);

  90.             return ret == 0 ? Integer.compare(this.time, other.time) : ret;
  91.         }
  92.     }
  93. }
复制代码
回复 支持 1 反对 0

使用道具 举报

LYJALEX__ 发表于 2016-1-9 10:49:02 | 显示全部楼层
第一题是否可以用 sorted double linked list + hash map?
插入 lgn,删除和查询 o 1
回复 支持 1 反对 0

使用道具 举报

巫山云似盖 发表于 2016-1-8 10:19:31 | 显示全部楼层
先赞一个,恭喜lz,很励志。面完后几周得知结果的?
回复 支持 反对

使用道具 举报

cyjbenyy 发表于 2016-1-8 11:01:10 | 显示全部楼层
Big cong! 顺便沾沾LZ喜气
找工作真心不容易,懂的都懂。。。
回复 支持 反对

使用道具 举报

umd2011 发表于 2016-1-8 11:03:27 | 显示全部楼层
恭喜楼主 !
马上要去Mountain View onsite了,希望能沾沾楼主的喜气。 Big bless
回复 支持 反对

使用道具 举报

zn88358800 发表于 2016-1-8 11:10:36 | 显示全部楼层
big cong 沾沾喜气
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-1-8 11:24:09 | 显示全部楼层
恭喜楼主拿到了Offer.然后有几点不清楚要问下楼主。1.第一题题目意思看不大懂,是给一个序列(时间点,股票值)?中间动态删除,然后求某个timeline之前的最大最小值?这个是怎么用heap做的? 2. complete tree返回最后一个level叶子,如何用二分做?  3. 求matrix里的黑色格子的四个边界是什么意思?是求某个黑色格子向四个方向所能延长的最远的黑色格子吗?二分算法是什么?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-8 11:39:01 来自手机 | 显示全部楼层
请问楼主股票那题求timestamp最大值是什么意思。一个time stamp不是只有一个值吗?还有请问complete tree楼主说二分法具体是值什么?
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-1-8 12:06:21 | 显示全部楼层
那个找边界,如果lz是对上下边界用binary search,那么左右一定要全走一遍才能确定边界吧。. visit 1point3acres.com for more.
如果这题意我没理解错的话。

回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:14:01 | 显示全部楼层
巫山云似盖 发表于 2016-1-8 10:19
先赞一个,恭喜lz,很励志。面完后几周得知结果的?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
面完第隔一周拿到口头offer,再隔一周拿到了正式的
回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:14:15 | 显示全部楼层
cyjbenyy 发表于 2016-1-8 11:01.鏈枃鍘熷垱鑷1point3acres璁哄潧
Big cong! 顺便沾沾LZ喜气
找工作真心不容易,懂的都懂。。。

共勉。。。。。。。
回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:14:43 | 显示全部楼层
umd2011 发表于 2016-1-8 11:03
恭喜楼主 !
马上要去Mountain View onsite了,希望能沾沾楼主的喜气。 Big bless
. From 1point 3acres bbs
加油,多看面经,版上的面经很有用的
回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:15:00 | 显示全部楼层

谢谢!!!
回复 支持 反对

使用道具 举报

DJ963 发表于 2016-1-8 12:30:35 | 显示全部楼层
首先恭喜楼主啦 不过关于这个.“给一个complete tree,返回最后一个level的叶子(用二分的思路)” 怎么用二分的思路解决啊 ? 这个题是要返回整个树的最后一层的最后一个节点吗
回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:36:11 | 显示全部楼层
bobzhang2004 发表于 2016-1-8 11:39. From 1point 3acres bbs
请问楼主股票那题求timestamp最大值是什么意思。一个time stamp不是只有一个值吗?还有请问complete tree楼 ...

是返回最后一个level的最后一个叶子,解答见上面一层
回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:37:44 | 显示全部楼层
yjfox 发表于 2016-1-8 12:06
那个找边界,如果lz是对上下边界用binary search,那么左右一定要全走一遍才能确定边界吧。
如果这题意我 ...

解答我写在14楼啦
回复 支持 反对

使用道具 举报

地里小马甲 发表于 2016-1-8 23:01:25 | 显示全部楼层
恭喜妹子!一直看你id!总算有了好结果了!
回复 支持 反对

使用道具 举报

MrA 发表于 2016-1-8 23:16:01 | 显示全部楼层
感谢LZ的分享!受益匪浅啊
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-9 06:49:34 | 显示全部楼层
第一轮的题目 楼主的解法 remove 操作是O(1)  getMax 和 getMin 操作是O(n)

另一种解法可以自己写一个indexed heap 通过在内部使用hashMap 将remove getMax getMin操作都变为 O(logn)

补充内容 (2016-1-10 07:34):
如果只是查询 那getMax getMin都是 O(1) remove还是O(logn)
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-9 07:41:13 | 显示全部楼层
第三轮合并 可以第一个binary search搜 0的边界  第二次搜1的边界  稍微改改就行
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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