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.