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

January 3, 2008 Posted by | Code Challenges | Leave a comment