Google Interview Question: Given an array of integers wh... | Glassdoor

Interview Question

Software Engineer Interview Mountain View, CA

Given an array of integers where each element points to the

  index of the next element how would you detect if there is a cycle in this array?
Tags:
algorithm
Answer

Interview Answer

18 Answers

1

The catch is to realize that if there is a cycle, it will result in an infinite loop

Interview Candidate on May 15, 2010
2

One possible solution is to keep a list for all visited positions.
If we hit a position that is already in the list, we've detected a cycle.
For this solution, time complexity is O(n) and space complexity is O(n).
How to do this in O(n) time and O(1) space?

Girish on May 21, 2010
2

use the contents of a position as an index into array and while traversing the contents, negate the contents after you visit it. if at any time you find the contents of a position as negative (given that every element points to the next element in array, you cannot have -ve numbers in array) this will run in o(n) with constant space
e.g.

array = [1,2,3,4,5,2] (zero based index)
a[0]=1
go to a[1] and negate a[0] to -1
a[1]=2
go to a[2] and negate a[1] to -2
like this when you hit a[5] =2 and then you see a[2] = -3, which is already visited so there is a loop/cycle

Anonymous on May 26, 2010
5

The problem is imprecisely stated. If every element a[i] contains a value that is an index into a (i.e. a value in the range 0..length(a)), then there *must* be at least 1 cycle, assuming a is of finite size. On the other hand, if a is allowed to contain values that are not valid indexes (negative, or >= length(a)), then it indeed takes some work to determine if a has cycles. So let's assume the latter.

If a is allowed to contain negative values to start with, then the negate-as-you-see-it solution doesn't work.

To determine if there is a cycle starting at any given element (isCycle(elemindex)) in O(1) space and O(n) time, you could walk 2 pointers starting at elemindex. One would go at normal speed (nextelem = a[thiselem]) and one would go at double speed (nextelem=a[a[thiselem]]). If the 2 pointers meet, isCycle() returns true. However, since you'd have to run isCycle(index) on every index to ask if there is a cycle *anywhere* in the array, this algorithm is O(n**2) in time. I'd have to ponder if there's an O(1) space / O(n) time algorithm for this...

Anonymous on Jul 1, 2010
0

if the array is not "full," then it must contain sentinel values which represent NULL references. You could use Integer.MIN (in Java parlance) or just -a.length.
this fixes the above criticism of the negate-as-you-see-it approach. What it doesn't fix is the fact that that the "graph" can be disconnected.
for instance [1,2,NULL,4,5,1]
a[0]->a[1]->a[2]->NULL
a[3]->a[4]->a[5]->a[1]->a[2]->NULL
in this case there are multiple references to element a[1], but it's not a cycle.
I think you're stuck with the N^2 solution.

Jimmy on Jul 24, 2010
8

Define two pointers
One pointer move one step each time, The other pointer move two steps each time.
If the pointers ever meet together (besides the start point) before one of the pointer reaches the end, then there is a loop. Otherwise, there isn't.
This takes O(n) time and O(1) space.

Anonymous on Oct 28, 2010
1

if there is a loop then that means that is a number repeated in the array. put the number in the array into a hashmap and compare the size of the hashmap to the size of the array. if less than there is a loop

Anonymous on Nov 14, 2010
0

If you interpret the question strictly, then the answer is TRUE -- it always has a loop.

Unless an element can point to nothing (with a negative index for instance) signaling that the iterator must terminate.

Gopi Reddy on Jul 18, 2012
1

How about incrementing a counter every time you follow a pointer and seeing if the final count is greater than the array length? If you've done more iterations than the array's length, that should indicate a cycle.

Emre Colak on Dec 8, 2013
0

Can some one explain the question ? If you have an array of integers then the ONLY interpretation of " ...each element points to the index of the next element" is the following array : a = [1,2,3,4,5,6,7 ...] . If that is the case - then what does it even mean to "have a cycle" ?

Anonymous on Aug 12, 2014
1

Sort it and see if we have duplicates works too.

mogung on Jan 27, 2015
0

Multiple approaches are possible.
If space of O(n) is allowed, add all pointers to a Set. If set size is less than array size, there is a cycle.
If linear time and constant space is desired, start 2 pointers at index 0, First pointer is incremented by 1 index, second incremented by 2 indices. If end is reached by either pointer, no cycle. If fast pointer '.next' is every slow pointer, there is a cycle.

Debosmit Ray on Mar 22, 2016
0

"turn" & check the first

Dmitry on Dec 28, 2018
0

The question is not clear . If each element's value is the next element's index then there'd be no cycle as mentioned above. I like the sets solution in terms of simplicity. To add to the possible solutions I propose hashing each index encountered with the value being the number of occurrences. Each time update the value of a key if it is already a 1 we've found a cycle. This should be O(n) for both time and space complexity.

One doubt I have with the fast/slow double pointer solution is the assumption that the existence of a cycle has to send the fast pointer back exactly to where it eventually meets the slow pointer. In situations where this isn't true an additional condition should be if the slow pointer reaches the end before the fast.

Ricardo Mitchell on May 4, 2019
0

If an array starts at index 0 and it has value 2. If the index 2 has value 1 and index 1 has value 0. Then it would be cyclic array. Because it starts and ends in the same index 0.

Anitha on Sep 25, 2019
0

public void detectCycle(int[] arr,int n){
        int slow=0,fast=arr[arr[slow]];
        boolean flag=false;
        while(fast=n)
            System.out.println("Cycle not present in arr");
    }

Rajeev pal on Mar 11, 2017
1

Is that the full version of the question? The one I heard before said that we just have a limited memory resource. But because my version and the one mentioned above don't prohibit us to modify the given data, so I think we just need one variable and one pointer for this question.

We assign the value of the first element in the array provided to our variable and pointer. Then we jump to the next element in the array and check if the value of that element is equal to the one in our variable. If not, assign the value of that element to the pointer and then change that value to the one we have in the variable. Jump to the next element by using the pointer and continue to do the same task like what we do with the previous element. The program will alert an infinite loop when it found there is an element with the same value in the variable.

Huan Kim Tran on Nov 8, 2015
2

What as the time and space complexity of the best solution? Can you do it in O(n) time and O(1) space?

Anonymous on May 17, 2010

Add Answers or Comments

To comment on this, Sign In or Sign Up.