Google Interview Question for Software Engineer / Developers






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

You can solve it using a dequeue in O(n)

- madhav February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could u give a pseudo code?

- Anonymous February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could u give a pseudo code?

- Anonymous February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This guy is right. I gave it a chance and thought a while about it.
Solution is based on this trick:

- maintain a deque of pair<int, int>'s where value is current element's index within the sliding window of length "k"
- crucial part is "to remove" each smaller pairs from the deque as inserting new elements (remove older pairs having smaller values than the new one).
- remove pairs whose time is over (value == k), next pair within the deque (end of the deque) is going to be the new max.

it is O(n) as each item visits the deque only twice.

Please just don't down/up-vote anything that you cannot seem to wrap your heads around.

- yemre_ankara December 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it can be solved in O(n).
you just need to think loud for it.

- pankaj December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, we can solve it using a dequeue in O(n).
The following is the Java implementation together with a simple test.

import java.util.*;

class MaximumSubarray 
{
	public static int[] maximumSubarray(int[] array, int K)
	{
		if (null == array) {return null;}
		if (array.length < K) {return null;}
		int[] output = new int[array.length - K + 1];
		LinkedList<Integer> list = new LinkedList<Integer>();
		for (int end = 0; end < array.length; end++)
		{
			while (list.size() > 0)
			{
				if (array[end] >= array[list.getLast()]) {list.removeLast();}
				else {break;}
			}
			list.addLast(end);
			int begin = end - K + 1;
			StringBuffer sb = new StringBuffer("begin = " + begin + "; end = " + end + "; list = " + list);
			if (begin >= 0)
			{
				output[begin] = array[list.getFirst()];
				sb.append("; output[" + begin + "] = array[" + list.getFirst() + "] = " + output[begin]);
				if (begin == list.getFirst()) {list.removeFirst();}
			}
			System.out.println(sb.toString());
		}
		return output;
	}

	public static void main(String[] args)
	{
		int[] array1 = {1, 2, 3, 1, 4, 5, 2, 3, 6};
		debug(maximumSubarray(array1, 3));
	}

	public static void debug(int[] array) {debug(array, " ");}
	public static void debug(int[] array, String separator)
	{
		StringBuffer buffer = new StringBuffer();
		for (int i = 0; i < array.length - 1; i++) {buffer.append(array[i] + separator);}
		if (array.length > 0) {buffer.append(array[array.length - 1]);}
		System.out.println(buffer.toString());
	}
}

The states will be like this (begin and end means the begin and end of sliding window):

begin = -2; end = 0; list = [0]
begin = -1; end = 1; list = [1]
begin =  0; end = 2; list = [2];    output[0] = array[2] = 3
begin =  1; end = 3; list = [2, 3]; output[1] = array[2] = 3
begin =  2; end = 4; list = [4];    output[2] = array[4] = 4
begin =  3; end = 5; list = [5];    output[3] = array[5] = 5
begin =  4; end = 6; list = [5, 6]; output[4] = array[5] = 5
begin =  5; end = 7; list = [5, 7]; output[5] = array[5] = 5
begin =  6; end = 8; list = [8];    output[6] = array[8] = 6

The dequeue (LinkedList in Java) is used to maintain
(1) the index of the largest element in the sliding window of width K
(2) the index of the largest element in the sliding window of width K, after (1) is removed from the sliding window
(3) the index of the largest element in the sliding window of width K, after (1)~(2) is removed from the sliding window
(4) the index of the largest element in the sliding window of width K, after (1)~(3) is removed from the sliding window
...

Obvious list.removeLast() and list.removeFirst() will not executed more than array.length times,
since list.addLast() will only be executed array.length times.

- Alva0930 February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Java Implementation....

