CareerCup

Step 1. Find the middle element of the linked list - This can be done in linear time by moving two pointers; one at 1x speed and the other at 2x speed. The pointer moving at 1x points to the middle when thepointer moving at 2x hits the end.

Step 2: Reverse the second part of the linked list (from middle to end) using recurssion - This can be done in linear time. Refer to linearspacetime.blogspot.com/#!/2012/05/reverse-singly-linked-list.html

Step 3: Use two pointers; one from the original start node and the other from the start of now reversed second part of the list. Move those pointers to their next nodes and compare. If they are equal till they hit the middle portion of the list, the linked list contains a palindrome string.

Note that other minor conditions need to be checked which I have not written above.

bool IsPalindrome(list*& left, list* right) {
    if (!right) {
       return true;
    }
    bool result =  IsPalindrome(left, right->next);
    if (result) {
        result = (left->data == right->data);
    }
    left = left->next;
    return result;

}

void Reverse(Node **List)
{
	Node *First = *List;
	Node *Prev  = NULL;
	Node *Next  = NULL;

	while(First)
	{
		Next = First->Next;	
		First->Next = Prev;
		Prev = First;
		First = Next;
	}

	*List = Prev;
}

bool IsPalindrome(Node *List)
{
	if(!List || !List->Next)
		return (true);
	else
	{
		Reverse(&(List->Next));
		return ((List->Data == List->Next->Data) && (IsPalindrome(List->Next->Next)));
	}
}

approchs:-
1)you can use internal stack.recursively call the funtion & check with first and last.increment accordingly.
2)move one pointer to the middle of list then revrse the first list.then check the first half and second half.

int palindrome(Node *head)
{
	Node *curr = head;
	int n = 0;
	while(curr)
	{
		n++;
		curr = curr->next;
	}
		
	Node *first = head;
	Node *second;
	for(int i=0; i<n/2; i++)
	{
		second = head;
		for(int j=1; j <(n-i); j++)
		{
			second = second->next;
		}
		if(first->data == second->data)
			first = first->next;
		else
		 return 0;
	}
    return 1;
}

static bool IsMyPalindrom( list* node )
{
    list* begin = node->GetFirst();
    list* end = node->GetLast();

    while( begin && end && begin->data == end->data && begin != end )
    {
        if( begin == end || begin->next == end || begin->next == end->prev )
        {
            return true;
        }
        begin = begin->next;
        end   = end->prev;
    }
    return begin == end;
}

CareerCup

Questions
Salaries
Forum
Resume
Chat
Blog
RSS
Sign In ▼

Amazon Interview Question for Software Engineer / Developers

amazon-interview-questions 16 Answers

Consider a singly linked list of characters. Find if the linked list is palindrome or not. Without using another DS, in-place checking was preferred.
- KSS on May 08, 2012 in United States
Amazon Software Engineer / Developer Algorithm



Country: United States
Interview Type: In-Person
More Questions from This Interview


2
of 2 vote

Step 1. Find the middle element of the linked list - This can be done in linear time by moving two pointers; one at 1x speed and the other at 2x speed. The pointer moving at 1x points to the middle when thepointer moving at 2x hits the end.

Step 2: Reverse the second part of the linked list (from middle to end) using recurssion - This can be done in linear time. Refer to linearspacetime.blogspot.com/#!/2012/05/reverse-singly-linked-list.html

Step 3: Use two pointers; one from the original start node and the other from the start of now reversed second part of the list. Move those pointers to their next nodes and compare. If they are equal till they hit the middle portion of the list, the linked list contains a palindrome string.

Note that other minor conditions need to be checked which I have not written above.
- Anonymous on May 08, 2012

what does the "DS" mean?....囧。。。
- kurskk141 on May 09, 2012

DS means Data Structure.
- Learner on May 09, 2012

also it will always return true
- what if left = 0 on May 11, 2012
Reply to Comment
1
of 1 vote

bool IsPalindrome(list*& left, list* right) {
if (!right) {
return true;
}
bool result = IsPalindrome(left, right->next);
if (result) {
result = (left->data == right->data);
}
left = left->next;
return result;

}

- dumbhead on May 09, 2012

It is a singly link list not the Binary tree.
- akshay.amu.1111 on May 09, 2012

yes it is. the call should be as IsPalindrome(head,head);
- dumbhead on May 10, 2012

Can we have a early return if we check for left == right?

And can you throw some light on how *& works?

I came up with a similar solution but by declaring the left pointer as static.

isPalindrome(static List *ptr1, List *ptr2).
- Curious on May 11, 2012

@dumbhead,
Your solution will work when left and right are 2 different variables and does not point to same memory location. And left has to be a global variable and should be visible accross function calls. Am I right?
- Ragavenderan on May 11, 2012

the space complexity of your solution is O(n) becoz of memory stack, so i guess this is not optimal
- Hei on May 13, 2012
Reply to Comment
0
of 0 vote


void Reverse(Node **List)
{
Node *First = *List;
Node *Prev = NULL;
Node *Next = NULL;



while(First)
{
Next = First->Next;
First->Next = Prev;
Prev = First;
First = Next;
}


*List = Prev;
}


bool IsPalindrome(Node *List)
{
if(!List || !List->Next)
return (true);
else
{
Reverse(&(List->Next));
return ((List->Data == List->Next->Data) && (IsPalindrome(List->Next->Next)));
}
}

- John on May 09, 2012

@John
You are recreating an entire reversed list. This is the ADDITIONAL DS that we are not supposed to use.
- Learner on May 09, 2012

