google onsite面经

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


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

第一轮：

美国大叔，一个股票的stream，每个时间点(timeline)都有股票的更新，实现两个function：

1.给一个timeline，删掉当前点的股票

2.给你一个timeline让你求出历史股票数据的最大值和最小值

我使用heap和hashmap做的

第二轮：

国人姐姐

1.给一个linkedList，返回倒数第n个node，这个题我已开始竟然说先把链表反转，真想一巴掌拍死自己。。。。有时候真的紧张会大脑短路

2.给一个complete tree，返回最后一个level的叶子（用二分的思路）

剩下的时间讨论了下类似于unique tree的题，没写code

午饭是内推我的前辈带我去吃的，因为比较紧张，所以并没有留意是不是好吃，好像还行吧

第三轮：

俄罗斯姐姐带了一个shadow白人小哥，这个小哥全程红脸，不知道是紧张还是本身就自带腮红

您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

回家的路上想到了，其实很简单，你们先自己想想

第四轮 都是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):
complete tree那道题是返回最后一个level的最后一个叶子

多谢楼主，写了写complete tree last leaf的code

1. public class CompleteTreeLastLeaf {
   
2.         static class TreeNode {
   
3.                 TreeNode left, right;
   
4.                 int val;
   
5. 
   
6.                 public TreeNode(int v) {
   
7.                         val = v;
   
8.                 }
   
9.         }
   
10. 
    
11.         public static TreeNode findCompleteTreeLastLeaf(TreeNode root) {
    
12.                 if (root == null) {
    
13.                         return null;
    
14.                 }
    
15.                 if (root.left == null && root.right == null) {
    
16.                         return root;
    
17.                 }
    
18.                 if (root.left != null && root.right == null) {
    
19.                         return root.left;
    
20.                 }
    
21.                 int left = countLeft(root.left);
    
22.                 int right = countLeft(root.right);
    
23.                 if (left == right) {
    
24.                         return findCompleteTreeLastLeaf(root.right);
    
25.                 } else {
    
26.                         return findCompleteTreeLastLeaf(root.left);
    
27.                 }
    
28.         }
    
29. 
    
30.         private static int countLeft(TreeNode left) {
    
31.                 if (left == null) {
    
32.                         return 0;
    
33.                 }
    
34. 
    
35.                 return countLeft(left.left) + 1;
    
36.         }
    
37. 
    
38.         public static void main(String[] args) {
    
39.                 TreeNode root = new TreeNode(1);
    
40.                 System.out.println(findCompleteTreeLastLeaf(root).val);
    
41.                 root.left = new TreeNode(2);
    
42.                 System.out.println(findCompleteTreeLastLeaf(root).val);
    
43.                 root.right = new TreeNode(3);
    
44.                 System.out.println(findCompleteTreeLastLeaf(root).val);
    
45.                 root.left.left = new TreeNode(4);
    
46.                 System.out.println(findCompleteTreeLastLeaf(root).val);
    
47.         }
    
48. }

复制代码

按照楼主的思路用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。
这两种方案我都实现了。

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. 
   
9.     // O(1)
   
10.     public void deleteStockPrice(int time) {
    
11.         deletedSet.add(time);
    
12.     }
    
13. 
    
14.     // O(logn)
    
15.     public void addStockPrice(StockPrice sp) {
    
16.         minHeap.add(sp);
    
17.         maxHeap.add(sp);
    
18.     }
    
19. 
    
20.     // O(1) for not deleted max, worst case O(nlogn). i.e. all items are deleted if the max is deleted
    
21.     public int getMax() {
    
22.         while(!maxHeap.isEmpty() && deletedSet.contains(maxHeap.peek().time))
    
23.             maxHeap.poll();
    
24.         return maxHeap.isEmpty() ? -1 : maxHeap.peek().price;
    
25.     }
    
26. 
    
27.     public int getMin() {
    
28.         while(!minHeap.isEmpty() && deletedSet.contains(minHeap.peek().time))
    
29.             minHeap.poll();
    
30.         return minHeap.isEmpty() ? -1 :  minHeap.peek().price;
    
31.     }
    
32. 
    
33. 
    
34.     // Method two, using a single BST tree to keep track of max/min
    
