由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - amazon 电面问题 求解答, 在线等
相关主题
O(N) sort integer array这题怎么做?
Google电话面试题目Given an array of N integers from range [0, N] and one is missing. Find the missing number.
一道老题问道题,谁给个效率高点的解法
careercup上这道题我竟然没看懂菜鸟问个two sum的变型题
算法题:两列找共同元素有O(n)的算法吗?请教一道算法题
a[i] + b[j] = c[k] 的题有靠谱的答案不?请教个面试题
求这道题的O(N)解 (转载)问一道面试题目
[合集] Google电话面试题目Minimum number of moves to make an integer array balance
相关话题的讨论汇总
话题: arrays话题: ram话题: each话题: 电面话题: 解答
进入JobHunting版参与讨论
1 (共1页)
r*****9
发帖数: 75
1
There are two integer arrays ,each in very large files (size of each is
larger than RAM). How would you find the common elements in the arrays in
linear time.
s******y
发帖数: 936
2
参考 bucket sort。
l*********8
发帖数: 4642
3
把大文件按int value range分成若干小文件

【在 r*****9 的大作中提到】
: There are two integer arrays ,each in very large files (size of each is
: larger than RAM). How would you find the common elements in the arrays in
: linear time.

h*******0
发帖数: 270
4
好方法

【在 l*********8 的大作中提到】
: 把大文件按int value range分成若干小文件
m*****n
发帖数: 2152
5
这要看具体RAM多大,数组多大了。
可以用bit 代表数字,INT级的数字 2^32,只要~1GB的内存就能全hash。如果内存还不
足,可以分区读入。

【在 r*****9 的大作中提到】
: There are two integer arrays ,each in very large files (size of each is
: larger than RAM). How would you find the common elements in the arrays in
: linear time.

r****s
发帖数: 1025
6
option 1:
int array这个应该是比较明显的提示,用bitmap sort类似的方法。
用一个2^32长度的array,每个element保存一个1/2值(short),那么总共需要的内存是2
^32=1k*1k*1k*4=4g。开个6g的java process就可以了。
然后把两个file读一遍就可以了。
option 2:
如果内存不够,就把array分成几次,每次都读一遍file。这样的好处是避免写硬盘。
option 3;
先把file分成小文件,然后再读入。这样的问题是写硬盘。
这样解题比较balanced,不偏向任何一方。
1 (共1页)
进入JobHunting版参与讨论
相关主题
Minimum number of moves to make an integer array balance算法题:两列找共同元素有O(n)的算法吗?
问个最近面试里的题目a[i] + b[j] = c[k] 的题有靠谱的答案不?
google 面试题求这道题的O(N)解 (转载)
一道google题[合集] Google电话面试题目
O(N) sort integer array这题怎么做?
Google电话面试题目Given an array of N integers from range [0, N] and one is missing. Find the missing number.
一道老题问道题,谁给个效率高点的解法
careercup上这道题我竟然没看懂菜鸟问个two sum的变型题
相关话题的讨论汇总
话题: arrays话题: ram话题: each话题: 电面话题: 解答