No I'm not!
where do you see a recreation of the entire list ?
I do the reverse on the list itself (using double pointer). and the comparison on the list itself. I do use recursion which implicitly means that I'm using a stack but there is nothing wrong with using recursion. The entire operation is happening on the same list (no additional lists).
- John on May 09, 2012
Reply to Comment
0
of 0 vote

approchs:-
1)you can use internal stack.recursively call the funtion & check with first and last.increment accordingly.
2)move one pointer to the middle of list then revrse the first list.then check the first half and second half.
- Anonymous on May 10, 2012
Reply to Comment
0
of 0 vote


int palindrome(Node *head)
{
Node *curr = head;
int n = 0;
while(curr)
{
n++;
curr = curr->next;
}

Node *first = head;
Node *second;
for(int i=0; i<n/2; i++)
{
second = head;
for(int j=1; j <(n-i); j++)
{
second = second->next;
}
if(first->data == second->data)
first = first->next;
else
return 0;
}
return 1;
}

- Mickey on May 10, 2012
Reply to Comment
0
of 0 vote


static bool IsMyPalindrom( list* node )
{
list* begin = node->GetFirst();
list* end = node->GetLast();



while( begin && end && begin->data == end->data && begin != end )
{
if( begin == end || begin->next == end || begin->next == end->prev )
{
return true;
}
begin = begin->next;
end = end->prev;
}
return begin == end;
}

- LBaralgeen on May 11, 2012
Reply to Comment
Subscribe to future comments.


Add a Comment
Name:

Writing Code? Surround your code with

and

to preserve whitespace.

Add Question
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.

How Can You Help CareerCup?

NEW! Cracking the Coding Interview iPhone App. Search for it on the iPhone / iPad App Store.
Top Companies

Amazon (3031)
Microsoft (1347)
Bloomberg LP (541)
Google (478)
Adobe (219)
Yahoo (201)
NVIDIA (166)
Qualcomm (166)
Goldman Sachs (142)
Epic Systems (113)
More Companies »

Top Jobs

Software Engineer / Dev... (6027)
Software Engineer in Te... (597)
Financial Software Deve... (242)
Developer Program Engin... (142)
Testing / Quality Assur... (95)
Program Manager (68)
Analyst (62)
Development Support Eng... (58)
Virus Researcher (25)
Quality Assurance Engin... (21)
More Jobs »

Top Topics

Algorithm (3079)
Coding (663)
Data Structures (358)
C (358)
C++ (356)
Terminology & Trivia (294)
Java (282)
Brain Teasers (237)
Object Oriented Design (208)
Arrays (203)
More Topics »

Chat is disabled. Don't you want to hear what people are chatting about? Enable Chat.
Report a Bug or Issue
Books

The Google Resume is a comprehensive book walking you through every aspect of getting a job at a top tech company, while Cracking the Coding Interview focuses on software engineering interviews.

Learn More
Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More
Resume Review

Most engineers make critical mistakes on their resumes. We can fix your resume with our custom resume review service. Or, sign up for our expedited Grade My Resume service, and get results more quickly.

Learn More
Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More
Information

Team, Contact & About
Chat Room
Chat Room Guide
Salaries
RSS
Behavioral Preparation Grid
Sample Resumes

Products

Cracking the Coding Interview
The Google Resume
CtCI iPhone App
Videos

Services

Mock Interviews
Grade My Resume
Resume Review
Wiser Profile (LinkedIn Review)

Social

CareerCup on Facebook
CtCI on Facebook
Gayle McDowell on Facebook
CareerCup on Twitter
Gayle on Twitter

CareerCup.com © 2012

public static void main(String[] args) {
		String arr[] = { "plates", "stop", "staple", "pots", "meat", "not", "pot", "team" };//read from file
		HashMap<String, TreeSet<String>> hashMap = new HashMap<String, TreeSet<String>>();
		for (int i = 0; i < arr.length; i++) {
			String s = arr[i];
			char charr[] = s.toCharArray();
			Arrays.sort(charr);
			String sorted = new String(charr);
			if (hashMap.containsKey(sorted))
				hashMap.get(sorted).add(s);
			else {
				TreeSet<String> ts = new TreeSet<String>();
				ts.add(s);
				hashMap.put(sorted, ts);
			}
		}
		System.out.println(hashMap);
	}

Following is the algorithm to check whether the singly link-list is palindrome or not in O(N) time and O(1) space.
Algorithm is as follows:
1. find the length of the link-list in O(n) time..
2. loop through half of the length.. floor(length(list)/2)...
2.1 extract the node from the list and push it to stack (in-place).
2.2 advance the current node pointer.

3.0 if length of list is Odd advance the current list pointer by 1.

4.0 loop till both the stack list pointer & current pointer is not NULL
4.1 compare the elements to see if they don't match return false.

5.0 return true;

following is the code snippet of the idea. Please suggest improvements

Note: the sub-list are not merged into single list but it can be easily done
using the same logic as create_stack method.

int length(node* h) {
	int l = 0;
	while (h) {
		++l;
		h = h->next;
	}
	
	return l;
}

node* create_stack(node*& h, node* n) {
	node* t = n->next;
	n->next = h;
	h = n;
	
	return t;
}

bool is_palindrome(node* h) {

	int len = length(h);
	node* l = h;
	node* r = NULL;
	
	
	for(int i=1; i<=len/2; ++i)
		l = create_stack(r, l);
		
	if (len % 2 != 0)
		l = l->next;
	
	while (l != NULL && r != NULL) {
		if (l->x != r->x)
			return false;
		
		l = l->next;
		r = r->next;
	}
	
	return true;
}