一亩三分地论坛

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

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

google 两轮电面经验分享

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

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

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

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

x
google hr主动联系,问要不要interview他们software position,简历发过去后安排电面.1point3acres缃
一轮:电话面试 (pass). 1point 3acres 璁哄潧
上来什么都没说,直接做题,给出一个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. visit 1point3acres.com for more.
第一题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 {

       
        static class TreeNode { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                TreeNode left;
                TreeNode right;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                int val;
                int subtreeNodeNum;
                public TreeNode(int val, int subtreeNodeNum) {. visit 1point3acres.com for more.
                        this.val = val;
                        this.subtreeNodeNum = subtreeNodeNum;. Waral 鍗氬鏈夋洿澶氭枃绔,
                }.1point3acres缃
        }
       
        // 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;
                }
                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 {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        return findNthSmallestNumber(root.right, k - (leftNum + 1));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
        }
       
        public static void main(String[] args) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                TreeNode root = buildTree();
                int res = findNthSmallestNumber(root, 7);
                System.out.println(res);
        }

        private static TreeNode buildTree() {-google 1point3acres
                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);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                root.left = no1;
                root.right = no2;
                no1.left = no3;
                no1.right = no4;
                no4.left = no5;
                return root;
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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