一亩三分地论坛

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

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

G家电面面经 10/1 目测也悲剧了TT

[复制链接] |试试Instant~ |关注本帖
littlecoolblaxk 发表于 2014-10-2 02:24:39 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other

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

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

x
好想哭啊TT  整个脑袋一片空白 根本不会思考。。好想骂自己。。TT
全力以赴了好久就为了这个 挺一般的题但是脑子根本不转了 诶 不说了 上面筋 move on吧. visit 1point3acres.com for more.

美国小哥, 按时打来 然后寒暄几句直接上题。
1 输入: 乱序的byte collection , 输出:有序byte 除去dup  说白了就是排序和去重 然后数据结构我说输入输出可以用List么 他说可以 所以大概就是输入一个无序的 List<Byte> 输出一个有序的且无重复元素的 List<Byte>

2 给你一个有序数组 和一个X 让你返回数组里所有满足a + b <= X的 tuple。  follow up: 换成 a, b, c三元  满足 a+ b+ c <= X  大概的方法签名如下: int xxxxxx(int[] array, int X)
. more info on 1point3acres.com
还在准备面试的小伙伴先想想再看下边答案吧  最近刷题刷傻了 根本感觉自己丧失了思考能力。。。。。。这么简单的题都答那么差TT
\. 1point3acres.com/bbs
\
\
\
\
\. From 1point 3acres bbs
\
\
\
\
\
\
第一题 我大概知道byte是个小一点的整数 但是具体概念不是特确定 所以就挂在这儿了(我偷偷浏览器维基百科了byte 倒不是说byte定义挂了我 但是因为对byte不太确定 所以有点懵了 无法思考+思路受阻 主要还是自己太挫吧)然后搜到的结果是byte是8位的int 没多想就说用快排 然后小哥说byte有什么特别之处?。。。。。突然恍然大悟 byte可能的值非常少 所以可以用数组记下每个值出现过没有。。开写 总体写的还行 但是我觉得我给的答案不是他想要的。 我就是弄了个数组叫xx吧比如 记录。。比如输入数组里有4 我就xx[4]++ ...其实我想到了没有必要记录具体出现过几次 但是太紧张了竟然没说。 然后小哥就说 我要是输入了N多同一个数据你存不下咋办啊 我说。。对哦。。。其实我心里是觉得 输入无非3种情况 1 没出现过 2出现过1次 3出现过不止一次 因为要去除dup 我觉得三种状态不太好写 就索性直接数数了 结果最后小哥跟我说 用boolean。。隐约觉得他是忘了要去除duplication了么- - 但是。。我又犯傻×。没提这事儿。。。。总之 非常简单的这道题 我答成这样。。。。

第二题 心里总觉得跟2sum有关 就说了个hashset 后来我俩讨论了一下 决定不用多余空间 就在原数组上找。 看见有序数组第一反应是啥!!!!!!!!!!!!!!二分搜索对不对!!!!!我竟然没说!!!!!!这题没啥trick 就正常写就行了。。。但是 因为我没说binary search 所以就从头开始找 (内心对自己说一万句呵呵)。。后来勉强糊弄过关 又follow up 说要找仨数儿。脑子已经不在这了。。稀里糊涂说了一堆nonsense   后来勉勉强强写了个我自己都不知道是啥的算法 然后小哥带着我小优化了一下 (简单优化了一下 没提升复杂度)。。就算过去了 这时候已经45分钟不止了 然后小哥说 我还有最后一个问题 (当然不是挖掘机哪家强)。。。我心说 不是还有题吧(之前amazon 1小时面了4道题 45分钟了又给我出了道题。。所以有阴影)小哥说 回到这道题最开始 还能不能优化? 我突然获得了思考能力 我说 二分法啊!!!!!他说 嗯 这就是我要的答案 = =|||

然后就尴尬的结束了坑爹的面试- - (敲完这些字感觉不难么难受了 诶)
. from: 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point 3acres 璁哄潧



补充内容 (2014-10-2 02:26):
哦对 第二题返回tuple总数就行 不用返回所有可行的tuple.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2014-10-2 05:18):
有同学问那个二分法是怎么回事 是这样 尾指针要找到是能满足要求的最大值对不对 那么一般的思路是 一个一个扫描 之前3sum大概也是这么做的 所以就没多想 其实这点还有优化空间 写不下了 下一条写

补充内容 (2014-10-2 05:19):
假设我的a= 1 X =3  那么如果数组形如:{1,2,44,55,66,77,78,88,99,100,。。。。。} 岂不是要浪费很长时间从尾开始遍历 这里如果用二分法就能在logN时间找到‘2’ 就省时间啦~

补充内容 (2014-10-2 09:16):. From 1point 3acres bbs
仔细想了一下这题 第一问确实是o(N) 这里说到二分法可能只是想提高一下效率吧 感觉自己压根就没看明白题 就只想着急的跟面试官交流 结果又紧张又乱 一团糟

评分

4

查看全部评分

hakase 发表于 2014-10-2 04:56:47 | 显示全部楼层
mhbkb 发表于 2014-10-2 04:46
同问  第二题就是首尾指针找啊  求问在哪用到二分啊?

确定了一个数字array[smallerIndex]之后,另一个数字必然是等于 (targetNum - array[smallerIndex]). visit 1point3acres.com for more.
那么就变成了[smallerIndex + 1, array.length - 1]区间找这个数字的题目。
换句话说,就变成了二分查找+多少个重复数字的题。
算是leetcode上那两道题的结合吧。
回复 支持 2 反对 0

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-7 08:05:47 | 显示全部楼层
谢谢大家的鼓励 今天收到邮件 说愿意继续走 next steps! 应该算是过了吧 不知道是再安排电面还是onsite了 无论如何 是个好消息!!还没面的小伙伴们加油吧

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

