int main(void)
{

My Blog

Posted 02/17/12 @ 11:09pm - By Ross

Interviews

Interview questions are the bane of my existence. Something about someone waiting on you to solve a problem causes me to second guess everything I do. However, I do find them interesting to think on after the interview is over. In a recent interview I was asked a question about removal of spaces from a string. My first take on the problem came up with the standard O(n2) version of the algorithm.

Here was my take on it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void TrimSpaces(char* word, int size)
{
  int ii, jj;

  for(ii = 0; ii < size;ii++)
  {
    if(word[ii] == ' ')
    {
      for(jj = ii; jj < size - 1; jj++)
      {
        word[jj] = word[jj + 1];
      }
      size--;
    }
  }
}

It’s a fairly straightforward implementation. Loop through and find each space and then shift over all the other characters in the string. In use it actually shouldn’t be too bad since spaces are typically less than half of the characters in a string. Regardless, it’s still not as efficient as it could be.

So as I laid in bed the other night a better solution occurred to me that can be done in linear time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void TrimSpaces(char* word, int size)
{
  int ii;
  int offset = 0;

  for(ii = 0; ii < size;ii++)
  {
    if(word[ii] == ' ')
    {
      offset++;
    }
    else
    {
      word[ii - offset] = word[ii];
    }
  }
}

In going through the string we simply keep track of how many spaces we have, then we know how much to shift the string as we go.

Another possibility is the allocation of a new string and copying over all characters except for spaces. This works well if you must preserve the original string. However, if you are merely editing the string an in place solution is superior.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

return 0;

}