Microsoft
3.6 of 5 7,063 reviews
www.microsoft.com Redmond, WA 5000+ Employees

Microsoft Software Development Engineer (SDE) Interview Question (student candidate)

I interviewed in Redmond, WA and was asked:
"[Round 1] Find loop in a linked list"
Add Tags [?]
Answer Flag Question

Part of a Software Development Engineer (SDE) Interview Review - one of 3,185 Microsoft Interview Reviews

Answers & Comments

0
of 0
votes
Answer : If he means a boolean function to see if there is a loop in the linked list or not, then the answer is to use two pointers (slow and fast). "slow" walks one step every time and "fast" walks two step every time , if you reach null with fast pointer , then there is no loop , else if the fast and slaw pointer meet then there is a loop.

if he means find the begin node of this loop (loop node), then you will write some extra code.
you now get the node where "fast" and "slow" pointers meet in. then, arithmetically, the distance between that node and the "loop node" is equal to the distance between the head of the linked list and the "loop node". what we can do is after the slaw and fast pointers meet , fast pointer will point to the head of the linked list and both the slaw and the fast pointers will continue with speed equal to one step every time until they meet. the "loop node" is the node they met in.
- Mahmoud Wahdan on Dec 08, 2012 Flag Response
0
of 0
votes
There is a blog discussing this problem:
http://codercareer.blogspot.com/2012/01/no-29-loop-in-list.html

Additionally, it's the 16th problem in the book <Coding Interviews: Questions. Analysis & Solutions>. You may get detailed analysis about this problem in the book.
- Harry on Dec 25, 2012 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Microsoft – Why Work for Us?

What do you want in a job? Do you want more than a paycheck? At Microsoft, you can discover potential you didn’t know you had, push your limits, turn your ideas into reality and make a real impact on the industry and… Full Overview

Provided by employer [?]

Tags are like keywords, helping to categorise interview questions that have something in common.

Glassdoor is your free inside look at Microsoft interview questions and advice. All interview reviews are posted anonymously by Microsoft employees and interview candidates.