Microsoft Interview Question Software Engineer / Developers
Team: Bing
Country: India
Interview Type: In-Person
The first part of the problem can be solved using dynamic programming which builds on string prefix. It is very similar to the longest common sub sequence problem.
Here, the columns will be the given array and the rows will be 1 to k. So any point in the matrix (row, column) says, if 'column' element is included in the window, what is the window size (that much characters to the left).
Finally after constructing the table of size k*n, where n is the length of the array, the minimum element in the kth row will give the position in the input array where the smallest windows (containing k 0's) ends and its value indicates the size of the window.
Recursion relation:
SmallestWindow( length, k ) =
= SmallestWindow (length-1, k-1) + 1 if input[length] == 0 (contributes one zero)
= SmallestWindow (length-1, k) + 1 if input[length] == 1 (simply adds length)
main()
{
int a[]={1,2,5,2,1,6,4,8,9,2,4,6,7,5,9,8,9,7,8,3,0,3};
int b[]={1,2,3,2,2,2,2,2,3,3};
int count=0,start=0,i,len,j;
len=sizeof(a)/sizeof(int);
for(i=0;i<10;i++)
{
for(j=0;j<len;j++)
{
if(a[j]==i && count==0)
start=j;
if(a[j]==i)
count++;
if(count==b[i])
{
printf("The window of %d is %d \n",i,j-start+1);
break;
}
}
count=0;
}
}
int j = 0;
int zero_count = 0;
int min_length = 0;
while( j < n){
if(a[j] == 0)
zero_count++;
if(zero_count == k)
break;
j++;
}
min_length = j;
j++;
while(j < n){
if(a[j] == 0)
move(i); // if a[i] == 0, then i is set to next 0 else next to next 0
if( j - i < min_length)
min_length = j - i;
j++;
}
There seems to be some problem with the code. Where is 'i' being initialized and populated in the above code?
int min_window_zero(const int& n, const int& k, const int * array)
{
vector<int> zero_indices_vector;
for (int i = 0; i < n; i++)
{
if (array[i] == 0)
zero_indices_vector.push_back(i);
}
int min_length = n;
for (int i = 0; i + (k - 1) < zero_indices_vector.size(); i++)
{
int tmp = zero_indices_vector[i+k-1] - zero_indices_vector[i] + 1;
if ( tmp < min_length )
min_length = tmp;
}
return min_length;
}
class Element
{
public:
Element(int num, int index):
number(num),
index(index),
next_required_occur(NULL)
{
for (int i = 0; i < 10; i++)
next_element_of_value[i] = NULL;
next_required_occur = NULL;
}
int number;
int index;
Element* next_element_of_value[10];
Element* next_required_occur;
int MinLength(const int* digit_occur)
{
int min = 0x7fffffff;
if (this->next_required_occur)
min = this->next_required_occur->index - this->index + 1;
for (int i = 0; i < 10; i++)
{
Element* next_element = next_element_of_value[i];
if (i != number && digit_occur[i] != 0){
if (next_element && next_element->next_required_occur){
if (next_element->next_required_occur->index - this->index + 1 > min)
min = next_element->next_required_occur->index - this->index + 1;
}
else
min = 0x7fffffff;
}
}
if (min == 7)
cout << index << endl;
return min;
}
};
int min_window_digits(const int& n, const int* digit_occur, const int * array)
{
vector<Element*> indices_vector_of_value[10];
Element* p_most_recent_element[10];
memset(p_most_recent_element, 0, sizeof(Element*) * 10);
//O(9n) = O(n)
for (int i = 0; i < n; i++)
{
int number = array[i];
Element* e = new Element(number, i);
p_most_recent_element[number] = e;
indices_vector_of_value[number].push_back(e);
for (int j = 0; j < 10; j++)
{
if (j != number){
if (p_most_recent_element[j])
p_most_recent_element[j]->next_element_of_value[number] = e;
}
}
}
//O(n)
for (int i = 0; i < 10; i++)
{
vector<Element*>& v = indices_vector_of_value[i];
for (int j = 0; j + digit_occur[i] - 1 < v.size(); j++)
{
if (digit_occur[i]-1 >= 0)
v[j]->next_required_occur = v[j+digit_occur[i]-1];
}
}
//O(n)
int min_length = n;
for (int i = 0; i < 10; i++)
{
vector<Element*>& v = indices_vector_of_value[i];
for (int j = 0; j < v.size(); j++)
{
int tmp = v[j]->MinLength(digit_occur);
if (tmp < min_length)
min_length = tmp;
}
}
return min_length;
}
No need for dp or any other paradigm. It'll make it complicated. It can be done (1st part) simply as:
#include<stdio.h>
int main()
{
int a[]={1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1};
int count=0;
int i,j;
int len=sizeof(a)/sizeof(int);
int min=len;
i=j=0;
while(i<len)
{
if(count==3)
{
while(a[j]!=0)
{
--j;
}
if((i-j)<min)
{
min=i-j;
}
i=i+1;
j=i;
count=0;
}
if(a[i]==0)
{
++count;
}
++i;
}
printf("%d",min);
return 0;
}
Let me knw if there r any hiccups in it.....
We need to start with a windows with K 0's. Move one-by-one to the right. Keep expanding that windows till you get another '0' ( K+1 0's). Now you shed all left elements, till one '0' is dropped to reach K 0's, to get new windows with K 0's. Now keep sliding this window till you reach end of the array and print the smallest window. will get back with code.
//Minimum set of k-zeros in an array of 1's and o's
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>
void main()
{
int min=0,w,n,t,i=0,k,sum,c,j,index;
int a[100],start[100],end[100],width[100];
clrscr();
printf("Enter n:");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter k:");
scanf("%d",&k);
index=0;
for(i=0;i<n;i++)
{
c=0;
for(t=i;t<n;t++)
{
if(a[t]==0)
{
start[index]=t;
i=t;
printf("index:%d-->%d ",index+1,start[index]);
break;
}
}
for(j=start[index];j<n;j++)
{
if(a[j]==0&&c!=k)
c++;
if(c==k)
{
end[index]=j;
width[index]=end[index]-start[index]+1;
printf("%d %d\n",end[index],width[index]);
break;
}
}
if(j==n&&c<k)
break;
index++;
}
min=n;
for(i=0;i<index;i++)
{
if(width[i]<min)
min=width[i];
}
printf("\n%d\n",min);
for(i=0;i<index;i++)
{
if(width[i]==min)
{
printf("\nMinimum wiNDOW is from index-%d to %d\n Elements are:",start[i],end[i]);
for(j=start[i];j<=end[i];j++)
printf("%d ",a[j]);
}
}
getch();
}
Solution to first question in O(n)
void main()
{
int a[]={1,0,0,0,0,1,0,0,0,1};
int length = sizeof(a)/sizeof(a[0]);
findMinWindow(a,length);
getch();
}
void findMinWindow(int a[],int n)
{
int k=3;
int j=0;
int min=0;
int max=n-1;
for(int i=0;i<n;i++)
{
if (a[i] == 0)
{
j++;
}
else
{
if(j >= k)
{
if(j < (max- min + 1))
{
max=i-1;
min=i-j;
}
}
j=0;
}
}
printf("The window lies from %d to %d", min+1, max+1);
}
Solution to first question in O(n)
void main()
{
int a[]={1,0,0,0,0,1,0,0,0,1};
int length = sizeof(a)/sizeof(a[0]);
findMinWindow(a,length);
getch();
}
void findMinWindow(int a[],int n)
{
int k=3;
int j=0;
int min=0;
int max=n-1;
for(int i=0;i<n;i++)
{
if (a[i] == 0)
{
j++;
}
else
{
if(j >= k)
{
if(j < (max- min + 1))
{
max=i-1;
min=i-j;
}
}
j=0;
}
}
printf("The window lies from %d to %d", min+1, max+1);
}
How about this :
#include<stdio.h>
void main(){
int a[]={1,0,0,1,0,1,0,0,0,1};
int len=sizeof(a)/sizeof(a[0]);
int i,pointer,count=0,k=3;
for ( i=0 ; i<len ; i++ ){
if ( !a[i] ){
a[count++]=i;
if ( count == k )
pointer=count-1;
else if ( count > k ){
if ( ( a[pointer] - a[pointer-(k-1)] ) > ( a[count-1] - a[count-k] ) )
pointer=count-1;
}
}
}
printf("min window from %d to %d\n",a[pointer-(k-1)],a[pointer]);
}
int minimumWindow(int a[], int n, int k)
{
int j(0), cnt(0), min_len(-1) ;
for (int i=0; i < n; i++)
{
if (a[i]==0) cnt++;
while (cnt == k) {
min_len = min_len == -1 ? i-j+1 : min(min_len, i-j+1);
if (a[j] == 1) j++;
}
}
return min_len;
}
Well, here is the algo i told.
- P January 24, 20121. Find the first window. Let start and end be the index of this window.
-- Width = end - start
Keep a min_width variable.
2. Now to find the next window, move the start pointer to second zero in the first window. now from start to end, we already have k-1 0's, we just need to find one more 0 after end. Find this zero, and set the end pointer to this index. this is the second window. set min_width as applicable (if this width is less than the prev width)
3) Keep on doing this, untill end reaches length - 1.
4) Return min_width
O(n) and in-place approach