Inplace algorithm to reverse a C style string

      In the last post, we have seen an effective algorithm to multiply a number by 7. In this post we shall see about an  effective algorithm to reverse a string. This is a classic interview question and well expect this question in your technical interview even at google, microsoft, yahoo, etc.

     In this algorithm, the interviewer mainly notices that is your algorithm inplace (i.e) can it do without using any extra memory? Thus we shall find a way to reverse a string without using additional string. The algorithm is given below.

Step 1: i = 0; j = length of string - 1
Step 2: swap string[i] and string [j]
Step 3: increment i and decrement j
Step 4: Go to step 2 if i < j

Thus a C++ code to reverse a C style string is given below:

void strrev(char *str)
{
  int n= strlen(str);
  for(int i = 0, j = n-1; i < j; i++,j--)
  {
    //swap a[i] and a[j]
    a[i] = a[i] ^ a[j];
    a[j] = a[i] ^ a[j];
    a[i] = a[i] ^ a[j];
  }
}

Fastest way to multiply a number by 7

Top companies like microsoft, google asks algorithm oriented questions to test the analytical skill of the candidate. Here is one such question.

Given a number N, devise an algorithm to multiply N by 7?

        Well we obviously think that N * 7 is the answer. But it is not. Remember multiplication is a tedious process. It needs many registers and takes some time to produce the output.Therefore we have to reduce the time complexity. The interviewer looks exactly the best possible answer and let us find it now.

       The bitwise operators are very fast enough and hence our intution tells us that the answer should involve bitwise operations. We know that we can multiply a number by 8 just by left shifting the number 3 positions. So we can use it to multiply N by 7. The working method is given below.

N * 7 = N * (8 - 1)
          = N * 8 -N
N * 7 = N << 3 - N

Thus a function in C to multiply N by 7 is given below.
int mul_by_seven ( int n)
{
  return (n << 3) - n;
}

In any technical interview the interviewer tries to find out how you work out solving a problem and hence talk aloud while you think.