Facebook Interview Question for SDE1s


Country: United States




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

@Koustav.adorable gave a solution using O(n) for both time and memory here I am providing a solution that is O(n) for time but O(1) for memory. Coded in a python one liner

def largestSK(seq):
     return sum(0 if (pos == value or pos == seq[value]) else 1 for pos, value in enumerate(seq))

@koustav.adorable great solution it helped me greatly to understand the problem, just one thing, maxLen should be 0 not 1. What if you have an empty list or a sorted vector as input?

- Fernando July 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@koustav: [1,2,0,2,2,4] returns 3, should return 4 as 4,2,0,1, I think Fernando has a similar issue

Assumptions:
- S is a sequence with unique values, because it has an order (or ordered set)
- Since the set can be empty that is only the case if
A[i] >= n or A[i] < 0, for all A[i], 0 <= i < n
- I therefore assume values within A have no constraint other than being
integers
[- a neat simplification would be to state, 0 <= A[i] < n for all A[i], 0 <= i < n
which would make the thing easier to code.]

Solution:
- insight brings drawing it as a graph. I think key is to notice it's a
graph problem, makes it easier to draw and argue.
- first approach is starting from each node until closing a cycle or until
encountering a node that has a value < 0 or >= n
This is inefficient as it might have common subproblems
It's O(n^2) worst time, e.g. for array [n-1, 0, 1, 2, ..., n-2]
- better approach is to start with node i and have an array which stores per
node how large the already discovered path is that one can visit starting
from node i. That is, how long is the path until it starts a cycle or
encounters a node of value bejond array range

this has time complexity of O(n) compensated, and a space complexity of O(n)
I get the imrpession there is a more elegant approach but coudln't find it
in 10 minutes thinking.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int max_component_size(const vector<int>& input) {
	size_t n = input.size();
	vector<int> component_size(n, 0);
	int max_size = 0;
	for (size_t i = 0; i < n; ++i) {
		if (component_size[i] == 0) {
			// 1. discover until 
			//    - a cycle
			//    - an already found component
			//    - a value "pointing" bejond array range
			size_t j = i;
			int disc_size = 0;
			while (component_size[j] == 0) {
				component_size[j] = -1;
				j = static_cast<size_t>(input[j]); // negative input values will create > n values
				if (j < n) disc_size++;
				else break;
			}
			if (j >= n || component_size[j] != -1) {		
				// it's a path enetering an already discovered
				// path or it's a path to nowhere j >= n
				if(j < n) disc_size += component_size[j];
				max_size = max(disc_size, max_size);
				// backtrack and store discovered component size
				j = i; 
				while (j < n && component_size[j] == -1) {
					component_size[j] = disc_size;
					j = input[j];
					disc_size--;
				}
			} else {
				// it's a cycle
				max_size = max(disc_size, max_size);
				while (component_size[j] == -1) {
					component_size[j] = disc_size;
					j = input[j];
				}
			}
		}
	}
	return max_size;
}

int main()
{	
	cout << max_component_size({ 5, 4, 0, 3, 1, 6, 2 }) << endl; // should be 4: sample given
	cout << max_component_size({ 1, 2, 0, 2, 2, 4 }) << endl; // should be 5: 5,4,2,1,0
	cout << max_component_size({ 5, 0, 1, 2, 3, 4 }) << endl; // should be 6: e.g. 0,5,4,3,2,1
	cout << max_component_size({ 1, 2, 3, 4, 5, 0 }) << endl; // should be 6: e.g. 0,1,2,3,4,5
	cout << max_component_size({ -1, 9, 2 }) << endl; // should be 1, 9
	cout << max_component_size({ -1, 9, -2 }) << endl; // should be 0
	cout << max_component_size({ 1, 0, -1, 2, 3, -3, 5, 8, 4 }) << endl; // 4: 8,4,3,2
}

