CODEWITHSUNDEEP
c#asp.netarraysstring
IrishChieftain
IrishChieftain

Reputation: 15253

Determing Palindrome from uint Input

Given the following:

protected bool IsPalindrome(uint x) // Samples: 1221, 456653
{

}

What's the best approach to determine if the input is a palindrome? Initially, I was trying out arrays by putting the input number into an array, reversing it in a for loop and assigning it to a temp array for comparison. However the indexing syntax got messy real fast, so I decided to simply treat the uint as a string.

Would the following be a valid solution in an interview whiteboard situation, or am I still over-complicating it?

protected bool IsPalindrome(uint x) 
{
    string givenNum = Convert.ToString(x);
    char[] input = givenNum.ToCharArray();
    Array.Reverse(input);

    string testString = String.Empty;
    foreach (char a in input)
        testString += a;

    if (givenNum == testString)
        return true;
    else
        return false;
}

Upvotes: 3

Views: 121

Answers (3)

Rion Williams
Rion Williams

Reputation: 76577

NOTE: Since the question explicitly asks for the uint type as input, you can likely expect that the interviewer doesn't really want to see any string conversion approaches, but rather mathematical ones. See juharr's implementation for an example, which works similar to my second example, but replaces the use of strings with a bit of modulo arithmetic to determine correctness.

Short Answer

If you are already using the Array.Reverse() method, then you could simply compare the string to its reverse:

protected bool IsPalindrome(uint x)
{
    // Get your string
    var s = x.ToString();

    // Reverse it
    var characters = s.ToCharArray();
    Array.Reverse(characters);

    // If the original string is equal to the reverse, it's a palindrome
    return s == new string(characters);
}

More Efficient (and Possibly Interviewey) Answer

Within an interview setting, the interviewer might be looking for something that doesn't necessarily leverage all of the existing built-in functions within the language and might want a more bare-bones performant / algorithmic approach (e.g. keeping track of indices, and comparing positional values that might not require you to iterate through every single element).

An implementation that still uses string conversion this might look something like this response:

protected bool IsPalindrome(uint x)
{ 
    // Build your string
    var chars = x.ToString();

    // Iterate through half of the elements
    for (var i = 0; i < chars.Length / 2; i++)
    {
         // If they are ever not equal, then it's not a palindrome
         if (chars[i] != chars[chars.Length - 1 - i])
         {
              return false;
         }
    }

    // If you've made it through, then you have a palindrome
    return true;
}

Performance Comparisons

You can use a Stopwatch() class to actually see which of these performs better on a given dataset. Using 50,000 random integer values and the methods detailed above, I received the following results locally:

ShortAnswerApproachDuration: 00:00:00.0890155
  EfficientApproachDuration: 00:00:00.0693814

A few observations from this:

  • Since the efficient approach doesn't iterate through all of the elements each time and exits as soon as it recognizes the element is not a palindrome, it's much (~22% faster).
  • The efficient approach is also more efficient with regards to storage/memory as it doesn't need to store a copy of the reversed array either.

You can play around with changing the algorithm and testing it online here.

Other Considerations

Depending on how specific your interviewer wants to get, they might throw things like handling actual strings and sentences, handling punctuation and capitalization between those, which are pretty trivial adjustments (e.g. use things like case-insensitivity comparisons, etc.).

Upvotes: 1

juharr
juharr

Reputation: 32296

For efficiency you can do the following to get the reverse numerically and compare

protected bool IsPalindrome(uint x)
{
    uint original = x;
    uint reverse = 0;
    while (x > 0) 
    {
        reverse *= 10;
        reverse += x % 10;
        x /= 10;
    }

    return original == reverse;
}

Upvotes: 4

Traveling Tech Guy
Traveling Tech Guy

Reputation: 27849

Turn the number into a string, and if that string is equal to its reverse, it's a palindrome:

protected bool IsPalindrome(uint x) { 
    string test = x.ToString();
    string tset = new string(test.ToCharArray().Reverse().ToArray());
    return test == tset;
}

Upvotes: 5

Related Questions