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.

- TJ September 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sri November 26, 2017 | Flag
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;
}

- Chris September 13, 2017 | Flag Reply
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;
        }
    }
}

- Makarand September 13, 2017 | Flag Reply
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;
}

- jay September 12, 2017 | Flag Reply
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;
}

- PenChief September 12, 2017 | Flag Reply
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

- Chris September 13, 2017 | Flag Reply
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.

- Stan.Belkin September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sri November 26, 2017 | Flag
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.

- zateon September 13, 2017 | Flag Reply
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) );  
})

- tnutty2k8 September 14, 2017 | Flag Reply
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.

- Zeus Bolt September 19, 2017 | Flag Reply
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;
		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);	
		

}

- Anonymous November 10, 2018 | Flag Reply
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;
	}

- koustav.adorable September 12, 2017 | Flag Reply
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.

- koustav.adorable September 12, 2017 | Flag Reply
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);

    }
}

- Toki September 12, 2017 | Flag Reply
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);

    }

}

- Toki September 12, 2017 | Flag Reply
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);

    }

}

- alexandru.antochi September 12, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More