- Chris July 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello Chris, both my solution and the previous one assume that you can't have duplicates. At the beginning I also was doubting if duplicates were allowed or not but as it is stated I think it makes more sense that you can't have them, also based on the given example. Anyway, the first solution I made accepted duplicates, the code is quite similar to the solution koustav.adorable offered but the visited list was initialized inside the for loop. In that way you check every possible loop starting from each position of the array (also you have to promote lenCurr to a set in order to avoid counting the duplicates more than once).
Cheers :)

- Fernando July 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int test(int[] source) {
int globalMax = 1;
Set<Integer> re = new HashSet<>();
for ( int i = 0; i< source.length; i++) {
int max = 1;
int start = source[i];
re.add(start);
while( (start>=0) && (start <source.length)) {
start = source[start];
if(!re.contains(start)){
max++;
re.add(start);
}else {
break;
}
}
re.clear();
if (max > globalMax)
globalMax = max;
}
return globalMax;
}

- Anonymous August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;


import java.util.ArrayList;
import java.util.List;

public class Main {

    static int [] array = new int[]{5,4,0,3,1,6,2};

    public static void main(String[] args) {
        List<Integer> set = createSet(2);
        System.out.println("Size of the set: "+set.size());
        String s = set.toString();
        System.out.println(s);
    }

    public static List<Integer> createSet(int n){
        List<Integer> set= new ArrayList<Integer>();
        try {
            while (true) {
                if(set.size()==0){
                    set.add(array[n]);
                }
                else {
                    int value = array[set.get(set.size() - 1)];
                    if(!set.contains(value)) {
                        set.add(value);
                    }
                    else {
                        throw new Exception("We already have the element");
                    }
                }

            }
        }catch (Exception e){

        } finally {
            return set;
        }

    }

}

- Jose Luis Larraz August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Main {

    static int [] array = new int[]{5,4,0,3,1,6,2};

    public static void main(String[] args) {
        List<Integer> set = createSet(2);
        System.out.println("Size of the set: "+set.size());
        String s = set.toString();
        System.out.println(s);
    }

    public static List<Integer> createSet(int n){
        List<Integer> set= new ArrayList<Integer>();
        try {
            while (true) {
                if(set.size()==0){
                    set.add(array[n]);
                }
                else {
                    int value = array[set.get(set.size() - 1)];
                    if(!set.contains(value)) {
                        set.add(value);
                    }
                    else {
                        throw new Exception("We already have the element");
                    }
                }

            }
        }catch (Exception e){

        } finally {
            return set;
        }

    }

}

- Jose Luis Larraz August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;


import java.util.ArrayList;
import java.util.List;

public class Main {

static int [] array = new int[]{5,4,0,3,1,6,2};

public static void main(String[] args) {
List<Integer> set = createSet(2);
System.out.println("Size of the set: "+set.size());
String s = set.toString();
System.out.println(s);
}

public static List<Integer> createSet(int n){
List<Integer> set= new ArrayList<Integer>();
try {
while (true) {
if(set.size()==0){
set.add(array[n]);
}
else {
int value = array[set.get(set.size() - 1)];
if(!set.contains(value)) {
set.add(value);
}
else {
throw new Exception("We already have the element");
}
}

}
}catch (Exception e){

} finally {
return set;
}
}
}

- Jose Luis Larraz August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int largestSet0(int[] A) { // O(n)
int max = 0;
int len = A.length;
for (int i = 0; i < len; i++) {
int count = 1;
int j = A[i];
while (j < len && A[j] != A[i]) {
int t = j;
j = A[j];
A[t] = len + j;
count++;
}
max = Math.max(max, count);

}
return max;
}

- I think it can work on O(n) November 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def printLongestCycle(list):
    visited = [0 for x in range(len(list))];
    maxLen = 1;
    for idx in xrange(len(list)):
        lenCurr = 0;
        while visited[idx] == 0:
              visited[idx] = 1;
              idx = list[idx];
              lenCurr = lenCurr + 1;
        maxLen = max(lenCurr, maxLen);
    return maxLen;

print(printLongestCycle([1, 2, 3, 4, 0, 5]));

- koustav.adorable July 29, 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