## Amazon Interview Question for Software Engineer / Developers

• 0

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;
node* first, second;
first = root;
}

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

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

little modification in above code...

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

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

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

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

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

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

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 */
{

/* 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

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

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

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

@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

@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)
{

struct node *temp;

//now code for swapping rest of the nodes
{
temp=temp2;
}

}``````

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

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

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.

Without Recursion:

node* swapList(node *firstNode)
{

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

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

{
prev=firstNode;
}

}

With recursion:

node* swapList(node *firstNode)
{

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

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

swap(firstNode);

}
//--------------------------------
swap(node *ptr)
{

node *prev;
{
swap(ptr);
}
prev=ptr;

}

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

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

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 *p *q,*r;
p=l1;
q=l1->next;
count=2;
while(q && --count)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
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

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()
{
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()
{
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

eww

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.