一亩三分地论坛

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

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

Google MTV 4/14 面经

[复制链接] |试试Instant~ |关注本帖
xuepanchen 发表于 2015-4-20 03:59:44 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
这周二在MTV面的,直接上面经

第一轮,印度哥哥

1. 给你一排栅栏,有N个,你要给它们上色。你有黑白两种颜色,颜色相同的栅栏最多只能两块连在一起,问你一共有多少种上色的方法。用DP做了,问了下复杂度什么的,做到常数的空间复杂度。
2. Leetcode原题,BEST TIME TO BUY AND SELL STOCK。分别问了一次,两次,还有N次,还问我有没有做过。我说三个都做过,然后简单给了思路。最后说N次的时候自己把思路记错了,两行代码的顺序搞反了,面试官发现了说逻辑有问题,我自己也一时没反应过来,还坚持说是对的。。。面试官也不知道要怎么改,就说这个一下子也理不清。
3. 最后还有5分钟,面试官说我们还能做点什么呢。我心想,不应该就是我的提问时间了嘛。。。结果又出了一道题。给你一个字典,里面全是由0和1组成的字符串,比如{1,1110,10001,01,001,1001,101,10,00}。然后给你M个0和N个1,问你最多可以找出几个字典里面的字符串,使得这些字符串里面一共有M个0和N个1。比如给你2个0,3个1,就返回{1,01,10}。给你5个0,5个1,就返回{1,01,101,10,00}。
理解这道题就花了5分钟,我一开始以为是问你可以用给你的0和1组成哪些字典里的字符,也就是每个字符串都可以用给你的这么多。正确理解后我说第一个想到的是贪心,但估计贪心不对,所以用DFS做,就从最短的开始往下搜。这个时候时间也超了,最后小哥走的时候说应该DP做,我说恩我知道了,但DFS肯定也行吧,小哥也没说什么。

第二轮,白人叔叔
. from: 1point3acres.com/bbs
1. 问了简历上的project。问了什么是deadlock,怎么解决deadlock。
2.先告诉我背景知识,图像中很多显示的都是近似。比如显示的一个圆并不是一个完美的圆,当你放大会发现都是相邻的像素点近似而成的。然后先让我开一个数组代表一个图片,里面数据的范围是0到255(黑是0,白是255),应该用什么数据类型。我没反应过来,面试官就说应该用unsigned char,我说哦。然后给了我一个函数,VOID PAINT(INT X, INT Y),这个函数就是将图面中坐标为(X,Y)的方格涂黑(0)。要我设计一个函数 VOID PAINT(FLOAT X, FLOAT Y)。因为给你的两个坐标不是整数,所以相当于会覆盖到相邻的四块方格,然后每个方格按照被覆盖的面积,涂上对应比例的灰度。比如某个方格被覆盖了一半的面积,那这个方块就是涂成灰色(127)。也就是模拟一下图像里面近似的做法。
我不知道出这道题的目的是什么。。。测试我数据类型之间的转换?考我数学功底?代码就是最简单的那种,写完貌似面试官觉得还行。

第三轮,欧洲哥哥

1. 给你一个文档,里面存的都是一个个文件的绝对路径,和这个文件的拥有者。比如“/FOO/CHH/1.TXT,LINDA”,“/FOO/CHH/2.TXT,PETER”,“/FOO/3.TXT,LINDA”。然后给你一个路径,找出这个路径下以及所有的子目录下哪个人的文件最多。比如给你“/FOO/SHH”那LINDA和PETER一样多,给你“/FOO”那就是LINDA多。
我就用TRIE的方法做了,每个节点除了存接下去的节点的MAP外,还要存到当前路径为止的每个用户的文件数。查询的时候就是把给你的路径走完,在最后的节点过一遍所有的用户看哪个人的文件最多。
写完有一点小BUG,指出了就改掉了,然后讨论时间复杂度。说如果有F个文档,每个文档平均有E个条目,然后假设最后树的高度是H,一共有P个用户,那建树的时间复杂度是多少,查询的复杂度多少。我说建树的复杂度就是F*E*H吧,小哥说并不是每次都要访问到整棵树的高度,我说给的不都是worst case下的复杂度的嘛,小哥说哦这样啊。然后查询的复杂度我说就是H,小哥说再想想,我说哦应该是H+P,因为到了最后一个点要把这个点所有用户都遍历一遍。这轮就结束了。