public static void findMaxNumberInSlidingWindow(int[] numbers, int k) {
		Queue<Integer> numberQueue = new LinkedList<Integer>();
		
		for (int i = 0; i < numbers.length; i++) {
			Queue<Integer> tmpQueue = new LinkedList<Integer>();
			
			while (!numberQueue.isEmpty()) {
				int index = numberQueue.remove();
				if(index > i - k && numbers[index] > numbers[i]){
					tmpQueue.add(index);	
				}
			}

			tmpQueue.add(i);
			numberQueue = tmpQueue;
			if (i >= k-1){
				System.out.println(numbers[numberQueue.peek()]);
			}
		}
	}

- Adnan Ahmad September 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"
#include <iostream>
using namespace std;
#define MAX(a,b,c) (a)>(b)&&(a)>(c) ? a : (b)>(c)?(b):(c)
int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {2,4,3,5,4,12,10,9,7,1,4,11};
	int n = sizeof(a) / sizeof(int);
	int k = 3;
	for(int i=0; i<n-k+1; i++)
		cout << (MAX(a[i], a[i+1], a[i+2])) << " ";
	cout << endl;
	return 0;
}
this is so simple, anything else they are expecting?

- Anonymous February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution would give O(nk). You need to get a O(n) solution.

- vinod. February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think it is O(n*k)... it is O(n-k+1) ~= (n)

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry mate, but it is O(nk). You are using a k-iteration loop inside the n-iteration loop.

- vinod. February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually it's O(n). k is a constant from user or given. If anything the worst case is when k = 1 which results in O(n-k+1) -> O(n). Neat solution.

- Mat February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not just use a max heap for k elements & you can get O(n*logk)
with O(k) space complexity

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution is good for k = 3 but it will not work for an arbitrary k input.

- Mat February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are repeating patterns for which max only needs to be calculated once. For sample i/p repeating patterns are 23,31,14,45,52,23. As k differs these patterns change accordingly.

- Kalyan February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

ch.v.suresh:

step 1: Find out max element between a[0] to a[k-1].
printf max element

Step 2: Compare next element in array with max element.
if(a[k] > max element)
max element = a[k]

printf - max element.

step3: increment k = k + 1;
Repeat step 3 till 'k' reaches end of array.

ex: 1 2 3 1 4 5 2 3 6
k = 3

step 1 : Max element in {1,2,3} is '3'
step 2: for '2' 1<3 3 k
for '3 4>3 4 k+1
for '1' 5>4 5 k+2
for '4' 5>2 5 k+3
for '5' 5>3 5 k+4
for '2' 6>5 6 k+5

- Anonymous February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does this work for
90 40 3 5 6 7 8

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi.
You need to maintain the following things in an array.
Let i,i+1,....i+k-1 be a window.(say 1)
The next window is i+1,i+2,...i+k. (say 2)The numbers from i+1,i+2,...i+k-1 are common to these 2 windows.
Assume you have the max in the window 1, denoted by max.
Now, the element A[i] is going out of window 2 and A[i+k] is coming into window 2.
So, possible cases are :-
1. max < A[i+k] =>max for window 2 = A[i+k].
2. max > A[i+k] and A[i] not = max. So the max for window 2 is same as window 1. But this max could change in the next window(s). So, we maintain the 2nd max(to the right of the current max),3rd max(to the right of 2nd max) etc.
Why right of the previous max? Because these are the elements that could potentially become max for next window(s).
Now, what do we do about A[i+k]?
Lets say, we have the following info in an array for window 1.
max, 2nd max(to the right of max), 3rd max(to the right of 2nd max), etc..
Now, if A[i+k] > 3rd max, for the next window (window 3), do we need to 3rd max of window 1?
No, since A[i+k] is already greater than 3rd max and occurs to the right of 3rd max.
So, formally, if we have the following info for current window
1st max,2nd max(to the right of 1st max), 3rd max(to the right of 2nd max)...jth max(to the right of j-1th max)
A[i+k] will displace all max elements that are less than it.

- Sriram S February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do we maintain the max array (1st max,2nd max.....) and update it efficiently??

- XYZ February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The max elements can be stored as a queue. In the worst case, we need to maintain k elements in the array, but in the average case, this number tends to be much lesser.

- Sriram S February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sriram
Can you please give a code or pseudo code

