CareerCup

#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <sstream>
#include <string.h>
#include <assert.h>
using namespace std;

/*
 * @param is: input string stream
 * @param N:  window size
 * @param K:  The biggest K elements in the window
 */
void findKMin(stringstream & is, int N, int K)
{
    assert(N >= K);
    
    // all the numbers in the window in the original order
    queue<multiset<int>::iterator> Q;  
    
    // The numbers in the window in sorted order
    multiset<int> S;
    
    int x;
    
    while (is >> x) {
        if (Q.size() == N) {
            auto pos = Q.front();
            Q.pop();
            S.erase(pos);
        }
             
        auto pos = S.insert(x);
        Q.push(pos);
        
        if (Q.size() == N) {
            auto pos = S.begin();
            for (int i = 0; i < K; i++)
                cout << *pos++ << " ";
            cout << endl;
        }
    }
}

int main()
{
    string data("5 2 1  3  6  7  8  2 9 1 3 11 13 15 16");
    
    cout << "data = " << data << endl;
    
    stringstream ss(data);
    findKMin(ss, 5, 4);
}

One simple approach is to track index of current min, while sliding window.
Say array is [5, 2, 1, 3, 6, 7, 8, 2] , n = 4, k = 5
loop i = 0; i < k;
So when i=0: you need to find min([5,2,1,3]) = 1 at j= 2

Now, you don't need to re-calculate min as long as i <=j < k
That is for i = 0..2, min = [1,1,1]
Now at i = 3: window is [3, 6, 7, 8] : min = 3 at j = 3
i = 4: [6,7,8,2]: min = 2 at j = 8

The worst case run time would be O(k*n) when the entire array X is sorted in increasing order. However, if we assume random uniform distribution it will be O(m*n) where m < k

Above algorithm can be modified a little to use a min-Heap of size k, where each node stores

key= value

and

data = arrayindex j

. So whenever i = j, you remove the root and min-Heapify (takes lg(k) )
In this case worst case would be O(lg(k) * n)

Use a binary search tree for storing the n elements. Basically the window size. Use a hash map with index in the original array as the key anf the address ot the poniter value in the BST as the value. For printing the k minimum elements just have to do in-order traversal of the tree. And as the qindow slides keep on deleting and adding the nodes to the BST.
The complexity for insertion in the BST is logn and deletion is also logn. For finding the element in the hashmap would take o(1). The creation of BST would take o(nlogn).

public void highestFeedPerSecond(int[] array,int k) throws InterruptedException {
		LinkedList<Integer> minimum=new LinkedList<Integer>();
		for(int i=0;i<array.length;i++) {
			int count=0;
			while(count < k) {
				minimum.add(array[i++]);
				count++;
			}
			System.out.println(""+getMinimum(minimum));
//			System.out.println(""+getMaximum(minimum));
			minimum.remove();
			k=1;
			i-=1;
		}
	}

	public int getMinimum(LinkedList<Integer> myMinQueue) {
		int minimum=Integer.MAX_VALUE;
		for(Integer myInteger:myMinQueue) {
			if(myInteger<minimum) {
				minimum=myInteger;
			}
		}
		return minimum;
	}

//o(n*k) solution

Build a max heap of size k which will hold the min k elements and the max of them at the root. When new integer comes compare it with root and if less than root, then delete root and insert the new element and heapify downwards. The complexity will be O(x(log k))

@nharryp that doesnt work what happens if the element that was left out of k in previous window of N is now a candidate for k elements in the current window. Your algorithm has no way to track this.
Maintaining heap of window size in an array and returning first k elements of the array is something that would work

@nharryp Your solution would be correct if it was not a sliding window, but just an increasing window.

public class ArrayInWindows {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {3,4,5,6,7,2,1,10,9,5};
int n=3, k=5;
System.out.println("Minimum elements of "+k+" windows - ");
int min = arr[0];
for(int i=1; i<(n+k-1); i++){
if(i >= arr.length) break;
if(arr[i] < min){
min = arr[i];
}
if(i>n-2) System.out.print(" "+min);
}
}
}

Please ignore the above code..

Below code is correct

/**
*
*/
package com.arrays;

/**
* @author adityagaitonde
*
*/
public class KMinimumElements {

private static void buildMaxHeap(int[] arr, int k) {
int heapSize = k;
for(int i= k/2; i>= 0; i--){
maxheapify(arr, i, heapSize);
}
}

private static int removeMax(int[] arr, int n, int heapSize) {
swap(arr, 0, n);
maxheapify(arr, 0, heapSize);
return heapSize;
}

private static void maxheapify(int[] arr, int index, int heapSize) {
int left = (index << 1) +1;
int right = left +1;

int largest = -1;
if(left < heapSize && arr[left] > arr[index]){
largest = left;
}else{
largest = index;
}
if(right < heapSize && arr[right] > arr[largest]){
largest = right;
}

if(largest != index){
swap(arr, largest, index);
maxheapify(arr, largest, heapSize);
}
}

private static void swap(int arr[], int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}

public static void main(String[] args) {
int arr[] = {3,4,5,6,7,2,1,10,0,5};
int n=6, k=3;
for(int i = 0; i < arr.length; i++){
if(i == (k-1)){
buildMaxHeap(arr, k);
}else if(i > k-1){
if(arr[i] < arr[0]){
removeMax(arr, i, k);
}
}
if(i>= n-1) printValues(arr,k);
}
}

private static void printValues(int[] arr, int k) {
System.out.println("----------------------------------------------------");
for(int i=0; i<k; i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}

Hi,
Could anyone please explain the question. I did not understand it.

We have a large array n a window which is a small array.
One edge of the window is at the beginning n now it slides
Right by one position.

This is what I could understand from the problem statement.
Anybody please explain me the question.

build a specialized queue with O(1) min operation, for each slide, just enque current element, and deque the oldest data item, apply min operation on this queue.