Google Interview Question
Software Engineer / DevelopersThis 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.
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.
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()]);
}
}
}
#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?
Sorry mate, but it is O(nk). You are using a k-iteration loop inside the n-iteration loop.
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.
Why not just use a max heap for k elements & you can get O(n*logk)
with O(k) space complexity
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
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.
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.
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;
}
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++;
}
}
}
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)...
#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);
}
}
}
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.
Amortized O(1) is because he's adding to the list only one element per number, and # removes <= # adds.
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.
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.
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
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]
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
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?
nlogk solution using BST to store frequencies of current k numbers. Adding, removal and retrieval of max all logk complexity, so totaling to nlogk :)
#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);
}
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.
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))
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]);
}
}
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)
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.
- 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?
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?
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
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
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
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)
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)])
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()
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.
> 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.
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
Please use 3 open curly braces before the code and 3 closed curly braces after the code for keep the code formatted
You can solve it using a dequeue in O(n)
- madhav February 16, 2011