CareerCup

import java.util.LinkedHashSet;
import java.util.Set;


public class IterativeSubset {

	public static void main(String[] args) {
		
		int array[]=new int[]{5,6,3,1,4,7,8,9,2,11,12,2,4,6,9,4,1};
		
		int arrayLngth=array.length;
		int i=0;
		Set<Integer> sets=new LinkedHashSet<Integer>();
		
		for(int j=0;j<arrayLngth;j++)
		{
			i=j;
			while(!sets.contains(array[i]))
			{
				i=array[i];
				sets.add(i);
			}
			System.out.println(sets.toString());
			sets.clear();
		}

	}

}

Can you provide an example?

public static Set<Integer>[] createSetOfElements(int a[]) {
		Set<Integer>[] allSets = new Set[a.length];
		int largestSetSize = 0;
		for (int i = 0; i < a.length; i++) {
			allSets[i] = new HashSet<Integer>();
			int element = a[i];
			while (!allSets[i].contains(element)) {
				allSets[i].add(element);
				if (element < a.length) {
					element = a[element];
				}
			}
			if (allSets[i].size() > largestSetSize) {
				largestSetSize = allSets[i].size();

			}
		}
		System.out.println("Size of Largest set is " + largestSetSize);
		System.out.println("Printing elements in all sets");
		int i = 1;
		for (Set<Integer> set : allSets) {
			System.out.print("Set# " + i++ + " =>  ");
			for (Integer integer : set) {
				System.out.print(integer + " ");
			}
			System.out.println();
		}
		return allSets;
	}

	public static void main(String[] args) {
		int a[] = { 1, 2, 3, 4, 4, 5 };
		createSetOfElements(a);
	}

Sample Input: { 1, 2, 3, 4, 4, 5 }
Output:
Printing elements in all sets
Set# 1 => 1 2 3 4
Set# 2 => 2 3 4
Set# 3 => 3 4
Set# 4 => 4
Set# 5 => 4
Set# 6 => 5

public static Set<Integer>[] createSetOfElements(int a[]) {
		Set<Integer>[] allSets = new Set[a.length];
		int largestSetSize = 0;
		for (int i = 0; i < a.length; i++) {
			allSets[i] = new HashSet<Integer>();
			int element = a[i];
			while (!allSets[i].contains(element)) {
				allSets[i].add(element);
				if (element < a.length) {
					element = a[element];
				}
			}
			if (allSets[i].size() > largestSetSize) {
				largestSetSize = allSets[i].size();

			}
		}
		System.out.println("Size of Largest set is " + largestSetSize);
		System.out.println("Printing elements in all sets");
		int i = 1;
		for (Set<Integer> set : allSets) {
			System.out.print("Set# " + i++ + " =>  ");
			for (Integer integer : set) {
				System.out.print(integer + " ");
			}
			System.out.println();
		}
		return allSets;
	}

	public static void main(String[] args) {
		int a[] = { 1, 2, 3, 4, 4, 5 };
		createSetOfElements(a);
	}

Sample Input: a[] = { 1, 2, 3, 4, 4, 5 }
Output:
Size of Largest set is 4
Printing elements in all sets
Set# 1 => 1 2 3 4
Set# 2 => 2 3 4
Set# 3 => 3 4
Set# 4 => 4
Set# 5 => 4
Set# 6 => 5

public class maxSet {
public static void main(String[] args) {
int a[] = {5,6,3,1,4,7,8,9,2,11,12,2,4,6,9,4,1};
int b[][] = new int[a.length][a.length];
for(int i=0;i<a.length;i++){
int j=i,n=0;
do{
boolean flag = false;
for(int k=0;k<a.length;k++){
if(b[i][k] == a[j])
flag = true;
}
if(!flag)
b[i][n]=a[j];
j=a[j];
n++;
}while(j<a.length && n<a.length);
}

System.out.println("\n\nSets generated: ");
int count[] = new int[a.length];
int max=0;
for(int i = 0; i<a.length;i++){
for(int j=0 ; j<a.length;j++)
if(b[i][j] != 0){
System.out.print(b[i][j]+ " ");
count[i]++;
}
if(count[i]>max)
max = count[i];
System.out.println();
}

System.out.println("\nSize of largest Set is :"+max);
}
}

Input:
5 6 3 1 4 7 8 9 2 11 12 2 4 6 9 4 1

Sets generated:
5 7 9 11 2 3 1 6 8
6 8 2 3 1
3 1 6 8 2
1 6 8 2 3
4
7 9 11 2 3 1 6 8
8 2 3 1 6
9 11 2 3 1 6 8
2 3 1 6 8
11 2 3 1 6 8
12 4
2 3 1 6 8
4
6 8 2 3 1
9 11 2 3 1 6 8
4
1 6 8 2 3

Size of largest Set is :9

Does the interviewer wants us to modify the given array so that we can find the longest such sequence? Or just print sequences (sets) to the given array?

an interesting variation of the question is, what is the maximum possible size of any set S[i]. the answer is n. all n elements have to be unique from 0 to n-1. another followup - if the n elements can be shuffled around ,create a set of sets of all possible maximum sets .

for example for number 0 1 2 3,
{1,2,3,0},{1,3,0,2} are 2 orderings for S[0] to be of maximum size.

public static void main(String[] args) {
		int[] input = new int[] { 1, 2, 3, 4, 4, 5};
		int[] setSize = new int[input.length];

		int max = -1;
		for (int index = 0; index < input.length; index++) {
			Set<Integer> set = new HashSet<>();
			int curr = input[index];
			boolean alreadySet = false;
			while (!set.contains(curr)) {
				set.add(curr);
				curr = input[curr];
				if (setSize[curr] > 0) {
					// -1 because a[curr] will already be there
					setSize[index] = set.size() + setSize[curr] - 1;
					alreadySet = true;
				}
			}
			if (!alreadySet) {
				setSize[index] = set.size();
			}

			if (max < setSize[index]) {
				max = setSize[index];
			}

			System.out.println("for index " + index + " set size " + setSize[index]);
		}

		System.out.println(max);
	}

public static void main(String args[]){
			
			int arr[]=new int[]{5,6,3,1,4,7,8,9,2,11,12,2,4,6,9,4,1};
			int len = arr.length;
			int maxcount = 0;
			int count = 0;
			Set<Integer> finalSet=null;
			
			for(int i=0;i<len;i++){
				Set<Integer> set = new LinkedHashSet<Integer>();
				int num = arr[i];
				count = 0;
				while(!set.contains(num)){
					set.add(num);
					num = arr[num];
					count++;
				}
				
				if(count>maxcount){
					maxcount = count;
					finalSet = set;
				}
			}
		System.out.println(finalSet);	
		System.out.println("Maxsize is :: "+maxcount);
			
		}

public static void main(String args[]){
			
			int arr[]=new int[]{5,6,3,1,4,7,8,9,2,11,12,2,4,6,9,4,1};
			int len = arr.length;
			int maxcount = 0;
			int count = 0;
			Set<Integer> finalSet=null;
			
			for(int i=0;i<len;i++){
				Set<Integer> set = new LinkedHashSet<Integer>();
				int num = arr[i];
				count = 0;
				while(!set.contains(num)){
					set.add(num);
					num = arr[num];
					count++;
				}
				
				if(count>maxcount){
					maxcount = count;
					finalSet = set;
				}
			}
		System.out.println(finalSet);	
		System.out.println("Maxsize is :: "+maxcount);
			
		}

,hlkjhkj