Yahoo Interview Question for Software Engineer / Developers


Team: Ad
Country: United States
Interview Type: In-Person




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

There is a better way in O(n) using a DP approach: Let's window size = w and array size = n, n>w.

Observe that the minimum at a position in current window is the minimum of what we would have seen so far and what we will see in future in the current window boundary. So, we can find min so far while traversing from left to right of the current window. But what about min in future? the trick is that we can traverse backwards to get the future min at a position. Also note that: windows separated by elements >=w will have no overlapping and so min so far should be reset at each block of w elements.

So, we will divide the array into [n/w] blocks. We'll keep calculate array's of min: min_so_far by traversing from start to end and min_in_future by traversing from end to start. Reset the min at the boundary of each block in the direction of traversal.

Example: [2,1,3,4,6,3,8,9,10,12,56] w=4
1. partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
min_so_far[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
min_in_future[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {min_in_future[i], min_so_far[i+w-1]}
sliding_min = 1, 1, 3, 3, 3, 3, 8, ....

public static int[] slidingWindowMin(final int[] in, final int w) {
    final int[] min_left = new int[in.length];
    final int[] min_right = new int[in.length];

    min_left[0] = in[0];
    min_right[in.length - 1] = in[in.length - 1];

    for (int i = 1; i < in.length; i++) {
        min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);

        final int j = in.length - i - 1;
        min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
    }

    final int[] sliding_min = new int[in.length - w + 1];
    for (int i = 0, j = 0; i + w <= in.length; i++) {
        sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
    }

    return sliding_min;
}

- zahidbuet106 June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

There is a better way in O(n) using a DP approach: Let's window size = w and array size = n, n>w.

Observe that the minimum at a position in current window is the minimum of what we would have seen so far and what we will see in future in the current window boundary. So, we can find min so far while traversing from left to right of the current window. But what about min in future? the trick is that we can traverse backwards to get the future min at a position. Also note that: windows separated by elements >=w will have no overlapping and so min so far should be reset at each block of w elements.

So, we will divide the array into [n/w] blocks. We'll keep calculate array's of min: min_so_far by traversing from start to end and min_in_future by traversing from end to start. Reset the min at the boundary of each block in the direction of traversal.

Example: [2,1,3,4,6,3,8,9,10,12,56] w=4
1. partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
min_so_far[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
min_in_future[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {min_in_future[i], min_so_far[i+w-1]}
sliding_min = 1, 1, 3, 3, 3, 3, 8, ....

public static int[] slidingWindowMin(final int[] in, final int w) {
    final int[] min_left = new int[in.length];
    final int[] min_right = new int[in.length];

    min_left[0] = in[0];
    min_right[in.length - 1] = in[in.length - 1];

    for (int i = 1; i < in.length; i++) {
        min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);

        final int j = in.length - i - 1;
        min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
    }

    final int[] sliding_min = new int[in.length - w + 1];
    for (int i = 0, j = 0; i + w <= in.length; i++) {
        sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
    }

    return sliding_min;
}

- zahidbuet106 May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome solution.

- dhs.du.08 June 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void main(String args[]) {
		int[] arr = {10,2,5,40,15,3,2};
		int index = 0;
		TreeSet<Integer> ts = new TreeSet<Integer>();
		for(int i=0; i<arr.length; i++)
		{	
			ts.add(arr[i]);
			if(ts.size()>=4)
			{
				System.out.println(ts.first());
				ts.remove(arr[index++]);
			}
			
		}
	}

- sp!de? July 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

C++ Solution by using a double-ended queue.It supports insertion/deletion from the front and back.

void SlidingWindowMin ( int Arr[], int Num, int WinSize, int SlideMin[]) {
  deque<int> Q;
  
  //Maintain the min element in the window in the front of the queue.
  
  for (int idx = 0; idx < WinSize; idx++) {
    while ( !Q.empty() && 
			Arr[idx] <= Arr[Q.back()] )
      Q.pop_back();
	  
    Q.push_back(idx);
  }
  
  for (int idx = WinSize; idx < Num; idx++) {
    SlideMin[idx-WinSize] = Arr[Q.front()];
  
	while (!Q.empty() && Arr[idx] <= Arr[Q.back()])
      Q.pop_back();
	
	while (!Q.empty() && Q.front() <= idx-WinSize)
      Q.pop_front();
    
	Q.push_back(idx);
  }
  
  SlideMin[Num-WinSize] = Arr[Q.front()];
}

Complexity:
Each element is Inserted and deleted at most once = 2n = O(n)

- R@M3$H.N March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ DownVoter, care to explain ?
Let me know if anything wrong in solution...

- R@M3$H.N March 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

There is a better way in O(n) using a DP approach: Let's window size = w and array size = n, n>w.

Observe that the minimum at a position in current window is the minimum of what we would have seen so far and what we will see in future in the current window boundary. So, we can find min so far while traversing from left to right of the current window. But what about min in future? the trick is that we can traverse backwards to get the future min at a position. Also note that: windows separated by elements >=w will have no overlapping and so min so far should be reset at each block of w elements.

So, we will divide the array into [n/w] blocks. We'll keep calculate array's of min: min_so_far by traversing from start to end and min_in_future by traversing from end to start. Reset the min at the boundary of each block in the direction of traversal.

Example: [2,1,3,4,6,3,8,9,10,12,56] w=4
1. partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
min_so_far[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
min_in_future[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {min_in_future[i], min_so_far[i+w-1]}
sliding_min = 1, 1, 3, 3, 3, 3, 8, ....

public static int[] slidingWindowMin(final int[] in, final int w) {
    final int[] min_left = new int[in.length];
    final int[] min_right = new int[in.length];

    min_left[0] = in[0];
    min_right[in.length - 1] = in[in.length - 1];

    for (int i = 1; i < in.length; i++) {
        min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);

        final int j = in.length - i - 1;
        min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
    }

    final int[] sliding_min = new int[in.length - w + 1];
    for (int i = 0, j = 0; i + w <= in.length; i++) {
        sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
    }

    return sliding_min;
}

- zahidbuet106 May 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

First of all, I think Ramesh N's solution with a deque might be right, at least if I understood it correctly (haven't tested it).

Anyway, my approach would be slightly different. Here are the general steps in my solution which I'll explain later:

1. Implement a MinStack class which is a stack that also keeps track of the minimum element with O(1) worst-case complexity. It supports the regular stack operations with O(1) worst-case complexity and a getMin() operation which returns the minimum of all the elements in the stack in O(1) worst-case as well.
2. Implement a MinQueue class which is a queue and similarly to the MinStack keeps track of the minimum element in the queue. Unlike the MinStack class, in MinQueue the worst-case complexity for the remove() operation might be O(n).
3. Use MinQueue to determine the minimum element for every k-element window in the input array. The complexity analysis will show that even though MinQueue's remove() operation's worst-case complexity is O(n), the overall run-time complexity for determining the minimum values for all the windows is still linear in the worst-case.

Implementation:
1. The MinStack class. Our goal is to implement a stack that supports all operation with O(1) worst-case complexity including the getMin() operation. We'll implement this by using two stacks: the first (stack) will store all the present elements in the stack and the second (called minStack) will be used to maintain the minimum element at each point. When we push an element to the stack, we'll push him to the first stack and if the element is lesser/equal than the element at the top of the minStack we'll push him to minStack as well. When we pop an element from the stack, we pop the element at the top of the stack and if the element we just popped is equal to the element at the top of the minStack then we'll pop an element from minStack as well. The getMin() operation will be implemented simply by returning (not popping) the element at the top of the minStack stack.

Code:

public class MinStack <T extends Comparable<T>> {
	
	private final Stack<T> stack;
	private final Stack<T> minStack;
	
	public MinStack(){
		stack = new Stack<T>();
		minStack = new Stack<T>();
	}
	
	public void push(T e){
		if (e==null){
			throw new NullPointerException("element cannot be null");
		}
		
		stack.push(e);
		if ((minStack.isEmpty()) || (minStack.peek().compareTo(e)>=0)){
			minStack.push(e);
		}
	}
	
	public T pop(){
		if (stack.isEmpty()){
			throw new NoSuchElementException("Stack is empty");
		}
		
		T e = stack.pop();
		if (minStack.peek().compareTo(e)==0){minStack.pop();}
		
		return e;
	}
	
	public T peek(){
		if (stack.isEmpty()){
			throw new NoSuchElementException("Stack is empty");
		}
		
		return stack.peek();
	}
	
	public boolean isEmpty(){return stack.isEmpty();}
	
	public T getMin(){
		if (minStack.isEmpty()){
			throw new NoSuchElementException("Stack is empty");
		}
		
		return minStack.peek();
	}
}

2. The MinQueue class. We'll implement the MinQueue class using two MinStack classes. The idea is similar to that of implementing a Queue using a Stack - you use two stacks: one (called pushStack) for adding elements to the queue and the other (called popStack) for removing elements from it. To add an element, simply push it into the pushStack stack. To remove an element, we first check whether the popStack is empty. If it is then we pop all the elements from pushStack and push them (in the order they were popped) to the popStack and then we pop one element from it. If popStack isn't empty then we just pop one element from it. Notice that the worst-case run-time complexity of the remove() operation is O(n) but we'll later see that it doesn't make the overall asymptotic complexity of our algorithm worse. The getMin() operation will be implemented simply by choosing the minimum of the minimum elements in pushStack and popStack.

Code:

public class MinQueue <T extends Comparable<T>> {
	
	private final MinStack<T> pushStack;
	private final MinStack<T> popStack;
	
	public MinQueue(){
		pushStack = new MinStack<T>();
		popStack = new MinStack<T>();
	}
	
	public void add(T e){
		if (e==null){
			throw new NullPointerException("e is null");
		}
		pushStack.push(e);
	}
	
	private void popFromStack(){
		while (!pushStack.isEmpty()){
			popStack.push(pushStack.pop());
		}
	}
	
	private T peekRemove(boolean remove){
		if ((pushStack.isEmpty()) && (popStack.isEmpty())){
			throw new NoSuchElementException("Queue is empty");
		}
		if (popStack.isEmpty()){this.popFromStack();}
		
		return (remove) ? popStack.pop() : popStack.peek();
	}
	
	public T remove(){
		return peekRemove(true);
	}
	
	public T peek(){
		return peekRemove(false);
	}
	
	public T getMin(){
		if ((pushStack.isEmpty()) && (popStack.isEmpty())){
			throw new NoSuchElementException("Queue is empty");
		}
		
		if (popStack.isEmpty()){return pushStack.getMin();}
		else if (pushStack.isEmpty()){return popStack.getMin();}
		
		return ((pushStack.getMin().compareTo(popStack.getMin()))<0) ? pushStack.getMin() : popStack.getMin();
	}
}

3. The main algorithm implementation is pretty straight forward using MinQueue. We add the first k (k=windowsSize) elements in the array to the MinQueue. We use getMin() to get the minimum element in the MinQueue. Then in each iteration step we move the window to the right by removing one element from the queue and add the next element in the array. For every new window we use getMin() to retrieve the minimum element.

Code:

public static <T extends Comparable<T>> void getMinArray(T[] input, T[] output, int k){
		if ((input==null) || (output==null)){
			throw new NullPointerException("Input arrays are null");
		}
		if ((k<1) || (k>input.length)){
			throw new IllegalArgumentException("k is illegal");
		}
		
		MinQueue<T> queue = new MinQueue<T>();
		for (int i=0,j=0;(i<=input.length) && (j<output.length);i++){
			if (i>=k) {
				output[j++] = queue.getMin();
				queue.remove();
			}
			if (i<input.length){queue.add(input[i]);}
		}
	}

Complexity Analysis: It would seem that because MinQueue's remove() operation's worst-case run-time complexity is O(n) that the overall algorithm complexity should be O(n^2) but in fact, the overall complexity is linear - O(n) in the worst-case as well.
To see this, let us count the total number of push() and pop() operations performed by the MinQueue throughout the entire run-time of our algorithm:

1. We push k elements to the first stack (adding the first k elements to the queue).
2. We want to remove an element from the queue. Elements are removed from the second Stack (popStack) which is currently empty after step 1 (but not necessarily after step 3) so we pop all the elements from the first stack (pushStack) and push them to the popStack - another 2k pushes and pops.
3. Now the popStack includes k elements which means that the next k elements removal would be require just a single pop() operation (for every remove() call). Every time we move the sliding window to the right we pop one element and push the new element in the window to the pushStack. This means that we'll need to move our sliding window k elements to the right before we popped all the elements from the popStack - total number of 2k pushes and pops.
4. We repeat steps 2-3 until the sliding window reaches the end of the original array.

How many times are steps 2-3 executed (each 2-3 steps execution requires 4k push and pop operations - 2k to push all the elements from pushStack to popStack when popStack becomes empty and another 2k to push and pop operations for moving the window k elements to the right)? At the end of steps 2-3 the sliding window moved k elements to the right so the number of times 2-3 are executed is equal to the number of times the sliding window can move k elements to the right. That number is (n-k)/k. It's n-k because of step 1 where we insert the first k elements without popping any element from the popStack. Thus, the total number of push and pop operations performed on the stacks is:
k + 4k*(n-k)/k = 4n - 3k.

Because MinStack::push() and MinStack::pop() are all O(1) worst-case operations and there are 4n-3k such operation then the overall worst-case run-time complexity is O(n) as desired (getMin() operations are O(1) as well).

Space complexity is obviously O(n) worst-case.

- IvgenyNovo March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I would make the queue a circularFifoQueue in order to reduce some of the ugliness in the "main algorithm". It would look something like this:

for (int i =0; i < input.length; i++) {
	minCircularQueue.add(input[i]);
	slidingWindowMinimums[i] = minCircularQueue.get();
}

- mayonesa April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

have you tried it with

[1, 3, 2, 4, 4]

?
If I understand the code correctly, it will produce:

[1, 4]

instead of

[1, 2]

- mayonesa.cosmica April 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Can we use a min heap of size 4 and every time an element goes out of the window, well remove the element form the heap. So at each step, we can print the element at the root of the min heap. I guess this should work.

- Anonymous March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this will work it will be nlog(m)

n = size of integer array
m = size of window

Looks like guys above have a O(n) approach though..

- byteattack June 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity O(nlog(w))

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class MinSlidingWindow {
	
	public List<Integer> minSlidingWindows(int windowSize, int[] numbers){
		ArrayList<Integer> minList = new ArrayList<Integer>();
		PriorityQueue<Integer> kNumbers = new PriorityQueue<Integer>(windowSize);
		for(int i = 0; i < numbers.length; i++){
			if(kNumbers.size() < windowSize){
				kNumbers.add(numbers[i]);
			} else {
				minList.add(kNumbers.peek());
				kNumbers.remove(numbers[i-windowSize]);
				kNumbers.add(numbers[i]);
			}
		}
		minList.add(kNumbers.peek());
		return minList;
	}
	
	public static void main(String[] args) {
		int[] numbers = {1,1,3,1,6,3,8,9,10,12,1};
		MinSlidingWindow msw = new MinSlidingWindow();
		System.out.println(msw.minSlidingWindows(4, numbers));
	}
}

There can be O(n) solution using Deque, but when we have to deal with data streaming(billions of number), where input will be just a number to add, using the above method, we can get the new min as per the window size.
In that case we need to make object of PriorityQueue to the class object, and instead of minList, just we need new min to be return

- Abhishek Kothari June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]) {
		int[] arr = {10,2,5,40,15,3,2};
		int index = 0;
		TreeSet<Integer> ts = new TreeSet<Integer>();
		for(int i=0; i<arr.length; i++)
		{	
			ts.add(arr[i]);
			if(ts.size()>=4)
			{
				System.out.println(ts.first());
				ts.remove(arr[index++]);
			}
			
		}
	}

