K*********n
发帖数: 2852 | 1 说是有100M的文本，比如小说。只有50M的内存，没有其他的硬盘空间。
要求能对这100M文本进行random access和一些操作，比如把词的顺序全都颠倒过来之类
的。
这有一个压缩方法，叫什么来着，忘了。
刚才面小公司被问到了，不会，百般提示才做出来。郁闷。
这种题不知道怎么准备啊…… |
l****c
发帖数: 782 | |
K*********n
发帖数: 2852 | 3 不是。首先这不是一个merge的问题，关键在于你要设计一个方法能够实现random acce
ss。也就是说明明是一个不能装进内存的文本，你需要能够randomly access。这个实现
了，reverse也就好办了。
另外external merge需要有磁盘空间存储中间文件。这个不允许。
我没有把career cup和leetcode所有题都做了，也做了一些，没见过这个。所以现在很
郁闷，碰到问这种问题，不会那就是不会了。
【在 l****c 的大作中提到】
: external merge?
|
g*****e
发帖数: 282 | 4 两次、多次hash？map/partition？不知道思路对不对，请指教 =)
acce
实现
【在 K*********n 的大作中提到】
: 不是。首先这不是一个merge的问题，关键在于你要设计一个方法能够实现random acce
: ss。也就是说明明是一个不能装进内存的文本，你需要能够randomly access。这个实现
: 了，reverse也就好办了。
: 另外external merge需要有磁盘空间存储中间文件。这个不允许。
: 我没有把career cup和leetcode所有题都做了，也做了一些，没见过这个。所以现在很
: 郁闷，碰到问这种问题，不会那就是不会了。
|
K*********n
发帖数: 2852 | 5 啊，这个给挖出来了。我贴了以后没人讨论……
这个给的答案我觉得挺那个的……
就是，word比integer大得多，一般来说。建一个hash table，把vocabulary里面的每一
个word都map成一个int。然后读入数据的时候，查阅hash table，在内存中存储的是in
t而不是word。
然后random access的时候，读的实际上是int，再用另一个hash table，这次key和val
ue反过来了，来查阅读到的int对应的word，就可以了。
这个压缩率是有限的，但是对于题目给的50M vs 100M，要求压缩率为50%，还是可以实
现的。int是4个字节，一个unicode char就是2个字节
【在 g*****e 的大作中提到】
: 两次、多次hash？map/partition？不知道思路对不对，请指教 =)
:
: acce
: 实现
|
g*****e
发帖数: 282 | 6 对，lookup table的思想。跟bitmap/hashtable一回事，经常用来压缩mem cost
每一
in
val
【在 K*********n 的大作中提到】
: 啊，这个给挖出来了。我贴了以后没人讨论……
: 这个给的答案我觉得挺那个的……
: 就是，word比integer大得多，一般来说。建一个hash table，把vocabulary里面的每一
: 个word都map成一个int。然后读入数据的时候，查阅hash table，在内存中存储的是in
: t而不是word。
: 然后random access的时候，读的实际上是int，再用另一个hash table，这次key和val
: ue反过来了，来查阅读到的int对应的word，就可以了。
: 这个压缩率是有限的，但是对于题目给的50M vs 100M，要求压缩率为50%，还是可以实
: 现的。int是4个字节，一个unicode char就是2个字节
|
K*********n
发帖数: 2852 | 7 说是有100M的文本，比如小说。只有50M的内存，没有其他的硬盘空间。
要求能对这100M文本进行random access和一些操作，比如把词的顺序全都颠倒过来之类
的。
这有一个压缩方法，叫什么来着，忘了。
刚才面小公司被问到了，不会，百般提示才做出来。郁闷。
这种题不知道怎么准备啊…… |
l****c
发帖数: 782 | |
K*********n
发帖数: 2852 | 9 不是。首先这不是一个merge的问题，关键在于你要设计一个方法能够实现random acce
ss。也就是说明明是一个不能装进内存的文本，你需要能够randomly access。这个实现
了，reverse也就好办了。
另外external merge需要有磁盘空间存储中间文件。这个不允许。
我没有把career cup和leetcode所有题都做了，也做了一些，没见过这个。所以现在很
郁闷，碰到问这种问题，不会那就是不会了。
【在 l****c 的大作中提到】
: external merge?
|
g*****e
发帖数: 282 | 10 两次、多次hash？map/partition？不知道思路对不对，请指教 =)
acce
实现
【在 K*********n 的大作中提到】
: 不是。首先这不是一个merge的问题，关键在于你要设计一个方法能够实现random acce
: ss。也就是说明明是一个不能装进内存的文本，你需要能够randomly access。这个实现
: 了，reverse也就好办了。
: 另外external merge需要有磁盘空间存储中间文件。这个不允许。
: 我没有把career cup和leetcode所有题都做了，也做了一些，没见过这个。所以现在很
: 郁闷，碰到问这种问题，不会那就是不会了。
|
|
|
K*********n
发帖数: 2852 | 11 啊，这个给挖出来了。我贴了以后没人讨论……
这个给的答案我觉得挺那个的……
就是，word比integer大得多，一般来说。建一个hash table，把vocabulary里面的每一
个word都map成一个int。然后读入数据的时候，查阅hash table，在内存中存储的是in
t而不是word。
然后random access的时候，读的实际上是int，再用另一个hash table，这次key和val
ue反过来了，来查阅读到的int对应的word，就可以了。
这个压缩率是有限的，但是对于题目给的50M vs 100M，要求压缩率为50%，还是可以实
现的。int是4个字节，一个unicode char就是2个字节
【在 g*****e 的大作中提到】
: 两次、多次hash？map/partition？不知道思路对不对，请指教 =)
:
: acce
: 实现
|
g*****e
发帖数: 282 | 12 对，lookup table的思想。跟bitmap/hashtable一回事，经常用来压缩mem cost
每一
in
val
【在 K*********n 的大作中提到】
: 啊，这个给挖出来了。我贴了以后没人讨论……
: 这个给的答案我觉得挺那个的……
: 就是，word比integer大得多，一般来说。建一个hash table，把vocabulary里面的每一
: 个word都map成一个int。然后读入数据的时候，查阅hash table，在内存中存储的是in
: t而不是word。
: 然后random access的时候，读的实际上是int，再用另一个hash table，这次key和val
: ue反过来了，来查阅读到的int对应的word，就可以了。
: 这个压缩率是有限的，但是对于题目给的50M vs 100M，要求压缩率为50%，还是可以实
: 现的。int是4个字节，一个unicode char就是2个字节
|
l**b
发帖数: 457 | |
q****m
发帖数: 177 | 14 能举个例子吗？
比如这个文件有如下四行，但是不能一次性读入内存
doctor
nurse
teacher
student
如何多次hash?
每一
in
val
【在 K*********n 的大作中提到】
: 啊，这个给挖出来了。我贴了以后没人讨论……
: 这个给的答案我觉得挺那个的……
: 就是，word比integer大得多，一般来说。建一个hash table，把vocabulary里面的每一
: 个word都map成一个int。然后读入数据的时候，查阅hash table，在内存中存储的是in
: t而不是word。
: 然后random access的时候，读的实际上是int，再用另一个hash table，这次key和val
: ue反过来了，来查阅读到的int对应的word，就可以了。
: 这个压缩率是有限的，但是对于题目给的50M vs 100M，要求压缩率为50%，还是可以实
: 现的。int是4个字节，一个unicode char就是2个字节
|
d*s
发帖数: 699 | 15 原则上disc也是random access device，就是慢一点而已，
能不能把disc理解为memory，memory理解为cpu cache？那么这个题的意思就是让你实
现一个基本的cache？我的想法是把100M分成N份，当某个位置的字节被要求读取的时候
，把相应的那份全部copy进memory并进行封装，从client看来就好像在读一个100M的内
存，但实际上你实现的是virtual memory
之类
【在 K*********n 的大作中提到】
: 说是有100M的文本，比如小说。只有50M的内存，没有其他的硬盘空间。
: 要求能对这100M文本进行random access和一些操作，比如把词的顺序全都颠倒过来之类
: 的。
: 这有一个压缩方法，叫什么来着，忘了。
: 刚才面小公司被问到了，不会，百般提示才做出来。郁闷。
: 这种题不知道怎么准备啊……
|
