## Facebook Interview Question for SDE1s

Country: United States

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

Is it just me, or is this a really easy question?

You know the length of the array. Say the array is length n. If you follow the indices of the elements of the array, and the number of steps/jumps you're taking exceeds n, then there must be a cycle.

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

Indices may not be connected inorder to follow them. eg. 5, 1, 1, 2, 3, 4.

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

In O(1) because it sais "each element points to the index of the next element".
That means every element's value must be [0..n-1]. So, it points either to itself or
an other element. Pointing to itself is a cycle. Thus every such array with at least
1 element will contain a cycle.

Can be proven by induction or by intuition. By intuition: try to form a linked list
without loop when there is no special indication for the next-pointer to mark the end.

That's probably not the intention of the question ;-), So I change interpreting arr[i] = i as loop, but rather interpret it as vertex with no outgoing edge (end node).

For convenience I keep the assumptions there can't be elements with value < 0 or >= n,
when n is the number of elements in arr. Now the graph has more interesting properties:
a) it is directed
b) every vertex has at most one outgoing edge (linked list)

The question is, no extra space is allowed, but are we allowed to modify the array?
If not then use the brute force approach (O(n^2)).

If modification is allowed, next question is do I need to undo the modification after
the algo finishes. I assume I can modify and don't have to undo:

Assuming I start DFS at a single vertex, it will detect a cycle if it re-visits a vertex.
If I start DFS from an other vertex, visiting an already visited vertex could mean:
- it was visited by a prior DFS run from an other vertex: cylce if prev. rund found cycle
- it was visited by this DFS run: cycle

Usually with DFS there is an enter and leave counter helping to distinguish between cycles forward edges and cross edges. Just a visited falg isn't enough (that's why some solutions here fail on test case 1 below). But since I have at most one outgoing edge, in a single DFS pass there can't be cross edges nor forward edges. But among different DFS passes I need to distinguish between whether I step into a cycle or hit a previous DFS tree.

I start at every vertext s: 0 <= s < n
I follow it's path until I get to a vertex with value >= n. While following that path
I change each vertext value to n + s. If the last vertex visited for this start
has a value of n + s, it was a cycle.

This will have O(n) time complexity because each vertex is visited exactly once.

``````#include <vector>
#include <iostream>
#include <limits>

using namespace std;

// solution 1: no extraspace, doesn't modify given vector, time complexity O(n^2)
// considers arr[i] = i as end node, not as cycle
// arr[i] < 0 and arr[i] >= n are not allowed
bool hasCycleBf(const vector<unsigned int>& arr) {
size_t n = arr.size();
for (size_t s = 0; s < n; ++s) {
size_t i = s, l = 0;
while (l <= n && i < n && arr[i] != i) {
i = arr[i];
l++;
}
if (l > n) return true;
}
return false;
}

// solution 2: marking visited elements, time complexity O(n)
bool hasCycle(vector<unsigned int> arr) // copy arr here, lazy programmer
{
size_t n = arr.size();

// do a kind of DFS from each starting index
for (size_t s = 0; s < n; ++s) {
size_t i = s;
while (i < n && arr[i] != i) {
int t = arr[i];
arr[i] = n + s;
i = t;
}
if (i == n + s) return true;
}
return false;
}

int main()
{                      //0,1,2,3,4,5
cout << hasCycleBf({ 0,1,5,4,3,5 }); // cycle
cout << hasCycleBf({ 1,2,3,4,5,0 }); // cycle
cout << hasCycleBf({ 1,2,3,4,5,5 }); // no cycle
cout << hasCycleBf({ 1,2,4,4,5,5 }); // no cycle
cout << endl;
cout << hasCycle({ 0,1,5,4,3,5 }); // cycle
cout << hasCycle({ 1,2,3,4,5,0 }); // cycle
cout << hasCycle({ 1,2,3,4,5,5 }); // no cycle
cout << hasCycle({ 1,2,4,4,5,5 }); // no cycle
return 0;
}``````

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

``````public class CycleFindingOverArray {

public static void main(String[] args) {
int [] F=  {6,6,0,1,4,3,3,4,0};
System.out.println( hasCycle(F));
}

/*
F can be thought of as a function that maps values of its indices to itself
where each i, 0<=i<=F.length -1
Cycle detection can be done with Floyd's cycle finding method
*/
static boolean hasCycle(int[] F) {
final int len = F.length;
int slow, fast;
switch (len) {
case 1:
/* loop of single element */
return F[0] == 0;
case 2:
/* loop(s) with first two elements */
return F[0] == 1 && F[1] == 0 || F [0]==0 || F[1] ==1;
default:
/* a bigger loop */
slow = F[0];
fast = F[F[0]];
while (slow != fast && fast >= 0 && fast <= F.length - 1) {
slow = F[slow];
fast = F[F[fast]];
}
return slow == fast;
}
}
}``````

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

Simple c++ solution.
It's easier than DFS since for every node there is only 1 descendant, so i insert for every route the nodes i visited, and check if they in the route. I don't want to repeat a visited nodes that i already check, so i have 2 sets, 1. all visited nodes, 2. new set for every new node-route.

