## Amazon Interview Question for Software Engineer / Developers

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

Dont think the solutions above will give right response
here's my recursive algo
node* swap (node* root)
{
if (root==NULL) return NULL;
if (root->link==NULL) return root;
node* first, second;
first = root;
second = root->link;
first->link= swap(second->link);
second->link=first;
}

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

you must return "second" at the end of the function...
And I think that this solution is the best one in this page after this improvement.........
REALLY THE BEST SOLUTION.....

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

little modification in above code...

node* swap (node* root)
{
if (root==NULL) return NULL;
if (root->link==NULL) return root;
node* first, second;
first = root;
if(first && first-next)
{
second = root->link;
first->link= swap(second->link);
second->link=first;
first=second;
}
return second
}

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

Hmm ... what makes this solution so good, KK? How are you measuring that? Lines of code? The length of the linked list being limited by stack size?

Also, there are still mistakes in the source code above. When you declare a pointer type, you must prepend the asterisk to each variable in the declaration list, so "second" is not a pointer.

We know that root is first. I'm not sure it adds to the readability to declare "first". Reducing the items a reader has to remember may make the code easier to understand, so I propose this:

``````node* swap(node* root) {
if (root == NULL) return NULL;
if (root->next == NULL) return root;

node* second = root->next;
root->next = swap(second->next);
second->next = root;

return second;
}``````

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

Oops! More redundancies I overlooked. Let's try this again. Also, let's rename root to make it symmetrical to second:

``````node* pairwise_swap(node *first) {
if (first == NULL || first->next == NULL) return first;

node* second = first->next;
first->next = pairwise_swap(second->next);
second->next = first;

return second;
}``````

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

algopadawan(dot)blogspot(dot)com/2012/05/k-reverse-linked-list(dot)html

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

void swap()
{
int len=count();
node *start=p;
node *prev=NULL;
node *temp=NULL;
for(int i=0;i<len && start !=NULL;i++)
{
if(start==p)
{
temp=start->next;
start->next=start->next->next;
temp->next=start;
prev=start;
start=start->next;
p=temp;
}
else
{
temp=start->next;
start->next=start->next->next;
temp->next=start;
prev->next=temp;
prev=start;
start=start->next;
}
}
}

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

struct node* exchange(struct node* node) {
if(node==NULL || node->next==NULL) return node;
struct node* p=node, *q=node->next;
do {
p->next = q->next;
if(p==node) node=q;
q->next=p;
p=p->next;
if(p != NULL) q=p->next;
} while(p!=NULL || q!=NULL);
return node; }

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

Take as an example: 1->2->3->4->5->6->NULL;
For the 1st time this algo is ok..the o/p is
2->1->3->4->5->6->NULL;
Now head points to 2
p points to 3 and q points to 4.ok.
Now for the second time....
The o/p must be 2->1->4->3->5->6->NULL;
it means 1 should point to 4.....
But from the second time onwards 1 points to 3 only........means th LIST itself is Deatroyed.....plz try to correct this.....Thanks

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

Yes, Good finding KK.
Here is the modified code, hope this will help to you.

struct node* swap(struct node* node){
if(node==NULL || node->next==NULL) return node;
struct node *p=node, *q=node->next;
do{
p->next=q->next;
if(p==node) node=q;
q->next=p;
if(p->next!=NULL) {
q=p->next;
if(q->next != NULL) { p->next=q->next; p=q; q=q->next; }}
else { p->next=q; p=q; }
}while( q->next != NULL || p->next !=NULL);
return node; }

i will do some more clean up. if this code is ok for you.
You can contact me if you need any other programming help.

Usually i like programming !!!

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

``````int pairwise()
{
struct node* t=p;
struct node* s;
while(t!=NULL && t->l!=NULL)
{
s=t->l;
t->l=t->l->l;
s->l=t;
if(t==p)
p=s;
t=t->l;
if(t->l!=NULL)
s->l->l=t->l;

}
}``````

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

void swap(int *a, int *b);
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
struct node *temp = head;

/* Traverse further only if there are at-least two nodes left */
while(temp != NULL && temp->next != NULL)
{
/* Swap data of node with its next node's data */
swap(&temp->data, &temp->next->data);

/* Move temp by 2 for the next pair */
temp = temp->next->next;
}
}

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

start = head
j = 1;
while(start != null)
n = start;
n = n->next;
j++;
if(j == jump)
{
j = 1;
saveNext = n->next;
n->next = null;
node* last = Reverse(start);
last->next = saveNext;
start = saveNext;
}

Node * Reverse(Node* n)
{
prev = null;
cur = n;
next;
while(cur != null)
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}

