Motorola Interview Question for Software Engineer / Developers






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

Keep a count of the total number of nodes in the linked list i.e every time you add a node increment the count.
So if there is a random pointer in the linked list then the total number of nodes will be less than the count that you have maintained.Because the nodes between the random pointer and the node to which it is pointing can never be accessed.

- Anonymous June 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if you had no control at the time of the list creation?
this wont work,...

I have a solution based on the hash map, but that handles only 1 type of mal pointer out of 2 possible cases,
The solution below solves the case when there is a loop in list...
1-2-3 4-5-6-null, 3 points to 1

start traversing the list and make a hash map as below and look for collision if there is a collision then there is a bad pointer
1 Null
2 1
3 2
now comes 1 again and collision occurs...
But another case:
1-2-3 4-5-6-null, 3 points to 5
is not solvable here as we do not have a reference to 4...

- Ashupriya July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about reversing the link list and checking if the number of nodes are the same for reversed and original lists?

- soho August 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

there may be a loop in there !!
so we also have to check for its existence first
then above method would work..

- prtkvaishnav July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wekk how do you reverse the list by traversing till the end right...and if u traverse like that and come back again you will find the same length and in case of a loop u cant even traverse to null

- Rahul January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

curr = head;
nxt = head->next;
head -> next = null;
while(nxt != null)
{
     p = nxt -> next;
     nxt -> next = curr;
     curr = nxt;
     nxt = p;
}

- prtkvaishnav July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is another way of saying "Check if the linked list contains loop".

- Anonymous September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void printLoopLocation(Node node)
	{
		boolean isLoop = false;
		Node slow;
		Node fast;
		int count=0;
		
		slow = fast = node;
		
		while(true)
		{
			
		slow = slow.getNext();
		fast = fast.getNext().getNext();
		
		if(slow == null || fast == null)
		{
			System.out.println("There is no loop in the list.");
			break;
		}
		if(slow == fast)
		{
			System.out.println("There is a loop in the list.");
			isLoop = true;
			break;
		}
		}
		
		if(isLoop)
		{
			// Now count the number of nodes in the loop
			
			slow = slow.getNext();
			count++;
			
			while(slow != fast)
			{
				slow = slow.getNext();
				count++;
				
			}
		}
		
		System.out.println("There are "+count+" nodes in the loop.");
		
		// Now we will find the starting point of the loop
		// Move both pointers to the start of the list
		
		slow = fast = node;
		
		for(int i=1;i<=count; i++)
		{
			fast = fast.getNext();
		}
		
		// Now fast pointer is count nodes away from the slow pointer
		// Increment both pointers one by one until they meet. Meeting point is the place where loop starts.
		
		while(slow != fast)
		{
			slow = slow.getNext();
			fast = fast.getNext();
		}
		
		System.out.println("The loop starts at "+ slow.getData());
	}

- pkd September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check for loop

- rishikantku June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

looping condition will not be sufficient.
It is possible that the wrong link is of another link list.
Correct me if am wrong
thanks.

- Rachit singhal May 09, 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