近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 9933|回复: 66
收起左侧

google onsite面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

下面是干货
**************************************************分割线***********************************************************

第一轮:
美国大叔,一个股票的stream,每个时间点(timeline)都有股票的更新,实现两个function:
1.给一个timeline,删掉当前点的股票
2.给你一个timeline让你求出历史股票数据的最大值和最小值
我使用heap和hashmap做的

第二轮:
国人姐姐
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,面试官更看重你的思路,还有你对数据结构和算法是不是能够灵活应用
. 1point3acres.com/bbs
5.中国同胞出题都更加偏向leetcode,而且都很给力,你懂得. 1point 3acres 璁哄潧

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

最后,求选组顺利啊

.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-1-8 12:35):
complete tree那道题是返回最后一个level的最后一个叶子

评分

7

查看全部评分

bobzhang2004 发表于 2016-1-14 04:35:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
多谢楼主,写了写complete tree last leaf的code
  1. public class CompleteTreeLastLeaf {
  2.         static class TreeNode {-google 1point3acres
  3.                 TreeNode left, right;
  4.                 int val;. visit 1point3acres.com for more.

  5.                 public TreeNode(int v) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.                         val = v;
  7.                 }. 鍥磋鎴戜滑@1point 3 acres
  8.         }

  9.         public static TreeNode findCompleteTreeLastLeaf(TreeNode root) {
  10.                 if (root == null) {
  11.                         return null;
  12.                 }
  13.                 if (root.left == null && root.right == null) {
  14.                         return root;
  15.                 }
  16.                 if (root.left != null && root.right == null) {. 1point3acres.com/bbs
  17.                         return root.left;
  18.                 }
  19.                 int left = countLeft(root.left);. 鍥磋鎴戜滑@1point 3 acres
  20.                 int right = countLeft(root.right);
  21.                 if (left == right) {
  22.                         return findCompleteTreeLastLeaf(root.right);
  23.                 } else {
  24.                         return findCompleteTreeLastLeaf(root.left);. visit 1point3acres.com for more.
  25.                 }
  26.         }
  27. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.         private static int countLeft(TreeNode left) {
  29.                 if (left == null) {
  30.                         return 0;
  31.                 }

  32.                 return countLeft(left.left) + 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.         }
  34. . 鍥磋鎴戜滑@1point 3 acres
  35.         public static void main(String[] args) {
  36.                 TreeNode root = new TreeNode(1);
  37.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  38.                 root.left = new TreeNode(2);
  39.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  40.                 root.right = new TreeNode(3);
  41.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  42.                 root.left.left = new TreeNode(4);
  43.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  44.         }. 1point 3acres 璁哄潧
  45. }
复制代码
回复 支持 0 反对 2

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:35:06 | 显示全部楼层
关注一亩三分地微博:
Warald
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.. from: 1point3acres.com/bbs

看到楼上讨论的一个问题是,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。
这两种方案我都实现了。

  1. public class StockStreaming {
  2.     // heap + hashmap
  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<>();.鏈枃鍘熷垱鑷1point3acres璁哄潧

  8.     // O(1)
  9.     public void deleteStockPrice(int time) {
  10.         deletedSet.add(time);
  11.     }

  12.     // O(logn)
  13.     public void addStockPrice(StockPrice sp) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.         minHeap.add(sp);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.         maxHeap.add(sp);
  16.     }

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

  23.     public int getMin() {
  24.         while(!minHeap.isEmpty() && deletedSet.contains(minHeap.peek().time))
  25.             minHeap.poll();
  26.         return minHeap.isEmpty() ? -1 :  minHeap.peek().price;
  27.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


  28.     // Method two, using a single BST tree to keep track of max/min
  29.     SortedSet<StockPrice> sortedPrice = new TreeSet<>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.     Map<Integer, StockPrice> prices = new HashMap<Integer, StockPrice>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.     int maxPrice = -1;
  32.     int minPrice = Integer.MAX_VALUE; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  33.     // O(logn)
  34.     public void deleteStockPrice2(int time) {
  35.         StockPrice sp = prices.get(time);
  36.         sortedPrice.remove(prices.get(time));
  37.         if(sortedPrice.isEmpty())
  38.         {
  39.             maxPrice = -1;
  40.             minPrice = Integer.MAX_VALUE;
  41.         }
  42. . visit 1point3acres.com for more.
  43.         if(sp.price == maxPrice)
  44.             maxPrice = sortedPrice.last().price;
  45.         if(sp.price == minPrice)
  46.             minPrice = sortedPrice.first().price;
  47.     }

  48.     // O(logn)
  49.     public void addStockPrice2(StockPrice sp){. Waral 鍗氬鏈夋洿澶氭枃绔,
  50.         prices.put(sp.time, sp);
  51.         sortedPrice.add(sp);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  52.         if(maxPrice < sp.price)
  53.             maxPrice = sp.price;
  54.         if(minPrice > sp.price). 1point 3acres 璁哄潧
  55.             minPrice = sp.price;
  56.     }

  57.     // O(1)
  58.     public int getMax2() {
  59.         return maxPrice;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  60.     }

  61.     // O(1)
  62.     public int getMin2() {
  63.         return minPrice;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  64.     }

  65.     public static class StockPrice implements Comparable<StockPrice>{
  66.         final int time;
  67.         final int price;
  68.         public StockPrice(int time, int price) {
  69.             this.time = time;
  70.             this.price = price;
  71.         }.1point3acres缃

  72.         @Override. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  73.         public int hashCode() {. From 1point 3acres bbs
  74.             return this.time * 51 + price;
  75.         }

  76.         @Override
  77.         public boolean equals(Object other) {
  78.             if(other == null) return false;
  79.             if(this.getClass() != other.getClass()) return false;
  80.             StockPrice b = (StockPrice) other;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  81.             return this.price == b.price && this.time == b.time;
  82.         }

  83.         @Override
  84.         public int compareTo(StockPrice other) {. 鍥磋鎴戜滑@1point 3 acres
  85.             int ret = Integer.compare(this.price, other.price);
  86. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  87.             return ret == 0 ? Integer.compare(this.time, other.time) : ret;
  88.         }
  89.     }
  90. }
复制代码
回复 支持 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,那么左右一定要全走一遍才能确定边界吧。. 1point 3acres 璁哄潧
如果这题意我没理解错的话。
. 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
Big cong! 顺便沾沾LZ喜气. from: 1point3acres.com/bbs
找工作真心不容易,懂的都懂。。。

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

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:14:43 | 显示全部楼层
umd2011 发表于 2016-1-8 11:03. 1point3acres.com/bbs
恭喜楼主 !
马上要去Mountain View onsite了,希望能沾沾楼主的喜气。 Big bless
.鐣欏璁哄潧-涓浜-涓夊垎鍦
加油,多看面经,版上的面经很有用的
回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 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
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴请问楼主股票那题求timestamp最大值是什么意思。一个time stamp不是只有一个值吗?还有请问complete tree楼 ...
. 鍥磋鎴戜滑@1point 3 acres
是返回最后一个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的边界  稍微改改就行
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-22 20:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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