Expedia Interview Question for Software Engineer / Developers






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

Here is a recursive solution:

void swapping(node *&head)
{
	node *forhead=head->next;
	if(forhead==NULL)
		return;	
	else if(forhead->next!=NULL)
	{
		swapping(forhead->next);
		head->next->next=forhead->next;
	}
	
	head->next=forhead->next;
	forhead->next=head;
	head=forhead;

}

- Anubhav Singh June 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Jack, swapping the node pointers.. It looks like there are quite a few special cases. Is there a generic way to write this?

- Khoa April 09, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't mention that he wanted consecutive pairs swapped. Overall, I followed inductive reasoning.

- Jack April 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

linked 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?

- Khoa April 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jack April 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

More formally...

n-1 and n are true, which implies n+1 and n+2 are true.

- Jack April 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we have to swap adjacent nodes (except the last node if odd number of nodes)??

e.g if original list is 2->9->7->6->7->NULL
so we should get result:9->2->6->7->7->NULL

is this the q??

- Ranveer April 13, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If n is odd, then n+1 is null. So you don't swap.

- Jack April 13, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using the pair pointer approach, how do you ensure that you adj pairs remain interconnected?

- Ash August 01, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please be more specific.

- Jack August 01, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a recursive solution:-

struct node* SwapAdjLinks(struct node* first)
{
struct node* second, *tail;
if(first != NULL && first->next != NULL)
{
second = first->next;
tail = SwapAdjLinks(second->next);
first->next = tail;
second->next = first;
first = second;
}
return first;

}

- Ashwin December 29, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Peace September 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Peace: thank you very much, now I can rest in peace for tomorrow's interview[amazon]. thank you !

- restlesstoday September 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}
}

- Anon May 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- toseef.koliyariwala September 09, 2013 | Flag Reply


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