Problem Statement- Palindromes

One of the most common subject which is often questioned in many coding interviews is the topic of a palindrome. So let’s discuss a couple of problem-solving methods for some palindrome based questions.

What problem statements are we discussing?

  • Given a number, determine if its a palindrome?
  • Given a singly linked list, determine if it is a palindrome.

So, what is a palindrome?

Palindrome can be a word, phrase or a number that can be read and spelled the same way in either direction.

19 Words That Are the Same Backwards and Forwards
Courtesy: Reader’s Digest`

Generally, palindrome based coding questions can be tested on integers, strings, linked lists, stacks etc

So let’s start from the most basic palindrome question:

Given a number, determine if its a palindrome?

This means if the input is “2332” the output should be true. Because if you reverse the number “2332”, it would be the same as the original.

So before we dive into coding, let’s discuss 3 main logic behind the following code.

  1. Negative numbers cannot be a palindrome.
  2. The last digit of a number can be obtained by determining the modulo of the number.

3. We are going to iterate through the number until the original number is greater than 0.

4. While loop: In each iteration, the modulo of the number is determined and the last digit obtained is added to the variable “reversed_integer”. Finally, the current last digit is removed from the original number by dividing it by 10.

5. If Condition: Finally we check for equality between the original number and the reversed number.

For E.g

Input : 2332

Problem Solution:

public class palindrome
{
public static void palindrom(int n)
{
int orginalNumber,reversedNum=0,lastDigit;
orginalNumber=n;
while(orginalNumber!=0)
{
lastDigit=orginalNumber%10;
reversedNum= reversedNum *10 + lastDigit; orginalNumber=orginalNumber/10;
}
if(reversedNum==n)
{
System.out.println(“It is a palindrome”);
}
else
{
System.out.println(“It is not a palindrome”);
}
public static void main(String[] args)
{
int x =121;
palindrom(x);
}
}

Explanation:

Iteration Steps

Iteration 1 : lastDigit=1 ; reversedNum=1 ; orginalNumber=12

Iteration 2 : lastDigit=2 ; reversedNum=12 ; orginalNumber=1

Iteration 3: lastDigit=1 ; reversedNum=121 ; originalNumber=0

<End of Iteration as while condition fails>

If look now checks if the originalNumber is same as reversedNum and prints the result.

Output:

It is a palindrome

Problem 2 :

Given a singly linked list, determine if it is a palindrome.

First, let’s discuss some basics of linked lists.

Definition: Linked List is a data structure that stores a collection of items. Imagine a chain when you try to visualize linked lists. Each ring is called “Node”. Each node has two sections

  • Data.
  • Address of the next node.
Image for post
Singly linked list

Question1: So how are they stored in the memory? Dynamic memory allocation.

Unlike an array, the nodes of the linked list are not stored in a consecutive manner. The best non-technical analogy would be the game of treasure hunt. Each clue paper you find is the data and clue written on it is the memory address of the next node.

Question 2: Can elements of a linked list contain duplicate data? Very important question especially if your problem statement is a “Palindrome”.

The answer is yes. A linked list can have duplicate items. While performing insertion, it doesn’t check for duplicate data.

Question 3: Lastly, can a linked list contain data of different types? Say, the first node as an integer stored in it, Can I store a character in the second node?

Yes, it is possible although you have to make sure the list is declared as List<Object> or List<Serializable>.

What is serializable — well this is topic is huge and it is out of the scope of this post. But I can tell you the basic idea behind serialization. Serializable is used to convert an object(Instance of a class) into bytes so that it can be written to a disk or can even be passed over the network.

Hard-disks or network components are hardware components. And these components don’t understand linked lists or any other data structures. So the object needs to be translated into a type that these hardware components can understand and that type is bytes.

It’s like visiting China without knowing Chinese. You need someone to translate the language for you for better communication. Serializable does this job. It converts the object into bytes and store it in the hard disk or sends the data across the network.

A linked list is much more than what is discussed above and I would suggest you read more on the topic of a linked list while preparing for an interview.

Now going back to the problem statement.

Image for post

Problem solution

//Definition of Node //

public class linkedlist_palindrome
{
Node head;
static class Node
{
int data;
Node next;
public Node(int d) {
data=d;
next=null;
}
}
// Function that chess for Palindrome //
public static void findmid(linkedlist_palindrome splitlist, Node h)
{
Node secondhead;
Node fastpointer=h;
Node slowpointer=h;
while(fastpointer!=null && fastpointer.next!=null)
{
fastpointer=fastpointer.next.next;
slowpointer=slowpointer.next;
}
secondhead=slowpointer.next;
slowpointer.next=null;
Node n1 = secondhead;
Node n2 = n1.next;
while(n1!=null && n2!=null){
Node temp = n2.next;
n2.next = n1;
n1 = n2;
n2 = temp;
}
secondhead.next = null;
//compare two sublists now
Node x= (n2==null?n1:n2);
Node y = h;
while(x!=null)
{
if(x.data != y.data)
System.out.println(“This is not palindrome”);
x = x.next;
y = y.next;
}

Problem Logic:

There are many ways you can find a palindrome in a linked list.

The above solution logic has the following steps,

  1. Split the linked list into two parts. This is done by finding the mid of the list and elements beyond the mid node are considered as the second list. In case of even number of nodes, there will be two mid nodes and the second mid node will be considered as a mid node.
  2. The second part of the list is reversed.
  3. The two lists are compared for equality to determine if the list is a palindrome or not.

The most important part of the above logic is to split the list into two parts. This is done by defining two pointers, one slow pointer and another fast pointer. The slow pointer points to the head and the fast pointer points to the second node. The loop iterates until the fast pointer reaches null. When the fast pointer reaches null, the slow pointer points to the mid value.

In the above example, 3 will be mid-node.

Output

Yes, it is a palindrome

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: