Feature #3: Find Dictionary

Description

We use a network protocol that encrypts all application messages using a proprietary scheme. The encryption scheme has a unique property that the sequence of encrypted messages in a session appears to be in sorted order according to a secret dictionary. However, the dictionary is not transmitted for security purposes.

Before the sender starts transmitting actual messages, it sends several encrypted training messages to the receiver. The sender guarantees that the training messages will follow the lexicographic order according to the unknown dictionary.

The receiver must reverse engineer the training messages and generate the dictionary for future communication with the sender. If the order of the messages is invalid, the receiver generates an empty dictionary and asks the sender to retransmit the training messages.

For simplicity’s sake, we can assume that the encrypted contents of the messages only consist of English lowercase letters.

Let’s review a few examples below:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.