``````#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;
bool isCycle (vector<int>& vec) {
unordered_set<int> visited;
unsigned int s = vec.size();
unsigned int count = 0;
for (unsigned int ind = 0; ind < vec.size(); ind++ ) {
if (visited.find(ind) != visited.end()) {
continue;
}
int ind1 = ind;
unordered_set<int> route;
do {
cout << "ind1 :" << ind1 << endl;
if(route.find(ind1) != route.end()) {
return true;
}
route.insert(ind1);
visited.insert(ind1);
ind1 = vec[ind1];
} while(ind1 >= 0);

}

return false;
}

int main()

{

std::vector<int> v={1,5,-1,-1,-1,-1,-1};
cout<<isCycle(v);

std::vector<int> v1={1,5,3,0,-1,3,-1};
cout<<isCycle(v1);

return 0;
}``````

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

Simple array loop with hash contains the visited indexes comes to mind:

``````void checkCircularArray(const std::vector<int>& arr)
{
std::unordered_set<int> VisitedIndex;
int index = -1;
for(size_t i = 0; i < arr.size(); ++i) {
if(index == -1) {
index = arr[0];
} else {
index = arr[index];
}
if(VisitedIndex.count(index)) {
std::cout << "Circular found!" << std::endl;
return;
}
VisitedIndex.insert(index);
}
std::cout << "No dependency found!" << std::endl;
}``````

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

@kustav.adorable: sorry, try this test case { 0,1,5,4,3,5 }, has a cycle but won't be detected

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

Just summarize values of all elements. If there is no cycles the sum should be equal to arithmetic progression of array size.

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

Fail: 0,1,5,4,3,5

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

Treat the array as a linked list. Then fast and slow pointer trick will solve the problem.

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

To not use extra space we can simply use the array as the visited map. Each time we visit a element we can overwrite it with a special value marking it visited.

``````function hasCycles(input) {
var visitedMarker = -1;
var currentIndex = 0;
for(var i = 0; i < input.length; ++i) {
var nextIndex = input[currentIndex];
if (input[nextIndex] === visitedMarker) {
return true;
}
input[currentIndex] = visitedMarker;
currentIndex = nextIndex;
}
return false;
}

var tests = [
[0,1,5,4,3,5], //true
[1,2,3,4,5,0], //true
[1,2,3,4,5,5], //false
[1,2,4,4,5,5]  //false
].forEach(function(test) {
console.log(test + ' hasCycles => ' + hasCycles(test) );
})``````

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

Its a common LinkedList problem. You can achieve this by using the Runner Technique on LinkedList.

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

``````public boolean isCycle(int[] arr) {

for(int i = 0;  i < arr.length; i++) {
Set<Integer> set = new HashSet<>();
if(arr[i] == -1)
continue;
int val = arr[i];
arr[i] = -1;
if(checkCycle(arr, set, val)) {
return true;
}

}

return false;

}

private boolean checkCycle(int[] arr, set<Integer> set,  int ind) {
if(arr[ind] == -1)
return false;
if(set.contains(ind) {
return true;
}
int val = arr[ind];
arr[ind] = -1;
return checkCycle(arr, set, val);

}``````

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

``````public static void main(String args[]) throws Exception {
int arr[] = { 2, 3, 4, 0, 1 };
// int arr[] = { 0, 1, 2, 3, 4 };
System.out.println(detectCycle(arr));
}

public static boolean detectCycle(int arr[]) {
final int N = arr.length;
int index = 0;
while (index < N) {
while ((!(arr[index % N] / N > 1)) && index < N) {
if (index != arr[index % N]) {
int temp1 = arr[index] % N;
arr[index % N] = arr[index % N] + N;
index = temp1;
} else {
index++;
}
}
index++;
}
if (Arrays.stream(arr).max().getAsInt() / N > 1)
return true;
return false;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

This is a plain DFS problem using recursion/iteration.
However, it gets a deal if you can do it without space.We can optimise space by using a bit array.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````public class Main {

public static void main(String args[]) {

CycleArray cycle = new CycleArray(new int[]{1,3,2,7,8,6,30,5,21,22});

System.out.print(isCycle(0,0, new int[]{1,3,2,7,8,6,30,5,21,22}));

}

private static boolean isCycle(int index_1, int index_2, int[] array) {

if (index_2 >= array.length || array[index_2] >= array.length) {
return false;
}
int single_jump = array[index_1];
int double_jump = array[array[index_2]];

return single_jump == double_jump || isCycle(single_jump, double_jump, array);

}
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````public class Main {

public static void main(String args[]) {

CycleArray cycle = new CycleArray(new int[]{1,3,2,7,8,6,30,5,21,22});

System.out.print(isCycle(0,0, new int[]{1,3,2,7,8,6,30,5,21,22}));

}

private static boolean isCycle(int index_1, int index_2, int[] array) {

if (index_2 >= array.length || array[index_2] >= array.length) {
return false;
}
int single_jump = array[index_1];
int double_jump = array[array[index_2]];

return single_jump == double_jump || isCycle(single_jump, double_jump, array);

}``````

}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````public class Main {

public static void main(String args[]) {

System.out.print(isCycle(0,0, new int[]{1,3,2,7,8,6,30,5,21,22}));

}

private static boolean isCycle(int index_1, int index_2, int[] array) {

if (index_2 >= array.length || array[index_2] >= array.length) {
return false;
}
int single_jump = array[index_1];
int double_jump = array[array[index_2]];

return single_jump == double_jump || isCycle(single_jump, double_jump, array);

}``````

}

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.