# Hacking Time

**Twitter Interview Online Test**

Alice and Bob are avid Twitter users and tweet to each other every day. One day, Alice decides to send Bob a secret message by encrypting it and tweeting it publicly to Bob. They had anticipated a scenario like this, and exchanged a shared secret key some time in the past. Unfortunately, Alice isn't very familiar with encryption algorithms, so she decides to make her own. Her encryption algorithm works as follows:

- Choose a key entirely composed of digits 0 - 9, for example: 12345.
- Iterate each letter of the plaintext message and rotate the letter forward a number of times equal to the corresponding digit in the key. If the rotation of the letter passes Z, start back at A.
- If the message is longer than the key, loop back to the first digit of the key again, as many times as needed.
- If a non-alphabetical character is encountered, leave it as it is and don't move to the next digit in the key.
- Characters should maintain their upper or lowercase orientation after rotation.

Here is an example message and its encrypted output using Alice's algorithm:

Original message: **Hi, this is an example**

Example Key: **4071321**

Encrypted message: **Li, ailu jw facntll**

Where **H** was rotated forward 4 letters to **L**, **i** rotated 0 to **i**, **t** rotated forward 7 letters to **a**, etc.

Satisfied with the security of her algorithm, Alice tweets the following ciphertext to Bob:

**Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. -Atvt hrqgse, Cnikg**

Uh oh! Unfortunately for Alice and Bob, you are “Eve”, the world's greatest hacker. You've been intercepting Alice's messages for some time now, and know she always ends her messages with the signature “**-Your friend, Alice**”. You job is now as follows:

- Determine the key Alice is using.
- Using this key, write a function to decrypt any future communications from Alice. This method should take the encrypted string as an input and return the original unencrypted string.

## Solution

### Step 1 Find the Key

Based on the rotation rules and a piece of decrypted message:

**Atvt hrqgse, Cnikg**

**Your friend, Alice**

We get the code

**251220825122082**

1st character **Y** + 2 is over Z. So start back at **A**.

2nd character **o** + 5 is **t**.

3rd **u** + 1 is **v**

etc.

The code is probably periodic on **2512208**, more precisely, on a rotation of **2512208** since we do not know where the start of the key is, since **Your friend, Alice** is not at the opening of the text.

Two ways to figure out where the key starts:

Apply all the possible rotations, such as

**2512208**,**5122082**,**1220825**, etc.. on the test case given

**Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. -Atvt hrqgse, Cnikg**

With the true key, the test case will be decrypted into

**Greetings friend, I have important info for you. The password to the secret treasure room is the word clocktower. -Your friend, Alice**

But this is kind of cheating. Although it's easy for us to identify and make sense of the message, it's way harder to implement the logic onto a machine.Another way is to count the number of letters before

**-Atvt hrqgse, Cnikg**.

Known the length of key is 7 and number of letters before the signature is N.

So the message is encrypted this way:

7 digit key| 7 digit key| ... | first N % 7 digits of key

7 letters | 7 letters | ... | N % 7 letters

The final key period in the message is incomplete with (N % 7) letters encrypted.

The remaining part of the key period (7 - N % 7) goes to**Your friend, Alice**.

So the first complete key period in**Your friend, Alice**starts at position (7 - N % 7).

In the test case give, there are 92 letters before the signature **Your friend, Alice**.

N = 92

(7 - N % 7) = 6

Therefore the start of key **2512208** is at the 6th index position which is the **8**.

So the actual key is **8251220**,

### Step 2 Recover from Rotation

Once the key is found, what left is just to rotate the encrypted message back.

Assume current letter in the encrypted message is msg[i] and current key digit is key[j],

original letter = msg[i] - key[j].

## Implementation

```
public String decrypt(String input, int[] key) {
StringBuilder res = new StringBuilder();
int i = 0;
for(char c: input.toCharArray()) {
if(i == key.length) i = 0;
if(Character.isLetter(c)) {
char firstLetter = c <= 'Z' ? 'A' : 'a';
c = (char)(c - key[i]);
if(c < firstLetter) c = (char)(c + 26);
i++;
}
res.append(c);
}
return res.toString();
}
```

#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.