35.     SortedSet<StockPrice> sortedPrice = new TreeSet<>();
    
36.     Map<Integer, StockPrice> prices = new HashMap<Integer, StockPrice>();
    
37.     int maxPrice = -1;
    
38.     int minPrice = Integer.MAX_VALUE;
    
39. 
    
40.     // O(logn)
    
41.     public void deleteStockPrice2(int time) {
    
42.         StockPrice sp = prices.get(time);
    
43.         sortedPrice.remove(prices.get(time));
    
44.         if(sortedPrice.isEmpty())
    
45.         {
    
46.             maxPrice = -1;
    
47.             minPrice = Integer.MAX_VALUE;
    
48.         }
    
49. 
    
50.         if(sp.price == maxPrice)
    
51.             maxPrice = sortedPrice.last().price;
    
52.         if(sp.price == minPrice)
    
53.             minPrice = sortedPrice.first().price;
    
54.     }
    
55. 
    
56.     // O(logn)
    
57.     public void addStockPrice2(StockPrice sp){
    
58.         prices.put(sp.time, sp);
    
59.         sortedPrice.add(sp);
    
60.         if(maxPrice < sp.price)
    
61.             maxPrice = sp.price;
    
62.         if(minPrice > sp.price)
    
63.             minPrice = sp.price;
    
64.     }
    
65. 
    
66.     // O(1)
    
67.     public int getMax2() {
    
68.         return maxPrice;
    
69.     }
    
70. 
    
71.     // O(1)
    
72.     public int getMin2() {
    
73.         return minPrice;
    
74.     }
    
75. 
    
76.     public static class StockPrice implements Comparable<StockPrice>{
    
77.         final int time;
    
78.         final int price;
    
79.         public StockPrice(int time, int price) {
    
80.             this.time = time;
    
81.             this.price = price;
    
82.         }
    
83. 
    
84.         @Override
    
85.         public int hashCode() {
    
86.             return this.time * 51 + price;
    
87.         }
    
88. 
    
89.         @Override
    
90.         public boolean equals(Object other) {
    
91.             if(other == null) return false;
    
92.             if(this.getClass() != other.getClass()) return false;
    
93.             StockPrice b = (StockPrice) other;
    
94.             return this.price == b.price && this.time == b.time;
    
95.         }
    
96. 
    
97.         @Override
    
98.         public int compareTo(StockPrice other) {
    
99.             int ret = Integer.compare(this.price, other.price);
    
100. 
     
101.             return ret == 0 ? Integer.compare(this.time, other.time) : ret;
     
102.         }
     
103.     }
     
104. }
     

复制代码

第一题是否可以用 sorted double linked list ＋ hash map？
插入 lgn，删除和查询 o 1

先赞一个，恭喜lz，很励志。面完后几周得知结果的？

Big cong! 顺便沾沾LZ喜气
找工作真心不容易，懂的都懂。。。

恭喜楼主 !
马上要去Mountain View onsite了，希望能沾沾楼主的喜气。 Big bless

big cong 沾沾喜气

恭喜楼主拿到了Offer.然后有几点不清楚要问下楼主。1.第一题题目意思看不大懂，是给一个序列（时间点，股票值）？中间动态删除，然后求某个timeline之前的最大最小值？这个是怎么用heap做的？ 2. complete tree返回最后一个level叶子，如何用二分做？  3. 求matrix里的黑色格子的四个边界是什么意思？是求某个黑色格子向四个方向所能延长的最远的黑色格子吗？二分算法是什么？

请问楼主股票那题求timestamp最大值是什么意思。一个time stamp不是只有一个值吗？还有请问complete tree楼主说二分法具体是值什么？

那个找边界，如果lz是对上下边界用binary search，那么左右一定要全走一遍才能确定边界吧。
如果这题意我没理解错的话。

巫山云似盖 发表于 2016-1-8 10:19
先赞一个，恭喜lz，很励志。面完后几周得知结果的？

面完第隔一周拿到口头offer，再隔一周拿到了正式的

cyjbenyy 发表于 2016-1-8 11:01
Big cong! 顺便沾沾LZ喜气
找工作真心不容易，懂的都懂。。。

共勉。。。。。。。