Coding Notes

Ideas and thoughts from Seth Long

Nonrepeated Character Search

My blog is now located at http://www.WhoIsSethLong.com

This code challenge was inspired by a book I recently read.  The book is called Programming Interviews Exposed: Secrets To Landing Your Next Job.  It’s a great book full of those fun technical questions you get asked during programming job interviews.

For this challenge, you will need to create a function/class/algorithm that takes a string and finds the first non-repeated character.  For example, in the word reaper the first non-repeated character is ‘a’.  The character ‘p’ is also not repeated but we are looking for the first one.

There are multiple ways to accomplish this but I’m going to only post 1 here.  To start, I first created a hash table with all the chars in the string and incremented each char as additional matches are found.  So for example, in the string reaper I will start with the char ‘r’ and add that to the hashtable and give it a value of 1.  Next I will add ‘e’ to the hash table and give it a value of 1. The char ‘p’ will get a value of 1 but the next char, ‘e’, already exists in the hashtable so we will increment it by 1 and it’s value becomes 2.  This is done for all the chars in the string.

Once this is done, we then read back over the string, comparing each char in the string to the hashtable till we find the first char that has a value of 1.  I know, it sounds a little confusing but if you read of the code sample it will make a lot more sense.

Here is a code sample in C#:

public char NonRepeatedChar(string s)
{
    Hashtable ht = new Hashtable();
    // loop through each char in string
    // and add to hashtable
    for (int x = 0; x < s.Length; x++)
    {
        char c = s[x];
        if (ht.ContainsKey(c))
        {
            // already exists in hashtable so
            // give it a value of 2.
            ht[c] = 2;
        }
        else
        {
            // does not already exist so give
            // an initial value of 1
            ht.Add(c, 1);
        }
    }
    // loop through the string again and
    // find the FIRST match in the hashtable
    // that has a value of 1 and return it.
    for (int x = 0; x < s.Length; x++)
    {
        char c = s[x];
        // check if the char’s value is 1
        if ((int)ht[c] == 1)
        {
            return c;
        }
    }
    // no match found
    return ;
}

Well, that’s all for now!

 (I just noticed the return value for the above code isn’t showing up. It’s just a null char.)

– Seth Long

Advertisements

January 3, 2008 - Posted by | Code Challenges

No comments yet.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: