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 garciacame 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