- fftish February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is the best i can come up with.

go(){
  int start=0,end=k-1,k;//k is de input
  while(end<a.length){
    if(end-start==k-1){
      start=findMax(start,end);
      System.out.println(a[start]+" ");
      end++;
    }
    else if(end-start==k)
      start++;
    else if(a[start]>a[end]){
      System.out.println(a[start]+" ");	
      end++;
    }
    else{
      System.out.println(a[end]+" ");
      start=end;
      end++;
    }
  }
}
int findMax(int start,int end){
  int max=start++;
  for(;start<=end;start++)
    if(a[start]>a[max])
      max=start;
  return max;
}

- Sathya February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if ur more concerned abt no: ifs in while loop use below

void go(){
  int start=0,end=k-1,k;//k is input
  start=findMax(start,end);
  System.out.println(a[start]+" ");
  end++;
  while(end<a.length){
    if(end-start==k){
      start=findMax(start+1,end);
      System.out.println(a[start]+" ");
      end++;
    }
    else if(a[start]>a[end]){
      System.out.println(a[start]+" ");	
      end++;
    }
    else{
      System.out.println(a[end]+" ");
      start=end;
      end++;
    }
  }
}

- Sathya February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude..all that is fine..but the basic problem is still the same. Can we improve the efficiency in the case when the maximum of last seen group is the first element of that group. Right now we are calling findmax in that case. But in worst case when array is sorted in decreasing order...it is
O((n-k+1).k)...

- XYZ February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@XYZ:
If a given array is random.The probability of what u saying is 1/n! do u think it is really worth to maintain the 2nd and 3rd maxs coz they wud be of no use if 1st max is defeated...

- Sathya February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

struct Node {
  struct Node* prev;
  struct Node* next;
  double value;
};

static void Remove(struct Node* n) {
  n->prev->next = n->next;
  n->next->prev = n->prev;
  n->next = n;
  n->prev = n;
}

int main(int argc, char* argv[]) {
  int k;
  sscanf(argv[1], "%d", &k);
  struct Node* elem = calloc(k, sizeof elem[0]);
  for (int i = 0; i < k; ++i) {
    elem[i].prev = &elem[i];
    elem[i].next = &elem[i];
  }
  struct Node list;
  list.prev = &list;
  list.next = &list;
  list.value = NAN;
  while (1) {
    for (int i = 0; i < k; ++i) {
      Remove(&elem[i]);
      scanf("%lg", &elem[i].value);
      // amortized O(1)
      while (list.prev->value <= elem[i].value) Remove(list.prev);
      elem[i].prev = list.prev;
      elem[i].next = &list;
      list.prev->next = &elem[i];
      list.prev = &elem[i];
      printf("%.17lg\n", list.next->value);
    }
  }
}

- Anonymous February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's O(n) where the constant doesn't depend on k.

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It'd be better if you first illustrate the idea briefly. It's hard to refute a claimed complexity by analyzing the code for all cases. Also, when you are explaining your idea to an interviewer, you first give him the idea (then pseudo-code and/or code).

Now, for your cases, it's hard for many (like me) to understand the amortized cost of O(1) in the inner loop. Your explanation would be appreciated.

- anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Amortized O(1) is because he's adding to the list only one element per number, and # removes <= # adds.

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't make sense. Please write pseudo code

- Troll February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

He's maintaining a list of the max in the current window of k items, followed by the max after that max, etc. He removes the element from k reads ago (assuming it was in the list; otherwise the Remove is a no-op), pops maximums that are no longer maximums, and inserts the value read at the end of the list.

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not better than maintaining a heap, in fact much worser

- GekkoGordan February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not maintaining the full heap, only the elements that could become maximums. It's amortized O(1) because anything less than the current element can be discarded.

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Okay I don't undestand, what exactly r u trying to do? pseudo code/ algorithm please.
Also demonstrate on this example 9 8 7 6 5 9 8 7 5 5 6 5 with k=3. if possible