第四轮,白人叔叔

1. 给你一个排序好的整数数组,让你在里面找四个数(每个数可以重复用)使得它们的和等于给定你的值V。其实这道题就是用HASHTABLE的N^2复杂度的做法,不难。我一看是排序好的,第一个想到的就是从两头夹逼的做法,就说把V分成两部分,一个是M,一个是V-M,然后每部分看看能不能等于两个值之和。之后在面试官的一步步提示下才想起来用HASHTABLE就好了。讨论了复杂度什么的。
2. CRACKING THE CODE INTERVIEW 13.9, WRITE AN ALIGNED MALLOC AND FREE FUNCTION。我和面试官说这道题是书上原题,大叔说哦这样啊,那我们换一道。
3. 问你怎么保存一颗二叉树。我说存一个INORDER,再存一个PREORDER或者POSTORDER。大叔说只能存一个,我说那就把树看作是FULL TREE,缺少的子树就存一个特殊符号标记一下,这样的话只需要存一个INORDER就行了,大叔说行了。

感觉自己运气挺好的,题目都算简单的,上午两轮面的一般,下午两轮好一点,有几个可以发挥的再好一点的地方。ANYWAY一直很感谢地里大家分享的面经,希望自己写的这些东西也能对大家有用。还是那句话,GOOGLE总的来说题目不难,但都要答的很好还是有些难度的。

最后,祝自己好运,也祝大家好运。求大家多给RP哈哈。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

7

查看全部评分

本帖被以下淘专辑推荐:

wild_ricky_0221 发表于 2015-4-21 08:34:39 | 显示全部楼层
public int solution(int n) {
                if(n <= 0)
                        return 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
               
                if(n == 1)
                        return 2;
               
                int lastTwoSame = 2; // till current n, # of methods with last two same, now n = 2
                int lastTwoDiff = 2; // till current n, # of methods with last two different, now n = 2;
               
                // if last two fences have the same color, you have 1 choice for current one, which lead to
                // new last two have different colors.
                // if last two fences have different color, you have two choice for current one, one will lead
                // to new last two have same colors, the other will lead to new last two have different colors.
                for(int i = 3; i <= n; i++)
                {
                        int temp = lastTwoSame;
                        lastTwoSame = lastTwoDiff;
                        lastTwoDiff = temp + lastTwoDiff;
                }
               
                return lastTwoSame + lastTwoDiff;
        }

楼主能帮忙看看我的第一题思路对吗?

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

hotIce 发表于 2015-4-26 12:10:33 | 显示全部楼层
celtspirit 发表于 2015-4-23 11:51
可以麻烦写一下转移方程么,想了好久。多谢啦

dp[m][n] represents the maximum number of string to choose for m zeros and n ones in [0...i - 1] subarray
assume ith element has x zeros and y ones
dp[m][n] = (m - x >0 && n - y > 0) ? max(dp[m][n][i - 1], dp[m - x][n - y][i - 1] + 1) : dp[m][n][i - 1];
dp[m][n][0] = 0;
. visit 1point3acres.com for more.
回复 支持 0 反对 1

使用道具 举报

yrcyq 发表于 2015-4-21 02:51:36 | 显示全部楼层
楼主能说下第一题怎么做吗?

