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


一亩三分地论坛

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

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

google 两轮电面经验分享

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

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

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

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

x
google hr主动联系,问要不要interview他们software position,简历发过去后安排电面
一轮:电话面试 (pass)
上来什么都没说,直接做题,给出一个n*n的棋盘,每一个格子里有一个数字,规则是从任意一个位置走到相邻的四个中的一个(上下左右),但只能走到比当前位置大数字大的地方,问给你一个这样的棋盘,给出里面的最长路径。(用recursion做就行了). more info on 1point3acres.com
二轮:电话面试(fail). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
给一个BST,每一个节点里存有包含自己节点的子节点的个数,让返回nth smallest number, 用binary search就可以了,但是code当时写的很烂,corner case没有处理好。。。第二天接到了hr的据信。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

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

使用道具 举报

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

使用道具 举报

hyliu0000 发表于 2015-11-30 03:46:38 | 显示全部楼层
Neil_Acton 发表于 2015-11-27 05:01. more info on 1point3acres.com
第一题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;. 1point 3acres 璁哄潧
                public TreeNode(int val, int subtreeNodeNum) {
                        this.val = val;
                        this.subtreeNodeNum = subtreeNodeNum;
                }
        }. 1point 3acres 璁哄潧
       
        // 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;. 鍥磋鎴戜滑@1point 3 acres
                if (leftNum >= k) {
                        return findNthSmallestNumber(root.left, k);
                } else if (leftNum + 1 == k) {
                        return root.val;.1point3acres缃
                } else {
. 1point3acres.com/bbs                        return findNthSmallestNumber(root.right, k - (leftNum + 1));
                }. From 1point 3acres bbs
        }. more info on 1point3acres.com
       
        public static void main(String[] args) {
                TreeNode root = buildTree();
                int res = findNthSmallestNumber(root, 7);
                System.out.println(res);
        }

        private static TreeNode buildTree() {. 1point3acres.com/bbs
                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;
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-24 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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