Amazon.com Interview Question
Web:
www.amazon.com
|
HQ:
Seattle, WA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,219 Interview Reviews |
Back to all Amazon.com Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Senior Software Engineer at Amazon.com:
Sep 1, 2009
1 of
1 people found this helpful
How to detect loops in a linked list without using a data structure
Add Tags
[?]
See more for this Amazon.com Senior Software Engineer Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Dec 8, 2009
Check out the Wiley's book "programming interviews exposed" that discusses this question in detail. Coming up with jeremy's solution on the spot is close to impossible.
You could check for every position i you come by as you jump from node to node, if any of the previous i-2 nodes' next pointer points to you. If there is a cycle, one will point to you.
You could check for every position i you come by as you jump from node to node, if any of the previous i-2 nodes' next pointer points to you. If there is a cycle, one will point to you.
Helpful Answer?
Yes |
No
Inappropriate?
Jan 22, 2011
fastest way:
suppose there is 'value' field in each node of linked list other that ther 'next node pointer'
as you traverse the list .. make the value field -1 or something like MAX_INT.... keep doing it either list ends or you see MAX_INT again...
suppose there is 'value' field in each node of linked list other that ther 'next node pointer'
as you traverse the list .. make the value field -1 or something like MAX_INT.... keep doing it either list ends or you see MAX_INT again...
Helpful Answer?
Yes |
No
Inappropriate?
May 10, 2011
Jeremy's answer is right; it's called Floyd's cycle finding algorithm
Helpful Answer?
Yes |
No
Inappropriate?
Members can
answer or comment on this question
–
Join Now (It's Free) or
Sign In
You might also be interested in: Interview Questions, Senior Software Engineer Interview Questions, Amazon.com Interview
4 of 5 people found this helpful
by jeremy: