Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
Actually, you CAN :)
1. keep the first node of the list
2. go through the list and reverse the direction of links.
if you reach to NULL , the answer is "NO loop"
if during step 2 you reach the kept first node than the answer is "YES, the is a loop"
First thing u are not allowed modify the list.
Second will you be able to modify the with only one pointer?
you are right (I was thinking about not comparing two walking pointers),
this one may take long but satisfies to your requirements:
while walking through the list keep max and min addresses of nodes and check
if n*(address size) > max-min then there is a loop
Tigran, we can't even check address, as each node of linked list is created dynamically. So we cannot predict address of any node.
I feel whatever Ashish has suggested is right way.
If we are allowed to use extra space then this problem can be solved in O(n) space and O(n) time complexity. store the memory in a list once a node is visited. on each visit check list whether it contains the memory location if not add the memory of the item else the point will be the loop point.
1) Revert list. If you reach root, there is a loop, if not, there is no loop.
2) Store address of highest element passed. If you find this element again, there is a loop. If reach end of list, there is no loops.
Ok, technically you use second pointer. Lets store unambiguous hash of root or highest element pointer...
It can be done using one pointer but not without extra space. You can store the addresses of all the nodes visited in a hashmap. And for every next node, check its presence in hashmap.
- Ashish Anand March 05, 2013