A file contains a number of repeated but not consecutive zeros. Can you read and store the file such that you save space, but you still can reconstruct the original file? Please C++ code.
(PS: this was an old interview coding question, which I am not going to use anymore)
Is the input stream a sequence of bits or bytes ?
ReplyDeleteIf there were ENOUGH zeros that they were especially common (but random) then sure, output a stream of bits showing where the 0s are and interleave the other bytes when decoding. But this won't work in general... the overhead of the bits would be too much if 0s weren't common enough. A classic compression algorithm (huffman, etc) would work even more efficiently, but again, that would not work in general.. the counterexample is a file of random noise. There are plenty of 0s but it's uncompressable.
ReplyDelete