Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

String Pattern Matching: Write a function that checks for a given pattern at the end of a given string

Posted by tekpool on October 15, 2006

String Pattern Matching: Write a function that checks for a given pattern at the end of a given string

In other words, Write a function, a variant of strstr that takes in 2 strings str1 and str2 and returns true if str2 occurs at the end of the string str1, and false otherwise.

bool str_str_end(char * str1, char * str2) 
{ 
        // Store the base pointers of both strings 
        char* beginStr1 = str1; 
        char* beingStr2 = str2; 

       // Move to the end of the strings 
        while(*str1++); 

        while(*str2++); 

        for(; *str1 == *str2; str1--, Str2--) 
       { 
       If( str2 == beginStr2 
                          || str1 == beingStr1) 
            { 
            break; 
            } 
       } 
       return    If(*str1 == *str2 
                    && str2 == beginStr2 
                    && *str1 != 0); 
}

Save the base addresses of the strings and then traverse to the end of the stings. To check if the string str2 occurs at the end of the string str1, start comparing characters from the end of the strings and move backwards. The function returns true when

  1. All the characters in str1 match all the characters in str2 from the end.
  2. The pointer str2 reaches back at the beginning of the string, which means there is nothing more to be compared
  3. The strings are not empty.

The above conditions are required so that the loops do not run in an infinite loop.

Advertisements

2 Responses to “String Pattern Matching: Write a function that checks for a given pattern at the end of a given string”

  1. Antibush said

    Bush goes ballistic about other countries being evil and dangerous, because they have weapons of mass destruction. But, he insists on building up even a more deadly supply of nuclear arms right here in the US. What do you think? Why has bush turned our country from a country of hope and prosperity to a country of belligerence and fear.
    Our country is in debt until forever, we don’t have jobs, and we live in fear. We have invaded a country and been responsible for thousands of deaths.
    The more people that the government puts in jails, the safer we are told to think we are. The real terrorists are wherever they are, but they aren’t living in a country with bars on the windows. We are.

  2. geb said

    Wow. I would go after someone writing code like “while (*str++);”
    This is wrong at several levels:
    – it doesn’t do what it’s supposed to do. You end up with the pointer pointing past the trailing 0.
    – it’s unclear, that is, harder than it needs be to maintain. Even if you get it right, someone coming after won’t be sure what you meant to do if there is a bug (as it is the case here).
    In this case, a proper way to write it is:
    while (*str)
    ++str;

    If I had a recommendation for anyone during interviews (or otherwise): make your code look as simple as possible, if not only because you’ll have less chances to shoot yourself in the foot. That will make you look much smarter that this arrogant looking & broken code. And people will want to work with your code.

    Not to mention the other problems with this code, like the changing variable names or the return statement with an if…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

 
%d bloggers like this: