传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 14856|回复: 72
收起左侧

Google 4月27 Onsite

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

2015(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
这周一面的,周五接到电话遭拒以下问题的解法欢迎大家多多指教多多讨论

第一轮:
. more info on 1point3acres.com多叉树,每个节点是一个整数,求书中最长递增路径比如5,6,7,8,9
看似简单其实有不少坑,感觉就是跪在这一轮了,所以后边面的反而很放松。。
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分
. Waral 鍗氬鏈夋洿澶氭枃绔,
第三轮:
一堆密码箱,每个密码都是四位0-9之间,算一个暴力破解序列,包含所有可能的四位序列,让这个序列尽量短
给了一个贪心算法,代码写的比较长,而且没bug free
. more info on 1point3acres.com
中饭时间。。。

第四轮:
系统设计题,设计google map后端存储,这个面试官口音极重,交流无力,希望大牛指点一下google map后端是怎么做的,怎么scale?

第五轮:
最后一轮,求sum(n^i) 就是1+n+n2+n3+...+n^N, 快速写了一个O(N)之后让我优化,其实这个二分O(lgN)很容易想的,但是当时用了很长时间表现不太好。
第二题是个矩阵,每个节点是一个计算机,计算机之间传一个文件的cost是节点值x路径长度,选择所有计算机为接收端,求所有文件传输的cost
快速写了个暴力方法
尝试动态规划无果
后来想到可以cache所有行列的cost和,正这一边反着一遍,然后状态转移就是O(1)了,但是没时间写了,在他提议下写了一个一维特殊情况的代码,中间有个加号还忘了写,算是sloppy coding吧
希望大牛们指点一下这个题


第一次大公司onsite,准备不足,跪了也是情理之中,感觉长时间准备还是很必要的,而且一定要多练纸上写代码,做到bug free

评分

10

查看全部评分

本帖被以下淘专辑推荐:

LYJALEX__ 发表于 2016-1-12 05:24:07 | 显示全部楼层
public String sequenceGenerator(){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                int start = 9999;
                String result = ""+start;
                Set<Integer> visited = new HashSet<>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                visited.add(start);
                while(visited.size()<10000){
                        int next = start*10%10000;
                        int i=0;-google 1point3acres
                        for(;i<=9;i++){
                                if (!visited.contains(next+i)) break;
                        }
                        visited.add(next+i);
                        start = next+i;
                        result+=i;. more info on 1point3acres.com
                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                return result;
                . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }

回复 支持 6 反对 0

使用道具 举报

aiwojiujiu 发表于 2016-1-15 07:47:27 | 显示全部楼层
umd2011 发表于 2016-1-15 07:38
大神, 都DP的状态转移方程!想不起来怎么优化啊,被自己的蠢下晕了。

        public static int getTotalDistance(int m, int n) {. more info on 1point3acres.com
                int[][] matrix = new int[m][n];
                for (int i = 0; i < m; i++) {
                        for (int j = 0; j < n; j++) {
                                matrix[0][0] += i + j;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        }
                }

                for (int i = 1; i < m; i++) {
                        matrix[0] = matrix[i - 1][0] + i * n - (m - i) * n;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
               
                for (int i = 0; i < m; i++) {
                        for (int j = 1; j < n; j++) {
                                matrix[j] = matrix[j - 1] + j * m - (n - j) * m;. 1point3acres.com/bbs
                        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
               
                int result = 0;
                for (int i = 0; i < m; i++) {
                        for (int j = 0; j < n; j++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                result += matrix[j];
                                System.out.print(matrix[j] + " ");
                        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        System.out.println();
                }
                return result;
        }
回复 支持 2 反对 2

使用道具 举报

ijk5554234 发表于 2015-7-21 04:18:40 | 显示全部楼层
那个密码的题自己用了hashset把所有访问过的数字全部存下来,贴一下自己的代码 最后string的长度是10003, 说明没有重复
        public static String getPass(HashSet<Integer> visit) {
                int num = 9999;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷                int count = 0;
                StringBuilder sb = new StringBuilder("999");
                while (visit.size() < 10000) {
                        sb.append(num % 10);
                        visit.add(num);
                        num *= 10;
                        num %= 10000;
                        int add = 0;
                        while (add < 9) {
                                if (!visit.contains(num + add)) {. more info on 1point3acres.com
                                        break;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                add++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }
                        num += (add % 10);
                        count++;. visit 1point3acres.com for more.
                }
                System.out.println(count);
                return sb.toString();
        }. 1point3acres.com/bbs

        public static void main(String[] args) {
                HashSet<Integer> visited = new HashSet<Integer>(0);
                String s = getPass(visited);
                System.out.println(s);
                System.out.println("length:" + s.length());
                for (int i = 0 ; i < 10000; i++) {
                        String num = Integer.toString(i);       
                        //refill the string, e.g:39->0039
                        if (num.length() < 4) {
                                StringBuilder sb = new StringBuilder(num);
                                for (int j = 0; j < 4 - num.length(); j++) {
                                        sb.insert(0, "0");. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                num = sb.toString();.1point3acres缃
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        if (s.indexOf(num) == -1) {
                                System.out.println("false");
                        }
                }       
        }
回复 支持 1 反对 1

使用道具 举报

averillzheng 发表于 2015-5-3 07:11:52 | 显示全部楼层
能分享一下密码的那题的code 吗?贪心怎么搞。 这个问题是一个npc问题。而且应该是求一个Hamiltonian cycle的问题。
回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2015-5-3 00:03:03 | 显示全部楼层
感觉题目都不好答呢
lz很好了
回复 支持 反对

使用道具 举报

 楼主| baudelaire 发表于 2015-5-3 15:58:05 | 显示全部楼层
averillzheng 发表于 2015-5-3 07:11
能分享一下密码的那题的code 吗?贪心怎么搞。 这个问题是一个npc问题。而且应该是求一个Hamiltonian cycle ...

其实我觉得贪心可以出最优解,因为所有数字是等价的。具体方法是从0000开始维护一个窗口变量,开始设为3,表示和后一个code重合长度为3,枚举第四个得到00001,重复这一步骤。如果发现枚举到的code出现过就缩小窗口大小。判重用hash
回复 支持 反对

使用道具 举报

owenwilder 发表于 2015-5-4 09:23:46 | 显示全部楼层
看来谷歌也是有时候难有时候简单,楼主要是一个月前面很可能就过了。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-5-4 10:12:47 | 显示全部楼层
baudelaire 发表于 2015-5-3 15:58.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实我觉得贪心可以出最优解,因为所有数字是等价的。具体方法是从0000开始维护一个窗口变量,开始设为3 ...

这不是贪心,是DFS方法。这个题的主要问题是你要能说清楚这样做下去能够得到所有的4位数字组成的密码。
回复 支持 反对

使用道具 举报

 楼主| baudelaire 发表于 2015-5-4 16:15:54 | 显示全部楼层
owenwilder 发表于 2015-5-4 09:23
看来谷歌也是有时候难有时候简单,楼主要是一个月前面很可能就过了。

恩恩 其实感觉自己主要问题是写代码容易出bug,准备一年以后再面一下
回复 支持 反对

使用道具 举报

 楼主| baudelaire 发表于 2015-5-4 16:17:58 | 显示全部楼层
averillzheng 发表于 2015-5-4 10:12
这不是贪心,是DFS方法。这个题的主要问题是你要能说清楚这样做下去能够得到所有的4位数字组成的密码。

能具体说一下你的思路吗? 我给的方法里边如果窗口size为0的话肯定能枚举出下一个没用过的code,所以10000次循环每次都能找到新code加到串里面
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-5-4 23:37:56 | 显示全部楼层
baudelaire 发表于 2015-5-4 16:17.1point3acres缃
能具体说一下你的思路吗? 我给的方法里边如果窗口size为0的话肯定能枚举出下一个没用过的code,所以1000 ...
. From 1point 3acres bbs
我是把这个题想成了一个图的问题。然后可以用dfs放来做遍历图。但是我不能证明dfs遍历的过程中,每个点只被走过一次。
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-7 13:13:42 | 显示全部楼层
baudelaire 发表于 2015-5-3 15:58
其实我觉得贪心可以出最优解,因为所有数字是等价的。具体方法是从0000开始维护一个窗口变量,开始设为3 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主,没太理解密码的题意啊。什么叫让这个序列最短啊?0000-9999不是一定有10000个数字么,那序列不是定长么(10000)?还请楼主指教下啊
回复 支持 反对

使用道具 举报

magicalcan 发表于 2015-5-19 16:28:38 | 显示全部楼层
第五轮第一个sum n^i怎么logn啊
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-5-19 21:14:12 | 显示全部楼层
magicalcan 发表于 2015-5-19 16:28.鏈枃鍘熷垱鑷1point3acres璁哄潧
第五轮第一个sum n^i怎么logn啊

刚才那个描述把我吓到了,其实是一个等比数列,等比数列有求和公式,当时需要算 x^N,   如果直接N个X相乘就是O(N),  但是这个没必要,比如 2^4 = (2^2) ^2
回复 支持 反对

使用道具 举报

dddxhh 发表于 2015-5-19 21:48:52 | 显示全部楼层
mkcing 发表于 2015-5-19 21:14
刚才那个描述把我吓到了,其实是一个等比数列,等比数列有求和公式,当时需要算 x^N,   如果直接N个X相乘 ...

这式子是f(m) = nf(m-1) + 1的形式,不算是等比数列。 矩阵快速幂吧
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-5-19 21:56:51 | 显示全部楼层
dddxhh 发表于 2015-5-19 21:48
这式子是f(m) = nf(m-1) + 1的形式,不算是等比数列。 矩阵快速幂吧

yes,  you are right.  矩阵快速幂的思路,应该和求X^N差不多吧
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-10 16:31:16 | 显示全部楼层
wangxinlei 发表于 2015-5-7 13:13
楼主,没太理解密码的题意啊。什么叫让这个序列最短啊?0000-9999不是一定有10000个数字么,那序列不是定 ...

同问楼主懂题目的意思。.鐣欏璁哄潧-涓浜-涓夊垎鍦
按照我的立即只要把密码当场一个整数,从0000 递增到9999就行, 不过好像太简单了应该是题目理解错了
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-10 16:49:46 | 显示全部楼层
第五轮第二题题意有点模糊,楼主能不能提供一个2*2的sample input and expected output?
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-11 14:26:09 | 显示全部楼层
请问楼主第一题路径要考虑从左child 到 parent 到 右child 这种情况吗。  谢谢~
回复 支持 反对

使用道具 举报

JimLuo 发表于 2015-6-12 02:03:36 | 显示全部楼层
感觉题目挺难得,多谢楼主分享
回复 支持 反对

使用道具 举报

Xin_walker 发表于 2015-6-20 06:40:59 | 显示全部楼层
volcano 发表于 2015-6-10 16:49
第五轮第二题题意有点模糊,楼主能不能提供一个2*2的sample input and expected output?

同求,顺求一维情况的思路。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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