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

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
}``````

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 :)

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];
while( (start>=0) && (start <source.length)) {
start = source[start];
if(!re.contains(start)){
max++;
}else {
break;
}
}
re.clear();
if (max > globalMax)
globalMax = max;
}
return globalMax;
}

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){
}
else {
int value = array[set.get(set.size() - 1)];
if(!set.contains(value)) {
}
else {
throw new Exception("We already have the element");
}
}

}
}catch (Exception e){

} finally {
return set;
}

}

}``````

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){
}
else {
int value = array[set.get(set.size() - 1)];
if(!set.contains(value)) {
}
else {
throw new Exception("We already have the element");
}
}

}
}catch (Exception e){

} finally {
return set;
}

}

}``````

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){
}
else {
int value = array[set.get(set.size() - 1)];
if(!set.contains(value)) {
}
else {
throw new Exception("We already have the element");
}
}

}
}catch (Exception e){

} finally {
return set;
}
}
}

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;
}

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]));``````

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.