Linkedin Loop - First DSA round for Software Engineer IC2
Summary
I had a pretty tough but smooth 60-minute DSA round for a Software Engineer IC2 role, where I was tasked with implementing an LZ78 compressor and decompressor, which I successfully completed.
Full Experience
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. I did it and was able to do both compression and decompression. It was about 60 minutes round.
Interview Questions (1)
LZ78 Compressor and Decompressor
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.