CareerCup

I have an O(nlogn) answer.
1) Sort the array. O(nlogn)
2) Then for every element keep checking the next element till end. If current element == next Elelement increase the counter. if current Element != next Element then check counter. If counter is zero then return that element. If counter is not zero then make counter zero and proceed. O(n).

space complexity is O(1).

No That is wrong. This does not work for {12,1,12,3,12,1,1,5,3,3 }.

Your approach will give you 2 where as actual answer is 5.

Node* insert(Node* random, int val )
{
Node* newNode = new Node;
newNode->data = val;
newNode->next = newNode;
//If node is empty
if( random == NULL )
return newNode;
Node* prev = random;
Node* start = random;
//For the cases where val > given node data
if( val > random->data )
{
while( (val > random->data) &&(prev->data <= random->data) && (random != start) )
{
prev = random;
random = random->next;
}
prev->next = newNode;
newNode->next = random;

}
//For the cases where val < given node data
else if( val < random->data)
{
while( (prev->data <= random->data) && ( random != start)
{
prev = random;
random = random->next;
}
while( (val > random->data) && (random != start))
{
prev = random;
random = random->next;
}
prev->next = newNode;
newNode->next = random;
}
//For the cases where val == given node data
else
{
newNode->next = random->next;
random->next = newNode;
}
return random;
}

Complexity is O(n)

Sorry got deleted while editing it.. will repost it again ...

@ansul - thanks for bringing that in. Just move that check to end that while loop instead of begining. If true then break that loop

I did not see question completely... this will take O(n) space complexity...

If you want to do in a single scan you need to use stack. As you know 2 stack, you can use reccurssion [ correct me if I am worng ]. Following is the C++ version of the algo :
Node* intersectionPoint( Node* L1, Node* L2)
{
if( (L1 == NULL) || ( L2 == NULL))
return NULL;
Stack* stack1 = new Stack;
Stack* stack2 = new Stack;

while( (L1 != NULL) || (L2 != NULL) )
{
if( L1 != NULL )
{
stack1->push(L1);
L1 = L1->next;
}
if( L2 != NULL )
{
stack2->push(L2);
L2 = L2->next;
}

}
Node* node1, node2, prev = NULL;
while( !stack1->empty() && !stack2->empty())
{
node1 = stack1->pop();
node2 = stack2->pop();

if( node1 == node2 )
{
prev = node1; // you can keep node2 also
}
else
return prev;

}
return prev;
}

To Construct any binary tree we need to know either preorder / postorder along with in order.
In this case preorder is given. Also we know that tree is a BST. So, in order will be the sorted array. So, sort the array. Now you have both in order and pre order. Now it is easy to construct the tree.