Interview Question


Country: United States




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

O(n) solution with extra memory for array of size k exists. ( i am assuming we have to do it inplace without using memory for array B )

- Cerberuz September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please explain....................

- Biswajit Sinha September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please explain how O(n) solution does exist with extra memory of size k........as per my thought in any case you need the complexity of ((n-k)+1)*k

- Biswajit Sinha September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We need a deque with following O(1) operations :
push_front(), pop_front(), pop_back()

1) The last element of deque will always hold the minimum element in each step( each step will give minimum for ith subarray ).
2) Element will be inserted in front only.

Suppose you have some elements in deque such that last element is minimum for subarray a[i-k] to a[i-1]. You need to find the minimum for subarray a[i-k+1] to a[i]

a) Pop all elements from front which are greater than a[i]
b) Pop all elements from back which have index less than equals to i-k
c) Push a[i] to front
d) Store last element as minimum of subarray a[i-k+1] to a[i]
Repeat a,b,c,d for all i

As all elements are inserted and deleted once only => O(n)

- Cerberuz September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution

- Biswajit Sinha September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Cerberuz: How will you do b) above efficiently? You might be inserting and deleting each element only once, but doesn't b) involve a linear search (O(k) every time you do this, which will give you O(nk) overall for this algo)?

- eugene.yarovoi September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution is indeed O(n).
All the elements which have index less than equals to i-k will be consecutive in the end of the deque.
*Any element with index < i will always be inserted before any other element which have index >= i.

- Cerberuz September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I see what you're doing. I didn't think you were enforcing order by index in the deque, but your last comment clarified it for me.

+1 from me.

- eugene.yarovoi September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cerberuz, could you clarify how this accomplishes the look-ahead aspect of the problem? Your solution seems to solve for min(A[i-k+1], A[i-k+2],...,A[i]), but not for min(A[i], A[i+1],...,A[i+k]).

Am I misunderstanding some aspect of your solution?

- Patrick September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess a reverse traversal with the last k-1 elements preloaded into the array would be the algorithm you describe, and begin with A[A.Count() - k]. Still, confused me for a minute there.

- Patrick September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For min( A[i], A[i+1], ..., A[i+k] ) : i+k can be greater than size of array.

- Cerberuz September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, in the problem those without k comparisons to make are dropped (so B.Length = A.Length - k + 1). I don't see how this can be a lookahead algorithm without a backwards traversal, since you're relying on the history of the search.

- Patrick September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Patrick, I am not able to get you, do you have a test case where the algorithm fails or you want to say that its not O(n) ?

- Cerberuz September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algorithm seems (again, I might be misunderstanding) to use a lookback, and since you didn't mention starting params I assume you'd go with the beginning, and assign B[i] to the value found for A[i]. I was just confused because you didn't describe the initialization or mapping between B and A. For example, with the array:
{5,1,3,4,2,7} with k=3, the output I understand from your algo would be {5, 1, 1, 1,2,2}, where the intended output is {1,1,2,2}. It's a small bug, in that you add on k-1 elements to the beginning. If I missed some part where you pre-process k-1 elements then begin to copy to B (or another way of handling this) then I take it all back. :)

Does that make sense?

- Patrick September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Firstly, i am not using array B for storing result ( result is stored inplace in the given array ).
e.g 5,1,3,4,2,7
Initialization : a[0] = minimum of ( a[0] to a[k-1] ) = 1
deque = 3->1 ( insert elements from min element till a[k-1] )

Now proceed from a[3] and fill values from a[1]
deque = 4->3->1 : a[1] = 1
deque = 2 : a[2] = 2
deque = 7->2 : a[3] = 2

- Cerberuz September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, gotcha, very nice. The initialization and the placing minimum calculated at a[i+k-1] into a[i] wasn't clear to me. Thanks!

- Patrick September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

// Worst Case O(nk) if array are already sorted.

