GE (General Electric) Interview Question
Software Engineer / Developerspublic void printMergepoint( SingleLinkedList<Integer> list1, SingleLinkedList<Integer> list2 ){
int size1 = list1.size();
int size2 = list2.size();
Iterator<Integer> it1 = list1.iterator();
Iterator<Integer> it2 = list2.iterator();
Integer first = it1.next();
Integer second = it2.next();
while( it1.hasNext() && it2.hasNext() ){
if( first.equals(second) ){
System.out.println("Merge point: " + first);
break;
}
if( size1 == size2 ){
first = it1.next();
second = it2.next();
}
else if( size1 > size2 ){
first = it1.next();
--size1;
}
else {
second = it2.next();
--size2;
}
}
}
//C++ code
Node* intersectAt(Node* roota, Node* rootb){
int lena = getLen(roota);
int lenb = getLen(rootb);
if (lena == 0|| lenb == 0)
return NULL;
Node* tempa = roota;
Node* tempb = rootb;
//align the starting point of both lists
for (int i= 0; i < lena - lenb; i++)
tempa = tempa->next;
for (int i = 0; i < lenb - lena; i+=)
tempb = tempb->next;
while (tempa != tempb){
tempa = tempa->next;
tempb = tempb->next;
}
return tempa;
}
//get the length of a list
int getLen(Node* root){
int i = 0;
while(root != NULL){
i++;
root = root->next;
}
return i;
}
Algo 1:
- Rahul D April 06, 2011Use 2 loops, take each node pointer of 1st link list & check it in 2nd link list.
time: O(n^2) space: O(1)
Algo 2:
Keep a visited flag with each node.
Traverse 1st linked list & make visited flag as 1 (initially all is 0)
Traverse the second linked list & merging point will already be 1.
time O(n): space O(n+m)
Algo 3:
count nodes of list 1 e.g. no_1 = 6
count nodes of list 2. e.g. no_2 = 4
take difference of both link list = 2
take 2 node pointers
pointer 1 at starting node on smallest linked list
keep second pointer difference of the nodes ahead on the bigger link list
now move both pointers by 1.
if both pointers are same at a point then you will get a merging point
time O(n) space O(1)
Algo 4:
make a look in 1st link list
user algo to find entry point of loop
time O(n) space O(1)
Algo 5:
assume both link list merging on a point.
assume total nodes before merging in 1st list is x & in 2nd list is y
after merging total nodes are z
time O(n) space O(1)
so you have x+z=c1(total nodes in list1), y+z=c2 (total nodes in list c2)
reverse any one list & count nodes
you have now x+y=c3
now slove eqetions