Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Hi, did you get this question during the group coding interview or regular technical interview. Can you share your experience?
void getmin(int a[],int n,int num)
{
int i=0;
int b[100];
push_back(0);
for(i=1;i<n;i++)
{
while(front()!=-100 && front() <= i-num)
pop_front();
while(front()!=-100 && a[back()]>a[i])
pop_back();
push_back(i);
if(i>=num-1)
b[i-num+1]=a[front()];
}
for(i=0;i<n-num+1;i++)
printf("%d\t",b[i]);
printf("\n");
}
/*A Simple Java Code would look like this: */
import java.util.Scanner;
public class SlidingWindow {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("enter number of elements:");
int n = in.nextInt();
int a[] = new int[n + 1];
int temp[] = new int[n + 1];
System.out.println("enter " + n + " elements:");
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
System.out.println("enter the window size: ");
int w = in.nextInt();
for (int i = 0; i < (a.length - w); i++) {
for (int j = i; j < w + i; j++) {
System.out.print(a[j] + " ");
temp[j] = a[j];
continue;
}
System.out.println("Minimum is: " + findMin(temp));
System.out.println("");
}
}
public static int findMin(int[] a) {
int len = a.length;
int val = a[0];
for (int i = 1; i < len; i++) {
if (val < a[i]) {
} else {
val = a[i];
}
}
return val;
}
}
Please correct me if I am wrong.
public static void maxSlidingwindow(int a[],int n,int w)
{
int b[]=new int[n];
Deque<Integer> q=new ArrayDeque<>();
for(int i=0;i<w;i++)
{
while(!q.isEmpty() && a[i]<=a[q.peekLast()])
q.removeLast();
q.addLast(i);
}
for(int i=w;i<n;i++)
{
b[i-w]=a[q.peekFirst()];
while(!q.isEmpty() && a[i]<=a[q.peekLast()])
q.removeLast();
while(!q.isEmpty() && q.peekFirst() <= i-w)
q.removeFirst();
q.addLast(i);
}
b[n-w]=a[q.peekFirst()];
for(int i=0;i<n;i++)
System.out.print(b[i]+"\t");
}
Here is a C# solution using a queue to hold the window elements.
I *think* that makes this O(n) since you only need to visit each element once, which is better than O(nw) where n is number of elements and w is the size of the window. However I'm still sketchy on my big O so appreciate comments/corrections if I'm wrong :)
- johny418 April 02, 2014