- sp!de? July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done using a double ended queue. T = O(n), S = O(k)

#include <iostream>
#include <deque>
using namespace std;

void maxSubarraySlidingWindow(int* arr, int n, int k) {
	// Create a deque to simulate a sliding window
	deque<int> dq(k);

	// Fill out the initial window
	for (int i = 0; i < k; i++) {
		// Removing all the elements that are greater than current element
		while (!dq.empty() && arr[dq.back()] >= arr[i]) {
			dq.pop_back();
		}

		// Pushing the index of the current element
		dq.push_back(i);
	}

	// Sliding the window for all the remaining array elements
	for (int i = k + 1; i < n; i++) {
		// Printing the smallest element (element at the front)
		cout << arr[dq.front()] << " ";

		// Removing elements that are out of the window
		while (!dq.empty() && dq.front() <= i - k) {
			dq.pop_front();
		}

		// Removing all the elements that are greater than current element
		while (!dq.empty() && arr[dq.back()] >= arr[i]) {
			dq.pop_back();
		}

		// Pushing the index of the current element
		dq.push_back(i);
	}

	// Printing for the final window element
	cout << arr[dq.front()] << " ";
	cout << endl;
}

int main() {
	int arr[] = { 2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 4;
	maxSubarraySlidingWindow(arr, n, k);
}

- akshaycj47 November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How is that you guys are so intelligent? I can't even think of so many approaches. I was given this problem in eBay interview and I was dumbstruck. Did you guys practice a lot? Pls help.

- ap June 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Arrays;

public class SlidingWindowMin {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		/*
		 * Given an array of integer, find the minimum in the sliding window of size 4, in most optimal way. 
		 * ex [2,1,3,4,6,3,8,9,10,12,56] 
		 * Output : [1,1,3,3,3,3,8.....]
		 */

		int[] a = {2,1,3,4,6,3,8,9,10,12,56};
		int window = 4;
		int min = Integer.MAX_VALUE;
		int[] ret = new int[a.length - window + 1];
		if (window > a.length) System.exit(-1);
		for (int i = window - 1; i < a.length; i++) {
			min = Integer.MAX_VALUE;
			for (int j = i - window + 1; j <= i; j++) {
				if (a[j] < min) min = a[j];
			}
			ret[i - window + 1] = min;
		}
		System.out.println("In: " + Arrays.toString(a) + ", out: " + Arrays.toString(ret));
	}
}

