Saturday, November 26, 2011

No. 23 - Palindrome Numbers


Problem: Please implement a function which checks whether a number is a palindrome or not. For example, 121 is a palindrome, while 123 is not.

Analysis: Many candidates can get a straight solution which converts the input number into a string first. However, it is not what interviewers expect usually.

Solution 1: Convert a Number into a String

It is easy to check whether a number is palindrome or not: We can check whether the first character and the last one are identical, and then check the second character and the second one from end, and so on. Therefore, we can firstly convert the input number into a string via the function sprintf, and then check whether the string is a palindrome.

This solution can be implemented as the following code:

bool IsPalindrome_solution1(unsigned int number)
{
    const int NUMBER_LENGTH = 20;
    char string[NUMBER_LENGTH];
    sprintf(string, "%d", number);

    return IsPalindrome(string);
}

bool IsPalindrome(const char* const string)
{
    bool palindrome = true;
    if(string != NULL)
    {
        int length = strlen(string);
        int half = length >> 1;

        for(int i = 0; i < half; ++ i)
        {
            if(string[i] != string[length - 1 - i])
            {
                palindrome = false;
                break;
            }
        }
    }

    return palindrome;
}

Usually the solution above is not the one expected by interviewers. One reason is that it is intuitive while interviewers expect something innovative, and the other is that it requires auxiliary memory to store the converted string.

Solution 2: Compose a Reversed Number

As we know, it is easy to get digits from right to left via / and % operators. For example, digits in the number 123 are 3, 2 and 1. We can construct a reversed number 321 with these three digits. And then we check whether the reverse number is identical to the original one. If it is, the original number is a palindrome.

Its corresponding code is shown below:

bool IsPalindrome_solution2(unsigned int number)
{
    int reversed = 0;
    int copy = number;

    while(number != 0)
    {
        reversed = reversed * 10 + number % 10;
        number /= 10;
    }

    return (reversed == copy);
}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks. 

7 comments:

  1. you don't have to reverse the entire number
    you can just reverse half of it and then compare to the half that is left

    public static boolean isPalindrom(int n) {
    int newNumber = 0;

    while (newNumber < n) {
    newNumber *= 10;
    newNumber += n % 10;

    if (newNumber == n) {
    break;
    }

    n /= 10;
    }

    return (newNumber == n);
    }

    ReplyDelete
  2. I don't follow it, because you are constantly, multiplying reverse * 10, so depending on the number of times you loop, it will be several orders of magnitude larger than copy....

    //132
    reversed = reversed * 10 + number % 10;
    //#1
    reversed = 1320 + y0
    //#2
    reversed = 132x0 + y1
    etc..

    ReplyDelete
  3. Hi Harry,

    Great post. Well thought out. This piece reminds me when I was starting out No. 23 - Palindrome Numbers after graduating from college.

    I have a VPC Network ACL that allows all inbound and outbound traffic (0.0.0.0/0) through. With Elastic Beanstalk I added an EC2 instance whose security group allows inbound traffic only from my IP address and sends all outbound to 0.0.0.0/0. This works just fine.

    A Security group is just like a firewall, it controls the inbound and outbound traffic in and out of your instance AWS Training . The command mentioned says to create a security group, and its function is the same. Moving along, once your security group is created, you can add different rules to it.

    But great job man, do keep posted with the new updates.

    Merci,
    Kevin

    ReplyDelete
  4. Hi There,

    Your writing shines like gold! There is no room for gibberish here clearly. You nailed it in No. 23 - Palindrome Numbers !

    I will have the mp3 files my customer buys on a wordpress page and a cart will direct them to that page. If I want the mp3 files to be downloaded by the customer is there any reason to protect them except to keep them from being indexed by a search engine? Do I need to have a key or do a get operation other than have server-side encryption in S3?

    Very useful article, if I run into challenges along the way, I will share them here.

    Grazie,
    Preethi.

    ReplyDelete
  5. NayHoh,


    11/10!! Your blog is such a complete read. I like your approach with No. 23 - Palindrome Numbers. Clearly, you wrote it to make learning a cake walk for me.


    Unfortunately, AWS IoT has a big problem with bridging to any broker other than mosquitto. Without shared subscriptions, it is nearly impossible to create a bridge that can withstand a heavy load. Ideally, our front end through AWS IoT will have 1-500k publishes at any one time, and subscribing to '#' and forwarding those messages to our backend broker is impossible - the throughput is not nearly high enough for one connection and it creates a single point of failure. AWS Training USA If the pipe breaks, the service breaks.

    Excellent tutorials - very easy to understand with all the details. I hope you will continue to provide more such tutorials.

    Kind Regards,
    Radhey

    ReplyDelete
  6. Hiya,


    Jeez oh man,while I applaud for your writing , it’s just so damn straight to the point No. 23 - Palindrome Numbers .

    I am preparing for AWS Solutions Architect Associate exam. Signed up for AWS free tier and wanted to do a hands-on session related to VPC. Appears, AWS free tier does not allow it now. What options exist to fulfill the hands-on requirements?
    AWS Training




    Very useful post !everyone should learn and use it during their learning path.


    Best Regards,
    Irene Hynes

    ReplyDelete