LinkedIn Software Engineer IC2 Interview Question LZ78 Compression

This was a pretty tough but a smooth round for me, where I was given a string manipulation based question, I had to compress and decompress the given string. It was LZ78 based question. /* LZ78 is a w

This was a pretty tough but a smooth round for me, where I was given a string manipulation based question, I had to compress and decompress the given string. It was LZ78 based question. / LZ78 is a well-known compression method. It works by splitting the input text in a sequence of unique substring ‘phrases’ (except maybe the last one). Each phrase is the concatenation of a previous phrase and a character that makes it unique. // For example, the string aababababbaa is compressed as follows: // For convenience, we define a phrase 0 that is the empty string. // Then we start processing the input and we see ‘a’. It’s the first time we see this phrase, // so we create phrase 1 defined as phrase 0 + symbol a (0+a for short). // We then see another ‘a’, which we have seen. So we add the next character (‘b’) and check for ‘ab’. // This one is new, so we defined phrase 2 as phrase 1 plus the symbol b (1+b for short). // We can continue doing this, and the result set of phrases is as shown in the table below. // ----------------------------------------- // | | a | ab | aba | b | abb | aa | // | 0 | 0+a | 1+b | 2+a | 0+b | 2+b | 1+a | // ---------------------------------------- // So, aababababbaa compresses down to // (0, a), (1, b), (2, a), (0, b), (2, b), (1, a) // We should also be able to decompress this back into the original string. // We will call this compression algorithm LZ78. Implement the decompressor and the compressor for LZ78. /

Solution : Use ArrayList and HashMap. I did it and was able to do both compression and decompression. It was about 60 minutes round.