Please navigate to the bottom of the page for Table of Contents

Saturday, May 21, 2011

String manipulation can be fun

String manipulations are a favorite topic for interview questions. They are small, easy to whiteboard and test your thinking power and logic. They are a great source for SDET interviews and allow the interviewer to dig deeper into test case generation also.

So, let's start by going over some simple string operations. I chose to use C/C++ programming language for this section as pointer understanding is critical (even if you code in the managed world of C# and JAVA). Without further ado, let's review 3 simple string functions – length, copy and concatenation.

Find the length of the string

// Simple funtion to calculate the length of a string
// Basically, keep counting the chars till the end
// of the string (aka NULL pointer) is met
int StringLength(char *input)
{
// initialize
int length = 0;

// loop through the entire string
while (*input)
{
// increment the length
length++;
// move to next char
// since *input points to the data
// input contains the actual address
// this is an example of pointer arithmetic
input++;
}
return length;
}



String copy – copy source string over target


// string copy - copy source string over target string
// can you find a possible bug in the code?
void StringCopy(char* target, char *source)
{
// loop through the source string
// and replace the characters in the target string
while (*source)
{
// assign the character
*target = *source;
// move the pointers to the next location
target++;
source++;
}
// terminate the target string
*target = '\0';
}



String concatenate - concatenate 2 strings


// string concatenate - concatenate 2 strings
void StringConcatenate(char* target, char *source)
{
// loop through the target string
// till you find the end
while (*target)
target++;

// now copy source characters to the target
while (*source)
{
// assign the character
*target = *source;
// move the pointers to the next location
target++;
source++;
}
// terminate the target string
*target = '\0';
}


All the above functions are self-explanatory. There are a few bugs and optimizations that can be done to these functions. I would like to leave that as an exercise for the readers and encourage you to post your responses.


In the next section, we will dig a little bit more deeper into strings.

9 comments:

  1. The mayor bug I see (specially in the "target" string when copying or concatenating strings) is that if "target" isn't properly memory allocated it would throw an error or exception.

    For concatenation, the size of the memory allocation will be:
    sizeof(char) * (target.lenght + source.lenght)

    Malloc for C++ lovers, Stackalloc for C# lovers :D

    ReplyDelete
    Replies
    1. Yes, the assumption is that memory has been properly allocated.

      Delete
    2. sizeof(char) is 1, by definition, so multiplying by it is bad form.
      A string is not terminated by a NULL pointer, it is terminated by a NUL char. This mistake is a bug in the comment of the solution to the first question. The distinction may seem trivial but the use of the word 'pointer' instead of 'char' is worrisome.

      Delete
  2. String copy – copy source string over target

    // string copy - copy source string over target string
    // can you find a possible bug in the code?
    void StringCopy(char* target, char *source)
    {
    // loop through the source string
    // and replace the characters in the target string
    while (*source)
    {
    // assign the character
    *target = *source;
    // move the pointers to the next location
    target++;
    source++;
    }
    // terminate the target string
    *target = '\0';
    }

    Well yes, I see a bug. If source is NULL you will basically slice off the target (i.e., the last line).

    ReplyDelete
  3. I think the bug of String copy code is that you lost the target, Maybe you want to save the address of target somewhere before you copy everything from source to target
    Is it a bug??

    ReplyDelete
    Replies
    1. The goal of the function is to copy the source data to target. Also, it is a copy of the pointer. So nothing gets lost. I encourage to run this test yourself.

      Delete
    2. Yes, it is true. You pass the pointer as parameter, instead of pointer to pointer, so nothing gets lost!
      I did run the test, just I coded using C#.
      Thank you so much! This is great post, I went through almost every topic here! I got interview next week, I hope I can run into similar question LOL!

      Delete
  4. If the target and source are overlapping that string copy written above wont work. Similar to MemMove Vs Memcopy

    ReplyDelete
  5. Thanks..very nice..for more string related interview questions please go through this blog adnjavainterview blog.

    ReplyDelete