Today I've decided that I want to review my basic computer science knowledge. And since I have a feeling that I may want to review this in the future again - I thought of making out of it a blogging experience. This way I kill two birds with one stone: blogging and review. Also even though there are lots of solutions and code sites on the web, this still may be of help to other colleagues of mine that plan to review.

The way I'm going to do the review is by solving popular programming problems which may be also a good preparation for a job interview. For my review I'm going to be using the Java programming language, but it should not matter for experienced programmers, since I'm going to use basic language structures and no external libraries.

Today I'll start with a classic popular problem:

*the palindrome*
For those who do not know what a palindrome is - it is a sequence of characters that can be interpreted in the same way independently of what direction is used to read them. For example "abba" is a palindrome because you can interpret this sequence in the same way independently of the direction you read the sequence.

One known problem is determining if a number is a palindrome. It is usually limited to no extra memory. Let's say we have two numbers: 1781 and 42124. The latter one is the palindrome, and the way we do it programmatically would be by comparing the first and last digit and moving on to the second and n-1 digit and so on. Now the main problem is determining the first and last digit which consists of numerical operations. Last digit is easy - just get the reminder of the division by 10 (modulus) but first digit requires a little bit of thought. So in our number 1781, for the first digit we basically need to divide it by 1000, and we get 1 (781 reminder). How do you find this 1000 number ? - just go through the digits and multiply 1 with 10 n-1 times. (Line 7-9).

Now as we have the first and last number we can compare them and fail right away if they're not equal. Truncating the number from the last and first digit is fairly easy : 1781 % 1000 reminder is 781, and then just divide by 10, and we have the 78 number. (Line 17). Lastly decrease div by 2 digits (Line 18). All in all you get an O(n) solution.

beautiful

ReplyDeleteHello, I enjoy reading your posts. Very entertaining and educational. My solution for this problem was to reverse the integer. If it is a palindrome, the reverse should be the same as the original number.

ReplyDeleteint reverse_integer(int num) {

bool neg = false;

if (num < 0) {

neg = true;

num = -num;

}

int result = 0;

while (num) {

result = result * 10 + (num % 10);

num /= 10;

}

return neg ? -result : result;

}

bool is_palindrome(int num) {

return (num == reverse_integer(num));

}