Facebook Interview Question
SDE1sCountry: United States
@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
}
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 :)
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;
}
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;
}
}
}
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;
}
}
}
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;
}
}
}
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 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
@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