[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 11680|回复: 66
收起左侧

google onsite面经

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

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

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

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

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


下面是干货. Waral 博客有更多文章,
**************************************************分割线***********************************************************
. visit 1point3acres for more.
第一轮:
美国大叔,一个股票的stream,每个时间点(timeline)都有股票的更新,实现两个function:
1.给一个timeline,删掉当前点的股票
2.给你一个timeline让你求出历史股票数据的最大值和最小值
我使用heap和hashmap做的

第二轮:
国人姐姐
1.给一个linkedList,返回倒数第n个node,这个题我已开始竟然说先把链表反转,真想一巴掌拍死自己。。。。有时候真的紧张会大脑短路
2.给一个complete tree,返回最后一个level的叶子(用二分的思路)
剩下的时间讨论了下类似于unique tree的题,没写code
. 牛人云集,一亩三分地
午饭是内推我的前辈带我去吃的,因为比较紧张,所以并没有留意是不是好吃,好像还行吧
.留学论坛-一亩-三分地
第三轮:
俄罗斯姐姐带了一个shadow白人小哥,这个小哥全程红脸,不知道是紧张还是本身就自带腮红
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
回家的路上想到了,其实很简单,你们先自己想想

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

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

. visit 1point3acres for more.

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

最后,求选组顺利啊
-google 1point3acres

补充内容 (2016-1-8 12:35):
complete tree那道题是返回最后一个level的最后一个叶子

评分

7

查看全部评分

bobzhang2004 发表于 2016-1-14 04:35:11 | 显示全部楼层
多谢楼主,写了写complete tree last leaf的code
  1. public class CompleteTreeLastLeaf {
  2.         static class TreeNode {.1point3acres网
  3.                 TreeNode left, right;
  4.                 int val;
  5. . 围观我们@1point 3 acres
  6.                 public TreeNode(int v) {
  7.                         val = v;
  8.                 }. From 1point 3acres bbs
  9.         }

  10.         public static TreeNode findCompleteTreeLastLeaf(TreeNode root) {
  11.                 if (root == null) {
  12.                         return null;
  13.                 }.1point3acres网
  14.                 if (root.left == null && root.right == null) {
  15.                         return root;
  16.                 }
  17.                 if (root.left != null && root.right == null) {
  18.                         return root.left;
  19.                 }
  20.                 int left = countLeft(root.left);
  21.                 int right = countLeft(root.right);
  22.                 if (left == right) {
  23.                         return findCompleteTreeLastLeaf(root.right);
  24.                 } else {
  25.                         return findCompleteTreeLastLeaf(root.left);
  26.                 }. 1point 3acres 论坛
  27.         }. visit 1point3acres for more.
  28. 来源一亩.三分地论坛.
  29.         private static int countLeft(TreeNode left) { 来源一亩.三分地论坛.
  30.                 if (left == null) {
  31.                         return 0;.留学论坛-一亩-三分地
  32.                 }

  33.                 return countLeft(left.left) + 1;
  34.         }
  35. . 1point3acres
  36.         public static void main(String[] args) {
  37.                 TreeNode root = new TreeNode(1);
  38.                 System.out.println(findCompleteTreeLastLeaf(root).val);. From 1point 3acres bbs
  39.                 root.left = new TreeNode(2);
  40.                 System.out.println(findCompleteTreeLastLeaf(root).val);. Waral 博客有更多文章,
  41.                 root.right = new TreeNode(3);.本文原创自1point3acres论坛
  42.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  43.                 root.left.left = new TreeNode(4);
  44.                 System.out.println(findCompleteTreeLastLeaf(root).val);
  45.         }.本文原创自1point3acres论坛
  46. }
复制代码
回复 支持 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里删除,这样找最大值,最小值同理。. visit 1point3acres for more.
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。
.本文原创自1point3acres论坛
另一种方案使用BST,可以实现Delete: o(logn), add: O(logn), getMax/Min: O(1),但是其实这两种方案是没有本质区别的,BST内存上反而会多占,而且Performance上,BST由于data locality其实不如heap。
这两种方案我都实现了。.1point3acres网
. Waral 博客有更多文章,
  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<>();
  8. . visit 1point3acres for more.
  9.     // O(1)
  10.     public void deleteStockPrice(int time) {
  11.         deletedSet.add(time);
  12.     }
  13. . 1point3acres
  14.     // O(logn)
  15.     public void addStockPrice(StockPrice sp) {
  16.         minHeap.add(sp);
  17.         maxHeap.add(sp);
  18.     }

  19.     // O(1) for not deleted max, worst case O(nlogn). i.e. all items are deleted if the max is deleted. 一亩-三分-地,独家发布
  20.     public int getMax() {
  21.         while(!maxHeap.isEmpty() && deletedSet.contains(maxHeap.peek().time)). 1point 3acres 论坛
  22.             maxHeap.poll();
  23.         return maxHeap.isEmpty() ? -1 : maxHeap.peek().price;
  24.     }-google 1point3acres

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

  31.     // Method two, using a single BST tree to keep track of max/min
  32.     SortedSet<StockPrice> sortedPrice = new TreeSet<>();
  33.     Map<Integer, StockPrice> prices = new HashMap<Integer, StockPrice>();
  34.     int maxPrice = -1;. more info on 1point3acres
  35.     int minPrice = Integer.MAX_VALUE;
  36. . 牛人云集,一亩三分地
  37.     // O(logn)
  38.     public void deleteStockPrice2(int time) {
  39.         StockPrice sp = prices.get(time);
  40.         sortedPrice.remove(prices.get(time));
  41.         if(sortedPrice.isEmpty())
  42.         {
  43.             maxPrice = -1;
  44.             minPrice = Integer.MAX_VALUE;
  45.         }

  46.         if(sp.price == maxPrice)
    . 围观我们@1point 3 acres
  47.             maxPrice = sortedPrice.last().price;
  48.         if(sp.price == minPrice). visit 1point3acres for more.
  49.             minPrice = sortedPrice.first().price;
  50.     }

  51.     // O(logn). 牛人云集,一亩三分地
  52.     public void addStockPrice2(StockPrice sp){. 牛人云集,一亩三分地
  53.         prices.put(sp.time, sp);
  54.         sortedPrice.add(sp);
  55.         if(maxPrice < sp.price)
  56.             maxPrice = sp.price;
  57.         if(minPrice > sp.price)
  58.             minPrice = sp.price;
  59.     }

  60.     // O(1)
  61.     public int getMax2() {
  62.         return maxPrice;. more info on 1point3acres
  63.     }

  64.     // O(1)
  65.     public int getMin2() {
  66.         return minPrice;
  67.     }

  68.     public static class StockPrice implements Comparable<StockPrice>{
  69.         final int time;
  70.         final int price;
  71.         public StockPrice(int time, int price) {. 一亩-三分-地,独家发布
  72.             this.time = time;
  73.             this.price = price;. 一亩-三分-地,独家发布
  74.         }. 围观我们@1point 3 acres
  75. . 1point3acres
  76.         @Override
  77.         public int hashCode() {
  78.             return this.time * 51 + price;. Waral 博客有更多文章,
  79.         }
  80. . 围观我们@1point 3 acres
  81.         @Override
  82.         public boolean equals(Object other) {
  83.             if(other == null) return false;
  84.             if(this.getClass() != other.getClass()) return false;
  85.             StockPrice b = (StockPrice) other;
  86.             return this.price == b.price && this.time == b.time;
  87.         }

  88.         @Override
  89.         public int compareTo(StockPrice other) {
  90.             int ret = Integer.compare(this.price, other.price); 来源一亩.三分地论坛.

  91.             return ret == 0 ? Integer.compare(this.time, other.time) : ret;. 围观我们@1point 3 acres
  92.         }
  93.     }.1point3acres网
  94. }
复制代码
回复 支持 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
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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,那么左右一定要全走一遍才能确定边界吧。. Waral 博客有更多文章,
如果这题意我没理解错的话。

回复 支持 反对

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 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喜气
找工作真心不容易,懂的都懂。。。

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

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:14:43 | 显示全部楼层
umd2011 发表于 2016-1-8 11:03
恭喜楼主 !
马上要去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楼 ...

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

使用道具 举报

 楼主| 宝贝忆彼岸 发表于 2016-1-8 12:37:44 | 显示全部楼层
yjfox 发表于 2016-1-8 12:06
那个找边界,如果lz是对上下边界用binary search,那么左右一定要全走一遍才能确定边界吧。
如果这题意我 ...
. 围观我们@1point 3 acres
解答我写在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的边界  稍微改改就行
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-24 04:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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