要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 16917|回复: 74
收起左侧

Google 4月27 Onsite

  [复制链接] |试试Instant~ |关注本帖
我的人缘0
baudelaire 发表于 2015-5-2 17:26:56 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

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

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


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

评分

10

查看全部评分


上一篇:Shopkick onsite面经
下一篇:【求助】求教POCKET GEMS必考题【成就系统设计】

本帖被以下淘专辑推荐:

我的人缘0
LYJALEX__ 发表于 2016-1-12 05:24:07 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
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;
                        for(;i<=9;i++){
                                if (!visited.contains(next+i)) break;
                        }. from: 1point3acres
                        visited.add(next+i);
                        start = next+i;. 围观我们@1point 3 acres
                        result+=i;
                }
                return result;
               
        }

回复 支持 6 反对 0

使用道具 举报

我的人缘0
aiwojiujiu 发表于 2016-1-15 07:47:27 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
umd2011 发表于 2016-1-15 07:38
大神, 都DP的状态转移方程!想不起来怎么优化啊,被自己的蠢下晕了。

        public static int getTotalDistance(int m, int n) {
. 牛人云集,一亩三分地                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;. 1point 3acres 论坛
                }
               
                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论坛
                }
                return result;.1point3acres网
        }
回复 支持 2 反对 2

使用道具 举报

我的人缘0
ijk5554234 发表于 2015-7-21 04:18:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
那个密码的题自己用了hashset把所有访问过的数字全部存下来,贴一下自己的代码 最后string的长度是10003, 说明没有重复
        public static String getPass(HashSet<Integer> visit) {
                int num = 9999;.1point3acres网
                int count = 0;
                StringBuilder sb = new StringBuilder("999");
                while (visit.size() < 10000) {
                        sb.append(num % 10);. 1point 3acres 论坛
                        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) {.留学论坛-一亩-三分地
                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();
                        }
                        if (s.indexOf(num) == -1) {. more info on 1point3acres
                                System.out.println("false");. visit 1point3acres for more.
                        }
                }       
        }
回复 支持 2 反对 1

使用道具 举报

我的人缘0
averillzheng 发表于 2015-5-3 07:11:52 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
能分享一下密码的那题的code 吗?贪心怎么搞。 这个问题是一个npc问题。而且应该是求一个Hamiltonian cycle的问题。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
houqingniao 发表于 2015-5-3 00:03:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感觉题目都不好答呢
lz很好了
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| baudelaire 发表于 2015-5-3 15:58:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2015-5-3 07:11
能分享一下密码的那题的code 吗?贪心怎么搞。 这个问题是一个npc问题。而且应该是求一个Hamiltonian cycle ...

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

使用道具 举报

我的人缘0
owenwilder 发表于 2015-5-4 09:23:46 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
看来谷歌也是有时候难有时候简单,楼主要是一个月前面很可能就过了。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2015-5-4 10:12:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
baudelaire 发表于 2015-5-3 15:58
其实我觉得贪心可以出最优解,因为所有数字是等价的。具体方法是从0000开始维护一个窗口变量,开始设为3 ...

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

使用道具 举报

我的人缘0
 楼主| baudelaire 发表于 2015-5-4 16:15:54 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
owenwilder 发表于 2015-5-4 09:23
看来谷歌也是有时候难有时候简单,楼主要是一个月前面很可能就过了。

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

使用道具 举报

我的人缘0
 楼主| baudelaire 发表于 2015-5-4 16:17:58 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2015-5-4 10:12
这不是贪心,是DFS方法。这个题的主要问题是你要能说清楚这样做下去能够得到所有的4位数字组成的密码。

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

使用道具 举报

我的人缘0
averillzheng 发表于 2015-5-4 23:37:56 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
baudelaire 发表于 2015-5-4 16:17
能具体说一下你的思路吗? 我给的方法里边如果窗口size为0的话肯定能枚举出下一个没用过的code,所以1000 ...
. 围观我们@1point 3 acres
我是把这个题想成了一个图的问题。然后可以用dfs放来做遍历图。但是我不能证明dfs遍历的过程中,每个点只被走过一次。
回复 支持 反对

使用道具 举报

我的人缘0
wangxinlei 发表于 2015-5-7 13:13:42 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
baudelaire 发表于 2015-5-3 15:58
其实我觉得贪心可以出最优解,因为所有数字是等价的。具体方法是从0000开始维护一个窗口变量,开始设为3 ...
.留学论坛-一亩-三分地
楼主,没太理解密码的题意啊。什么叫让这个序列最短啊?0000-9999不是一定有10000个数字么,那序列不是定长么(10000)?还请楼主指教下啊
回复 支持 反对

使用道具 举报

我的人缘0
magicalcan 发表于 2015-5-19 16:28:38 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第五轮第一个sum n^i怎么logn啊
回复 支持 反对

使用道具 举报

我的人缘0
mkcing 发表于 2015-5-19 21:14:12 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
magicalcan 发表于 2015-5-19 16:28. Waral 博客有更多文章,
第五轮第一个sum n^i怎么logn啊
来源一亩.三分地论坛.
刚才那个描述把我吓到了,其实是一个等比数列,等比数列有求和公式,当时需要算 x^N,   如果直接N个X相乘就是O(N),  但是这个没必要,比如 2^4 = (2^2) ^2
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
mkcing 发表于 2015-5-19 21:56:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
dddxhh 发表于 2015-5-19 21:48 来源一亩.三分地论坛.
这式子是f(m) = nf(m-1) + 1的形式,不算是等比数列。 矩阵快速幂吧

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

使用道具 举报

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

同问楼主懂题目的意思。. 1point 3acres 论坛
按照我的立即只要把密码当场一个整数,从0000 递增到9999就行, 不过好像太简单了应该是题目理解错了
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
milanelllo13 发表于 2015-6-11 14:26:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问楼主第一题路径要考虑从左child 到 parent 到 右child 这种情况吗。  谢谢~
回复 支持 反对

使用道具 举报

我的人缘0
JimLuo 发表于 2015-6-12 02:03:36 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感觉题目挺难得,多谢楼主分享
回复 支持 反对

使用道具 举报

我的人缘0
Xin_walker 发表于 2015-6-20 06:40:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
volcano 发表于 2015-6-10 16:49
第五轮第二题题意有点模糊,楼主能不能提供一个2*2的sample input and expected output?

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 18:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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