我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

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

Google MTV面经

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

2016(1-3月) 码农类General 硕士 全职@Google - 猎头 - Onsite  | Other | fresh grad应届毕业生

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

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

x
  • 第一题:给两个长度相等的string,如果两个string对应位置的字母不相同记为一个distance,如果现在能够交换一次其中一个string中任意位置的两个char,返回能够将distance缩到最小的两个char的index(如果有多个最优解只返回一个);第二题:有3n个数围成一个环,取走其中一个的话会顺带去掉这个数相邻的两个数(这两个不计入总和),剩下的继续围成环,问取走n个数构成总和的最大值。
  • Android手机手势解锁的所有可能性(至少连接4个点,至多全部9个),需要考虑三点一线invalid的情况,如果考虑成1-9九宫格的话就是从1连到3这样的路径是不允许的。
  • Leetcode的serialize and deserialize binary tree的变形,不需要存每个node的value,只需要结构。
  • 第一题:超大文件按行去重,如果有多行内容是一样的,去除其中重复行只保留一行;第二题:实现一个size很小的hashtable(情景是:实际使用中用到的entry很少,如果正常hashtable会导致很大的overhead,所以需要设计一个这种情景下overhead很小的hashtable)


评分

3

查看全部评分


上一篇:Quora Data Science Intern Onsite
下一篇:lyft电面一题
我的人缘0
adiggo 发表于 2016-5-4 00:13:43 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一轮第二题有点像burst balloons.  
回复 支持 1 反对 0

使用道具 举报

我的人缘0
wtcupup 发表于 2016-2-24 11:34:10 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一轮第二题是数学题还是coding题?求思路
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-2-24 11:36:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wtcupup 发表于 2016-2-24 11:34.1point3acres网
第一轮第二题是数学题还是coding题?求思路

有点数学题的壳子,其实里面是套了一个house robber
回复 支持 反对

使用道具 举报

我的人缘0
kinggarden2001 发表于 2016-2-24 13:25:34 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问环路这个题是不是从任意点开始算都行?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-2-24 23:31:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
kinggarden2001 发表于 2016-2-24 13:25
请问环路这个题是不是从任意点开始算都行?

嗯,我觉得是,但是给的环是以数组呈现的,只是收尾认为他们是链接的,所以从第0个开始算比较方便吧

补充内容 (2016-2-25 02:54):
*首尾
回复 支持 反对

使用道具 举报

我的人缘0
hzyslddm 发表于 2016-2-26 06:39:20 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bihuang0910 发表于 2016-2-24 11:36
有点数学题的壳子,其实里面是套了一个house robber

感觉还是跟house robber不太一样,求LZ谈谈具体思路,有点想不明白T T
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-2-27 11:13:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
hzyslddm 发表于 2016-2-26 06:39
感觉还是跟house robber不太一样,求LZ谈谈具体思路,有点想不明白T T

其实我也没分析清楚,可以这样想:如果给你一个solution,怎么判断是valid的,结论是只要没有两个相邻的,就一定有办法取得到。那么问题就变成了,有3n个房子,从中选取n个,其中不能有相邻的房子,是不是就比较像house robber了

评分

1

查看全部评分

Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
bobzhang2004 发表于 2016-2-28 02:42:22 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bihuang0910 发表于 2016-2-27 11:13
其实我也没分析清楚,可以这样想:如果给你一个solution,怎么判断是valid的,结论是只要没有两个相邻的 ...

这个确实和house robber II有点像,应该是dp吧,还得用一维记录取了几个吧

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
hzyslddm 发表于 2016-2-28 09:31:57 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bihuang0910 发表于 2016-2-27 11:13
其实我也没分析清楚,可以这样想:如果给你一个solution,怎么判断是valid的,结论是只要没有两个相邻的 ...

谢谢LZ点拨!
列了一下DP的方程,maxValue[j]表示数组里下标从i到j的数组成的环里(i,j相邻,不能同时取)能取到的最大值,那么可以分为取i,取i+1,取j,取j-1,四种情况,化成一个长度-3的子问题
. 留学申请论坛-一亩三分地maxValue[j] = Max(maxValue[i+3][j] + nums[i+1],
                                maxValue[i+1][j-2] + nums[j],
                                maxValue[i+2][j-1] + nums,
                                maxValue[j-3] + nums[j-1],
                               )

