## AlgoFreek

BAN USERNode* 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)

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.

Rep**nickjonson885**, Consultant at ASUI am Department director in a Libera company. I live in Buffalo NY, USA. I am a hard worker girl ...

Rep**juanitajboon**, Applications Developer at 247quickbookshelpHi everyone, I am from Pelham. I currently work in the Hechinger as Cashier.I like to do creative things ...

Rep**dalejohnson762**, Accountant at ABC TECH SUPPORTI have exceptionally skilled Journalists possessed dogged determination to find the new story and deliver it to the public. I ...

Rep**jenniferdray9**, Accountant at ABC TECH SUPPORTHi I am Jennifer D. Ray from san Diego.Currently i am working as a parts salesperson in Rite solution ...

Rep**loreleijhansen**, Aghori Mahakal Tantrik at ABC TECH SUPPORTI am Lorelei.I am working in a store as a Bonus clerk promoting the development, and implementation and solutions ...

Rep**RobertBaumbach**, Administrative Manager at Meridian Mechanical Services

Rep**ellenabeaudry4**, Analyst at Boomerang CommerceI'm a 23 year-old blogger, make-up junkie and follower of Hinduism.I love Reading because it brings happiness for ...

Rep**paulaamontalvo**, AT&T Customer service email at AMDI am working as Human Resources Associates, and my duties are for obtaining, recording, and interpreting human resources information within ...

Rep**SarahSKelly**, Game Programmer at AkamaiI am Professor, and I am also a skilled fiction writer. I have a collection of novels published in the ...

Rep**brigidfwindle**, Android Engineer at A9I am able to communicate clearly and have a friendly disposition and a positive attitude. I am passionate about exploring ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

I have an O(nlogn) answer.

- AlgoFreek December 31, 20121) 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).