- GekkoGordan February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let k =3;
step 1: Maintain 'k' array tree.root having max element in tree.
Display max element.
Here tree having one root, left,middle,right nodes.

index = k;
node = left_node;

step 2: if(node->value == root)
{
node->value = a[index]; // Insert new element in tree

Find out max value of tree.
root = max_value
}
else
{
node->value = a[index]; // Insert new element in tree

if(node->value > root)
root = node->value;
}

print root.

step3: index=index+1;
if(index %k == 0) node = left_node;
else if((index+1)%k ==0) node = middle_node;
else if(index+2)%k==0) node = last_node;
Repeat step 2 till index reaches 'n'.

Example: 90 40 3 5 6 7 8

Here: 90- root
90- left node
40- middle node
3- right node o/p -> 90
for '5' - 5 has to replace left node first.
here root and left node same.
Insert 5 in left node.max element in tree is 40.
Now tree,
40 - root
5 - left
40 - middle
3 - right o/p -> 40
for '6' - Replace 6 in middle node.
Here same like above case.
Now tree,
root- 6
left - 5
middle-6
right - 3 o/p->6
For '7' - Replace right node.
Here a[index]>root so, root = a[index]
now tree,
root - 7
left - 5
middle-6
right -7 o/p->7
For '8'- Replace left node.
Here a[index]>root so, root = a[index]
root - 8
left node - 8
middle - 6
right node - 7 o/p->8

Final o/p = 90 40 6 7 8

- ch.v.suresh February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do not think it is O(n)

- Anonymous February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a[i] = { 1, 2, 3, 1, 4, 5, 2, 3, 6 };
b[j] = { 2, 3, 3, 4, 5, 5, 5, 6 };

Construct array b from a where
j = i - 1;
b[j] = max(a[i], a[i-1], b[j-1]);

now if k = 1
return the array a
for rest
return b[j=k-2 to length of b]

- Anonymous February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesnt work with ur own eg..put k=2..b[6] shud be 3 but 5 in ur eg

- Sathya February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can be done in o(n)
each iteration maintain two maximum values of subset k...
next iteration i.e i+1.....
if(max1==i+1-k)
compare(max2,arr[i+1])
else
compare(max1,arr[i+1])
assign max1 & max2
go for next i;
this gives o(n)time complexity.
plz correct me if nything wrong in this

- Anonymous February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

example array = 5 2 6 1 3 12 7
k = 3;
max1 = 6 max2 = 5
for next iteration max1 = 6 and max2 is eliminated, now how do you get the max2?

- Anonymous February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops this will not work out.......my bad!! thanks for pointing out

- Anonymous February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

nlogk solution using BST to store frequencies of current k numbers. Adding, removal and retrieval of max all logk complexity, so totaling to nlogk :)

- Giorgi February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For complexity analysis, I guess you meant "balanced" BST, like AVL or RB tree. Otherwise, worst case complexity for a BST operation could be O(k), which leads O(nk) complexity.

- anonymous February 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "iostream"
using namespace std;
#define N 3

typedef struct nn{
int data;
int index;
struct nn *next;
struct nn *pre;
}record;

void findMin(int *a, int size){
record * head = new record;
record *p = head, *q;
for(int i = 1; i < N; i++){
p->next = new record;
q = p;
p = p->next;
p->pre = q;
}
p->next = head;
head->pre = p;
int currentMax = 0;
int stored = 0;
int i,j;
for(i = 0; i < N; i++){
p->index = -N-1;
p=p->next;
}
p = head;
q = head;
for(i = 0; i < size; i++){
while(a[i] >= p->data && i-p->index < N){
p = p->pre;
}
p = p->next;
p->data = a[i];
p->index = i;
while (i-q->index >= N) q = q->next;
cout<<q->data<<endl;;

}

}

int main(){
int a[] = {1,2,3,1,4,5,2,3,6};
findMin(a,9);
}

- Anonymous February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dirty coder!!!

- anonymous March 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Isn't it Range Minimum Query problem, where each range is of size k and there are total n-k+1 queries? In that case, we can use either of below two:

