CareerCup

Here is a C# solution using a queue to hold the window elements.

protected Int32 MinFromWindowOfSize(List<int> baseList, int windowSize)
    {
        List<int> window = new List<int>();
        Int32 retVal = Int16.MaxValue;

        foreach (int num in baseList)
        {
            window.Add(num);
            if (window.Count > windowSize)
            {
                window.RemoveAt(0);
            }
            if (window.Count == windowSize && window.Sum() < retVal)
                retVal = window.Sum();
        }

        return retVal;
    }

I *think* that makes this O(n) since you only need to visit each element once, which is better than O(nw) where n is number of elements and w is the size of the window. However I'm still sketchy on my big O so appreciate comments/corrections if I'm wrong :)

Hi, did you get this question during the group coding interview or regular technical interview. Can you share your experience?

void getmin(int a[],int n,int num)
{
     int i=0;
     int b[100];
     push_back(0);
     for(i=1;i<n;i++)
     {
        while(front()!=-100 && front() <= i-num)
              pop_front();
        while(front()!=-100 && a[back()]>a[i])
              pop_back();
        push_back(i);
        if(i>=num-1)
           b[i-num+1]=a[front()];
     }
     for(i=0;i<n-num+1;i++)
        printf("%d\t",b[i]);
     printf("\n");
}

/*A Simple Java Code would look like this: */
import java.util.Scanner;

public class SlidingWindow {

    public static void main(String[] args) {
	// TODO Auto-generated method stub

	Scanner in = new Scanner(System.in);
	System.out.println("enter number of elements:");
	int n = in.nextInt();
	int a[] = new int[n + 1];
	int temp[] = new int[n + 1];
	System.out.println("enter " + n + " elements:");
	for (int i = 0; i < n; i++) {
	    a[i] = in.nextInt();
	}

	System.out.println("enter the window size: ");
	int w = in.nextInt();

	for (int i = 0; i < (a.length - w); i++) {
	    for (int j = i; j < w + i; j++) {
		System.out.print(a[j] + " ");
		temp[j] = a[j];
		continue;
	    }
	    System.out.println("Minimum is: " + findMin(temp));
	    System.out.println("");

	}
    }

    public static int findMin(int[] a) {
	int len = a.length;
	int val = a[0];
	for (int i = 1; i < len; i++) {
	    if (val < a[i]) {

	    } else {
		val = a[i];
	    }
	}
	return val;
    }
}

Please correct me if I am wrong.

public static void maxSlidingwindow(int a[],int n,int w)
    {
        int b[]=new int[n];
        Deque<Integer> q=new ArrayDeque<>();
        for(int i=0;i<w;i++)
        {
            while(!q.isEmpty() && a[i]<=a[q.peekLast()])
                q.removeLast();
            q.addLast(i);
        }
        for(int i=w;i<n;i++)
        {
            b[i-w]=a[q.peekFirst()];
            while(!q.isEmpty() && a[i]<=a[q.peekLast()])
                q.removeLast();
            while(!q.isEmpty() && q.peekFirst() <= i-w)
                q.removeFirst();
            q.addLast(i);
        }
        b[n-w]=a[q.peekFirst()];
        
        for(int i=0;i<n;i++)
            System.out.print(b[i]+"\t");
    }