Expedia Interview Question
Software Engineer / Developerslinked list: 5 6 7 => 6 5 7 notice now 6 is pointing at 6. Just 1 location away.
linked list: 5 6 7 8 => 6 5 8 7 notice now 5 is pointing at 8 which is 3 locations away.
If we are to swap the node pointers, there are many special cases. How does inductive reasoning help with dealing with special cases? Did you come up with an algorithm that is simpler?
I would consider a slightly different algorithm than before...
I noted that null is the terminator. Create a pair-pointer(pp) that indicates which pair to swap.
General cases:
Base cases:
null
1 null
pp->1->2->null
swap 1 and 2. Restore pp.
pp->2->1->null
pp=pp.next.next
Inductive step:
pp is null and so stop
pp->3
2->1->3->null
Cannot swap 3 and null so stop.
pp->3
2->1->3->4->null
swap 3 & 4. Restore pp.
pp=pp.next.next;
and so on.
This is inductive because the next pair is based on the truth of the events of the previous pair.
I was asked a similar Question in my amazon interview. A small addition to it was swapping all the alternate nodes.
I know its pretty simlae to do if you are good are linkedlist and pointers. Few points one should keep in mind.
1) Check for the poll conditions. I mean the head and tail of linked list.
2) Linked list once subjected to swap operation should return the head pointer in the end.
3) Detect Loops. Most important. If there is loop in the linked, the you swap operation might run tirelessly.
4) ... There are more such test cases. Above three were the most important I thought of.
I was asked abt this in msft. Here's the solution I came up with.
void reverseNodes(Node ** head)
{
Node* pt1, pt2, temp;
//input validation
pt1 = *head;
pt2 = pt1->next;
*head = pt2;
while(pt1)
{
temp = pt2->next;
pt2->next = pt1; //Links reversed for adj nodes.
if(temp == NULL)
{
pt1->next = NULL;
}
else if(temp->next == NULL) //odd # of nodes, last node.
{
pt1->next = temp;
}
else
pt1->next = temp->next;
pt1 = temp;
if(temp == NULL)
{
pt2 = NULL;
}
else
{
pt2 = temp->next;
}
}
}
Another solution using 3 pointers,
void reverseNodes(Node ** head)
{
Node* cur, nxt, prv;
cur = *head;
while(cur)
{
if ( !(nxt = cur->next) ) break;
cur->next = nxt->next;
nxt->next = cur;
if ( cur == *head )
{
*head = nxt;
}
else
{
prv->next = nxt;
}
prv = cur;
cur=cur->next;
}//end of while
}// end of reverseNodes
Here is a recursive solution:
}
- Anubhav Singh June 15, 2012