- FredCycle March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about using a balanced BST, like this:

void getMinInWindow(vector<int>& res, const vector<int>& src, int windowSize)
{
    res.clear();

    set<int> windowSet;
    int i, j, n = src.size();
    for(i = 0; i + windowSize <= n; ++i){
        for(j = 0; j < windowSize; ++j) windowSet.insert(src[i+j]);
        res.push_back(*windowSet.rbegin());
        windowSet.erase(src[i]);
    }
}

- uuuouou March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

for(i=0;i<length-3;i++)
cout<<max(max(a[i],a[i+1]),max(a[i+2],a[i+3]));

- Anonymous March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class MinWindow{
	public static void main(String a[]) {
		int[] arr = {3,6,1,2,4,10,9,7,6,5,8,3};
		printWindow(arr);
	}
	
	static void printWindow(int[] arr) {
		int pos = -1;
		for(int i=0;i<arr.length -3;i++) {
			if (pos==i-1) {//Min Val out of window
				pos = getMinPos(i,arr);
			} else if (arr[pos] > arr[i+3]) {//New val in window less than current MIN
				pos = i+3;
			}
			System.out.print(arr[pos] + "\t");
		}
		System.out.println();
	}
	
	static int getMinPos(int i,int[] arr) {
		int pos1,pos2;
		if (arr[i]<arr[i+1]) pos1 = i; else pos1 = i+1;
		if (arr[i+2]<arr[i+3]) pos2 = i+2; else pos2 = i+3;
		if (arr[pos1]<arr[pos2]) return pos1; else return pos2;
	}
}

