由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教2个 huge file的面试题
相关主题
一道java面试题贡献几道面试题
一道 纽约 Morgan Stanley IT Equity Trading 面试题G家面经求指点--beanbun--G--dictionary
google phone interview问个面试题
问个google面试题一道Google面试题
求Twitter onsite 经验 (分享些它家的题目)Groupon 電面
F家电面:group Anagramsgoogle面试题(已经挂了,没有包子哈)
面试题 finding missing valuefacebook telephone interview from careercup
kth smallest element问一个 String array sorting 的题。
相关话题的讨论汇总
话题: file话题: hash话题: trie话题: element话题: f1
进入JobHunting版参与讨论
1 (共1页)
m******9
发帖数: 968
1
问题1: 2个超大file,memory容不下,都是unsorted,假设里面全是integer。如何找
出2个文件
中的重复部分?
我看到的一个答案是:
step 1: external merge sort F1 (file 1): 将原文件分成若干个temporary
smaller
files, 对每个temporary small file进行quicksort,然后对所有smaller files 进行
multiple-way merge sort, 重新合并成一个sorted big file.
step 2: traverse F2, binary search F2's each element in F1,
step 3: 能找则是common element,如果找不到则继续读取判断下一个element
问题2: 1个超级大文件,unsorted,里面都是string。如何找出所有的anagram?
这个题没什么思路
求教了,谢谢
g*******y
发帖数: 1930
2
在一个超大的file里面做binary search太费时间了
一般找重复的,用hash最好了,可以minimize disk I/O
m*****f
发帖数: 1243
3
en.
1. hash or bitmap
2. trie

【在 g*******y 的大作中提到】
: 在一个超大的file里面做binary search太费时间了
: 一般找重复的,用hash最好了,可以minimize disk I/O

g*******y
发帖数: 1930
4
第二个用trie,到底能不能比hash更省空间,我一直有个疑惑

【在 m*****f 的大作中提到】
: en.
: 1. hash or bitmap
: 2. trie

m*****f
发帖数: 1243
5
这个我也没有真的实现过....不过string题用trie直观, 好处应该更容易吹

【在 g*******y 的大作中提到】
: 第二个用trie,到底能不能比hash更省空间,我一直有个疑惑
s***t
发帖数: 49
6
hash talbe 放在什么地方呢?

【在 g*******y 的大作中提到】
: 在一个超大的file里面做binary search太费时间了
: 一般找重复的,用hash最好了,可以minimize disk I/O

a****n
发帖数: 1887
7
hash 和 trie都有内存问题吧?
m******9
发帖数: 968
8
hash应该也有memory的限制,这个文件太大,不能全部放到hash table中,能不能解释
一下,怎么
hash呀,谢谢

【在 g*******y 的大作中提到】
: 在一个超大的file里面做binary search太费时间了
: 一般找重复的,用hash最好了,可以minimize disk I/O

g*******y
发帖数: 1930
9
存在disk上吧,内存肯定存不下

【在 a****n 的大作中提到】
: hash 和 trie都有内存问题吧?
m******9
发帖数: 968
10
长牙的羊: 我没有跟上你的第2题答案的思路,能不能解释一下,trie如何找anagram
,是不是还要
将每个word都事先sort一遍呀?谢谢

【在 m*****f 的大作中提到】
: en.
: 1. hash or bitmap
: 2. trie

m*****f
发帖数: 1243
11
是呀

【在 m******9 的大作中提到】
: 长牙的羊: 我没有跟上你的第2题答案的思路,能不能解释一下,trie如何找anagram
: ,是不是还要
: 将每个word都事先sort一遍呀?谢谢

m******9
发帖数: 968
12
另外问一下,如果用trie,把每个words都sort,(假设是升序)。 在trie中也可以判
断出是
anagram了,但是到时该如何将这些words还原呢?谢谢

【在 m*****f 的大作中提到】
: 是呀
v*****t
发帖数: 127
13
one idea might be:
store complete words at leaf node, or you can store dictionary indexes of
the words if you want to save some space

【在 m******9 的大作中提到】
: 另外问一下,如果用trie,把每个words都sort,(假设是升序)。 在trie中也可以判
: 断出是
: anagram了,但是到时该如何将这些words还原呢?谢谢

1 (共1页)
进入JobHunting版参与讨论
相关主题
问一个 String array sorting 的题。求Twitter onsite 经验 (分享些它家的题目)
问两道amazon的面试题F家电面:group Anagrams
问个google面试题面试题 finding missing value
问个google面试题kth smallest element
一道java面试题贡献几道面试题
一道 纽约 Morgan Stanley IT Equity Trading 面试题G家面经求指点--beanbun--G--dictionary
google phone interview问个面试题
问个google面试题一道Google面试题
相关话题的讨论汇总
话题: file话题: hash话题: trie话题: element话题: f1