推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

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

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

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

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

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

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

Google Phone:
1.  boolean hasDuplicateCharacter(String word);
给定一个string 判断是否有重复的char. from: 1point3acres.com/bbs
2. Lowest Common Parent of two nodes in a binary tree
这里有点tricky的是LCP和LCA的区别,假如p,q 是BT中的两个node,p是q的ancestor,那么LCA是p, LCP是p的parent。

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

第二轮:
Longest [continuous increasing] subarray, 返回长度
e.g. 1,2,3,5,8,9,12,13
LCIS: 1,2,3   return 3. 1point3acres.com/bbs
. more info on 1point3acres.com

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


中午, 斯德哥尔摩小哥带吃饭逛校园聊人生。。
. more info on 1point3acres.com
第三轮:
1. one edit distance-google 1point3acres
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. 1point3acres.com/bbs
电面第二轮:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Java 概念 + 数据结构。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
给一个数组, 长度为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实现迭代在时间和空间上有什么区别。

withdraw onsite

Indeed OA
就是这个:http://www.1point3acres.com/bbs/thread-145192-1-1.html
withdraw phone interview

Uber Phone + Onsite (详见这个帖子:http://www.1point3acres.com/bbs/thread-158786-1-1.html)

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

Redwood Campus:
4. Fusion Supply Chain Management
纯聊天

. 鍥磋鎴戜滑@1point 3 acres
5. Advanced Security Team
[1] SQL injection
[2] 谈谈当下你关心的安全问题。。XCodeGhost. From 1point 3acres bbs
[3] PKI Infra
[4] Kerberos..完全忘了。。
[5] LinkedList找环 I(判断是否有环), II(找环起点)
[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 | 显示全部楼层
kinggarden2001 发表于 2016-1-28 07:53. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题可以dp 吧?

对 就是dp
回复 支持 反对

使用道具 举报

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

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

            for(int i=0; i<matrix.length; i++){. 1point 3acres 璁哄潧
                    int max=0;
                    for(int j=matrix[0].length-1; j>=0; j--){
                            res[i][j]+=max;
                            if(matrix[i][j]==1){
                                    max++;
                            }else if(matrix[i][j]==-1){
. Waral 鍗氬鏈夋洿澶氭枃绔,                                    max=0;
                                res[i][j]=0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                            }
                    }
            }

            for(int j=0; j<matrix[0].length; j++){
                    int max=0;
                    for(int i=0; i<matrix.length; i++){
                            res[i][j]+=max;
                            if(matrix[i][j]==1){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                    max++;
                            }else if(matrix[i][j]==-1){
                                    max=0;
                                res[i][j]=0;
                            }
                    }
            }
. more info on 1point3acres.com
            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;-google 1point3acres
                            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;
                            }
                    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            }
            return max;
    }

回复 支持 反对

使用道具 举报

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

public static int findMax(int[][] matrix){

嗯 大致看了下应该是对的 实现的时候面试官要求2 pass 最后取max的那次遍历实际上可以和更新纵向怪兽数量的遍历合并 纵向更新完 res矩阵也就是最终状态了
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-2-2 13:27:21 | 显示全部楼层
ryb 发表于 2016-1-29 00:05. visit 1point3acres.com for more.
对 就是dp
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
怎么感觉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
嗯 大致看了下应该是对的 实现的时候面试官要求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. . more info on 1point3acres.com
  3.         static class TreeNode {. 1point3acres.com/bbs
  4.                 TreeNode left, right;
  5.                 int val;

  6.                 public TreeNode(int val) {
  7.                         this.val = val;
  8.                 }
  9.         }

  10.        
  11.         public static TreeNode getLowestCommonParent(TreeNode root, TreeNode p, TreeNode q) {
  12.                 if (root == null) {
  13.                         return null;
  14.                 }
  15.                
  16.                 if (root.left == p || root.right == p || root.left == q || root.right == q) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.                         return root;
  18.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.                 TreeNode left = getLowestCommonParent(root.left, p, q);. From 1point 3acres bbs
  20.                 TreeNode right = getLowestCommonParent(root.right, p, q);. visit 1point3acres.com for more.
  21.                 if (left != null && right != null) {
  22.                         return root;
  23.                 }
  24.                 if (left != null) {
  25.                         return left;
  26.                 } else {
  27.                         return right;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.                 }. From 1point 3acres bbs
  29.         }
  30.        
  31.        
  32.         public static void main(String[] args) {
  33.                 TreeNode root = new TreeNode(50);
  34.                 root.left = new TreeNode(10);
  35.                 root.right = new TreeNode(60);
  36.                 root.left.left = new TreeNode(5);
  37.                 root.left.right = new TreeNode(20);
  38.                 root.right.left = new TreeNode(55);
  39.                 root.right.left.left = new TreeNode(45);
  40.                 root.right.right = new TreeNode(70);
  41.                 root.right.right.left = new TreeNode(65);
    . 1point 3acres 璁哄潧
  42.                 root.right.right.right = new TreeNode(80);
  43.                 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  44.                 System.out.println(getLowestCommonParent(root, root.left.left, root.left.right).val);
  45.                 System.out.println(getLowestCommonParent(root, root.right.left, root.right.left.left).val);
  46.                 System.out.println(getLowestCommonParent(root, root.right.right, root.right.right.left).val);
  47.         }
  48. }
复制代码
回复 支持 反对

使用道具 举报

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"这个题是怎么做的吗?
. From 1point 3acres bbs
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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-17 19:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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