一亩三分地论坛

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

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

Google Phone + Onsite 以及其他多家公司面经

[复制链接] |试试Instant~ |关注本帖
ryb 发表于 2016-1-28 10:52:26 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 Onsite 在线笔试 |Passfresh grad应届毕业生

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

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

x
1111光棍节onsite的。。拖延症晚期所以拖到今天才发出来。。(其实是一朋友想要。。). from: 1point3acres.com/bbs

Google Phone:.鐣欏璁哄潧-涓浜-涓夊垎鍦
1.  boolean hasDuplicateCharacter(String word);
给定一个string 判断是否有重复的char
2. Lowest Common Parent of two nodes in a binary tree. From 1point 3acres bbs
这里有点tricky的是LCP和LCA的区别,假如p,q 是BT中的两个node,p是q的ancestor,那么LCA是p, LCP是p的parent。

Onsite:
第一轮:
Bomb Game,给一个m*n的二维数组,其中有: -1 墙, 1 怪兽, 0 空白。 你有一个炸弹,可以扔在除墙之外的任意位置,最多可以炸死几个怪兽。
一开始给出了Brute Force的方法O(m*n*(m+n)), 后来优化给出了O(mn)的方法。 聊了一下可能出现的问题,如何test。

第二轮:.1point3acres缃
Longest [continuous increasing] subarray, 返回长度. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
e.g. 1,2,3,5,8,9,12,13
LCIS: 1,2,3   return 3
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

Longest continuous increasing path in a tree (不一定是binary的)
跟上题类似,算一个follow up,用了一个top-down的递归方法,后面又讨论了一下bottom-up的方法。面试官和shadow表示可以可以。。follow up是Tree -> DAG


中午, 斯德哥尔摩小哥带吃饭逛校园聊人生。。

第三轮:
1. one edit distance
2. 设计一个Meeting Room Reservation System,偏OOD,实现:
boolean reserve(double start_time, double end_time, double duration);
void cancel(double start_time, double end_time);
follow-up:如果遇到PDT-PST PST-PDT那一天该怎么handle。 答案是不用handle, 因为用Unix standard time的,根本没有PST/PDT这一说。。

第四轮:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Merge Intervals。。不多说了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

Yahoo(内推)
电面第一轮:
Java 概念 + 数据结构。。多态继承 static, hashmap hashtable treemap等等 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Coding: word break II
电面第二轮:
Java 概念 + 数据结构。。.1point3acres缃
给一个数组, 长度为9999,里面存了0-9999, 找到missing number。要求用三种解法做。。-google 1point3acres
withdraw onsite

Appfolio
电面:
给一个 API List<Restaurant> getRestaurant(ne_x, ne_y, sw_x, sw_y); 只能返回前50个restaurants,要求实现List<Restaurant> getAllRestaurant(ne_x, ne_y, sw_x, sw_y);
follow-up: 如果API不稳定经常挂,应该存什么信息来加速recovery; 递归改迭代/迭代改递归; stack和queue实现迭代在时间和空间上有什么区别。
.1point3acres缃
withdraw onsite.1point3acres缃

Indeed OA. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就是这个:http://www.1point3acres.com/bbs/thread-145192-1-1.html. 1point 3acres 璁哄潧
withdraw phone interview