- a segment tree (heap like DS) with O(n) pre-processing and each query takes O(log n). So total complexity O(n logn).

- a DP based solution that fills a matrix M of size n times logk, where M[i][j] stores the maximum value of a sub-array of size 2^j starting at i. Now each query mapped to a comparison of max values of 2 regions that overlap the entire range of size k.

This approach has O(n logk) preprocessing, and each query takes O(1). Hence, total complexity O(n logk). It's both faster, and quicker to code; but, needs O(n logk) space compared to O(n) space for first approach.

- buried.shopno March 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you need a queue and max heap, enqueue each element to queue and add to max heap, check if queue size is bigger than k, dequeue the front, and delete it from heap. which has log k cost, so total cost would be o(n.log(k))

- erinc March 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Would u mind to explain how you delete an item from heap in O(log k)? To my understanding heap is only good, i.e. O(log k) complexity, to delete min/max item.

- anon March 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a C# solution based on DP. The problem is trivially solved for frame size 1 (output == input). Using solution for frame size k-1 and input array, we can build solution for frame size k using the formula

maxK[i] = max(maxK_1[i-1], input[i])

static void PrintMaxSubK(int[] a, int k)
{
    if (a == null || a.Length < 1 || k < 0)
    {
        // error cases
        return;
    }

    // adjust target frame size if needed
    if (k > a.Length) k = a.Length;

    int[] maxCurrent = new int[a.Length];
    a.CopyTo(maxCurrent, 0);    
    int[] maxNext;
    int l;

    // gradually increase frame size
    for (l = 1; l < k; l++)
    {
        maxNext = new int[a.Length];

        for (int i = l; i < a.Length; i++)
        {
            maxNext[i] = (a[i] >= maxCurrent[i-1]) ? a[i] : maxCurrent[i-1];
        }

        maxCurrent = maxNext;
    }

    // output values
    for (int i = k - 1; i < maxCurrent.Length; i++)
    {
        Console.WriteLine(maxCurrent[i]);
    }
}

- saifullah.baig March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is still o(nk)?

- Anonymous March 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems so to me

- saifullah.baig March 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a BST of size k. First add the first k numbers from the array into the BST. Then we can start:
For the first one, just get the biggest number from the BST. Then move on: remove the first value in the array from BST, add the (k+1)th value in the array to BST, get the biggest number. Go one until reach the end of the array.
It will take O(n*logk). Using BST, not heap because remove a given number from a heap takes O(k), well BST takes O(logk). O(1)+O(k) = O(K). O(logk)+O(logk)=O(logk)

- Jike March 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When people talk about BST, they often forget that WORST case height (i.e. complexity to remove/find an element in BST) is O(n). Don't say you'd implement a RB tree to balance the height O(log n) at each step. Being said that, your algorithmic complexity is O(nk).

Either of the two approaches that buried posted seems efficient and quick to implement.

- LOL March 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Assume 0 based array index below.

- Create an array 'max' of size n, where max[i] represents index of the element containing maximum value of sub-array a[i-k+1...i]. first k-1 elements of max array would be marked with some invalid value (lets say -1).

- Compute max[k-1] by scanning first k elements of the array a[0...k-1].

- Value of max[k] would be
   if(a[k] > max[k-1]) {
      max[k] = k // a[k] is bigger than max value of a[0...k-1]
   }
   else if(max[k-1] != 0) {
      max[k] = max[k-1] // 0th element did not have max value, thus max value remain unchanged for a[1...k]
   }
   else {
      max[k] = -1 //unknown because first element a[0] had the max value which is dropped from the window a[1...k] now.
   }

- Thus, we can compute the max of a[i...i+k-1] in constant time using max value of a[i-1...i+k-2] except the last scenario above.

- Now, Lets traverse the array backwards and compute the same max values and store them in array b_max.

- Here, for a window a[i...i+k-1], at least one of max[i+k-1] and b_max[i] would not be -1 since the last scenario in the above if block cannot happen in both directions. That index value would contain the max value for a given window.

