Amazon Interview Question Software Engineer / Developers
Team: hyderabad
Country: India
Interview Type: Phone Interview
Hi Ashish, can you please share the interview experience as well along with the questions. It will be very helpful . Thanks Ashish.
hi ashish.. it was just this one question on telephonioc round.. i gave a different approach and and i was asked to narrate my code line by line over phone. and then he did debugging and testinng of the code . thats it !
Guys, please don't give negative votes to the best solutions. Atleast try to understand the solution before giving it a vote. This solution is the best available on this post :)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
}*HEAD=NULL,*ptr=NULL,*p=NULL;
void display(struct node *pass)
{
ptr=pass;
if(ptr==NULL)
printf("list is empty");
while(ptr!=NULL)
{
printf("%d",ptr->data);
ptr=ptr->link;
}
}
void reverse()
{
struct node *even,*posteven,*ptr1;
even=NULL;posteven=NULL;
ptr1=HEAD;
while(ptr1!=NULL && ptr1->link!=NULL && ptr1->link->link!=NULL)
{
even=ptr1->link;
ptr1->link=ptr1->link->link;
even->link=posteven;
posteven=even;
ptr1=ptr1->link;
}
if(ptr1->link==NULL | ptr1==NULL) //u should check dis also
ptr1->link=even;
else
{
even=ptr1->link;
even->link=posteven;
posteven=even;
ptr1->link=even;
}
}
void main()
{
int l;
l=0;
while(l==0)
{
p=(struct node*) malloc(sizeof(struct node));
p->link=NULL;
printf("enter the num");
scanf("%d",&p->data);
if(HEAD==NULL)
{
HEAD=p;
ptr=p;
}
else
{
ptr->link=p;
ptr=ptr->link;
}
printf("press 0 to add more");
scanf("%d",&l);
}
display(HEAD);
reverse();
printf("\n");
display(HEAD);
}
there is a error in ur code..check these conditions also..i posted the correct code above
while(ptr1!=NULL && ptr1->link!=NULL && ptr1->link->link!=NULL)
{
even=ptr1->link;
ptr1->link=ptr1->link->link;
even->link=posteven;
posteven=even;
ptr1=ptr1->link;
}
if(ptr1->link==NULL | ptr1==NULL) //u should check dis also
ptr1->link=even;
else
{
even=ptr1->link;
even->link=posteven;
posteven=even;
ptr1->link=even;
}
I believe I've fixed the slight error in your code - your original code never would always result in a runtime error (for both even and odd length input)
Your code yielded this when I debugged it:
(ODD LENGTH) input: 1->9->3->8->5->7->7->null
output: 1->3->5->7->null and 7->8->9->null, then would give a runtime error at line (l->next = l->next->next;), as you would be trying to access the next field of a null value.
(EVEN LENGTH) input: 1->9->3->8->5->7->null
output: 1->3->5->null and 7->8->9->null, then when you attempt to connect the two lists in the last line (l->next=pre_evenNode;) you would run into a runtime error again as you are trying to access the next field of a null value. It is even guaranteed that l will be null because it is the only way to exit your while loop..
main(){
//head represents the head of the input list as shown above;
list *l=head;
list *evenNode;
list *pre_evenNode;
pre_evenNode = NULL;
if (head == NULL)
return;
while(l->next != NULL){
evenNode=l->next;
l->next=l->next->next;
evenNode->next=pre_evenNode;
pre_evenNode=evenNode;
if (l->next != NULL)
l=l->next;
}
l->next=pre_evenNode;
}
@"Your code does not work with this list
1->4->3->2->5->2
- other_anonym on May 07, 2012"
Previously I assumed that the odd/even values must converge to a median value. If this is not the case, then a little extra work must be done at the end (pseudocode for comparing values) I believe the algorithm is still O(n) and is still inplace with any input:
main(){
//head represents the head of the input list as shown above;
list *l=head;
list *evenNode;
list *pre_evenNode;
pre_evenNode = NULL;
// no list, no dice
if (head == NULL)
return NULL;
// unzip the list into two lists:
while(l->next != NULL){
evenNode=l->next;
l->next=l->next->next;
evenNode->next=pre_evenNode;
pre_evenNode=evenNode;
if (l->next != NULL)
l=l->next;
}
// if there is no conflict, connect the two lists and return.
if ( I < pre_evenNode) {
l->next=pre_evenNode;
return head;
}
// the following code simply zips together the two sorted lists
list *a, *b;
a = head;
b = pre_evenNode;
// assign smallest value to head
if (a < b) {
head = a;
a = a->next;
} else {
head = b;
b = b->next;
}
curr = head;
// iterate through both lists until 1 is done
while ( (a!=NULL) && (b!=NULL) ) {
if (a<b) {
curr->next = a;
a = a->next;
} else {
curr->next = b;
b = b->next;
}
}
// finish the other list
while ( a!=NULL) {
curr->next = a;
a = a->next;
}
while ( b!=NULL) {
curr->next = b;
b = b->next;
}
// return new sorted list
return head;
}
Your Idea is not generic dude ,does not work with the following List :(
13->19->23->8->25->7->27
Sort in terms of three elements to get the result...
1->9->3->8->5->7->7
Step a: 1-3-9-8-5-7-7
Step b:1-3-8-9-5-7-7
Step c:1-3-5-8-9-7-7
Step d: 1-3-5-7-8-9-7
Step e: 1-3-5-7-7-8-9
Actually I am not really sure if we are supposed to sort the list, or always return the list with the order of the even nodes reversed. The example given is ambiguous, but I suspect it's the latter, otherwise the question doesn't need to explicitly assume that the even nodes are in decreasing order.
it is just the sorting of link list so you can use any sorting technique and sort th elink list..
class Node
{
int data;
Node next;
Node(int data)
{
this.data=data;
this.next=null;
}
Node(Node n)
{
this.data=n.data;
this.next=null;
}
public int getData()
{
return data;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next=next;
}
}
class LinkedList
{
Node first;
LinkedList(Node first)
{
this.first=first;
}
public void insertLast(Node n)
{
if(first==null)
{
first=n;
}
else
{
Node temp=first;
while(temp.getNext()!=null)
{
temp=temp.getNext();
}
temp.setNext(n);
}
}
public void insertFirst(Node n)
{
if(first==null)
{
first=n;
}
else
{
n.setNext(first);
first=n;
}
}
Node getFirst()
{
return first;
}
public void mergeList(LinkedList l2)
{
Node temp=this.first;
while(temp.getNext()!=null)
{
temp=temp.getNext();
}
temp.setNext(l2.first);
}
public void printList()
{
Node temp=first;
while(temp.getNext()!=null)
{
System.out.println(temp.getData());
temp=temp.getNext();
}
System.out.println(temp.getData());
}
}
class Arrange
{
public static void main(String a[])
{
LinkedList l=new LinkedList(null);
for(int i=0;i<a.length;i++)
{
Node n=new Node(Integer.parseInt(a[i]));
l.insertLast(n);
}
l.printList();
LinkedList l1=new LinkedList(null);
LinkedList l2=new LinkedList(null);
System.out.println("l1 l2 created");
Node temp=l.getFirst();
int i=1;
while(temp.getNext()!=null)
{
if(i==1) { l1.insertLast(new Node(temp));i=0;}
else {l2.insertFirst(new Node(temp));;i=1;}
temp=temp.getNext();
}
if(i==1){l1.insertLast(new Node(temp));}
else{l2.insertFirst(new Node(temp));;i=1;}
System.out.println("Now l1:");
l1.printList();
System.out.println("Now l2:");
l2.printList();
System.out.println("Now l1l2:");
l1.mergeList(l2);
l1.printList();
}
}
If this is a doubly linked list, we can do the sorting in place in O(n) time.
its just a merge starting from the tail of the linked list, where one array is starting at location 1, and other at n (for odd length)
eg: 1->9->3->8->5->7->7
lst1: 1->3->5->7<=end pointer for increasing list
lst2: 9->8->7
^start pointer for decreasing list
now merge from the end of the original list
If this is a doubly linked list, we can do the sorting in place in O(n) time.
its just a merge starting from the tail of the linked list, where one array is starting at location 1, and other at n (for odd length)
eg: 1->9->3->8->5->7->7
lst1: 1->3->5->7;7<=end pointer for increasing list
lst2: 9->8->7; 9<=start pointer for decreasing list
now merge from the end of the original list
It seems like the easiest way to do this would be to keep a stack of the even values. When you reach the end of the linked list, you just pop the stack and add the nodes to the end of the linked list.
Psuedo code
LinkedListNode sortLL (LinkedListNode head)
LinkedListNode curr = head;
LinkedListNode tmp = null;
Stack nums = new Stack();
while(curr != null)
if(curr.next != null && curr.next.next != null)
push curr.next onto your stack
assign curr.next to curr.next.next
increment to the next node, curr = curr.next
else
while(stack is not empty)
assign tmp to curr.next (should be null since curr is at the end of the list)
assign curr.next to stack.pop()
assign curr.next.next to the end of the list (tmp)
increment to the next node, curr = curr.next
return head (which should still be pointing to the head of your linked list)
return null (if list was empty)
By the logic of this solution, the time complexity would be O(n+m) where n is the odd number nodes and m is the even. It seems counter intuitive, since there is a while loop within a while, which should be n^2. But if you look at how the list is looped through you see that the first while loop only goes through every other node (pushing the even nodes to the stack as it skips over them).
Then in the second while loop, in the else block, loops through only the values that were pushed into the stack (i.e. m which were the even placed nodes). So technically O(n+m) is O(n) where n is the total number of nodes, making this an in place solution.
Assumptions made are:
1. Even number of nodes, where 1st node is odd and last node is even
2. The last odd node is <= the last even node
I used a similar approach, except I cheated a little by storing the node values instead. That way I don't have to modify the pointers at all and can just update the values of the even nodes. I also used a FIFO queue instead of a LIFO stack.
void reverse(Node n, boolean even, ArrayDeque<Integer> queue) {
if(n == null) {
return;
} else if(even) {
queue.addFirst(n.value);
reverse(n.next, false, queue);
n.value = queue.removeLast();
} else {
reverse(n.next, true, queue);
}
}
node *change(node *head) {
if (!head || !head->next)
return head;
node *odd,*even,*temp1,*temp2;
temp1 = odd = head;
temp2 = even = head->next;
bool flag1 = true,flag2 = true;
while(flag1 || flag2) {
if (temp1 && temp1->next) {
temp1->next = temp1->next->next;
temp1 = temp1->next;
}
else
flag1 = false;
if (temp2 && temp2->next) {
temp2->next = temp2->next->next;
temp2 = temp2->next;
}
else
flag2 = false;
}
temp2 = reverse(even);
temp1 = odd;
while(temp1->next)
temp1 = temp1->next;
temp1->next = temp2;
return odd;
}
I have used a different set (1,2,3,4,5,6,7) and sorted the list as expected. You can change the value while trying yourself to the one given in question:
CODE:::
import java.awt.List;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListSample {
public static void main(String[] args) {
LinkedList LList = new LinkedList();
Iterator LList2;
LList.add(0, 1);
LList.add(1, 2);
LList.add(2, 3);
LList.add(3, 4);
LList.add(4, 5);
LList.add(5, 6);
LList.add(6, 7);
System.out.println("THe Linked List is:"+LList);
System.out.println("THe Linked List is:"+LList.size());
separateLinkList(LList);
}
public static void separateLinkList(LinkedList lList) {
int firstlement = (Integer) lList.element();
LinkedList even = new LinkedList();
LinkedList odd = new LinkedList();
for(int i=0; i<lList.size(); i++) {
int count = 0;
int a = i%2;
if (a == 0) {
odd.add(count, lList.get(i));
count++;
}
else if (a == 1) {
even.add(count, lList.get(i));
count++;
}
}
Collections.sort(odd);
odd.addAll(even);
System.out.println("The Odd Linked List is:"+odd);
}
}
import java.awt.List;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListSample {
public static void main(String[] args) {
LinkedList LList = new LinkedList();
Iterator LList2;
LList.add(0, 1);
LList.add(1, 2);
LList.add(2, 3);
LList.add(3, 4);
LList.add(4, 5);
LList.add(5, 6);
LList.add(6, 7);
System.out.println("THe Linked List is:"+LList);
System.out.println("THe Linked List is:"+LList.size());
separateLinkList(LList);
}
public static void separateLinkList(LinkedList lList) {
int firstlement = (Integer) lList.element();
LinkedList even = new LinkedList();
LinkedList odd = new LinkedList();
for(int i=0; i<lList.size(); i++) {
int count = 0;
int a = i%2;
if (a == 0) {
odd.add(count, lList.get(i));
count++;
}
else if (a == 1) {
even.add(count, lList.get(i));
count++;
}
}
Collections.sort(odd);
odd.addAll(even);
System.out.println("The Odd Linked List is:"+odd);
}
}
82 int count = 1;
83 Node<T> * tempList = header;
84 Node<T> * oddList = NULL;
85 Node<T> * evenList = NULL;
86 Node<T> * nextNode = NULL;
87 if(header == NULL)
88 return ;
89 while(tempList != NULL)
90 {
91 nextNode = tempList->next;
92 if(count % 2 != 0)
93 {
94 if(oddList == NULL)
95 oddList = tempList;
96 else {oddList->next = tempList;oddList = oddList->next;}
97 }
98 else
99 {
100 if(evenList == NULL)
101 {
102 evenList = tempList;
103 evenList->next = NULL;
104 }
105 else { tempList->next = evenList; evenList = tempList;}
106 }
107 count++;
108 tempList = nextNode;
109 }
110 oddList->next = evenList;
111 return ;
Keep connecting the even nodes and while at the same time remove odd nodes and connect in the reverse way. At the end of traversal you would have two linked list :
1. Even nodes linked list
2. Reversed odd node linked list.
You would need 3 pointers and one temp node variable:
1. Pointer 1 : even -- which would traverse on even nodes only.
2. Pointer 2 : odd -- which would traverse on odd nodes only.
3. Pointer 3 : revHead -- head of reversed odd linked list.
4. Temp variable -- temporarily hold the odd node.
private static void modify(Node head)
{
if(head == null ||head.next == null || head.next.next == null)
{
return ;
}
Node even = head;
Node odd = head.next;
Node revhead = null;
Node temp = null;
while(true)
{
temp = odd;
if(odd.next != null)
{
odd =odd.next.next;
}else
{
break;
}
if(even.next != null)
{
even.next = even.next.next;
even = even.next;
}else
{
break;
}
temp.next = revhead;
revhead = temp;
}
temp.next = revhead;
revhead = temp;
}
void transform() {
node *first = head;
node *middle = head->next;
node *second = middle;
node *fwdFirst = second->next;
node *fwdSecond = fwdFirst->next;
while (fwdFirst) {
first->next = fwdFirst;
second->next = fwdSecond;
first = first->next;
second = second->next;
if (fwdSecond)
fwdFirst=fwdSecond->next;
else
fwdFirst = NULL;
if (fwdFirst)
fwdSecond = fwdFirst->next;
else
fwdSecond = NULL;
}
first->next = middle;
}
node *pattern(node *head)
{
if(head == NULL)
return NULL;
node *h1,*h2,*p1,*p2;
h1=head;
h2=head->next;
p1=head;
p2=NULL;
if(head->next != NULL)
{
p2=head->next->next;
h2->next = NULL;
}
while(p2 != NULL)
{
p1->next = p2;
p1 = p2;
if(p1->next != NULL)
{
p2 = p1->next->next;
p1->next->next = h2;
h2 = p1->next;
}
else
p2 = NULL;
}
p1->next = h2;
return head;
}
void arrageNodesImpl( LinkedListNode* node,LinkedListNode *oddnodes)
{
if(node)
{
if(node->next != NULL)
{
LinkedListNode *localoddnode=node->next;
node->next=node->next->next;
arrageNodesImpl(node->next,localoddnode);
LinkedListNode *iterator=node;
while(iterator->next)
{
iterator=iterator->next;
}
iterator->next=localoddnode;
localoddnode->next=NULL;
}
}
return;
}
Assuming its a singly linked list, here is a solution in O(n) time.
logic :
1. Construct two separate linked lists. One with values in odd position & other with values in even position.
The second list would be constructed in reverse. i.e., first 9 will be added, then 8 will be added which would point to 9 as the "next", then 7 will be added to the list, which would be point to 8 as "next".
2. Point the last node of first list to the head of the second list.
here is the working java code :
class LL {
int data;
LL next;
LL(int data, LL next) {
this.data = data;
this.next = next;
}
}
public static LL rearrange(LL root) {
LL list1 = root;
LL list2Head;
LL list2End;
LL tempHead = new LL(list1.data,null), tempEnd = null, temp;
list2Head = tempHead;
list2End = null;
list1 = list1.next;
while(list1 != null) {
temp = new LL(list1.data,tempEnd);
tempEnd = temp;
list1 = list1.next;
if(list1 != null) {
temp = new LL(list1.data, null);
tempHead.next = temp;
tempHead = tempHead.next;
list1 = list1.next;
}
}
tempHead.next = tempEnd;
return list2Head;
}
input linkedlist= 1->9->3->8->5->7->7
- ashish April 10, 2012output linked list should be 1->3->5->7->7->8->9
main(){
//head represents the head of the input list as shown above;
list *l=head;
list *evenNode;
list *pre_evenNode;
pre_evenNode=NULL;
while(l!=NULL){
evenNode=l->next;
l->next=l->next->next;
evenNode->next=pre_evenNode;
pre_evenNode=evenNode;
l=l->next;
}
l->next=pre_evenNode;
}
explaination: link all odd nodes one after other and reverse all even nodes while traversing for odd nodes. Finally link tha last odd node with the last even node;