一亩三分地论坛

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

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

google电面 题没见过,也没做出来

[复制链接] |试试Instant~ |关注本帖
xingrunzhi 发表于 2016-9-22 05:07:39 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
刚刚电面了g家,发个帖子攒攒人品,实在是不会了。我感觉基本上是fail了
PST时间1点约得电面,打电话来听是个中国人。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后问了问简历,介绍了一下自己。寒暄一下吧。
然后就上题。
. 1point3acres.com/bbs
Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32, find the maximum result of a[i] XOR a[j].

我说brute force肯定行,他说你不用写这个太简单了。接下来我就想,那异或XOR吗,你看最左边的位呗,然后就说你开32*N的数组,记他们BIT的信息。.1point3acres缃
接下来就说根据第一位分两大类呗,0一类,1一类。就问我那后面31位怎么办?
我想法是根据第二位分类,以此类推,最后做32个候选的union。结果想想不对,intersection也不对。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
最后我不知道怎么办了,服输了,问他,他说你在31位里面已经分好的0的大类里面,继续分1 分0,recursively做,可是我想了想那也不能出一个数啊,是两个数配对的啊
期间我也想是不是3维DP做。也没说,一直在这条路上走,也不对,我也不知道了。. 1point 3acres 璁哄潧
交流吧,我感觉题都不会,也没什么交流了。
lz到最后一行代码都没写,绝逼是没戏了。
发个帖子给自己攒点人品吧,小伙伴们谁会做,抬我一手。讲道理,我没见过这道题,也不会做,你们可以教教我。感谢了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

2

查看全部评分

本帖被以下淘专辑推荐:

clfhaha1234 发表于 2016-9-22 05:25:27 | 显示全部楼层
建一个trie tree,左节点是0,右节点是1,

建好之后O(N)判断每一个number,比如10101,就看根的左节点(0)存在否,有的话继续往下,再看下一个右节点(1)有没有,直到结束。因此时间复杂度在O(32*N),依然是O(N)的复杂度
回复 支持 7 反对 0

使用道具 举报

WhatsFLAG 发表于 2016-9-27 10:01:08 | 显示全部楼层
rexue70 发表于 2016-9-22 11:36
其实不对的,
考虑以下情况:-google 1point3acres.鏈枃鍘熷垱鑷1point3acres璁哄潧
100..000  (1,2)

我有一个新的立场,大神你帮我看看对不对,这个问题其实就是找互补的数字,那么最理想的状况就是0000...000 和 1111...111这种的,也就是说如果有两个数字的和 等于 1111...111这种的就一定是解了,那么我把所有数字排序以后,把问题转化为求 2 Sum clostest 并且只能小于或者等于 target这个问题来做,进而求解呢?
回复 支持 1 反对 0

使用道具 举报

