简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
When we get a question, we need to think through the special cases that may have. I think we could ask the interviewer for some vague cases. For example, in this problem, we can either define -12321 be palindrome or not. My code is designed for not. In the first place, I wanna use Dynamic Programming to solve this. To recursive down the integer, and compare the two integers beside. While, my first version of DP code went through in my compiler, while not in Online Judge. Because DP is too slow which causes time limit exceed. And as we all know that, all the DP can be transferred into loop. We only need to think problem from bottom up to top down. My code paste below. Pay attention to some barrier condition which is quite easy cause infinite loop.
should add following code into your while loop to include 10101 case:
ReplyDeleteif((x/10)%10 == 0)
{
if((x/power)*10 != x/(power/10))
return false;
else
{
x = x = (x - (x/power)*power - x%10) / 100;
power /= 10000;
}
}
I don't think so. In 10101 case, the power will be 10000 before go into the while loop. Since the frond 1 equals the back 1, so after the first loop, the variable x become 10 and power become 100. Do the loop again and you will find it still goes through. After the second loop, the variable x become 1 and the power become 1. Then do a final loop and it returns true at the end.
DeleteWhy you use power? Isn't that a extra variable you use? But the question says do not use extra space.
ReplyDelete我已经好久木有刷题了。extra space在面试的理解应该是O(n)的space，constant的space是可以的。
Delete