t*****a
发帖数: 106 | 1 看别人面经，有道题不理解
原帖地址:http://www.mitbbs.com/article_t/JobHunting/32622081.html
为了阅读方便，我把其中用到的部分摘出来，感谢bainikolaus提供面经。
“第四轮
问我知不知道zip文件，我说用过但不知原理。他就说我们来讨论一下
假设一个文件压缩后的表示是
#3, #5, #6, 2 5, #8...
”#k“形式的代表这个数字k，两个数字“i j”形式的代表取前 i 个
数字做 j 长的 circular重复，像上面那个表示，前面3个都是表示单个数字，
然后 2 5表示取前2个数字 （既56），组成5个数字，不够的从头再取，所以就是56565
最后上面解压缩后应该为
3, 5, 6, 5, 6, 5, 6, 5, 8...
要我写的是压缩算法的代码。
我提出从头扫，一边一边用hashtable记下见过的number，每前进一位就检查hashtable
有没有符合当前数字模式的number出现过，然后他说还不错，写代码。一边写一边出现
bug，一边发现很多写代码前没考虑的东西，最后勉强算写完，时间也到了，他说这个
他也没写过，是在一篇paper上看到的算法，原算法跟我的有些不同，倒是都用了
hashtable。。。“
解答:
“对input从左往右扫，维持一个hashtable记录前面所出现过所有三位数和它们最后一次
出现的位置，举个例子说明
input：2 3 4 5 2 3 4 5 1...
用 digit 代表正在扫描的数字，record表示hashtable：
digit record
2 {}
3 {}
4 {234: 0}
5 {234: 0, 345: 1}
2 {234: 0, 345: 1, 452: 2}
3 {234: 0, 345: 1, 452: 2, 523: 3}
4 {234: 4, 345: 1, 452: 2, 523: 3}
.
.
.
此外，在扫描一个数字的时候，如果发现有重复出现的三位数，那么就开始对比下去，
尝试找到最长的match。继续用回上面的例子：
在扫描到第二个4的时候，会发现234重复出现，所以就继续比较input[3] 和 input[7]
, 两个都是5，match，所以继续比较input[4] 和 input[8], 一个是2另一个是1，不匹
配，停止，所以在这次发现重复里面就找到一个长度为4的重复，写下压缩记录"4 4" (
往回退4个数字复制4个), 然后继续扫描下一个数字 1。大概思路就是这样，当然中间
还有很多细节，我当时用了一个差不多的想法，一边写代码就一边发现很多东西没有考
虑周全。。。”
不理解为什么要3个3个的search,如果每三个搜索的话，那下面的情况怎么办？还是说
两个的压缩都不需要做，因为不会提供太多的空间增益？
"abcbcbcabcbcbc"
如果两个两个的search,应该是#a,#b,#c,24,71.
三个三个的搜索是 #a,#b,#c,#b,#c,#b,#c,71.
两个的省空间啊 | s**x
发帖数: 7506 | 2 you can google LZW algorithm, should be similar to one of those. learned
that before, not forgot the details .... | t*****a
发帖数: 106 | 3 Thanks. I will read it.
【在 s**x 的大作中提到】
: you can google LZW algorithm, should be similar to one of those. learned
: that before, not forgot the details ....
|
|
