Amazon Interview Question Software Engineer in Tests SDE1s
Country: India
Interview Type: In-Person
You will also have to take care for the situation when the LL size is even. In that case, there is no middle element per se, so the range to be reversed are the elements [ n/2 ; n-1 ], where "n" is the size of LL.
0 1 2 3 4 5
a->b->c->c->b->a // original LL
a->b->c->a->b->c // reversed at mid-point LL
reversing the 2nd part can be confusing incase length of word is odd, eg: bob
an alter-net approach:
use pointer1 in the start(right). use pointer2 at the end(left). pointer1 moves right to left, pointer2 moves left to right. at any point if the pointer value if don't match its not a palindrome. this check must be done unless the pointer are pointing to same character or consecutive. n/2(even length) or n/2+1(oddlength)
@ the person above, linked list is one direction, not 2. You are thinking about double linked list.
Great idea, but remember to return the linked list back because you may need to use it in the further.
Stack can solve this problem, but as we can't use extra memory, we can still use recursion to simulate stack. size()/2 stacks is ok.
1) Use the two pointer method till first points to middle and second points to end (both even and odd lists should be handled)
2) Reverse the list from head till middle
3) Compare both the lists and report true or false
4) Reverse the first half again and revert the list to its original form
You can simplify this by
1. Find the mid point by using the slow and fast runners and then push the first half to the list to a stack from the slow runner. Note that, at this point slow runner is pointing the middle of the linked list and the elements in the stack are in the reverse order.
2. Iterate from the middle to the end of the list with slow pointer and compare the top of the the stack at each iteration. If they don't match return false.
If you can't use extra storage, then you can solve this recursively:
bool isPalindrome(Node** left, Node* right) {
if (!right) return true;
bool ispal = isPalindrome(left, right->next);
if (ispal == false) return false;
// check if the values are the same
ispal = (right->data == (*left)->data);
// go to next
*left = (*left)->next;
return ispal;
}
Call this function like:
bool isp = isPalindrome(&head, head);
@oOZz: Using a stack to compare the elements will work. This might work faster as you can store the nodes in the stack as you slide the slow runner. You dont need the extra traversals reverse the list and revert it back. But this uses n/2 extra space. Decent solution if extra space is not a concern.
The basic idea is to use recursion. We need to have the notion of a 'mirrorNode' to solve this problem. For ex: the last node is the mirror node of the first, the second last is the mirror node of the second and so on. Based on this idea, a simple recursive trick like the below does the job.
A stack cannot be used for this problem as it will take extra memory.
Full java implementation is below.
package org.murali.algos;
import java.util.Scanner;
import java.util.regex.Pattern;
public class LinkedListCareerCup {
class NodeCareerCup {
Object val;
NodeCareerCup next;
public NodeCareerCup(Object val, NodeCareerCup next) {
super();
this.val = val;
this.next = next;
}
}
NodeCareerCup head = null;
public boolean CheckIfPalindrom() {
if (head == null || head.next == null) {
return true;
}
NodeCareerCup retNode = checkPalindromeRec(head, head);
return retNode != null;
}
public NodeCareerCup checkPalindromeRec(NodeCareerCup current, NodeCareerCup head) {
// last node
if (current.next == null) {
if (current.val.equals(head.val)) {
return head.next;
} else {
return null;
}
}
else {
NodeCareerCup mirrorNode = checkPalindromeRec(current.next, head);
if (mirrorNode != null) {
if (mirrorNode.val.equals(current.val)) {
if (mirrorNode.next == null) {
return head;
}
return mirrorNode.next;
}
else {
return null;
}
}
return null;
}
}
public void AddNode(NodeCareerCup node) {
node.next = head;
head = node;
}
public static void main(String[] args) {
LinkedListCareerCup ll = new LinkedListCareerCup();
Pattern pattern = Pattern.compile(System.getProperty("line.separator") + "|\\s");
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(pattern);
System.out.println("/////////////////////////////////////");
System.out.println("Enter numbers with spaces in-between and hit enter twice. For ex:");
System.out.println("1 2 3 3 2 1\n");
System.out.println("");
System.out.println("/////////////////////////////////////\n");
int i;
while (scanner.hasNextInt()) {
i = scanner.nextInt();
ll.AddNode(ll.new NodeCareerCup(new Integer(i), null));
}
System.out.println("That the given list is a palindrome is " + ll.CheckIfPalindrom());
}
}
// some C/C++ style pseudo code
// needs some validations such as check for invalid pointers and etc..
{{
node* reverse_linked_list( node * head)
{
if (head== NULL || head->next==NULL)
{
return head;
}
node *new_head = reverse_linked_list(head->next);
head->next->next = head;
head->next = NULL;
return new_head;
}
Node * MiddleOfList(Node *head)
{
node * middle ;
node * temp = head;
while(temp ->next!=NULL)
{
temp =temp ->next->next
middle = middle->next
}
return middle;
}
BOOL palindrome (Node *head)
{
Node *middle = MiddleOfList(head) ;
head = reverse_linked_list(middle)
while (middle ->next != NULL)
{
if (middle->data == head->data )
continue;
else return false ;
}
return true
}
}}
an alter-net approach:
use pointer1 in the start(right). use pointer2 at the end(left). pointer1 moves right to left, pointer2 moves left to right. at any point if the pointer value if don't match its not a palindrome. this check must be done unless the pointer are pointing to same character or consecutive. n/2(even length) or n/2+1(oddlength)
What a crazy fellow u are? Do you think it is possible to traverse both ways in a linked list? Or are u assuming a Doubly-Linked List?
there's a recursive approach to this
bool isPalindrome ( Node* head, Node*& compare, Node* localNext )
{
if ( NULL == localNext )
{
return true;
}
else if ( NULL != localNext->next && head == compare )
{
//Still looping
return isPalindrome ( head, compare, localNext->next );
}
if ( compare->data != localNext->data )
{
return false;
}
else
{
compare = compare->next;
return true;
}
}
given singly linked list
how you find number of nodes and middle of the node
example 1->2->3->4->5->4->3->2->1
If n is length of linked list, upper bound of n/2. In odd case, you have to ignore n/2 +1 and in even case, you should not.
if there is a limitation on extra memory then Node temp, and data compare would need to be passed to the isPalindrome class.
public boolean isPalindrome(Node head, Node temp, char compare){
while(head != null){
compare = head.data;
temp = head;
while(temp.next != null){
temp = temp.next;
compare = temp.data;
}
temp = null;
if(!((head.data).equals(compare)){
return false;
}
head = head.next;
}
return true;
}
if there is a limitation on extra memory then Node temp, and data compare would need to be passed to the isPalindrome class. (i didnt realize that i had not logged in when i posted the solution before)
public boolean isPalindrome(Node head, Node temp, char compare){
while(head != null){
compare = head.data;
temp = head;
while(temp.next != null){
temp = temp.next;
compare = temp.data;
}
temp = null;
if(!((head.data).equals(compare)){
return false;
}
head = head.next;
}
return true;
}
Use recursion to go to the middle of the linkedlist and then when you reach there, there are two parts, first one keeps reading the node data backwards as part of recursion popping out, while the second pointer keeps going forward - reading the data from next nodes. Keep comparing data for both of these and check whether it is palindrome or not till last. a sample java code snippet is below
strnode_ is the head node which invokes isPalindrome(strnode_) to check for palindrome.
public boolean isPalindrome(Node str)
{
if(str!=null){
if(count<midlen-1)
{
count++;
strnode_ = strnode_.next_;
getRevChar(str.next_);
}
if(isPalindrome){
if(isOdd){
strnode_ = strnode_.next_;
isOdd = false;
}
strnode_ = strnode_.next_;
isPalindrome = str.data_ == strnode_.data_ ? true : false;
return true;
}
else
{
return false;
}
}
return false;
}
No need to modify the list.
1- Traverse till middle element.
2- Keep another pointer at first element.
3- Keep matching values on these two pointers till the second pointer reaches end of list. If all matches then palindrome else not.
you are the closest of the bunch, but your code checks for AckAck instead of AckkcA.
Implement getLength(Node) and a getNth(Node,int) methods
use getNth(head,int) to 'march backwards' from the midpoint.
no recursion or allocation involved.
O(n^2) -- n calls to getNth, which is O(n)
recursive, modifying, or allocating implementations are O(n)
The recursive approach breaks the "extra memory" rule. Each recursion pushes another Node reference onto the stack. Given a string of N characters, there will be N/2 levels of recursion, each with a value on the stack. The stack frame will have a value for each parameter passed to the recursive routine, so passing two parameters pushes two Node references per recursion. Also, stack memory is more limited than heap memory.
slow = head; fast=head
while(fast->next != null && fast->next->next!=null)
//fast->next = null odd case
//fast->next->next = null even case
{
fast = fast->next->next;
slow = slow->next;
}
start = head;
mid = slow -> next;
while(mid!= null)
{
if(mid.val != start.val)
return false; // not palindrome
mid = mid -> next;
start = start -> next;
}
return true; // palindrome case
#include <stack>
using namespace std;
class Node
{
public:
char data;
Node* next;
Node():next(NULL){}
};
bool findPalindrome(Node* root)
{
if(!root)
return false;
Node* t1=root;
Node* t2=root;
stack<char> st;
bool end=false;
//bool odd=false;
while (true)
{
if (t1==NULL)
break;
if(!end)
{
st.push(t1->data);
}
else
{
char ch = st.top();
if(t1->data!=ch)
return false;
st.pop();
}
if(t1)
t1=t1->next;
if(t2)
{
t2=t2->next;
if(t2)
t2=t2->next;
else
{
st.pop();
}
}
if(!t2)
{
end=true;
}
}
return true;
}
1> Scan the linked list to get the count of elements(n).
2> Set the middle as floor(n/2).
3> Now maintain a counter and scan the linked list till the middle is reached, While scanning add the elements in a stack.
4> Now move from the middle one element at a time and pop the element from the stack and compare.
5> If mismatch, not a palindrome
6> If matched till the end of the linked list and the stack is empty, then it is palindrome.
I think this can be done in linear time, we keep two pointers: one is slow and the other is fast, slow move forward one step and fast move forward two steps, then when fast is null or fast->next is null, slow points to the middle node of the list, at the same time, we use stack to keep nodes the slow has ever pointed to. Then move to slow to next, and compare the top value of stack with the value slow points to until slow is null or stack is empty. here are my codes:
#include<iostream>
#include<stack>
#include<string>
using namespace std;
typedef struct node_s {
char val;
struct node_s* next;
}node_t;
node_t* createList(char* s) {
node_t* head = NULL;
node_t* temp = NULL;
node_t* p = NULL;
while (*s) {
p = (node_t*)malloc(sizeof(node_t));
p->val = *s;
p->next = NULL;
if (NULL == head) {
head = p;
} else {
temp->next = p;
}
temp = p;
s++;
}
return head;
}
void destroyList(node_t* head) {
node_t* p = head;
while (p) {
head = p->next;
free(p);
p = head;
}
}
bool isPalindrome(node_t* head) {
stack<node_t*> m_stack;
node_t* slow = head;
node_t* fast = head;
m_stack.push(slow);
while (fast->next && fast->next->next) {
slow = slow->next;
m_stack.push(slow);
fast = fast->next;
fast = fast->next;
if (NULL == fast->next)
m_stack.pop();
}
slow = slow->next;
node_t* temp = NULL;
while (slow && !m_stack.empty()) {
temp = m_stack.top();
m_stack.pop();
if (slow->val != temp->val)
return false;
slow = slow->next;
}
if (slow || !m_stack.empty())
return false;
return true;
}
int main(int argc, char* argv[]) {
char s[] = "12345678987654321";
node_t* head = createList(s);
if (isPalindrome(head))
cout << "yes" << endl;
else
cout << "non" << endl;
destroyList(head);
cin.get();
return 0;
}
Traverse the linked list and populate a Hashtable with the data and a count. If the data is present in the Hashtable increment the count, if not set the count as 1. Complexity -- O(n),
where n is the length of the linked list
Using the keySet method of a HashTable, traverse through each key of the Hashtable. Extract the count value of each key using it's get method.
With an if condition check to see
1) If the value is 1 , increment a counter to 1. If (nested if ) the value of the counter is greater than 1 break out of the loop by returning false. [Odd lengthed palindromes]
2) Else if the value != 2, return false
3) Else return true.
here is a method in ruby using an array to check if the list is a palindrome
def is_palindrome?
current = @head
full_list = []
while current.next_node != nil
full_list += [current.value.to_s]
current = current.next_node
end
full_list += [current.value.to_s]
full_list == full_list.reverse ? true : false
end
Go to the middle and reverse the second part of the linked list
- DashDash May 14, 2013Now we have 2 pointers one pointing to the first element and the other to the middle element. Compare and return true if pallindrome