GE (General Electric) Interview Question for Software Engineer / Developers






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

Algo 1:
Use 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

- Rahul D April 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reverse both the linked list....compare each element of linked list and stop where they differ....That point is the intersection point.....

- vivek April 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- m@}{ April 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

time: O(N) space: O(1)

- m@}{ April 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Connect the end to the beginning of one of the lists. Now the problem has been reduced to the common problem of finding loop in a linked list. Finding the beginning of the loop is also a well known problem.

- Anonymous April 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- css April 06, 2011 | 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