Complexitiy would be O(n). what do you think?

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

nevermind. This is incorrect.

- Anonymous March 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

corrected formatting...

- Assume 0 based array index below.

- Create an array 'max' of size n, where max[i] represents index of the element containing maximum value of sub-array a[i-k+1...i]. first k-1 elements of max array would be marked with some invalid value (lets say -1).

- Compute max[k-1] by scanning first k elements of the array a[0...k-1].

- Value of max[k] would be

if(a[k] > max[k-1]) {
      max[k] = k // a[k] is bigger than max value of a[0...k-1]
   }
   else if(max[k-1] != 0) {
      max[k] = max[k-1] // 0th element did not have max value, thus max value remain unchanged for a[1...k]
   }
   else {
      max[k] = -1 //unknown because first element a[0] had the max value which is dropped from the window a[1...k] now.
   }

- Thus, we can compute the max of a[i...i+k-1] in constant time using max value of a[i-1...i+k-2] except the last scenario above.

- Now, Lets traverse the array backwards and compute the same max values and store them in array b_max.

- Here, for a window a[i...i+k-1], at least one of max[i+k-1] and b_max[i] would not be -1 since the last scenario in the above if block cannot happen in both directions. That index value would contain the max value for a given window.

Complexitiy would be O(n). what do you think?

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

never mind. This is incorrect.

- Anonymous March 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for (int i=0;i<k;i++) {
if(a[i] > k)
big = a[i];
Mapp[arrayNum]=big;
}
int arrayNum=2;
for(i=k;i<n;i++){
if(a[i] > big) {
big=a[i];
}
Mapp[arrayNum]=big;
}


so now .. at the end, we have Outputs
Mapp[arrayNum]

so for every Array of K elements, which starts with index arrayNum, Mapp[arrayNum] is the biggest element

- Lohith Ravi March 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All you need to do is maintain the max (denoted by 'maxs') and the second max (denoted by 'maxs2') of each set of size 'k' and iterate over the list of size 'n'. Using DP this can be done as follows:

void maxOfSubArray(int* array, int index, int k, int* maxs, int* maxs2, int maxIndex) {

if(index == k - 1) {
maxs[maxIndex] = array[0];
maxs2[maxIndex] = array[0];
for(int i = 0; i < k; ++i) {
if(array[i] > maxs[maxIndex]) {
maxs[maxIndex] = array[i];
}
if((array[i] > maxs2[maxIndex]) &&
(array[i] < maxs[maxIndex])) {
maxs2[maxIndex] = array[i];
}
}
} else {
maxOfSubArray(array, index - 1, k, maxs, maxs2, maxIndex - 1);
if(maxs[maxIndex - 1] == array[index - k - 1]) {

if(maxs2[maxIndex - 1] > array[index]) {
maxs[maxIndex] = maxs2[maxIndex - 1];
maxs2[maxIndex] = array[index];
} else {
maxs[maxIndex] = array[index];
maxs2[maxIndex] = maxs2[maxIndex - 1];
}
} else {
if(maxs[maxIndex - 1] > array[index]) {
maxs[maxIndex] = maxs[maxIndex - 1];
maxs2[maxIndex] = array[index];
} else {
maxs[maxIndex] = array[index];
maxs2[maxIndex] = maxs[maxIndex - 1];
}

}
}
}

iint main() {

int array[] = {
1, 2, 3, 1, 4, 5, 2, 3, 6
};
int length = 9;
int k = 3;

int* maxs = new int[length - k + 1];
int* maxs2 = new int[length - k + 1];
maxOfSubArray(array, length - 1, k, maxs, maxs2, length - k);

std::cout << std::endl;
for(int i = 0; i < (length - k + 1); ++i) {
std::cout << maxs[i] << "\t";
}
std::cout << std::endl;

delete[] maxs;
delete[] maxs2;

return 0;
}

Only in the base case do we iterate over the first 'k' elements to find the max; otherwise we're just traversing the list one time, so the complexity would be O(n + k), i.e. linear time