muzac 发表于 2016-9-22 09:02:36 | 显示全部楼层
clfhaha1234 发表于 2016-9-22 05:25
建一个trie tree,左节点是0,右节点是1,
. 鍥磋鎴戜滑@1point 3 acres
建好之后O(N)判断每一个number,比如10101,就看根的左节点( ...

这破论坛我就服你
回复 支持 1 反对 0

使用道具 举报

GavinM 发表于 2016-9-22 12:19:01 | 显示全部楼层
应该差不多等于stackoverflow里面的思路,实现了一下。有些细节没有很注意。可以一起交流一下。主要思路就是recursive,应该类似O(32*n) = O(n)吧        .鏈枃鍘熷垱鑷1point3acres璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. From 1point 3acres bbs
public static int getLargestTwo(List<Integer> nums){
                List<Integer> sub_0 = new ArrayList<>();
                List<Integer> sub_1 = new ArrayList<>();
                int max = 0;
                for(int k : nums) max = Math.max(max, k);
. more info on 1point3acres.com                int prone = 1;
                while((prone << 1) <= max) prone = (prone << 1);
                for(int k : nums){
                        if((k & prone) != 0) sub_1.add(k);
                        else sub_0.add(k);
                }
                return getLargestTwoHelper(sub_0, sub_1, prone >> 1);
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public static int getLargestTwoHelper(List<Integer> nums_1, List<Integer> nums_2, int prone){
                if(nums_1.size() == 0 || nums_2.size() == 0) return 0;
                if(prone == 0) return nums_1.get(0) ^ nums_2.get(0);
                List<Integer> sub_10 = new ArrayList<>();
                List<Integer> sub_11 = new ArrayList<>();
                List<Integer> sub_20 = new ArrayList<>();. more info on 1point3acres.com
                List<Integer> sub_21 = new ArrayList<>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                for(int m : nums_1){
                        if((m & prone) != 0) sub_11.add(m);
                        else sub_10.add(m);
                }
                for(int m : nums_2){
                        if((m & prone) != 0) sub_21.add(m);
                        else sub_20.add(m);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
                if(sub_11.size() > 0 && sub_20.size() > 0 || sub_10.size() > 0 && sub_21.size() > 0){
                        return Math.max(getLargestTwoHelper(sub_21, sub_10, prone >> 1), getLargestTwoHelper(sub_11, sub_20, prone >> 1));
                }else return Math.max(getLargestTwoHelper(sub_20, sub_10, prone >> 1), getLargestTwoHelper(sub_11, sub_21, prone >> 1));
        }
回复 支持 1 反对 0

使用道具 举报

zyoppy008 发表于 2016-9-22 06:50:18 | 显示全部楼层
Easy 全部于第一个xor 然后get first and second largest to xor
回复 支持 0 反对 1

使用道具 举报

354886 发表于 2016-9-22 05:21:12 | 显示全部楼层
看一下这个:

http://stackoverflow.com/questions/9320109/two-elements-in-array-whose-xor-is-maximum
回复 支持 反对

使用道具 举报

 楼主| xingrunzhi 发表于 2016-9-22 05:28:17 | 显示全部楼层
clfhaha1234 发表于 2016-9-22 05:25
建一个trie tree,左节点是0,右节点是1,

建好之后O(N)判断每一个number,比如10101,就看根的左节点( ...
. visit 1point3acres.com for more.
服,你这个行
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 05:53:07 | 显示全部楼层
深度搜索0101010… 和101010… 最长的两个相乘不行吗?
. 1point 3acres 璁哄潧
补充内容 (2016-9-22 05:55):
. Waral 鍗氬鏈夋洿澶氭枃绔,相XOR说错了

补充内容 (2016-9-22 05:59):. 鍥磋鎴戜滑@1point 3 acres
甚至不需要搜索,所有数字直接跟01010101010101 和 1010101011010 进行xor 得到的结果 leading 1最长的两个进行XOR就好了吧
回复 支持 反对

使用道具 举报

rexue70 发表于 2016-9-22 06:04:18 | 显示全部楼层
WhatsFLAG 发表于 2016-9-22 05:53
深度搜索0101010… 和101010… 最长的两个相乘不行吗?

补充内容 (2016-9-22 05:55):
. 鍥磋鎴戜滑@1point 3 acres
能举个例子吗?为什么所有数字和010101xor呢?
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 06:06:59 | 显示全部楼层
rexue70 发表于 2016-9-22 06:04. Waral 鍗氬鏈夋洿澶氭枃绔,
能举个例子吗?为什么所有数字和010101xor呢?

通过这一步找到最长的 通过和 1010 ... 异或 结果为1的长度可以确定 0101...开头的数字有多长吧……
回复 支持 反对

使用道具 举报

rexue70 发表于 2016-9-22 06:22:06 | 显示全部楼层
WhatsFLAG 发表于 2016-9-22 06:06
通过这一步找到最长的 通过和 1010 ... 异或 结果为1的长度可以确定 0101...开头的数字有多长吧……

我跑了几个例子,感觉你是高手。。。。
厉害 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所有数字和101010xor,最长的那个n1
所有数字和010101xor,最长的那个n2
return n1 xor n2. visit 1point3acres.com for more.

补充内容 (2016-9-22 06:29):
需要top和second,如果两个最长的一样就取second
回复 支持 反对

使用道具 举报

deadline1314 发表于 2016-9-22 07:05:37 | 显示全部楼层
zyoppy008 发表于 2016-9-22 06:50
Easy 全部于第一个xor 然后get first and second largest to xor

感觉不太对,两个最大的数取XOR 不一定结果是最大的值吧
回复 支持 反对

使用道具 举报

tjcd 发表于 2016-9-22 07:23:04 来自手机 | 显示全部楼层
你那个分组方法是可以的,用recurrsion
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-22 07:28:41 | 显示全部楼层
deadline1314 发表于 2016-9-22 07:05.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉不太对,两个最大的数取XOR 不一定结果是最大的值吧

想错了。
回复 支持 反对

使用道具 举报

tjcd 发表于 2016-9-22 07:40:28 | 显示全部楼层
rexue70 发表于 2016-9-22 06:22
我跑了几个例子,感觉你是高手。。。。
厉害 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所有数字和101010xor,最长的那个n1
.鏈枃鍘熷垱鑷1point3acres璁哄潧
其实不对的,
考虑以下情况:
100..000  (1,2)
000..000  (1,1)
111..111  (1,1)
. from: 1point3acres.com/bbs
按照所说leading 1 最多的是 100...000 但是肉眼都能看出的答案中并不包含该数。
感觉像这种解法面试的时候基本可以忽略,哪怕是对的,你有信心跟面试官讲清楚么。。。
回复 支持 反对

使用道具 举报

kin332026 发表于 2016-9-22 08:00:38 | 显示全部楼层
clfhaha1234 发表于 2016-9-22 05:25
建一个trie tree,左节点是0,右节点是1,
.1point3acres缃
建好之后O(N)判断每一个number,比如10101,就看根的左节点( ...
. 1point3acres.com/bbs
试了下,可以的, 厉害。
回复 支持 反对

使用道具 举报

shuiguo 发表于 2016-9-22 08:20:31 | 显示全部楼层
记得这题以前在地里讨论过。。。。
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 09:41:13 | 显示全部楼层
tjcd 发表于 2016-9-22 07:40
. Waral 鍗氬鏈夋洿澶氭枃绔,其实不对的,
考虑以下情况:
100..000  (1,2)

那个方法的确有问题我默认了检查匹配,但也可能111和000匹配,如果我对所有数字建立一棵二叉树,找到第一个分叉以后镜像搜索,找最深处呢?大神你觉得这个方法可行吗?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-22 09:59:27 | 显示全部楼层
对每个数进行右移操作去看他最左的1的位置,然后维护两个指针,max,  secMax, 分别指向有最左1的数和第二左的1的数。这样做可以嘛? O(32 * N)
回复 支持 反对

使用道具 举报

tjcd 发表于 2016-9-22 10:17:46 | 显示全部楼层
WhatsFLAG 发表于 2016-9-22 09:41
那个方法的确有问题我默认了检查匹配,但也可能111和000匹配,如果我对所有数字建立一棵二叉树,找到第一 ...

大神谦虚了。解法是这个思路。我比较懒,比较倾向于直接用list做参数然后加recursion。 形成的 recursion tree是同样的结构, 空间开销可能稍微大一些但理论值也是O(n),不过代码应该比较短。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-22 10:25:03 | 显示全部楼层
原数组a (sort,并且去掉duplicate以后)取反得到数组b. visit 1point3acres.com for more.
然后a, b merge, 如果两个来自a和b的元素x, y在merged数组中相邻,就取x, y的同或。
结果是所有x, y同或众最大的。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

原理是0<=a < b < c,则 (a^(~c)) <= (b^(~c))

补充内容 (2016-9-22 10:31):
想复杂了。突然感觉用上面这个原理,sort完a以后two pointer扫一扫就完了...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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