买房小白任秀坡在湾区买房经历(一)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
国内机会:实时大数据分析领域领导者
Web/大数据/机器学习/产品等职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 1855|回复: 8
收起左侧

google 两轮电面经验分享

[复制链接] |试试Instant~ |关注本帖
yingryic 发表于 2015-11-26 14:56:52 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - Other - HR筛选 技术电面  | Fail | fresh grad应届毕业生

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

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

x
google hr主动联系,问要不要interview他们software position,简历发过去后安排电面. 1point3acres.com/bbs
一轮:电话面试 (pass). From 1point 3acres bbs
上来什么都没说,直接做题,给出一个n*n的棋盘,每一个格子里有一个数字,规则是从任意一个位置走到相邻的四个中的一个(上下左右),但只能走到比当前位置大数字大的地方,问给你一个这样的棋盘,给出里面的最长路径。(用recursion做就行了)
二轮:电话面试(fail)
给一个BST,每一个节点里存有包含自己节点的子节点的个数,让返回nth smallest number, 用binary search就可以了,但是code当时写的很烂,corner case没有处理好。。。第二天接到了hr的据信。。。

评分

1

查看全部评分

bobzhang2004 发表于 2015-11-26 22:45:55 来自手机 | 显示全部楼层
第一面是矩阵中的最长上升序列吧,用记忆化搜索?
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2015-11-27 05:01:33 | 显示全部楼层
第一题dp记忆优化, 扫一遍就行了。 第二题recursion 每次subproblem 是 左子树找 n  或者 右子树找 n-1-left (left 表示左子树节点个数)
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-30 03:46:38 | 显示全部楼层
Neil_Acton 发表于 2015-11-27 05:01
第一题dp记忆优化, 扫一遍就行了。 第二题recursion 每次subproblem 是 左子树找 n  或者 右子树找 n-1-le ...

第一题四个方向都可以走。 如何dp?
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2015-11-30 12:00:15 | 显示全部楼层
hyliu0000 发表于 2015-11-30 03:46
第一题四个方向都可以走。 如何dp?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是加一个 memorization   每个点不需要重复找最长路径
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-30 23:27:55 | 显示全部楼层
Neil_Acton 发表于 2015-11-30 12:00
就是加一个 memorization   每个点不需要重复找最长路径

也就是说你用个boolean[] visited来避免重复去同一个点?
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-30 23:39:18 | 显示全部楼层
Neil_Acton 发表于 2015-11-30 12:00
就是加一个 memorization   每个点不需要重复找最长路径

明白了。。 你的意思用一个二维矩阵去记录每个点的最长路径。
回复 支持 反对

使用道具 举报

红色鲱鱼 发表于 2015-11-30 23:39:57 | 显示全部楼层
楼主的第二题没太看懂。如果每个节点存着自己所有子节点的个数的话那么根节点的值一定是最大的,如何形成BST?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 01:34:14 | 显示全部楼层
第二题代码,欢迎指正
public class NthSmallestNumber {
-google 1point3acres
       
        static class TreeNode {
                TreeNode left;
                TreeNode right;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                int val;
                int subtreeNodeNum;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                public TreeNode(int val, int subtreeNodeNum) {
                        this.val = val;
                        this.subtreeNodeNum = subtreeNodeNum;
                }
        }
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        // 1 2 3 4 5    k = 2, return 2. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        public static int findNthSmallestNumber(TreeNode root, int k) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if (root == null || root.subtreeNodeNum < k) {
                        return Integer.MIN_VALUE;. From 1point 3acres bbs
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                int leftNum = root.left == null? 0 : root.left.subtreeNodeNum;
                if (leftNum >= k) {
                        return findNthSmallestNumber(root.left, k);
                } else if (leftNum + 1 == k) {
                        return root.val;
                } else {. 1point3acres.com/bbs
                        return findNthSmallestNumber(root.right, k - (leftNum + 1));. From 1point 3acres bbs
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        .1point3acres缃
        public static void main(String[] args) {
                TreeNode root = buildTree();
                int res = findNthSmallestNumber(root, 7);
                System.out.println(res);
        }

        private static TreeNode buildTree() {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                TreeNode root = new TreeNode(11, 6);
                TreeNode no1 = new TreeNode(8, 4);
                TreeNode no2 = new TreeNode(7, 1);
                TreeNode no3 = new TreeNode(2, 1);
                TreeNode no4 = new TreeNode(10, 2);
                TreeNode no5 = new TreeNode(9, 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                root.left = no1;
                root.right = no2;
                no1.left = no3;
                no1.right = no4;
                no4.left = no5;
                return root;
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-4-20 07:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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