rettyye3 发表于 2014-10-2 04:20:15 | 显示全部楼层
第二题难道不是 2sum(3sum)? 一个头指针 一个尾指针 遇到a+b<=X了, 所有(a, m), m<=b的都是... .鐣欏璁哄潧-涓浜-涓夊垎鍦
求问二分怎么做?
回复 支持 1 反对 0

使用道具 举报

nostal 发表于 2014-10-2 02:33:21 | 显示全部楼层
拍拍,不怕的,机会大大的有,加油
回复 支持 反对

使用道具 举报

熊笨笨 发表于 2014-10-2 03:37:01 | 显示全部楼层
说了他想要的答案就可以过了
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-2 03:50:22 | 显示全部楼层
我觉得第二题不是DFS吗?请问lz是具体怎么使用二分法的
回复 支持 反对

使用道具 举报

chaseqi 发表于 2014-10-2 04:22:45 | 显示全部楼层
patpat~ 楼主加油 拿到G家的电面很厉害了!
回复 支持 反对

使用道具 举报

wzf1943 发表于 2014-10-2 04:29:55 | 显示全部楼层
austurela 发表于 2014-10-1 13:50
我觉得第二题不是DFS吗?请问lz是具体怎么使用二分法的

就是 leetcode 2 Sum 3 Sum的变种
回复 支持 反对

使用道具 举报

mhbkb 发表于 2014-10-2 04:46:22 | 显示全部楼层
同问  第二题就是首尾指针找啊  求问在哪用到二分啊?
回复 支持 反对

使用道具 举报

hakase 发表于 2014-10-2 04:50:24 | 显示全部楼层
patpat,code interview的时候不要紧张,不要抢答。思考好,先写思路再实现。
回复 支持 反对

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-2 05:11:17 | 显示全部楼层
rettyye3 发表于 2014-10-2 04:20
第二题难道不是 2sum(3sum)? 一个头指针 一个尾指针 遇到a+b

就是尾指针那里 假设数组后半部分都是很大的数 这样一个一个找 很浪费时间 所以要用二分法找到最大的那个满足条件的数
回复 支持 反对

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-2 05:11:57 | 显示全部楼层
nostal 发表于 2014-10-2 02:33
拍拍,不怕的,机会大大的有,加油

谢谢哦!!我真的是个很panic+不乐观的人 所以心里还是挺打鼓的
回复 支持 反对

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-2 05:12:56 | 显示全部楼层
熊笨笨 发表于 2014-10-2 03:37
说了他想要的答案就可以过了

真的么 但愿但愿 主要整个过程磕磕绊绊 然后说了二分法以后他也没让再实现
回复 支持 反对

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-2 05:14:06 | 显示全部楼层
austurela 发表于 2014-10-2 03:50
我觉得第二题不是DFS吗?请问lz是具体怎么使用二分法的

DFS 那就n平方复杂度么? 二分可以变成nlogN复杂度 二分法思路我一会儿补充在原帖里吧
回复 支持 反对

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-2 05:14:55 | 显示全部楼层
chaseqi 发表于 2014-10-2 04:22
patpat~ 楼主加油 拿到G家的电面很厉害了!

谢谢- -找朋友内推的所以有面试 很多小公司投了几个月了都是石沉大海
回复 支持 反对

使用道具 举报

 楼主| littlecoolblaxk 发表于 2014-10-2 05:15:36 | 显示全部楼层
hakase 发表于 2014-10-2 04:50
patpat,code interview的时候不要紧张,不要抢答。思考好,先写思路再实现。

是的 我就是太紧张了 所以思路一下乱了- -
回复 支持 反对

使用道具 举报

rettyye3 发表于 2014-10-2 05:37:34 | 显示全部楼层
hakase 发表于 2014-10-2 04:56
确定了一个数字array[smallerIndex]之后,另一个数字必然是等于 (targetNum - array[smallerIndex])
那 ...

个人觉得没必要这么做吧... 比如你现在有一个数组1,2,3,4,5,6, target是1000000
也就是所有组合都是满足的, 按照你这样的算法是不是选下1, 然后二分找到6; 选2, 然后二分找到6 ...
这样复杂度是不是就变成O(nlogn)了?
回复 支持 反对

使用道具 举报

hakase 发表于 2014-10-2 06:26:23 | 显示全部楼层
rettyye3 发表于 2014-10-2 04:20. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题难道不是 2sum(3sum)? 一个头指针 一个尾指针 遇到a+b

第一个数字是线性的复杂度,查找其对应的第二个数字也是线性复杂度。
使用二分法的话可以加速第二个数字的查找。使其变成O(log n) (找到这个点之后,与这个数字相同的数字以及后面的数字都是满足要求的). 1point 3acres 璁哄潧
所以,使用最简单的做法时间复杂度是平方级,而结合二分法则是O(nlog n)。
略优于第一种解法。
回复 支持 反对

使用道具 举报

rettyye3 发表于 2014-10-2 06:44:18 | 显示全部楼层
hakase 发表于 2014-10-2 06:26
第一个数字是线性的复杂度,查找其对应的第二个数字也是线性复杂度。
使用二分法的话可以加速第二个数字 ...

第一种解法整个复杂度是O(n)啊 头尾指针向中间移动

第二种解法在像楼主所举的那个例子(target很小, 数组里面数都很大)时候效果会很好...
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2014-10-2 08:12:30 | 显示全部楼层
第二题二不二分没啥区别,要是问的是有多少个pair且数组里不会有相同元素的情况下才有nlogn的复杂度,要返回所有数字对的话你肯定得遍历一遍,复杂度还是会变成n2
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 17:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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