Defining palindrome from uint input
Considering the following:
protected bool IsPalindrome(uint x) // Samples: 1221, 456653
{
}
What's the best approach to determine if an input is a palindrome? I originally tried arrays by putting the input number into an array, reversing it in a for loop and assigning it to the temp array for comparison. However, the indexing syntax got very fast, so I decided to just treat the uint as a string.
Is the next correct solution in an interview board 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;
}
source to share
NOTE. ... Since the question explicitly asks for the type
uint
as input, you can probably expect that the interviewer doesn't really want to see any string conversions, but rather mathematical ones. See the juharr implementation for an example that works similarly to my second example, but replaces the use of strings with modulo arithmetic bits to determine correctness.
Short answer
If you are already using the method Array.Reverse()
, you can simply compare the string with 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 a palindrome
return s == new string(characters);
}
A more efficient (and possibly interviewable) answer
As part of the interview, the interviewee may be looking for something that does not necessarily use all the existing built-in functions within the language and may require a more efficient algorithmic approach (for example, tracking indices, and comparing positional values, which may not require you to repeat every single element).
An implementation that still uses string conversion might look something like this answer :
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 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 comparison
You can use the class Stopwatch()
to really see which one performs better on a given dataset. Using 50,000 random integers and the methods described above, I got local results:
ShortAnswerApproachDuration: 00:00:00.0890155
EfficientApproachDuration: 00:00:00.0693814
A few observations from this:
- Since the efficient approach does not iterate over all the elements every time and exits as soon as it recognizes the element, this is not a palindrome, it is significantly (22% faster).
- The efficient approach is also more storage / memory efficient since it doesn't need to keep a copy of the reversing array.
You can play with the algorithm change and test it online here .
Other considerations
Depending on how specific your interlocutor wants to fetch, they might throw things like handling actual strings and sentences, handling punctuation marks and capital letters between those that are fairly trivial adjustments (for example, using things like comparing randomness and etc.).
source to share