Facebook Interview Question
SDE1sCountry: United States
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;
}
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;
}
}
}
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;
}
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;
}
Just summarize values of all elements. If there is no cycles the sum should be equal to arithmetic progression of array size.
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) );
})
public boolean isCycle(int[] arr) {
for(int i = 0; i < arr.length; i++) {
Set<Integer> set = new HashSet<>();
if(arr[i] == -1)
continue;
set.add(i);
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;
}
set.add(ind);
int val = arr[ind];
arr[ind] = -1;
return checkCycle(arr, set, val);
}
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;
}
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);
}
}
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);
}
}
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);
}
}
Is it just me, or is this a really easy question?
- TJ September 14, 2017You 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.