- Anonymous March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

your solution is not extendable to arbitrary window size, w.

- zahidbuet106 May 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

void find(int a[],int n)
	{
		int t=a[0],j=0,k=0;
		for(int i=k;k<=n-4;i++)
		{
			if(j==4)		// if reached end of kth window
			{

				System.out.print(t+" ");
				k++;						// move to next window
				i=k;
				t=a[i];
				j=0;
			}
			if(t>a[i])
				t=a[i];
			j++;

		}
		

	}

- Aman Raj March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can be done using dynamic programming.
The recurrence relation is - opt(i,i+3)=min{ opt(i,i+2), arr[i+3] }

we have to calculate - opt(1,4) , opt(2,5), ..., opt(n-3,n).

- khunima March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would we calculate opt(0,3)?

- vinay March 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int min = array[0];
		int N = array.length;
		int j=0;
		System.out.println("min "+min);
		for(int i=0;i<N;i++,j++){
 			if(j==slide){
				System.out.println(min);
				j=0;
				min = Integer.MAX_VALUE;
				i-=slide-1;
 			}
 			if(min>array[i]){
 				min= array[i];
			}
		}

- sree March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

See below code. Tested that it works. The worst case complexity is O(n).

Basically, initialize your min value and its position. For every new item which comes into the
windows compare it with the min and update if necessary. If the min value is out of the window, recalculate the minimum else just continue moving the window.

