Encryption and decryption

January 23, 2018

Introduction

It is another 10:00 PM mock interview. I had a very good peer to ask me about time complexity related to 26 * x calculation, I ended up to correct my time complexity analysis, and tried to optimize the time.

Code review

Here is the C# code I wrote in mock interview.

My argument of time complexity with the peer, a top ranking 60 university with computer science major master degree student, who is graduating this May. What is time complexity 26 * x?

To decrypt the each char in the string with length n, then the total sum of number of chars 1 + 2 + .. + n = n², how many number of char in sum will be O(N²).

If each while loop only 26 is taking off, and then it will take O(N²) while loop and make the time complexity to O(n²).

So this mock interview, I wrote extra 3 lines of code from line 26 to line 28.

if(smaller)
{
   diff += (97 - diff)/ 26 * 26;
}

With this calculation, I reduce the while loop times to O(n) time.

Correction on unknow number x analysis

Here is the analysis with the fix of unknown number x.