Last week , a couple of my friends had Microsoft phone interviews. Since I got my internship last summer, they have been coming to me for advice and interview "training". In coming up with some questions to give my friends, I remembered the isPalindrome function I saw a while back and came up with this question:
bool isPalindrome(int x) {
}x is guaranteed to be a positive number, and single digit numbers are palindromes. By the way converting to a string is not an option :D nice try.
7 comments:
bool isPalindrome(int x){
if(x < 10 && x > -10)
return true; // if the number is single digit return true
int i; //holds the number of characters in the integer
for(i = 0; pow(10.0, i) < x; i++); // determines the number of characters in an integer
if(int(x/int(pow(10.0, i-1))) == (x%10))
return isPalindrome((x - (int(x/int(pow(10.0, i-1))) * int(pow(10.0, i-1))))/10); // Returns a substring of the integer eg x = 12121; 212 would be passed in
else
return false; //
}
Thats a math intensive solution pretty cool. Any more takers?
boolean isPalindrome(int x){
return x-invert(x)==0;
}
int invert( x){
int y=0;
while (x!=0){
y = y*10 + x%10;
x/=10;
}
}
O(n), no recursion ;)
Reader kleber garcia came up with a more elegant solution to the problem.
Here is my solution to the problem. Not the fanciest but I think it does what it is supposed to do. This blog doesn't allow me to declare the bitset properly though :).
bool isPalindrome(int number)
{
const int size = 32;
bitset<size> ins;
int count = 0;
number = number;
while (count < size)
{
if (number < 1) break;
ins[count] = number%2;
number = number >> 1;
++count;
}
for (int i=0,j=count-1; i < count; ++i, --j)
{
if (ins[i] != ins[j])
return false;
}
return true;
}
Alexand3r, checking that a number is a palindrome is not the same as checking that its binary is a palindrome; which is what you are doing... You method detects that 17 is a palindrome, because it is, 10001
hehe. Before this was on the blog you provided only binary test cases so i assumed integers in binary representation. Anyway here's it for base 10.
bool isPalindrome(int number)
{
int count = 0;
int num[16] = {0};
while ((number%10)>0)
{
num[count] = number%10;
number = number/10;
++count;
}
for (int i=0, j=count-1; i < count; ++i, --j)
if (num[i] != num[j]) return false;
return true;
}
Post a Comment