Amazon Interview Question
Software Engineer in Tests// returns head of new list.
public Node reverseInPairs(Node head) {
Node first = head;
Node second = first.next;
if (first == null || second == null) {
return head; // can't reverse a singleton/empty list. head remains the same
}
while (first != null && second != null) {
temp = first.next.next;
second.next = first;
first = temp;
second = first.next;
}
return head.next;
}
Guess above code doesn't work. After first iteration, first pair gets disjoint from the rest. Can u check?
Sandy, You are right.
We need to add one line to the while loop above as in here:
while (first != null && second != null) {
temp = first.next.next;
second.next = first;
first.next = temp;
first = temp;
second = first.next;
}
void m_swapPair(struct node** head)
{
struct node* p = *head;
struct node* q = p->link;
if(p == NULL || q == NULL)
{
cout<<"list is empty or the singleton node exits";
}
else
{
while(true)
{
int temp = p->key;
p->key = q->key;
q->key = temp;
if(q->link != NULL)
p = p->link->link;
else
{
cout<<"even number of nodes";
break;
}
if(p->link != NULL)
q = q->link->link;
else
{
cout<<"odd number of nodes";
break;
}
}
}
}
void m_swapPair(struct node** head)
{
struct node* p = *head;
struct node* q = p->link;
if(p == NULL || q == NULL)
{
cout<<"list is empty or the singleton node exits";
}
else
{
while(true)
{
int temp = p->key;
p->key = q->key;
q->key = temp;
if(q->link != NULL)
p = p->link->link;
else
{
cout<<"even number of nodes";
break;
}
if(p->link != NULL)
q = q->link->link;
else
{
cout<<"odd number of nodes";
break;
}
}
}
}
for the first one just recursively call the reversing procedure of linked list
code for this
struct node *Group2Reverse(struct node *L)
{
struct node *p,*q,*r;
struct node *head=L;
int count=2;
p=NULL:
if(!L||L->next==NULL)
return L;
q=L;
while(q && count--)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
if(q)
head->next=Group2Reverse(q);
else
head->next=NULL
return p;
}
public static boolean issym(Node root)
{
if(root==null)
return true;
return iss(root.left,root.right);
}
public static boolean iss(Node l, Node r)
{
if(l==null && r==null)
return true;
if(l!=null && r!=null && l.data==r.data)
return (iss(l.left,r.right) && iss(l.right,r.left));
return false;
}
public static Node rev(Node s)
{
if(s==null or s.next==null)
return ;
Node c=s;
Node a=s;
Node b=a.next;
Node first;
a.next=b.next;
b.next=a;
first=b;
c=a;
a=a.next;
b=a.next;
while(a!=null && b!=null)
{
a.next=b.next;
b.next=a;
c.next=b;
c=a;
a=a.next;
if(a==null ||a.next==null)
b=null;
else
b=a.next;
}
return first;
}
public Node reversePairsSLL(Node head){
Node first=head, second=first.next, third=second.next;
if(first==null || second==null) return head;
head=second;
while(first!=null && second!=null){
second.next=first;
if(third.next==null)first.next=third;else first.next=third.next;
first=third;
second=first.next;
if(second==null) return head;
third=second.next;
}
return head;
}
BR: Block reversal
t : tail
cn = current node
k = size of block; 2 in this case
r: Resultant linked list
BR()
r = NULL
t = cn
for each i from 0 to k-1
if(cn)
tmp = cn->n
cn->n = r
cn = t
t->n = BR(cn)
return r
Here is the code for reversing elements in linked list.I think it works fine.
lass Node
{
int x;
Node next=null;
Node()
{
}
Node(int r)
{
x=r;
}
void insert(int xx)
{ Node temp=this;
while(temp.next!=null)
temp=temp.next;
Node n=new Node(xx);
temp.next=n;
}
void display()
{Node temp=this;
while(temp.next!=null)
{
System.out.println("num="+temp.x);
temp=temp.next;
}
System.out.println("num="+temp.x);
}
}
public class job {
public static void main(String []args){
Node head=new Node(0);
for (int i=1;i<10;i++)
head.insert(i);
head.insert(10);
//for (int i=10;i>0;i--)
//head.insert(i);
//head.display();
Node xx;Node yy;
xx=head;yy=xx.next;
while(xx!=null&&yy!=null)
{
int temp=xx.x;
xx.x=yy.x;
yy.x=temp;
if(xx.next.next!=null&&yy.next.next!=null)
{
xx=xx.next.next;
yy=yy.next.next;
}
else{
xx=null;yy=null;
}
}
head.display();
}
}
struct node* reverse(struct node *head, int k)
{
struct node *prev = NULL, *current = head, *next;
int count = 0;
while(current != NULL && count < k)
{
next = current -> next;
current -> next = prev;
prev = current;
current = next;
}
if(next != NULL)
head -> next = reverse(next, k);
return prev;
}
Put k = 2 for this case
void swap(struct node **front)
{
struct node *cur, *temp,*prev;
if(!(*front))
printf("no elemet in the list\n");
else
{
cur=*front;
if(!cur->next)
;
else
{
cur=cur->next;
if(!cur->next)
{
cur->next=*front;
(*front)->next=NULL;
*front=cur;
}
else
{
prev=cur;
cur=cur->next;
prev->next=*front;
(*front)->next=cur;
temp=*front;
*front=prev;
prev=cur;
cur=cur->next;
while(prev && cur)
{
prev->next=cur->next;
cur->next=prev;
temp->next=cur;
temp=prev;
prev=prev->next;
if(prev)
cur=prev->next;
}
}
}
}
return;
}
#include <limits.h>
int third_biggest(int *arr, int size)
{
int first = INT_MIN, second = 0, third = 0;
for(int i=0;i<size;i++)
{
if(arr[i] > first)
{
third = second;
second = first;
first = arr[i];
}
}
return third;
}
Not sure if this is the best solution
sorry the above code doesn't work in few cases
This one works
- sun July 30, 2011