Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
Cyrus,can u pls tell more about the subarrays,are they overlapping or is it something like sliding window?
Cyrus could you post your code for this question? thx
Did they ask it on a phone interview?
@cyrus : Here is a o(n) approach using doubly ended queue./****************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct DQnode
{
int data,index;
struct DQnode *next,*prev;
};
struct DQueue
{
struct DQnode *front,*rear;
};
struct DQueue *createDQueue(void)
{
struct DQueue *newNode=(struct DQueue *)malloc(sizeof(struct DQueue));
newNode->front=newNode->rear=NULL;
return newNode;
}
struct DQnode *newDQnode(int data,int index)
{
struct DQnode *temp=(struct DQnode *)malloc(sizeof(struct DQnode));
temp->data=data;
temp->index=index;
temp->prev=temp->next=NULL;
return temp;
}
int isDQueueEmpty(struct DQueue *DQ)
{
return (DQ->front==NULL);
}
void DQPushBack(struct DQueue *DQ,int data,int index)
{
struct DQnode *temp=newDQnode(data,index);
if(DQ->front==NULL&&DQ->rear==NULL)
DQ->front=DQ->rear=temp;
else
{
DQ->rear->next=temp;
temp->prev=DQ->rear;
DQ->rear=temp;
}
}
void DQPopFront(struct DQueue *DQ)
{
if(isDQueueEmpty(DQ))
return;
struct DQnode *temp=DQ->front;
if(DQ->front==DQ->rear)
DQ->front=DQ->rear=NULL;
else
{
DQ->front->next->prev=NULL;
DQ->front=DQ->front->next;
temp->next=NULL;
}
free(temp);
temp=NULL;
}
void DQPopBack(struct DQueue *DQ)
{
if(isDQueueEmpty(DQ))
return;
struct DQnode *temp=DQ->rear;
if(DQ->front==DQ->rear)
DQ->front=DQ->rear=NULL;
else
{
DQ->rear->prev->next=NULL;
DQ->rear=DQ->rear->prev;
temp->prev=NULL;
}
free(temp);
temp=NULL;
}
struct DQnode *frontDQueue(struct DQueue *DQ)
{
if(isDQueueEmpty(DQ))
return NULL;
struct DQnode *temp=DQ->front;
return temp;
}
struct DQnode *backDQueue(struct DQueue *DQ)
{
if(isDQueueEmpty(DQ))
return NULL;
struct DQnode *temp=DQ->rear;
return temp;
}
void maxSlidingWindow(int arr[],int n,int k)
{
int i;
struct DQueue *DQ=createDQueue();
for(i=0;i<k;i++)
{
while(!isDQueueEmpty(DQ)&&(arr[i]>=backDQueue(DQ)->data))
DQPopBack(DQ);
DQPushBack(DQ,arr[i],i);
}
for(;i<n;i++)
{
printf("%d ",arr[frontDQueue(DQ)->index]);
while(!isDQueueEmpty(DQ)&&(frontDQueue(DQ)->index<=i-k))
DQPopFront(DQ);
while(!isDQueueEmpty(DQ)&&(arr[i]>=backDQueue(DQ)->data))
DQPopBack(DQ);
DQPushBack(DQ,arr[i],i);
}
printf("%d ",arr[frontDQueue(DQ)->index]);
}
int main()
{
int arr[] = {5,6,1,2,3,4,5,6,7,8,9};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
maxSlidingWindow(arr, n, k);
scanf("%d");
return 0;
}
/****************************************************************/
@cyrus:The above code was posted by me.Suggestions,modifications and comments are welcome.
Yes, gautam's solution works, here's the python version:
#!/usr/bin/python
from collections import deque
def slide_win(l, k):
dq=deque()
for i in range(0,len(l)):
while len(dq)>0 and dq[-1][1]<=i-k:
dq.pop()
while len(dq)>0 and l[i]>=dq[0][0]:
dq.popleft()
dq.appendleft((l[i],i))
if i>=k-1:
print dq[-1][0]
def main():
l=[5,6,1,2,5,4,8,2,4,3]
k=3
print "l="+str(l)
print "k="+str(k)
slide_win(l,k)
if __name__ == "__main__":
main()
I dont understand why do we need sliding window or any other such complication, its a simple liner traversal algo:
O(n)
void findmax (int a[], int k, int n) {
int count = 0;
int max = Integer.MIN_Value;
int i = 0;
while ( i < n) {
while (count < k && i < n) {
if (a[i] > max) {
max = a[i];
}
count++;
i++;
}
System.out.println(max);
count = 0;
max = Integer.Min_Value;
}
}
Algorithm explained here: codercareer.blogspot.com/2012/02/no-33-maximums-in-sliding-windows.html
Java Version of the code
public 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.size() > 0
&& numberQueue.peek() > i - k
&& (numbers[numberQueue.peek()] > numbers[i])) {
tmpQueue.add(numberQueue.remove());
}
tmpQueue.add(i);
numberQueue = tmpQueue;
if (i>=k-1)
System.out.println(numbers[numberQueue.peek()]);
}
}
A simple O(n) solution could be to get the max of first k elements of the array and push this max into an arraylist(call it maxs). Now start a loop from i=k and push max(maxs.last(),a[i]).
Thsats it. Code below:
ArrayList<int> getMaxs(int[] a, int k) {
ArrayList<int> maxs = new ArrayList<int>();
maxs.Add(Math.Max(a.SubAarray(0,k)));
for(int i=k;i<a.length;i++) {
maxs.add(maxs.Last(),a[i]);
}
return maxs;
}
What about using an iterator It to go over the input array.Keep a new array of size k and for each k section in the input store the maximum value in the new new array(of size k). O(n) time; O(k) space.
Lets say we have 2 arrays: in and out. In is the input and out is the output of size k. At the end array out will have :
- at position 0 the maximum value for the first k values in the array in.
- at position 1 the maximum value for the second k values in array in
.....
and so on.
int idx ; // index to go over the in array
int idx_K; // index to go over the out array
idx_K = idx / k;
so if (in[idx] > out[idx_K]) out[idx_K] = in[idx];
return out;
It returns 6 3 4. I forget to ask how do u divide in subarrays? I assumed first k elem then next k and so on
no, the sub-arrays are not consecutive, they are overlapping like in a sliding window.
So for the above example the answer should b:
max(6,5,4) = 6
max(5,4,3) = 5
max(4,3,1) = 4
max (3,1,2) = 3
max (1,2,3) = 3 and so on.....
ok this is max element in sliding window
keep an aux array of size k
and copy first k elements of the entire frame into the aux array and find max
so it ll be the max of first subarray
now for(i=k to n)
include an element
if(arr[i]>max)
max=arr[i]
print max for consecutive subarrays
Naive solution: find max of each subarray by scanning the subarray - total time O(kN)
This can be improved by using the previous max when possible, for example:
suppose max of A[0..10] is 100. Now we try to find new max for A[1..11]. So we can check if A[11] is more than 100 and if so then it's the max, otherwise if A[0] was not the max then the max is still 100. But the worst case will still be O(kN).
A different solution using a heap will give O(N log N) time which might be better, if k>lg N.
You push the first k items (each item consists of the value and its position) into a max-heap. Now you peek the top of the heap to find the first max. For each subsequent item, push it into the heap, and peek at the top element. If the top is an item in the current window then it's the current max, otherwise pop it and peek at the new top element.
Use a TreeSet to insert element into the Set (addition of element takes O(logn))
then when size of set is equal to K ,use the last() to retrieve the last element(which is the greatest element) and remove the first element in the set using remove(first())...-total complexity is Nlogn
Since the size of the tree is K the and each operation remove, insert, find_max takes O(log K) time and you have to repeat N times, so the total time is O(N log K).
And btw, I already gave that solution above.
#include <stdio.h>
int main()
{
int array[12]={1,6,7,8,3,2,4,-6,4,13,1,17};
int K,max_value,temp,i=0;
scanf("%d",&K);
temp = K;
max_value = array[0];
for( i=0; i<12;i++)
{
if(K > 0)
{
if(max_value < array[i+1])
{
max_value = array[i+1];
}
K--;
}
else
{
printf("Max value %d\n",max_value);
max_value = array[i+1];
K=temp;
}
}
return 0;
}
Hi cyrus,
wanted to confirm.
if the array contains
9,8,7,6,5,4,3,1,0
and k=3
does that mean
the sub arrays would be
9,8,7
8,7,6
7,6,5
6,5,4
5,4,3
4,3,2
3,2,1
2,1,0
?
yes u r right.... i missed 2 in the array.
my solution:
int findMaxIndex (arr, start, k) {
maxI = start;
for(i=start+1; i<start+k; i++) {
if (arr[i] > arr[maxI]) {
maxI = i;
}
}
return maxI;
}
void printMaxInSubArray(arr, k) {
maxI = findMaxIndex(arr, 0, k);
print arr[maxI];
for (i=k; i<arr.size; i++){
if (arr[i] > arr[maxI] ) {
maxI = i;
}
print arr[maxI];
}
}
#include<iostream>
#include<conio.h>
using namespace std;
void find_max_in_sub_arrays(int* pIntArray, int nLength, int nLengtOfSubArray)
{
for(int i = 0; i < nLength; i++)
{
int nStartIndexSubArray = i;
int nEndIndexSubArray = i + nLengtOfSubArray - 1;
int nMaxOfSubArray = pIntArray[nStartIndexSubArray];;
for(int j = nStartIndexSubArray + 1; j <= nEndIndexSubArray; j++)
{
if(pIntArray[j] > nMaxOfSubArray)
{
nMaxOfSubArray = pIntArray[j];
}
}
for(int k = nStartIndexSubArray; k <= nEndIndexSubArray; k++)
{
cout << pIntArray[k] << ",";
}
cout << endl;
cout << "max of this sub array = " << nMaxOfSubArray << endl;
if(nEndIndexSubArray == nLength - 1)
{
break;
}
}
}
int main()
{
//int nArray[] = {8,1,4,9,6,3,5,2,7,0};
int nArray[] = {22,11,33,44,66,88,99,10,100};
int nLength = sizeof(nArray)/sizeof(int);
for(int i = 0; i < nLength; i++)
{
cout << nArray[i] << ",";
}
cout << endl;
int nSizeOFSubArray = 3;
find_max_in_sub_arrays(nArray, nLength, nSizeOFSubArray);
_getch();
}
Use doubly ended queue .time complexity - o(n).space complexity - o(n).
- gautam714 January 20, 2013