一亩三分地论坛

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

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

Google MTV面经

[复制链接] |试试Instant~ |关注本帖
bihuang0910 发表于 2016-2-24 11:15:13 | 显示全部楼层 |阅读模式

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

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

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

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). 1point3acres.com/bbs

. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

3

查看全部评分

adiggo 发表于 2016-5-4 00:13:43 | 显示全部楼层
第一轮第二题有点像burst balloons.  
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-2-24 11:34:10 | 显示全部楼层
第一轮第二题是数学题还是coding题?求思路
回复 支持 反对

使用道具 举报

 楼主| bihuang0910 发表于 2016-2-24 11:36:32 | 显示全部楼层
wtcupup 发表于 2016-2-24 11:34
第一轮第二题是数学题还是coding题?求思路

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

使用道具 举报

kinggarden2001 发表于 2016-2-24 13:25:34 | 显示全部楼层
请问环路这个题是不是从任意点开始算都行?
回复 支持 反对

使用道具 举报

 楼主| bihuang0910 发表于 2016-2-24 23:31:53 | 显示全部楼层
kinggarden2001 发表于 2016-2-24 13:25
请问环路这个题是不是从任意点开始算都行?

嗯,我觉得是,但是给的环是以数组呈现的,只是收尾认为他们是链接的,所以从第0个开始算比较方便吧
-google 1point3acres
补充内容 (2016-2-25 02:54):
*首尾
回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-2-26 06:39:20 | 显示全部楼层
bihuang0910 发表于 2016-2-24 11:36
有点数学题的壳子,其实里面是套了一个house robber

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

使用道具 举报

 楼主| bihuang0910 发表于 2016-2-27 11:13:49 | 显示全部楼层
hzyslddm 发表于 2016-2-26 06:39
感觉还是跟house robber不太一样,求LZ谈谈具体思路,有点想不明白T T

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-28 02:42:22 | 显示全部楼层
bihuang0910 发表于 2016-2-27 11:13
其实我也没分析清楚,可以这样想:如果给你一个solution,怎么判断是valid的,结论是只要没有两个相邻的 ...

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-2-28 09:31:57 | 显示全部楼层
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));
        }-google 1point3acres
        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];-google 1point3acres
                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) {
                        for(int i = 0; i+end < nums.length ; i++) {
                                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])));. visit 1point3acres.com for more.
                        }
                }
                return maxValue[0][nums.length-1];
        }

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

使用道具 举报

pocketlion 发表于 2016-2-28 13:43:14 | 显示全部楼层
第一题大家想到的最优解是怎样的呀?
回复 支持 反对

使用道具 举报

 楼主| bihuang0910 发表于 2016-2-29 03:54:17 | 显示全部楼层
pocketlion 发表于 2016-2-28 13:43
第一题大家想到的最优解是怎样的呀?

我用了一个hashtable中套hashtable的方式,外层用需要的char作为key,里层hashtable作为value;里层hashtable用待换的char作为key,待换的char所在的index作为value。O(n)的时间复杂度,O(n)空间复杂度
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-4 03:06:18 | 显示全部楼层
请问“实现一个size很小的hashtable”就是自己用array实现一个hashmap吗?
回复 支持 反对

使用道具 举报

 楼主| bihuang0910 发表于 2016-3-4 12:51:36 | 显示全部楼层
bobzhang2004 发表于 2016-3-4 03:06
请问“实现一个size很小的hashtable”就是自己用array实现一个hashmap吗?
. 1point 3acres 璁哄潧
是的,不过重点考量是如何避免hash带来的overhead
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-3-4 13:31:17 | 显示全部楼层
请问楼主面完多久送了 HC啊
回复 支持 反对

使用道具 举报

 楼主| bihuang0910 发表于 2016-3-4 13:48:18 | 显示全部楼层
ninacc 发表于 2016-3-4 13:31
请问楼主面完多久送了 HC啊

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

使用道具 举报

kinggarden2001 发表于 2016-3-4 13:53:23 | 显示全部楼层
bihuang0910 发表于 2016-2-29 03:54
我用了一个hashtable中套hashtable的方式,外层用需要的char作为key,里层hashtable作为value;里层hasht ...

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

使用道具 举报

ninacc 发表于 2016-3-4 15:42:35 | 显示全部楼层
bihuang0910 发表于 2016-3-4 00:48
我是周五面的,第二周周五送的HC
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
谢谢!祝楼主好运!!!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-4 17:13:04 | 显示全部楼层
bihuang0910 发表于 2016-3-4 12:51
是的,不过重点考量是如何避免hash带来的overhead

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

使用道具 举报

 楼主| bihuang0910 发表于 2016-3-5 06:29:20 | 显示全部楼层
bobzhang2004 发表于 2016-3-4 17:13. from: 1point3acres.com/bbs
请问是怎么避免呢?

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

使用道具 举报

陈润鹏 发表于 2016-5-3 23:32:58 | 显示全部楼层
第一题第二问 的方程 是不是 dp[i][j] = max(dp[i][k-1]+nums[k]+dp[k+1][j])  i<=k<=j 把n阔成2n
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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