Amazon Interview Question Software Development Managers


Country: India
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
1
of 1 vote

O(N) time, O(1) space: recursive

1. Traverse till middle
2. One pointer at start, second half of the string will recurse till end
3. Keep matching, at first unmatch, break and report false
4. Return true if all matches
(Somewhat tricky to write but optimal)

O(N) time O(1) space:

1. Find length (if not given)
2. Traverse till middle of list
3. Reverse second half of list
4. Keep two pointers, one at start, other at middle
5. Keep comparing until you match them all (i.e., reach till end of second half)
6. If at any point characters don't match break and report false, else true
7. Reverse the second half again to restore or if there is a specification that you can't modify the input.

O(N) time, O(N) space:

If you are asked not to reverse the list then following can be brute force idea:
1. Traverse the list once
2. Make string out of it
3. Check if the string is palindrome

- mag on January 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Question is, to use one char / string variable, not pointer

- Anonymous on January 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its simple..
1) find the middle element of list using slow/fast pointer approach.
2) when u r traversing till middle, keep writing all chars in a temporary string variable
3) when u reach middle, read the temp string backwards and compare that with the next nodes in the list.. :))

- Pappu Pager on January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great solution

- Anonymous on January 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure what is the meaning of "Can use only a string variable"? A java String ?

- Mathew on January 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You cannot construct the string by traversing through the linked list and then reverse it . which means two strings are created.

- Anonymous on January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the list.Save the letters in the string.Check the string for a pallindrome

- Anonymous on January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working Correct


#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;

class Node{
public:
char name;
Node *next;
Node(char n){
name=n;
next=NULL;
}
};
class sll{
public:
Node *head;
sll(){
head=NULL;
}
void insert(char name){
Node *n=new Node(name);
Node *temp=head;
if(head==NULL){head=n;return;}
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=n;
}
void display(){
Node *temp=head;
while(temp!=NULL){
cout<<temp->name<<"-->";
temp=temp->next;
}
}
};
void func(Node *ptr1,Node *ptr2){
if(ptr2==NULL) return;
func(ptr1,ptr2->next);
if(ptr1->name!=ptr2->name) {cout<<ptr1->name<<" not equals to "<<ptr2->name<<endl;
cout<<"Not a palindrome\n";
system("pause");
exit(1);}
*ptr1=*ptr1->next;
}
void checkPalindrome(sll list){
Node *ptr1, *ptr2;
ptr1=ptr2=list.head;
while(ptr1!=NULL&&ptr1->next!=NULL){
ptr1=ptr1->next->next;
ptr2=ptr2->next;
}
if(ptr2!=NULL){
func(list.head,ptr2);
}
}
int main(){
sll list;
string str;
cout<<"Enter a string to check for palindrome: ";
cin>>str;
for(int i=0;i<str.length();i++){
list.insert(str[i]);
}
checkPalindrome(list);
cout<<"Palindrome\n";
system("pause");
return 0;
}

- HarishIITR on January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please write the algorithm and complexity

- Anonymous on January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it even without string variable:

1). Find the middle element, using node->next and node->next->next, and
simultaneously find the length of the list.

2). If the length is odd, delete the middle element.

3). Reverse the second half of the list (recursive method).

4). Compare the first and the second half of the list.

- sergey.a.kabanov on January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about this??

public boolean isPallindrome(Node head) {
		Node n = head;
		String s = "";
		while (n.next != null) {
			if (s.lastIndexOf(n.data) == -1) {
			 s += n.data;
			} else {
				 s.replace(n.data, "");
			}
			n = n.next;
		}
		  
		return (s.length() == 0);
	}

- lj on January 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

oopas my soltion doesn't quite work. Correction to my previous post. Some pallidrome's have 1 character that is not repeated like "radar".

public String adjustString(String nodeString, String s) {		
		if (s.indexOf(nodeString) == -1) {
			 s += nodeString;
			
			} else {
			 s = s.replaceAll(nodeString, "");			
			}	
		return s;
	}
	public boolean isPallindrome(Node head) {
		Node n = head;
		String s = "";
		while (n.next != null) {		
			adjustString(n.data, s);
			n = n.next;
		}
		   adjustString(n.data, s);
		  
		return (s.length() <= 1);
	}

- lj on January 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Declare a linked list of type string

linkedlist<String>l1 = new linkedlist<string>();
int size =l1.size();
boolean res = boolean pali( LinkedList l1); //recursive function call;
if (res ==1)
sysout("pali");
else
sysout(not a pali");


boolean pali(LinkedList L1)
{
Int i,j,size;
for (i = size; i>=0;i++) //Pointing to the last node of the list
{
for (j=0;j<=size;j++)//Pointing to the first node of the list
{
if (l1.get(i) == l1.get(j))// comparison of last node with first node
return 1;
Else
return 0;
}
}
}

- QC on February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This routine doesn't use a string. It traverses the list using 2 pointers - one fast (2x) and one slow to find the middle of the list. Once the middle is found, the middle pointer continues recursively to the end of the list and then each char is compared as the recursive stack unwinds.

{
struct llist {
char c;
struct llist *next;
};

typedef struct llist List;

int isPali(List *list)
{
List *sp = list;
List *fp = list;
List *bp = list;

if (list == NULL) return 0;

while (fp != NULL)
{
sp = sp->next;
fp = fp->next;
if (fp != NULL) fp = fp->next;
}

return pali(&bp, sp);
}

int pali(List **first, List *second)
{
int t;

if (second == NULL) return 1;
t = pali(first, second->next);
if (t == 0) return 0;
if ((*first)->c != second->c) return 0;
*first = (*first)->next;
return 1;
}

}

- Keith Deacon on January 28, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

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. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

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