Uber Phone + Onsite (详见这个帖子:http://www.1point3acres.com/bbs/thread-158786-1-1.html). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,
Oracle onsite, 这个比较特殊。。每一组面试的问题都差别很大,大多数都是在聊简历,这里就写一下我遇到的technical的问题吧。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Santa Clara Campus:
1. Oracle network team:
一段C code debug.. strcpy没有指定长度 可能会越界,改用strncpy

2. Solaris OS Networking Team
讨论了一下MPTCP,TCP recv_window, congestion window, AIMD

3. Oracle Storage System
                                                                                                                                                [1] 用一个array实现两个stack
[2] 如何判断一个系统是big endian 还是little endian 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 1point 3acres 璁哄潧
Redwood Campus:. 1point3acres.com/bbs
4. Fusion Supply Chain Management
纯聊天


5. Advanced Security Team
[1] SQL injection
[2] 谈谈当下你关心的安全问题。。XCodeGhost
[3] PKI Infra
[4] Kerberos..完全忘了。。
[5] LinkedList找环 I(判断是否有环), II(找环起点).鏈枃鍘熷垱鑷1point3acres璁哄潧
[6] 一道概率分布的题。。

6. Real Application Cluster
isPalindrome。。国人大哥放水了。。

----------------------------------------
以上,祝大家新年里找工顺利!

                               
                       
               

评分

2

查看全部评分

rb131108 发表于 2016-1-28 22:58:20 | 显示全部楼层
第一轮:
Bomb Game,给一个m*n的二维数组,其中有: -1 墙, 1 怪兽, 0 空白。 你有一个炸弹,可以扔在除墙之外的任意位置,最多可以炸死几个怪兽。
一开始给出了Brute Force的方法O(m*n*(m+n)), 后来优化给出了O(mn)的方法。 聊了一下可能出现的问题,如何test。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

请问这个炸弹爆炸的范围是怎么说的?
回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-1-28 22:59:56 | 显示全部楼层
rb131108 发表于 2016-1-28 06:58
第一轮:.鐣欏璁哄潧-涓浜-涓夊垎鍦
Bomb Game,给一个m*n的二维数组,其中有: -1 墙, 1 怪兽, 0 空白。 你有一个炸弹,可以扔在 ...

对。。忘记说了 炸弹爆炸可以清除这个炸弹所在的一行和一列的怪兽,但是不能穿过墙
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-28 23:53:21 | 显示全部楼层
第一题可以dp 吧?
回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-1-29 00:05:40 | 显示全部楼层

对 就是dp
回复 支持 反对

使用道具 举报

rb131108 发表于 2016-1-29 00:06:17 | 显示全部楼层
写了下,感觉和trap rain water那类题很像

public static int findMax(int[][] matrix){
            // -1 for wall, 1 for monster
            int[][] res=new int[matrix.length][matrix[0].length];. Waral 鍗氬鏈夋洿澶氭枃绔,
            for(int i=0; i<matrix.length; i++){
                    int max=0;
                    for(int j=0; j<matrix[0].length; j++){. 鍥磋鎴戜滑@1point 3 acres
                            res[i][j]+=max;
                            if(matrix[i][j]==1){
                                    max++;
                            }else if(matrix[i][j]==-1){
                                    max=0;
                                res[i][j]=0;
                            }
                    }
            }

            for(int i=0; i<matrix.length; i++){
                    int max=0;
                    for(int j=matrix[0].length-1; j>=0; j--){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                            res[i][j]+=max;-google 1point3acres
                            if(matrix[i][j]==1){. 鍥磋鎴戜滑@1point 3 acres
                                    max++;
                            }else if(matrix[i][j]==-1){
                                    max=0;
                                res[i][j]=0;
                            }
                    }. From 1point 3acres bbs
            }
. more info on 1point3acres.com
            for(int j=0; j<matrix[0].length; j++){
                    int max=0;. 1point3acres.com/bbs
                    for(int i=0; i<matrix.length; i++){
                            res[i][j]+=max;
                            if(matrix[i][j]==1){
                                    max++;
                            }else if(matrix[i][j]==-1){
                                    max=0;
                                res[i][j]=0;
                            }
                    }
            }

. visit 1point3acres.com for more.            for(int j=0; j<matrix[0].length; j++){
                    int max=0;
                    for(int i=matrix.length-1; i>=0; i--){
                            res[i][j]+=max;
                            if(matrix[i][j]==1){
                                    max++;
                            }else if(matrix[i][j]==-1){
                                    max=0;
                                    res[i][j]=0;
                            }
                    }
            }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            int max=0;
            for(int i=0; i<matrix.length; i++){
                    for(int j=0; j<matrix[0].length; j++){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                            int val=res[i][j];.鐣欏璁哄潧-涓浜-涓夊垎鍦
                            if(matrix[i][j]==1){
                                    val++;
                            } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                            if(val>max){
                                    max=val;
                            }
                    }
            }.1point3acres缃
            return max;. more info on 1point3acres.com
    }

回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-1-29 00:18:37 | 显示全部楼层
rb131108 发表于 2016-1-28 08:06. from: 1point3acres.com/bbs
写了下,感觉和trap rain water那类题很像. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

public static int findMax(int[][] matrix){
.鏈枃鍘熷垱鑷1point3acres璁哄潧
嗯 大致看了下应该是对的 实现的时候面试官要求2 pass 最后取max的那次遍历实际上可以和更新纵向怪兽数量的遍历合并 纵向更新完 res矩阵也就是最终状态了
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-2-2 13:27:21 | 显示全部楼层

怎么感觉fulltime的题好难啊。。。
回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-2-2 13:29:40 | 显示全部楼层
gjxwin 发表于 2016-2-1 21:27
怎么感觉fulltime的题好难啊。。。

我感觉我遇到的题算中等偏简单的。。我看有phd的面试有数学+概率的题(也有可能和他的方向有关系)。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-8 11:37:10 | 显示全部楼层
ryb 发表于 2016-1-29 00:18.鏈枃鍘熷垱鑷1point3acres璁哄潧
嗯 大致看了下应该是对的 实现的时候面试官要求2 pass 最后取max的那次遍历实际上可以和更新纵向怪兽数量 ...

这个题应该是和flower and garden是一个题吧
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-8 11:37:57 | 显示全部楼层
楼主可以详细说说"Meeting Room Reservation System"这个题是怎么做的吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-9 04:22:07 | 显示全部楼层
写了下phone interview的题
  1. public class LowestCommonParent {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  2.         static class TreeNode {
  3.                 TreeNode left, right;
  4.                 int val;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  5.                 public TreeNode(int val) {
  6.                         this.val = val;. 1point3acres.com/bbs
  7.                 }
  8.         }

  9.        
  10.         public static TreeNode getLowestCommonParent(TreeNode root, TreeNode p, TreeNode q) {
  11.                 if (root == null) {
  12.                         return null;
    . visit 1point3acres.com for more.
  13.                 }
  14.                
  15.                 if (root.left == p || root.right == p || root.left == q || root.right == q) {
  16.                         return root;. 鍥磋鎴戜滑@1point 3 acres
  17.                 }
  18.                 TreeNode left = getLowestCommonParent(root.left, p, q);
  19.                 TreeNode right = getLowestCommonParent(root.right, p, q);
    . 鍥磋鎴戜滑@1point 3 acres
  20.                 if (left != null && right != null) {
  21.                         return root;
  22.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.                 if (left != null) {
  24.                         return left;
  25.                 } else {. visit 1point3acres.com for more.
  26.                         return right;
  27.                 }
  28.         }
  29.        
  30.        
  31.         public static void main(String[] args) {
  32.                 TreeNode root = new TreeNode(50);
  33.                 root.left = new TreeNode(10);
  34.                 root.right = new TreeNode(60);. 1point 3acres 璁哄潧
  35.                 root.left.left = new TreeNode(5);
  36.                 root.left.right = new TreeNode(20);
  37.                 root.right.left = new TreeNode(55);
  38.                 root.right.left.left = new TreeNode(45);. Waral 鍗氬鏈夋洿澶氭枃绔,
  39.                 root.right.right = new TreeNode(70);
  40.                 root.right.right.left = new TreeNode(65);
  41.                 root.right.right.right = new TreeNode(80);
  42.                
  43.                 System.out.println(getLowestCommonParent(root, root.left.left, root.left.right).val);
  44.                 System.out.println(getLowestCommonParent(root, root.right.left, root.right.left.left).val);
  45.                 System.out.println(getLowestCommonParent(root, root.right.right, root.right.right.left).val);
  46.         }
  47. }
复制代码
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-9 05:25:38 | 显示全部楼层
ryb 发表于 2016-1-29 00:18
嗯 大致看了下应该是对的 实现的时候面试官要求2 pass 最后取max的那次遍历实际上可以和更新纵向怪兽数量 ...

2pass怎麼做?我想的和樓上的也差不多,不過上下左右已經4次了。。還能怎麼優化啊?
回复 支持 反对

使用道具 举报

GUIXIANG 发表于 2016-3-21 11:47:37 | 显示全部楼层
bobzhang2004 发表于 2016-3-9 04:22
写了下phone interview的题

第18行这样判断之后直接返回root,相当于是LCA,不是LCP吧?楼主说明了他们两个不一样的。

弱问楼主,这一题node类有parent field吗?

补充内容 (2016-3-21 14:17):
我傻了,这么写没问题。。。
回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-3-21 11:55:17 | 显示全部楼层
bobzhang2004 发表于 2016-3-7 19:37
楼主可以详细说说"Meeting Room Reservation System"这个题是怎么做的吗?

Short Answer: 就是用一个24*60的数组去mark每一天的每一个room的预定情况
回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-3-21 11:56:50 | 显示全部楼层
guschen802 发表于 2016-3-8 13:25
2pass怎麼做?我想的和樓上的也差不多,不過上下左右已經4次了。。還能怎麼優化啊?
. more info on 1point3acres.com
其实是4pass。。。只不过我的方法是从左到右,从上到下,面试官看上去是2pass 但是更新的时候还算一次pass
回复 支持 反对

使用道具 举报

 楼主| ryb 发表于 2016-3-21 11:58:05 | 显示全部楼层
GUIXIANG 发表于 2016-3-20 19:47
第18行这样判断之后直接返回root,相当于是LCA,不是LCP吧?楼主说明了他们两个不一样的。

弱问楼主, ...

没有Parent Node, 和Leetcode上的题差不多,只不过如果LCA算出来是两个node其中一个node,还需要继续算一下parent node
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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