## Amazon Interview Question for Software Development Managers

• 0

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 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.. :))

Comment hidden because of low score. Click to expand.
0

Great solution

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 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.``````

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 ?

Comment hidden because of low score. Click to expand.
0

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

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

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:
sll(){
}
void insert(char name){
Node *n=new Node(name);
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=n;
}
void display(){
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;
while(ptr1!=NULL&&ptr1->next!=NULL){
ptr1=ptr1->next->next;
ptr2=ptr2->next;
}
if(ptr2!=NULL){
}
}
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;
}

Comment hidden because of low score. Click to expand.
0

Can you please write the algorithm and complexity

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

``````public boolean isPallindrome(Node 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);
}``````

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;
}
String s = "";
while (n.next != null) {
n = n.next;
}

return (s.length() <= 1);
}``````

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

Declare a linked list of type string

int size =l1.size();
boolean res = boolean pali( LinkedList l1); //recursive function call;
if (res ==1)
sysout("pali");
else
sysout(not a pali");

{
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;
}
}
}

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;
}

}

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

string str = "";
string copyLL(Node *start)
{
if(start == null) return str;
str = concat(str,start.value);
start = start->Next;
copyLL(start);
}

isPalindrome(string str)
{
int len = len(str);
int i, j;
int count = 0;
for (i = 0, j = len-1; i <(len/2); i++, j--)
if(str[i] == str[j])
count = 1;
if(count != 0) return true;
else return false;
}
}

Name:

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

### Books

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

### 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.