void findMin(int *arr,  int k , int len)
{
	int i,j,min=INT_MAX, index =0,l=0;
	for(i=0; i<=len-k; i++)
	{
		if(index > i && index < i+k)
		{
			if(arr[i+k-1] < min)
			{
				min = arr[i+k-1];
				index = i+k-1;
			}
		}
		else
		{
			min = INT_MAX;
			for(j=i; j<i+k ;j++)
				if(arr[j] <= min)
				{	
					min = arr[j];
					index = j;
				}
		}
		printf("%d ",min);
	}
}

- Aalok September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why -ve Vote...

- Aalok September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem statement said you must do it in less than O(nk), but by your own acknowledgment, it's O(nk).

- eugene.yarovoi September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have given you +1 despite the fact that you are supposed to return the output vector, and that too without extra space..

- Prashant R Kumar September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have given you +1 despite the fact that you are supposed to return the output vector, and that too without extra space..

- Prashant R Kumar September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nk) is not a problem...Problem is making it inplace..Which looks impossible..

- Prashant R Kumar September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Cerberuz: i didnt understand exactly what is happening in here in the deque. plz can u elaborate.

- kiranbsravi September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For each subarray of type a[i-k+1] to a[i] you have to maintain deque such that it contains elements less than equals to a[i] in non increasing order from front.
So in each step you throw out all elements from front which are greater than a[i] and elements from back which are not in current window.
As deque is sorted in non increasing order, minimum element of sub array will always be at its end.

- Cerberuz September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks ..

- kiranbsravi September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@cerberuz I think the below mentioned code will explain properly what cerberuz proposed......what do you say cerberuz?

package programs;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;


public class program1 {
    public static void BuildArray(ArrayList<Integer> A,int k)
    {
        ArrayDeque<Integer>D = new ArrayDeque<Integer>();
        ArrayList<Integer> L = new ArrayList<Integer>();
        int q = k;
        for(int i=0;i<A.size();i++)
        {
            if(D.isEmpty())
            {
                D.addFirst(i);                
                if(i==(q-1))
                {
                    q++;
                    L.add(A.get(D.getLast()));
                }
                else
                    continue;
            }                
            else 
            {
                for(Iterator itr = D.iterator();itr.hasNext();)
                {
                    int num = ((Integer)itr.next()).intValue();
                    if(A.get(num)>A.get(i))
                    {
                        D.removeFirst();
                    }
                    else
                        break;
                    
                }
                for(Iterator itr = D.descendingIterator();itr.hasNext();)                
                {
                    
                    int w = q-k-1;
                    int num = ((Integer)itr.next()).intValue();
                    if(num<=w)
                    {
                        D.removeLast();
                    }
                    else
                        break;                    
                }
                D.addFirst(i);                
                if(i==(q-1))
                {
                    q++;
                    L.add(A.get(D.getLast()));
                }
                else
                    continue;
            }
        }
        System.out.print("Now the array is: ");
        for(int i=0;i<L.size();i++)
        {
            System.out.print(L.get(i)+" ");
        }
    }
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        ArrayList<Integer> D = new ArrayList<Integer>();
        System.out.println("Please enter the no. of array elements: ");
        int l = in.nextInt();
        for(int i=0;i<l;i++)
        {
            D.add(in.nextInt());
        }
        System.out.println("Please enter window length: ");
        //int k = in.nextInt();
        BuildArray(D,in.nextInt());
    }
    
    
}

- Biswajit Sinha September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cerberuz i need comment of you on this code

- Biswajit Sinha September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks fine, i haven't checked for all corner cases.

- Cerberuz September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use counting sort ,then just take out 1st element at each pass....

- Anonymous September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Range of elements in array can be very large. Counting sort cant be used in that case.

- Cerberuz September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

People on this site sure like to throw around terms without actually understanding what they mean.

- Anonymous September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use counting sort,then just take out 1st element at each pass...

- abhishek September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Won't work for "3, 1, 9, 0, 2"

- Cerberuz September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

worst idea..........take ur time buddy..........it's not that much easy

- Biswajit Sinha September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think u should use counting sort rather than comparison sort,then just take 1 element at each step out

- abhishek September 11, 2012 | 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