Harman Kadron Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

Node* findLoopNode(Node* LL){
	if(!LL) return NULL;

	else if(LL->next == LL) return LL;
	//the linked list contains only one node which points back to itself

	else{
		Node* fast, *slow, *head;
		
		head = fast = slow = LL;

		do{
			if(!fast->next && !fast->next->next) 
					fast = fast->next->next;
			else return NULL;// there is no loop
			
			slow = slow->next;
		}while(fast!=slow);
		//there is a loop and the below snippet finds the node pointed back
		while(fast != head){
			fast = fast->next;
			head = head->next;
		}

		return head;//the required node
	}
}

- Ashish June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Ashish,
first of all, Nice code. But i didn't understand the below code snippet logic.

//there is a loop and the below snippet finds the node pointed back
while(fast != head){
fast = fast->next;
head = head->next;
}

Is it true that "fast" and "head" points move the same distance before reaching the intersection node.
My understanding is that "head' point needs to move it's pointer for each cycle (fast) and check whether head and fast pointers are equal.

Can you explain this code snippet logic ?

- Pavankumar thati June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, it will always be true that "fast" and "head" points move the same distance before reaching the intersection node. You can do a dry run by taking an example which will clear your doubt.

Also I did a mistake in the above code which I have rectified :
this
head = fast = slow;

should be

head = fast = slow = LL;

- Ashish June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Ashish,
I'm confused with below:
if(!fast->next && !fast->next->next) -- why inverted values?
It'd be good if you can briefly comment how this overall code is working:

- Diwakar June 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think moving one pointer twice at speed of other is self evident, its like two people jogging on a circular track. the faster one will eventually meet the slower one.
Finding the node where the loop begins is interesting.

Lets say fast and slow meet at point p

head-------loopbegin------------meetingPoint----------pointingtoLoopBegin

Lets say head->LoopBegin = x
loopBegin->meetingPoint = y
meetingPoint -> pointingToLoopbegin = z

distance travelled by slow node = x +y
distance travelled by faster one = x + y + z + y

so as t = d/s and t(slower) = t(faster)
(x+y)/s = (x+2y+z)/2s
solving it will give x = z;

- arpit.gautam July 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How will you make sure that this logic will always work.
I mean, is there any mathematic model or anything to proof that this is an impeccable model.

- DyingLizard February 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

int Check_Loop(Node head)
{
	Node temp,prev,curr;

	temp=head;

	if(temp==NULL) return 0;
	if(temp->next == temp) return 1;

	prev=head;
	curr=head->next;

	while(curr!=NULL)
	{
	if(prev->next==cur->next)
	return 1;
	else {
	prev=prev->next;
	curr=curr->next->next;
	}
	}
	return 0;
}

- Santhosh K June 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we could simply maintain a list of visitedNodes. So during iteration if we find any node thats already part of visited node list then we could say we have loop provided the list does not any duplicates.

If duplicates we need to come up with hashcode for each node and do comparison. Hope that make sense. Anyways following is the java snippet that should tell you loops and the link thats actually causing the loop (for no duplicates scenario)

List visitedNodes = new ArrayList();
		ListNode prevNode = null;
		tempNode = headNode;
		
		while(!visitedNodes.contains(tempNode) && tempNode.nextNode != null){
			visitedNodes.add(tempNode);
			prevNode = tempNode;
			tempNode = tempNode.nextNode;
		}
		
		if(tempNode.nextNode != null){
			System.out.println("Link from "+ prevNode.toString()+ " to " + tempNode.toString() +" causing cycles");
		}

- reachpraveen11 August 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please refer to ostermiller.org/find_loop_singly_linked_list.html.

You don't have to use a "visited flag" or additional information, just a slow iterator and a fast iterator. The " The Tortoise and the Hare Algorithm".

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

- Bruno September 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved using Floyd's Algorithm of Cycle Detection:
Search on Google "explain-how-finding-cycle-start-node-in-cycle-linked-list-work". Answer can be found on Stack Overflow.

- bhuleskar April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked list

<a href="newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html">newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html</a>

- Ashish July 22, 2014 | 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