## Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

WRONG!
at so many levels.

Comment hidden because of low score. Click to expand.
0

n cannot be less then k. you are trying to find 5 minimum out of 4.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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).

Comment hidden because of low score. Click to expand.
0

Insertion & deletion in BST may not be log(n) untill the BST is balanced!! if the tree is skewed, insertion may take as high as O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void highestFeedPerSecond(int[] array,int k) throws InterruptedException {
for(int i=0;i<array.length;i++) {
int count=0;
while(count < k) {
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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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))

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

If you are losing a number when you slide the window, delete it from the heap also and maintain the heap to be of k size also when you slide. I think it would work

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Please ignore the above code..

Below code is correct

/**
*
*/
package com.arrays;

/**
*
*/
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();
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

How do you keep track of the minimum k elements?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.