Samsung Interview Question
Software Engineer / DevelopersCountry: United States
Use a hashtable that stores value of the array as 'key' and index as 'value'. Iterate through the array, each time checking if the array element is present in the hashtable. If yes, it implies that there is a cycle in the array and the length of the cycle = current_array_index - 'value' in the hashtable.
However here if array contains wide range of numbers lets say cycle is like
2->200->3000->30000 then what is hashtable size?
static int detectCycle(int[] a) {
for(int i =1; i< a.length; i++) {
if(a[i] == a[0]){
//Cycle possible
boolean cycleDetected = true;
for(int j = 1; j< i && j+i<a.length; j++) {
if(a[j] != a[j+i]) {
//Not a cycle
cycleDetected = false;
break;
}
}//for
if(cycleDetected) {
//Cycle detected
return i;
}
}
}
//No cycle
return -1;
}
public int CycleLength(int[] intar )
{
bool check = true;
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < intar.Length; i++)
{
if (dict.Count == 0)
{
dict.Add(i,intar[i]);
}
else
{
if (dict.ContainsValue(intar[i]))
{
if (!(dict[(i % dict.Count)] == intar[i]))
{
check = false;
}
}
else { dict.Add(i,intar[i]);}
}
}
if (check)
return dict.Count;
return 0;
}
public static boolean detectcycle(int array[]){
int startindex= 0;
int count=1;
for(int i=1;i<=array.length/2;i++){
//detect cycle
if(array[i]==array[startindex]){
//store lastIndex or one cycle
int lastIndex=i-1;
//System.out.println(lastIndex);
while(startindex<=lastIndex&&i<array.length){
if(array[i]==array[startindex]){
i++;
startindex++;
}
else {
System.out.println("no cycle found");
return false;
}
}
System.out.println("cycle length is : "+count);
}
else{
count++;
}
}
return true;
}
var B = [];
for( i = 0 ;i< A.length ;i++){
c= 0;
B[c] = A [i] ;
for(j=i+1;j<A.length;j++){
if(A[i]!=A[j])B[++c] = A[j] ;
else{
k= 0;p =j;
while(k<=c){
if(A[p]!=B[k])
break;
p++;k++;
}
if(k==c+1){
console.log("Pattern found" + j + c ) ;
for(t =0;t<=c;t++)
console.log( B[t] );
i= A.length;j = A.length
}
else{
console.log(c,j);
B[++c] = A[j];}
}
}
}
- peter January 14, 2014