return prev;

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

return should be n

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

> 1->2->3->4->5->1(this is circular one)

Is the 1 at the beginning and the end the same node?

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

Swap current node and (current node)->next beginning with head untill you either encounter NULL or it equals the head(in case the list is circular). Complexity: O(n)

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

@anonymous: your solution may not work with the following circular linked list: 1->2->3->4->5->3 (two '3's are at the same node)

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

@kolo dude....
its not a circular LL. In circular LL last node always points to the head node.

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

they always ask to write a running code on paper. so practice to write a code...
anyone with the code !!

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

there is nothing to test about the logic in this question, interviewer is trying to test the pointer manipulation. here we need to handle specially for head pointer. i.e for Head node and Head-> next nodes swap , swap using **Headref, i,e change the head node points to...

``````SwapTwoNodes(struct node **headref)
{

//code to swap head node
struct node *temp;
temp = *headref;
**headref= temp->link;
temp->link=*headref->link;
*headref->link=temp;

//now code for swapping rest of the nodes
while(temp->link!=*headref)
{
temp2=temp1->link;
temp->link=temp2->link;
temp2->link=temp->link->link;
temp->link->link=temp2;
temp=temp2;
}

}``````

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

i/p: 1->2->3->4->5->6---->1 (loop)
o/p: 2->1->4->3->6->5---->2

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

assume temp1 is a typo for temp

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

Will it be eassier to just swap data instead of pointer??
Also, we can use recursion to perform swapping for simple linked list...I am not sure if that can be done for circular linked list too.

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

//L is header

Node t1,t1,temp;
if(L->next!=NULL)
{
t1=L->next;
t2==t1->next;
temp=t2->next;
L->next=t2;
t2->next=t1;
t1->next=temp;
temp=t1;
}

while(temp!=null)
{
t1=temp->next;
t2=t1->next;
t3=t2->next;
temp->next=t2;
t2->next=t1;
t1->next=t3;
temp=temp->next->next;
}

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

boundary case : either you are at last node or you are not
if you get circular list, two case might happen:
a.)either your next node refers to first node(means you have one next node with which you can swap) - swap and quit
b.) or next node refers to second node in list(means you are at the last node) - quit here

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

Here is the simplest I could get it:

``````Node* FlipPairsList(Node* list)
{
if (!list)
{
return list;
}
else if (!list->next)
{
return list;
}
else
{
Node* t = 0;
Node* p = list;
list = list->next;
while (p && p->next)
{
t = p->next->next;
p->next->next = p;
if (t == 0)
{
p->next = 0;
}
else if (t->next == 0)
{
p->next = t;
}
else
{
p->next = t->next;
}
p = t;
}
return list;
}
}``````

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

Here is the C++ Code for this problem

``````bool CList::SwapAdjacent()
{
SNode *pList = m_pRoot;
bool fIsCircular = false;
if(!pList || !pList->pNext)
return fIsCircular;

SNode *pNext = NULL, *pTrack = pList;
int nData = 0;

while((pList != NULL && pList->pNext!= NULL))
{
// case where the list has odd elements and is circular
if(pList->pNext == pTrack)
{
fIsCircular = true;
break;
}

pNext = pList->pNext;
nData = pList->nData;
pList->nData = pNext->nData;
pNext->nData = nData;

pList = pNext->pNext;
// case where the list has even elements and is circular
if(pList == pTrack)
{
fIsCircular = true;
break;
}
}
return fIsCircular;
}``````

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

There r two way to solve this prob :
1.Without Recursion.
2.With Recursion.

[1]Without Recursion:

node* swapList(node *firstNode)
{
node *head,*prev;

if(node==NULL) //if List is empty
{
printf("List is Empty");
}

if(node->link==NULL)//if List is having Single node
{
printf("List is having single node");
head=firstNode;
}

if(firstNode->link->ink!=NULL)//to set head of the new list.It will swap only starting two nodes.
{
head=firstNode->link;
firstNode->link=head->link;
head->link=firstNode;
}

while(firstNode->link->link!=NULL)//swap remaining nodes
{
prev=firstNode;
firstNode=firstNode->link;
prev->link=firstNode->link;
firstNode->link=firstNode->link->link;
prev->link->link=firstNode;
}

return head;
}

[2]With recursion:

