来讨教个面试题# JobHunting - 待字闺中
l*r
1 楼
有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
(i,j,k) 满足条件A[i]+B[j]+c[k]=1000
这个改怎么做最优？
(i,j,k) 满足条件A[i]+B[j]+c[k]=1000
这个改怎么做最优？
d*b
2 楼
1000太小，1T太大，所以只要 有三组 1000个桶。然后计数，剩下的就是排列组合问题
了。
了。
l*r
3 楼
A,B也外排一下
然后binary search？
【在 d******b 的大作中提到】
: 1000太小，1T太大，所以只要 有三组 1000个桶。然后计数，剩下的就是排列组合问题
: 了。
然后binary search？
【在 d******b 的大作中提到】
: 1000太小，1T太大，所以只要 有三组 1000个桶。然后计数，剩下的就是排列组合问题
: 了。
o*r
4 楼
1T的数字？我觉得可以先去一下重复的，去重复的时候顺便桶排序一下变成一个数出现
多少次。之后要处理的
就很少了。
【在 l*********r 的大作中提到】
: 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
: (i,j,k) 满足条件A[i]+B[j]+c[k]=1000
: 这个改怎么做最优？
多少次。之后要处理的
就很少了。
【在 l*********r 的大作中提到】
: 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
: (i,j,k) 满足条件A[i]+B[j]+c[k]=1000
: 这个改怎么做最优？
z*n
5 楼
条件太少了，数据类型是什么？short，integer， long（long）， 这个不同，方法自
然不同。
然不同。
l*r
6 楼
都是int类型
【在 z*********n 的大作中提到】
: 条件太少了，数据类型是什么？short，integer， long（long）， 这个不同，方法自
: 然不同。
【在 z*********n 的大作中提到】
: 条件太少了，数据类型是什么？short，integer， long（long）， 这个不同，方法自
: 然不同。
p*r
7 楼
这就是个3sum题，
你不用管它大不大，多少T
既然没排序，扫描一遍是跑不掉的。
优化方面可以考虑的是：
#1 先扫描一遍：把的值先排除
#2 去重
然后排序
【在 l*********r 的大作中提到】
: 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
: (i,j,k) 满足条件A[i]+B[j]+c[k]=1000
: 这个改怎么做最优？
你不用管它大不大，多少T
既然没排序，扫描一遍是跑不掉的。
优化方面可以考虑的是：
#1 先扫描一遍：把的值先排除
#2 去重
然后排序
【在 l*********r 的大作中提到】
: 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
: (i,j,k) 满足条件A[i]+B[j]+c[k]=1000
: 这个改怎么做最优？
z*n
8 楼
int32？
那简单了，不用排序，直接建个表查表就行了，也就1G额外空间--处理3T数据，开了1G
空间，怎么说都不过份吧？
int32也就只能表示4G个unique的数，一个数据集直接开4G bit（500M bytes）的空间
，扫一遍，用第i bit表示i+INT_MIN这个int在数据集中存在与否。也就是用500M空间
表示了1T数据，而且还能O（1）时间查询一个整数存在与否。
懒得继续码字了，这个字典都给建好了，剩下的该怎么做应该不用多废话了吧。
【在 l*********r 的大作中提到】
: 都是int类型
l*r
9 楼
double 咋整？
1G
【在 z*********n 的大作中提到】
:
: int32？
: 那简单了，不用排序，直接建个表查表就行了，也就1G额外空间--处理3T数据，开了1G
: 空间，怎么说都不过份吧？
: int32也就只能表示4G个unique的数，一个数据集直接开4G bit（500M bytes）的空间
: ，扫一遍，用第i bit表示i+INT_MIN这个int在数据集中存在与否。也就是用500M空间
: 表示了1T数据，而且还能O（1）时间查询一个整数存在与否。
: 懒得继续码字了，这个字典都给建好了，剩下的该怎么做应该不用多废话了吧。
1G
【在 z*********n 的大作中提到】
:
: int32？
: 那简单了，不用排序，直接建个表查表就行了，也就1G额外空间--处理3T数据，开了1G
: 空间，怎么说都不过份吧？
: int32也就只能表示4G个unique的数，一个数据集直接开4G bit（500M bytes）的空间
: ，扫一遍，用第i bit表示i+INT_MIN这个int在数据集中存在与否。也就是用500M空间
: 表示了1T数据，而且还能O（1）时间查询一个整数存在与否。
: 懒得继续码字了，这个字典都给建好了，剩下的该怎么做应该不用多废话了吧。
z*n
10 楼
我是不是提前先问你这是啥数据类型了？
是不是说了不同类型手法不一样。
然后你告诉我是int
我码了七行字解了后你啥别的不说只回仨字“double咋整”？
自己琢磨吧。
【在 l*********r 的大作中提到】
: double 咋整？
:
: 1G
H*5
11 楼
非double和double难度完全不是一个数量级，可以另外开一贴
: double 咋整？
: 1G
【在 l*********r 的大作中提到】
: double 咋整？
:
: 1G
: double 咋整？
: 1G
【在 l*********r 的大作中提到】
: double 咋整？
:
: 1G
c*t
12 楼
bitmap怎么处理重复数据？
1G
【在 z*********n 的大作中提到】
:
: 我是不是提前先问你这是啥数据类型了？
: 是不是说了不同类型手法不一样。
: 然后你告诉我是int
: 我码了七行字解了后你啥别的不说只回仨字“double咋整”？
: 自己琢磨吧。
1G
【在 z*********n 的大作中提到】
:
: 我是不是提前先问你这是啥数据类型了？
: 是不是说了不同类型手法不一样。
: 然后你告诉我是int
: 我码了七行字解了后你啥别的不说只回仨字“double咋整”？
: 自己琢磨吧。
z*n
13 楼
天然去重啊？还需要如何处理。
【在 c********t 的大作中提到】
: bitmap怎么处理重复数据？
:
: 1G
l*r
14 楼
大牛，失礼失礼...
还在消化你的解法。。。
【在 z*********n 的大作中提到】
:
: 天然去重啊？还需要如何处理。
还在消化你的解法。。。
【在 z*********n 的大作中提到】
:
: 天然去重啊？还需要如何处理。
c*t
15 楼
题目要求找出所有的(i,j,k) 满足条件A[i]+B[j]+c[k]=1000
【在 z*********n 的大作中提到】
:
: 天然去重啊？还需要如何处理。
【在 z*********n 的大作中提到】
:
: 天然去重啊？还需要如何处理。
相关阅读
求trick 面试题FORD的这个邮件代表offer吗？请问一下大家对MapR这家公司怎么看？强势预测G今年崩盘，步L后尘腰斩L家的CEO真是蠢到极点了硅谷烙印要改革H1B啦。。。 (转载)停招华男new grad，工作AA新阶段 (转载)请问下失业救济可以领几次？palantir現在怎么样？有了解的么分享新开发的一个app，招募合伙（推广/技术）请问我怎么知道Coursera的课是收费的还是免费的？tnnd， 这个版还有人管么？！onetimeshoes号召大家入伍的如何查一个雇主是否支持过h1b?本版需要一个能引导正常话题交流的板斧OPT期间可以被美国总公司派遣海外吗？F1-H1-F1 和以后再H1 好纠结~ 求助先拿OPT工作再回学校答辩的问题the low status of workers and the servant mentality求助h1b transfer跟layoff