A technical blog about programming and technology.

Saturday, April 28, 2007

Microsoft Interviews

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:

Dion said...

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; //
}

David Fowler said...

Thats a math intensive solution pretty cool. Any more takers?

Kleber Garcia said...

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 ;)

David Fowler said...

Reader kleber garcia came up with a more elegant solution to the problem.

Alexand3r said...

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;
}

David Fowler said...

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

alexand3r said...

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;
}