- Karan Gupta April 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reposting to allow code indentation:-

All you need to do is maintain the max (denoted by 'maxs') and the second max (denoted by 'maxs2') of each set of size 'k' and iterate over the list of size 'n'. Using DP this can be done as follows:

void maxOfSubArray(int* array, int index, int k, int* maxs, int* maxs2, int maxIndex) {
	
	if(index == k - 1) {
		maxs[maxIndex] = array[0];
		maxs2[maxIndex] = array[0];
		for(int i = 0; i < k; ++i) {
			if(array[i] > maxs[maxIndex]) {
				maxs[maxIndex] = array[i];
			}
			if((array[i] > maxs2[maxIndex]) &&
			   (array[i] < maxs[maxIndex])) {
				maxs2[maxIndex] = array[i];
			}
		}
	} else {
		maxOfSubArray(array, index - 1, k, maxs, maxs2, maxIndex - 1);
		if(maxs[maxIndex - 1] == array[index - k - 1]) {
		
			if(maxs2[maxIndex - 1] > array[index]) {
				maxs[maxIndex] = maxs2[maxIndex - 1];
				maxs2[maxIndex] = array[index];
			} else {
				maxs[maxIndex] = array[index];
				maxs2[maxIndex] = maxs2[maxIndex - 1];
			} 
		} else {
			if(maxs[maxIndex - 1] > array[index]) {
				maxs[maxIndex] = maxs[maxIndex - 1];
				maxs2[maxIndex] = array[index];
			} else {
				maxs[maxIndex] = array[index];
				maxs2[maxIndex] = maxs[maxIndex - 1];
			}
			
		}
	}
}

int main() {

	int array[] = {
		1, 2, 3, 1, 4, 5, 2, 3, 6
	};
	int length = 9;
	int k = 3;
	
	int* maxs = new int[length - k + 1];
	int* maxs2 = new int[length - k + 1];
	maxOfSubArray(array, length - 1, k, maxs, maxs2, length - k);
	
	std::cout << std::endl;
	for(int i = 0; i < (length - k + 1); ++i) {
		std::cout << maxs[i] << "\t";
	}
	std::cout << std::endl;
	
	delete[] maxs;
	delete[] maxs2;
	
	return 0;
}

Only in the base case do we iterate over the first 'k' elements to find the max; otherwise we're just traversing the list one time, so the complexity would be O(n + k), i.e. linear time

- Anonymous April 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

One possible solution:
1. Use a max heap of size K to get the maximum of K elements at any time.
2. Use a hash map that would let you directly access any element in the heap, with the index of that element in the array as key.

Why this works?
Lets suppose you have to find the maximum between index P and P-K, Now will have a heap that contains K elements between index P-1 and P-K-1,
--Pop element at index P-K-1 from heap and hashmap(Cost = O(1)+O(logK))
--insert element at index P in the heap and hashmap(cost = O(1)+O(logK))
--top element from the heap gives you maximum between index P and P-K (cost = O(1))
You would repeat above N-K+1 times so
total cost = (N-K+1) * O(logK) = O(N*logK)

- Epic_coder October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There exists a O(n) solution using a deque
Google for it you will find it

- Geek January 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a sliding range minimum query problem. It can be solved in O(n) time.

import collections

# Given an array and an integer k , find the maximum for each and every
# contiguous sub array of size k.

class SlidingRangeMinimum:
    """h t t p://wcipeg.com/wiki/Sliding_range_minimum_query"""
    def __init__(self):
        self._data = collections.deque()
        self._range_begin = 0
        self._range_end = 0
    def push_back(self, val):
        new_val = (val, self._range_end)
        while len(self._data) > 0 and self._data[-1] > new_val:
            self._data.pop()
        self._data.append(new_val)
        self._range_end += 1
    def pop_front(self):
        assert len(self._data) > 0
        self._range_begin += 1
        if self._data[0][1] < self._range_begin:
            self._data.popleft()
    def range_begin(self):
        return self._range_begin
    def range_end(self):
        return self._range_end
    def range_len(self):
        return self._range_end - self._range_begin
    def min(self):
        return self._data[0][0]
    def data(self):
        return self._data

