Microsoft Interview Question
Applications DevelopersCountry: India
Interview Type: Written Test
Sample Input : [1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 20, 23, 30,31,32,33]
Sample Output: 4 sequences
int compute(int a[],int n)
{ count=1;i=0;
while(i<n)
{ if(a[i+1]!=a[i]+1)
count++;
i++;
}
return(count);
}
If sorting is allowed than we can get the result in O(nlogn) time. Sample java code
public static int find2(int[] a) {
int[] b = new int[a.length + 1];
System.arraycopy(a, 0, b, 0, a.length);
b[a.length] = Integer.MAX_VALUE;
Arrays.sort(b);
int count = 1;
int num = 0;
for (int i = 1; i < b.length; i++) {
if (b[i] > b[i - 1] + 1) {
if (count > 1) {
num++;
}
count = 1;
} else {
count++;
}
}
return num;
}
int _tmain(int argc, _TCHAR* argv[])
{
int num_list[] = {1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 20, 23, 30, 31, 32, 33};
int seq_count = 0;
int seq_started = 0;
for (int i = 0; i < sizeof(num_list) / sizeof(int) - 1; i++)
{
if (num_list[i+1] == num_list[i] + 1)
{
if (seq_started == 0)
{
seq_count++;
seq_started = 1;
}
}
else
{
if (seq_started == 1)
seq_started = 0;
}
}
printf("%d sequences", seq_count);
getchar();
return 0;
}
void NumberOfSequences()
{
int arr[]={1,2,5,6,7,8,10,11,12,14,16,17,18,19,20};
int count=0;
bool IsSequence=false;
for(int i=1;i<sizeof(arr)/sizeof(int);i++)
{
if(arr[i-1]==arr[i]-1)
{
if(!IsSequence)
{
count++;
IsSequence=true;
}
}
else
IsSequence=false;
}
cout<<"Count is "<<count<<endl;
}
int seq_in_array ( int* array, int size )
{
// Initialize two begin and end pointers to the start of the array
int* begin_ptr = array;
int* end_ptr = array;
int i,counter = 0;
if ( size == 0 || size == 1)
{
return size;
}
else
{
for ( i = 0 ; i < size - 1; i++ )
{
if ( *(end_ptr+1) == *(end_ptr)+1 )
{
end_ptr++;
}
else
{
if ( begin_ptr == end_ptr )
{
begin_ptr++;
end_ptr++;
}
else
{
end_ptr++;
begin_ptr = end_ptr;
counter++;
}
}
}
if ( begin_ptr != end_ptr )
counter++;
}
return counter;
}
#include<iostream.h>
int main()
{
int a[30],i=0,size,j=0,count=0,temp;
cout<<"enter the array size: ";
cin>>size;
cout<<"\nenter the elements:\n";
while(i<size)
cin>>a[i++];
for(i=0;i<size;i++)
{
for(j=0;j<i;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
i=0;
while(i<size)
{
j=0;
if(a[i+1]==a[i]+1)
{
count++;
cout<<"\nSequence "<<count<<":{";
cout<<a[i];
while(a[i+j+1]==a[i+j]+1)
{
cout<<", "<<a[i+j+1];
j++;
}
cout<<"}";
i=i+j+1;
}
else
i++;
}
cout<<"\n";
return 0;
}
int findseq(int a[],int size)
{
int count=0;
while(--size)
{
if(a[i]==a[i+1]-1) continue;
count++;
}
return count;
}
my understanding of the question is:
- Andi November 15, 2012input: int[] a = {2,3,12,5,6,89,1,10,13,77,11,90}
Output:
{1,2,3,}
{5,6}
{10,11,12,13}
{89,90}
am I correct?