private static class MinObject {
        int value = Integer.MAX_VALUE;
        int position;
    }

    /**
     * Given an array of integer, find the minimum in the sliding window of size 4, in most optimal way.
     * ex [2,1,3,4,6,3,8,9,10,12,56]
     * Output : [1,1,3,3,3,3,8.....]
     */
    private static void arrayMinProblem() {
        src_array = new ArrayList<Integer>(Arrays.asList(2,1,3,4,6,3,8,9,10,12,56));
        
        // Initialize the minimum value and position
        int windowSize = 3;
        MinObject minimum = findMin(0, windowSize, src_array);
        System.out.print(minimum.value +", ");

        for(int i=1; i< src_array.size()-3;i++){
            if(i > minimum.position) {
                minimum = findMin(i, i+windowSize, src_array);
                System.out.print(minimum.value +", ");
                continue;
            }
            int newItem = src_array.get(i+windowSize);
            if(newItem > minimum.value && i <=minimum.position) {
                System.out.print(minimum.value +", ");
                continue;
            }
            if(newItem < minimum.value) {
                minimum.value = newItem;
                minimum.position = i+windowSize;
                System.out.print(minimum.value +", ");
            }
        }
    }
    
    // inclusive of both start and end indexes
    private static MinObject findMin(int startIndex, int endIndex, List<Integer> array) {
        int i = startIndex;
        MinObject returnValue = new MinObject();
        for(; i<= endIndex; i++) {
            if(returnValue.value > array.get(i)) {
                returnValue.value = array.get(i);
                returnValue.position = i;
            }
        }
        return returnValue;
    }

- Anonymous March 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not O(n)...actually O(nw) and performance will be getting slower with increasing window size.

- zahidbuet106 June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can someone please explain how can this problem be solved using a min-heap.
I am stuck at the point when a new element comes in for the next window, how will i delete the previous/last element from the heap to maintain the window size in heap ?

- duskan April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Most optimal way? WTF does that even mean?

- La expletife March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem can be solved by below methods along with their run-times mentioned.
Brute-Force Method --- O (nw)
Using a Heap --- O(n log w)
Using a Deque --- O(n)
The interviewer expected an Optimal Solution in terms of Run-time.

- R@M3$H.N March 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For w=4, all are O(n).

Talking about most optimal run-time is nonsensical, without talking about the model, in which case it becomes theoretical, and a stupid interview question.

- L A S O U N D W A V E March 21, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More