def solve(s, k):
    if len(s) < k: return []
    ret = []
    srm = SlidingRangeMinimum()
    for i in xrange(len(s)):
        srm.push_back(-s[i])
        if i >= k-1:
            ret.append(srm.min())
            srm.pop_front()
    return ret

s = [int(i) for i in "1 2 3 1 4 5 2 3 6".split()]
k = 3
print ','.join([str(-i) for i in solve(s, k)])

- Nightingale November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code for an O(N) solution, using a Max Queue that supports enqueue, dequeue, and get_max in ammortized O(1).

class MaxQueue(object):
    """
    A max queue using two stacks
    """
    def __init__(self):
        # a stack that holds incoming elements
        self.enq = []
        # a stack that holds outs outgoing elements
        self.deq = []

    def enqueue(self, val):
        # add to the incoming
        self._enqueue(val, self.enq)
        
    def dequeue(self):

        # if someone called dequeue and there's nothing in the dequeue
        if len(self.deq) == 0:
            # clear the incoming stack
            while len(self.enq) > 0:
                # put the elements onto the outgoing stack
                self._enqueue(self.enq.pop()[0], self.deq)

        # now return the last element on the outgoing stack
        return self.deq.pop()[0]

    def get_max(self):

        # the idea here is that the max is the max of two stacks
        if not self.enq and not self.deq:
            raise ValueError("Queue is empty")
        elif not self.deq:
            return self.enq[-1][1]
        elif not self.enq:
            return self.deq[-1][1]
        else:
            return max(self.enq[-1][1], self.deq[-1][1])

    # protected enqueue method to handle both stacks
    def _enqueue(self, val, queue):

        if len(queue) > 0:
            item_max = max(queue[-1][1], val)
        else:
            item_max = val
    
        queue.append((val, item_max))

def crawling_window(vector, k):

    # use our fancy queue
    mq = MaxQueue()

    # initialize the first window
    for i in range(k):
        mq.enqueue(vector[i])

    # print the max of the first window
    print mq.get_max()

    # crawl the vector
    for i in range(k, len(vector)):
        
        # dequeue the oldest
        mq.dequeue()
        # insert the newest
        mq.enqueue(vector[i])
        # get the max
        print mq.get_max()

- Rob January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The best possible solution here would be O(nlogk). At each stage you need to maintain the k largest numbers, and you could use a min heap to do this. I think this is similar to the find the largest k numbers in an array type question.

- vinod. February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What u mean by 'each stage'?can u explain a bit more?

- Sathya February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

> The best possible solution here would be O(nlogk)

No, there's an O(n) solution that makes one linear pass. The trick is that if there's a smaller number followed by a bigger number, you can forget about the smaller number entirely.

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So what will happen if we have monotoneously decreasing array?

- Zerg February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Incorrect! Will not work for monotonically decreasing input.

- Epic_coder October 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i guess in O(n) it can be done..
just have a look at this algo.

let say the array is a[7]={45,34,12,36,34,67,1)

1) take a variable max=0(initially).
2) iterate through the array by using one for loop.
3)then in for loop use the following code.

for(int i=0;i<8;i++)
{
if((a[i] > a[i+1]) && (a[i]> a[i+2]))
{
max=a[i];
}
else
{
if( a[i]> a[i+1} && (a[i] < a[i+2]))
max=a[i+2];
else
{
if(a[i]< a[i+1} && (a[i] > a[i+2]))
max=a[i+1];
elseif(a[i+1}<a[i+2])
max=a[i+2];
else
max=a[i+1];
}
printf("%d\n",max);
}//end of for loop
this is for array with no two same elements

- asetech February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please use 3 open curly braces before the code and 3 closed curly braces after the code for keep the code formatted

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@asetech:What r u doing?if u r trying to find max of 3 try this
a>b?(a>c?a:c):(b>c?b:c)

- Sathya February 15, 2011 | 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