Amazon Interview Question
Country: India
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))
Yup. I also thought about the same solution. Use max heap that will hold min k elements. The size of the heap would remain n. Also deletion and insertion in heap on average case is O(1). So it would be very efficient.
@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
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.
- Westlake March 16, 2014