代码如下:
        public static void main(String args[]) {
                int[] nums = {1,7,4,5,6,2,9,3,8};
                System.out.println(maxValueRemovingNumFromCycle(nums));
        }
        public static int maxValueRemovingNumFromCycle(int[] nums) {
                if(nums == null || nums.length == 0 || nums.length%3 != 0)
                        return 0;
                int[][] maxValue = new int[nums.length][nums.length];
                for(int i = 0; i+2 < nums.length; i+= 1) {
                        maxValue[i+2] = Math.max(nums, Math.max(nums[i+1],nums[i+2]));
                }
                for(int end = 5; end < nums.length; end+= 3) {. 1point 3acres 论坛
                        for(int i = 0; i+end < nums.length ; i++) {-google 1point3acres
                                maxValue[i+end] = Math.max(maxValue[i+3][i+end] + nums[i+1],Math.max(maxValue[i+1][i+end-2] + nums[i+end], Math.max(maxValue[i+2][i+end-1] + nums,maxValue[i+end-3] + nums[i+end-1])));
                        }
                }
                return maxValue[0][nums.length-1];
        }. 留学申请论坛-一亩三分地

补充内容 (2016-2-28 09:56):
好像还是不对的说。。反例 6 2 9 3 8 1 7 4 5
回复 支持 反对

使用道具 举报

我的人缘0
pocketlion 发表于 2016-2-28 13:43:14 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题大家想到的最优解是怎样的呀?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-2-29 03:54:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
pocketlion 发表于 2016-2-28 13:43. 牛人云集,一亩三分地
第一题大家想到的最优解是怎样的呀?
来源一亩.三分地论坛.
我用了一个hashtable中套hashtable的方式,外层用需要的char作为key,里层hashtable作为value;里层hashtable用待换的char作为key,待换的char所在的index作为value。O(n)的时间复杂度,O(n)空间复杂度
回复 支持 反对

使用道具 举报

我的人缘0
bobzhang2004 发表于 2016-3-4 03:06:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问“实现一个size很小的hashtable”就是自己用array实现一个hashmap吗?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-3-4 12:51:36 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bobzhang2004 发表于 2016-3-4 03:06
请问“实现一个size很小的hashtable”就是自己用array实现一个hashmap吗?

是的,不过重点考量是如何避免hash带来的overhead
回复 支持 反对

使用道具 举报

我的人缘0
ninacc 发表于 2016-3-4 13:31:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问楼主面完多久送了 HC啊
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-3-4 13:48:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
ninacc 发表于 2016-3-4 13:31
请问楼主面完多久送了 HC啊

我是周五面的,第二周周五送的HC
回复 支持 反对

使用道具 举报

我的人缘0
kinggarden2001 发表于 2016-3-4 13:53:23 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bihuang0910 发表于 2016-2-29 03:54
我用了一个hashtable中套hashtable的方式,外层用需要的char作为key,里层hashtable作为value;里层hasht ...

Dictionary<Tuple<char,char>, int> 这样似乎更简单。
回复 支持 反对

使用道具 举报

我的人缘0
ninacc 发表于 2016-3-4 15:42:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bihuang0910 发表于 2016-3-4 00:48
我是周五面的,第二周周五送的HC
. 一亩-三分-地,独家发布
谢谢!祝楼主好运!!!
回复 支持 反对

使用道具 举报

我的人缘0
bobzhang2004 发表于 2016-3-4 17:13:04 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bihuang0910 发表于 2016-3-4 12:51
是的,不过重点考量是如何避免hash带来的overhead

请问是怎么避免呢?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| bihuang0910 发表于 2016-3-5 06:29:20 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bobzhang2004 发表于 2016-3-4 17:13
请问是怎么避免呢?

不hash,直接iterate array来一一比较,因为他只要求存很少的内容(最多3个),所以iterate比用hash效率更高
回复 支持 反对

使用道具 举报

我的人缘0
陈润鹏 发表于 2016-5-3 23:32:58 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题第二问 的方程 是不是 dp[i][j] = max(dp[i][k-1]+nums[k]+dp[k+1][j])  i<=k<=j 把n阔成2n
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-28 04:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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