Interview Question
Country: United States
public class LongSequenceTest {
public static ArrayList<Integer> LongSequence(Integer... sequence) {
if (sequence == null || sequence.length == 0)
return null;
List<Integer> seqList = new ArrayList<Integer>(Arrays.asList(sequence));
Collections.sort(seqList);
List<Integer> currentSeq = new ArrayList<Integer>();
List<Integer> retSeq = new ArrayList<Integer>();
currentSeq.add(seqList.get(0));
int lastValue = seqList.get(0);
int longSeq = 0;
for(int i=1; i < seqList.size(); i++){
if(lastValue+1 == seqList.get(i)){
currentSeq.add(seqList.get(i));
lastValue++;
} else {
if(longSeq == 0 || currentSeq.size() > longSeq){
longSeq = currentSeq.size();
retSeq = currentSeq;
}
lastValue = seqList.get(i);
currentSeq = new ArrayList<Integer>();
currentSeq.add(seqList.get(i));
}
}
if (longSeq == 0 || currentSeq.size() > longSeq){
retSeq = currentSeq;
}
return (ArrayList<Integer>) retSeq;
}
public static void main(String arg[]) {
ArrayList<Integer> ret = LongSequence(7, 2, 3, 5, 6, 9);
for(Integer i : ret) {
System.out.print(i + " ");
}
}
}
if space complexity is not the issue ,u can use Hashset . First insert all the element then for each element search its next or previous if anyone present .If any one present delete both from the HashSet and increase the counter accordingly and search for next element .For each new element make count=0,also make track of max count .complexity O(n) both in space and time
#include<stdio.h>
#include<stdlib.h>
void sort_array(int arr[], int n)
{
int i, j, temp;
for (i = 0 ; i < ( n - 1 ); i++)
{
for (j = 0 ; j <( n - i - 1); j++)
{
if (arr[j] > arr[j+1])
{
/* Swapping */
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main()
{
int i;
int arr[] = {1,4, 3, 2, 45, 7, 48, 66} ;
sort_array(arr,7);
printf("%d ",arr[0]);
for(i=1;i<sizeof(arr)/sizeof(int);i++)
{
if( (arr[i] - arr[i-1]) == 1)
printf("%d ",arr[i]);
else
break;
}
return 0;
}
- Rich August 17, 2013