Sort in odd increasing even decreasing linked list

In the given linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How it can be sorted in increasing order?

Solution is very easy and is in linear time.

Given linked list

a1->a2->a3->......an

a1, a3, a5... are in increasing order.
a2, a4, a6... are in decreasing order.

First step is to get the linked list of odd numbered nodes only.
Means a1->a3->a5->...
This can be done in O(n)

Similar for even numbered nodes, a2->a4->.... This is again in linear time.
Now reverse the a2->a4-> list. It can be done in O(n).

Merge it with a1->a3->... It also has linear complexity.

And you will get a sorted linked list in linear time. 

Deletion of arbitrary node in the linked list

Given any node in a liked list without start pointer, how will you delete that node?
And what problem(s) will arise?

Solution is swap content of it with the next node (pointed by next pointer). And delete next node instead.
Problem will arise when this will be a terminal node (node with null next pointer). It will free a memory location that is longer used and still pointed by a node of linked list.

Yahoo interview questions

Yahoo visited our campus on 26th Oct. 2010. Its selection process consists of
1. Written Objective Test
2. Coding Round
3. 2 Technical Interviews
4. 1 HR Interview

Written Objective is pretty simple. One can easily get through with sound knowledge of Data structures, Algorithms, Operating Systems, Database Management Systems and little bit Discrete Mathematics.

In coding round, two problems were given which were simple if you are a regular programmer.
First one is to implement GREP without using any API/Library that supports such functionality.

Second one was level order traversal of a binary search tree. It concerned with finding sum at each level of tree that stores integers at each node.

Technical round were not that tough.

Questions are:

In first round:

1. Print linked list in reverse order using a recursive function. A code is to be written.
2. Given any node of a linked list (but not the start node), how that node can be deleted. And what problems can be faced later?
3. Two blind people are sitting near a table top. On table, there are n head faced coins and n tail faced coins. How they can distribute such that each one have equal number of heads and tails?
4. Solve f(n) = f(n-2)+2 and f(n) = f(n/2)+2 and similar RRs.

In second round:

1. Given a linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How can linked list be sorted in increasing order?
Solution is pretty simple and is in linear time.

2. How map (in C++) guarantees search in O(logn) in worst case?

Questions are quite easy.
Still I was unable to answer few one. Solution to someone I will post in my next blog.