回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-21 09:28:07 | 显示全部楼层
wild_ricky_0221 发表于 2015-4-21 08:34
public int solution(int n) {
                if(n
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你的做法赞!我当时用了四个变量分别存白白,白黑,黑白,黑黑哈哈。还是你的好,学习了
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-21 09:32:43 | 显示全部楼层
yrcyq 发表于 2015-4-21 02:51
楼主能说下第一题怎么做吗?

你可以看一下板凳同学写的解法,很棒。
我当时就是最直白的用了四个变量存了白白,白黑,黑白,黑黑这四种连续两块栅栏的上色可能。然后找当前栅栏上色的方法和前两块栅栏上色方法之间的联系
白白=黑白. from: 1point3acres.com/bbs
白黑=白白+黑白
黑白=黑黑+白黑
黑黑=白黑
最后把四种加起来就好了
回复 支持 反对

使用道具 举报

wild_ricky_0221 发表于 2015-4-21 10:19:57 | 显示全部楼层
xuepanchen 发表于 2015-4-21 09:28
你的做法赞!我当时用了四个变量分别存白白,白黑,黑白,黑黑哈哈。还是你的好,学习了

谢谢楼主, 碰巧想到了,祝楼主拿offer
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-21 10:40:34 | 显示全部楼层
第一轮第三题应该是个背包问题 可以用dp解
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-21 11:11:42 | 显示全部楼层
wild_ricky_0221 发表于 2015-4-21 10:19
谢谢楼主, 碰巧想到了,祝楼主拿offer

恩谢谢你,心里还是不太有底,祝自己好运吧
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-21 11:13:35 | 显示全部楼层
hotIce 发表于 2015-4-21 10:40
第一轮第三题应该是个背包问题 可以用dp解

恩你说得对,用DP解肯定没错。不过我还是觉得DFS也可以,而且复杂度也不差
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-21 11:57:23 | 显示全部楼层
xuepanchen 发表于 2015-4-21 11:13
恩你说得对,用DP解肯定没错。不过我还是觉得DFS也可以,而且复杂度也不差

三维dp O(num0 * num1 * sizeof(array)) .鏈枃鍘熷垱鑷1point3acres璁哄潧
dfs我感觉是exponential
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-21 23:09:08 | 显示全部楼层
hotIce 发表于 2015-4-21 11:57
三维dp O(num0 * num1 * sizeof(array))
dfs我感觉是exponential

dp 的复杂度还有再乘以最长字符串长度~
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-22 01:29:00 | 显示全部楼层
houqingniao 发表于 2015-4-21 23:09. 鍥磋鎴戜滑@1point 3 acres
dp 的复杂度还有再乘以最长字符串长度~
.鏈枃鍘熷垱鑷1point3acres璁哄潧
先预处理下字符串数组就行了 每个字符串数下有几个0和1除非有很长很长的字符串 否则不影响时间复杂度
回复 支持 反对

使用道具 举报

celtspirit 发表于 2015-4-23 11:51:08 | 显示全部楼层
hotIce 发表于 2015-4-22 01:29
先预处理下字符串数组就行了 每个字符串数下有几个0和1除非有很长很长的字符串 否则不影响时间复杂度

可以麻烦写一下转移方程么,想了好久。多谢啦
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-4-23 12:40:25 | 显示全部楼层
xuepanchen 发表于 2015-4-21 09:32
你可以看一下板凳同学写的解法,很棒。
我当时就是最直白的用了四个变量存了白白,白黑,黑白,黑黑这四 ...

这个题做成这样,就可以用矩阵乘法来做到logN了。
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-25 02:23:26 | 显示全部楼层
Linzertorte 发表于 2015-4-23 12:40
这个题做成这样,就可以用矩阵乘法来做到logN了。

能说一下怎么用矩阵乘法嘛嘻嘻
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-25 02:24:19 | 显示全部楼层
hotIce 发表于 2015-4-22 01:29
先预处理下字符串数组就行了 每个字符串数下有几个0和1除非有很长很长的字符串 否则不影响时间复杂度
. Waral 鍗氬鏈夋洿澶氭枃绔,
同求预处理完之后的转移方程
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-4-25 04:20:56 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 05:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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