node* swapList(node *firstNode)
{
node *head,*prev;

if(node==NULL) //if List is empty
{
printf("List is Empty");
}

if(node->link==NULL)//if List is having Single node
{
printf("List is having single node");
head=firstNode;
}

if(firstNode->link->ink!=NULL)//to set head of the new list.It will swap only starting two nodes.
{
head=firstNode->link;
firstNode->link=head->link;
head->link=firstNode;
}

swap(firstNode);

return head;
}
//--------------------------------
swap(node *ptr)
{

node *prev;
if(ptr->link->link!=NULL)
{
ptr=ptr->link->link;
swap(ptr);
}
prev=ptr;
ptr=ptr->link;

prev->link=ptr->link;
ptr->link=ptr->link->link;
prev->link->link=ptr;
}

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

ptr=head;
pptr=NULL;
while(ptr->next!=NULL)
{
temp=ptr->next->next;
ptr->next->next=ptr;
if(pptr!=NULL)
{
pptr->next=ptr->next;
}
pptr=ptr;
ptr->next=temp;

ptr=ptr->next;
}

//looking forward to constructive suggestions

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

``````swap_pairs (list *p1)
{
list *temp = NULL, *prev = NULL;
while (p1 != NULL) {
if (p1->next) {
temp = p1->next;
p1->next = temp->next;
temp->next = p1;
if (prev) {
prev->next = temp;
prev = p1;
}
}
}
}``````

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

Good one. Did you forget to add p1 = p1->next after prev = p1; ??

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

struct node *swapper2(struct node *l1)
{
struct node *head;
struct node *p *q,*r;
p=l1;
q=l1->next;
head=p;
count=2;
while(q && --count)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
head->next=swapper2(q);
return p;

}

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

Wow, this question has really made its rounds since I started asking it in interviews :)

Take a look at this iterative solution. Recursively, it is a bit shorter, but I usually prefer iterative solutions.

``````node* swap_pairwise(node* root) {
if (root == NULL || root->next == NULL) return root;

// Prepend a node to root to reduce special-casing.
std::auto_ptr<node> aux(new node(0));
aux->next = root;
node* n1 = aux.get();

while (n1->next != NULL && n1->next->next != NULL) {
node *n2 = n1->next, *n3 = n2->next, *n4 = n3->next;

n1->next = n3;
n3->next = n2;
n2->next = n4;

n1 = n2;
}
return aux->next;
}``````

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

Actually, I had meant to remove the first if-conditional, because it will be properly handled by the while-loop, even if the linked list is NULL or just one element. Apologies. Here is the corrected code:

node* swap_pairwise(node* root) {
// Prepend a node to root to reduce special-casing.
std::auto_ptr<node> aux(new node(0));
aux->next = root;
node* n1 = aux.get();

while (n1->next != NULL && n1->next->next != NULL) {
node *n2 = n1->next, *n3 = n2->next, *n4 = n3->next;

n1->next = n3;
n3->next = n2;
n2->next = n4;

n1 = n2;
}
return aux->next;
}

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

``````public void Interchange()
{
Node<T> current = _head;
while (current != null)
{
var tuple = Tuple.Create(current, current.Next, current.Next?.Next, current.Next?.Next?.Next);
if (tuple.Item1 != null && tuple.Item2 != null && tuple.Item3 != null)
{
tuple.Item1.Next = tuple.Item3;
tuple.Item3.Next = tuple.Item2;
tuple.Item2.Next = tuple.Item4;
}
current = current.Next?.Next;
}
}``````

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

``public void Interchange()``

``{``

``Node<T> current = _head;``

``while (current != null)``

``{``

``var tuple = Tuple.Create(current, current.Next, current.Next?.Next,  current.Next?.Next?.Next);``

``if (tuple.Item1 != null && tuple.Item2 != null && tuple.Item3 != null)``

``{``

``tuple.Item1.Next = tuple.Item3;``

``tuple.Item3.Next = tuple.Item2;``

``tuple.Item2.Next = tuple.Item4;``

``}``

``current = current.Next?.Next;``

``}``

``}``

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

``````public void Interchange()
{
Node<T> current = _head;
while (current != null)
{
var tuple = Tuple.Create(current, current.Next, current.Next?.Next, current.Next?.Next?.Next);
if (tuple.Item1 != null && tuple.Item2 != null && tuple.Item3 != null)
{
tuple.Item1.Next = tuple.Item3;
tuple.Item3.Next = tuple.Item2;
tuple.Item2.Next = tuple.Item4;
}
current = current.Next?.Next;
}
}``````

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

``````Node* reverse(Node *Root)
{
Node* nRoot,temp ;
if(Root==null) return null;
nRoot = Root->next;
if(nRoot==null) return Root;

while(root!=null)
{
temp = root->next;
root->next = temp->next;
temp->next = root;
root=root->next;
}
return nRoot;
}``````

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

tum sab log mera loda chuso

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

eww

Add a Comment
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.

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