## Microsoft Interview Question for Software Engineer Interns

• 0

Country: United States

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

Every element of this array have "next" element to go (including itself). So we can do "next" starting from any element infinite times and always can continue. Thus EVERY possible array will have loop because array is finite. Loop length could be from 0 to N (whole array).

What case could be considered as no-loop array?

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

It's still not clear for me :)

Need more test cases:

[1, 1, 1, 1, 1, 1, 1] loop? For me it's a full array loop.
[1, 1, 1, 1, 1, 1, 0] loop? For me it's a zero length/self loop on the last element.
[1, 1, 1, 0, 1, 1, 1] loop? Same as previous. But some elements can't be reached from first.
[1, 1, 1, 1, 1, 1, -2, 1, 1] loop? A loop of length three.
 loop? A full array self loop :)
[] loop?

From math point of view (theory of permutations) all examples have loops. From 0 to N length. Except last. It's degenerate/edge case.

Is it clear why i'm so confused? :)

Conceptually this problem on finding a loop in a single linked list. Usually people solve such problem by reversing links, or by using two iterators (with step size 1 and 2 consequently).

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

Save path in map (or int array) and check index for visiting

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

This should be similar to link list loop finding problem

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

If I understood @sergey 's comment above; every finite array has loop in it.
If there are N elements in array then only at the max (N-1) times you can go to distinct position.

At (N-1)th hop you have already visited all the indexes. Hence when you take Nth hop, you will land on one of the reviosuly visited place. Thus it is a loop.

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

@Sergey, sorry, I should've clarified this. A loop is something that starts and ends at a particular index. In the example, the loop went from 0->2, 2->3, and 3->0, so the loop started and ended with 0. If we have an array of [-1, 2], then this would not be a loop because index 0->1, but 1->1, so we don't start and end with the same index.

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

``````static boolean cyclesThroughStart(int start, int... arr) {
int slowIdx = start;
int fastIdx = start;
do {
slowIdx = f(arr,slowIdx);
fastIdx = f(arr,f(arr,fastIdx));
if (slowIdx == start || fastIdx == start) {
return true;
}
} while(slowIdx != fastIdx);
return false;
}

static int f(int[] arr,int idx) {
idx += arr[idx];
return Math.abs(idx % arr.length);
}``````

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

So, if I read it correctly we are checking whether the cycle passes through the start index.
In which case this code should work:

``````static boolean cyclesThroughStart(int start, int... arr) {
int slowIdx = start;
int fastIdx = start;
do {
slowIdx = f(arr,slowIdx);
fastIdx = f(arr,f(arr,fastIdx));
if (slowIdx == start || fastIdx == start) {
return true;
}
} while(slowIdx != fastIdx);
return false;
}

static int f(int[] arr,int idx) {
idx += arr[idx];
return Math.abs(idx % arr.length);
}``````

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

Through dfs

``````#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool detect(int v,vector<int>V[],bool visited[],bool recur[],bool& det)
{
visited[v]=true;
recur[v]=true;
for(int i=0;i<V[v].size();i++)
if(visited[V[v][i]]==false)
detect(V[v][i],V,visited,recur,det);
else if(visited[V[v][i]]==true && recur[V[v][i]]==true)
det=true;
recur[v]=false;
}

int main(void)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
vector<int>V[n+5];
for(int i=0;i<n;i++)
V[i].push_back((i+arr[i]+n)%n);
bool visited[n];
bool recur[n];
memset(visited,0,sizeof(visited));
memset(recur,0,sizeof(recur));
bool x=false;
for(int i=0;i<n;i++)
if(visited[i]==false)
detect(i,V,visited,recur,x);
if(x==false)
cout<<"NO LOOP"<<endl;
else
cout<<"Loop exist"<<endl;
return 0;
}``````

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

This is my solution using ArrayList. Suggestions are welcomed.

I am adding every visited index in the arrayList and checking that whether it's been previously added or not. If it is already in the arrayList then there exist a cycle otherwise no cycle.

Even if the array is like [2,0,0,0,0]. There is a cycle after first iteration. Because after reaching at index 2 from the start, in the next iteration I am again visiting it because of the 0 displacement.

If the above situation is not to be taken care of then we can add one more condition to check whether the new value is the same as previous(previous = value at the end of the for loop) value then need to break the loop and return false.

``````public class FindCycleInArray {

ArrayList<Integer> arrayList = new ArrayList<Integer>();

public boolean findCycle(int a[]){

for(int i=0;i<a.length;){
int value = (i+a[i])% a.length;

if(arrayList.contains(value)){
return true;
}
else{
}
i=value;

}

return false;
}
}``````

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

``````public static boolean hasLoop(int start, int[] array){
BitSet db = new BitSet(array.length);
int pos=start;
for(int i =0;i<array.length+1;i++){
if(db.get(pos)) return false;
db.set(pos);
pos = pos + array[pos];
if(pos < 0) pos = (pos%array.length) + array.length-1;
else  pos = (pos%array.length);
if (pos == start)  return true;
}
return false;
}``````

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

IsLoop() {
return TRUE; // there will always be a loop
}

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

* 1. Start from first element, if zero then we can't move forward.
* 2. Record the current index in bitset : store.set(i, true);
* 3. If not zero, the nextIndex = (curIndex+a[i])%size
* 4. Move to next index and follow same step.
* 5. If bitset.size() == size , that means we have covered all elements of array.
* 5. If we find bitset.get(index) == true, break the loop and return true;

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

{{
* 1. Start from first element, if zero then we can't move forward.
* 2. Record the current index in bitset : store.set(i, true);
* 3. If not zero, the nextIndex = (curIndex+a[i])%size
* 4. Move to next index and follow same step.
* 5. If bitset.size() == size , that means we have covered all elements of array.
* 5. If we find bitset.get(index) == true, break the loop and return true;
}}

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.

### 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.