一亩三分地论坛

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

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

Google 4月27 Onsite

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

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

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

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

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

第一轮:
多叉树,每个节点是一个整数,求书中最长递增路径比如5,6,7,8,9
看似简单其实有不少坑,感觉就是跪在这一轮了,所以后边面的反而很放松。。

第二轮:
四叉树压缩黑白图片,一个图片递归分成2x2四部分,如果一个区域颜色一样就设为叶子节点,算黑像素比例. 鍥磋鎴戜滑@1point 3 acres
follow up是给两个图片,把白色视为不透明,黑色视为透明,重叠在一起,返回一个图片,都用四叉树表示
这个递归不难,感觉做的不错,最后出了一个小bug,在他提示下改了

第三轮: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
一堆密码箱,每个密码都是四位0-9之间,算一个暴力破解序列,包含所有可能的四位序列,让这个序列尽量短
给了一个贪心算法,代码写的比较长,而且没bug free

中饭时间。。。

第四轮:. 鍥磋鎴戜滑@1point 3 acres
系统设计题,设计google map后端存储,这个面试官口音极重,交流无力,希望大牛指点一下google map后端是怎么做的,怎么scale?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第五轮:. Waral 鍗氬鏈夋洿澶氭枃绔,
最后一轮,求sum(n^i) 就是1+n+n2+n3+...+n^N, 快速写了一个O(N)之后让我优化,其实这个二分O(lgN)很容易想的,但是当时用了很长时间表现不太好。
第二题是个矩阵,每个节点是一个计算机,计算机之间传一个文件的cost是节点值x路径长度,选择所有计算机为接收端,求所有文件传输的cost
快速写了个暴力方法. From 1point 3acres bbs
尝试动态规划无果
后来想到可以cache所有行列的cost和,正这一边反着一遍,然后状态转移就是O(1)了,但是没时间写了,在他提议下写了一个一维特殊情况的代码,中间有个加号还忘了写,算是sloppy coding吧-google 1point3acres
希望大牛们指点一下这个题


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

评分

8

查看全部评分

本帖被以下淘专辑推荐:

LYJALEX__ 发表于 2016-1-12 05:24:07 | 显示全部楼层
public String sequenceGenerator(){
                int start = 9999;. 1point3acres.com/bbs
                String result = ""+start;. 鍥磋鎴戜滑@1point 3 acres
                Set<Integer> visited = new HashSet<>();
                visited.add(start);
                while(visited.size()<10000){
                        int next = start*10%10000;
                        int i=0;
                        for(;i<=9;i++){-google 1point3acres
                                if (!visited.contains(next+i)) break;
                        }
                        visited.add(next+i);
                        start = next+i;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        result+=i;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                return result;
               
        }

回复 支持 4 反对 0

使用道具 举报

aiwojiujiu 发表于 2016-1-15 07:47:27 | 显示全部楼层
umd2011 发表于 2016-1-15 07:38
大神, 都DP的状态转移方程!想不起来怎么优化啊,被自己的蠢下晕了。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
        public static int getTotalDistance(int m, int n) {.1point3acres缃
                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;
                        }
                }
                鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                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();.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }.1point3acres缃
                return result;
        }
回复 支持 1 反对 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)) {
                                        break;
                                }
                                add++;
                        }
                        num += (add % 10);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        count++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }
                System.out.println(count);
                return sb.toString();
        }

        public static void main(String[] args) {-google 1point3acres
                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();. more info on 1point3acres.com
                        }. from: 1point3acres.com/bbs
                        if (s.indexOf(num) == -1) {. more info on 1point3acres.com
                                System.out.println("false");
                        }
                }        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
回复 支持 1 反对 1

使用道具 举报

houqingniao 发表于 2015-5-3 00:03:03 | 显示全部楼层
感觉题目都不好答呢 .鐣欏璁哄潧-涓浜-涓夊垎鍦
lz很好了
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| baudelaire 发表于 2015-5-3 15:58:05 | 显示全部楼层
averillzheng 发表于 2015-5-3 07:11. from: 1point3acres.com/bbs
能分享一下密码的那题的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 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这不是贪心,是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
能具体说一下你的思路吗? 我给的方法里边如果窗口size为0的话肯定能枚举出下一个没用过的code,所以1000 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我是把这个题想成了一个图的问题。然后可以用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. 鍥磋鎴戜滑@1point 3 acres
第五轮第一个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. Waral 鍗氬鏈夋洿澶氭枃绔,
刚才那个描述把我吓到了,其实是一个等比数列,等比数列有求和公式,当时需要算 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个数字么,那序列不是定 ...

同问楼主懂题目的意思。-google 1point3acres
按照我的立即只要把密码当场一个整数,从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?

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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