Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
I do not think that there is any complex thing to explain in my code.
I am using a deque whose front will always contain maximum element.
First I am putting first K element's index in my deque along with the condition such that, If coming element is less than last element of deque then there is no need to store its index.
Then in second while loop, I am checking if current maximum goes out of the window or not.
Third while loop is similar to first one.
I don't know what is difficult to understand in this code. People wants everything to be served to them ready to eat. Please apply your mind to understand the code by running over some example. This is how you will grow.
Downvoting just for fun is not good for such a great platform provided to us.
Ok.
If you look closely then you can see that, we are adding and removing each element in the deque, exactly once. So, it will be O(n)
When an element enters the queue from the back, it can knock out all the smaller elements in front of it, because those elements are also older than it. Since every new element enters the queue at its proper position in terms of bigness/smallness, you are guaranteed that the queue preserves order.
An element may eventually reach the front of the queue, even though it's too old to actually count for anything, but @nitingupta180 handles that by just dropping them on the floor when they reach the front if they're too old. I suppose you will occasionally have multiple elements at the front of the queue that need to be dropped, but this will be balanced by occasions where the front element is young enough.
I think this solution time-complexity is O(nk). The worst case of the loop here should be K-1.
while(!Qi.empty() && arr[i] >= arr[Qi.back()])
{
Qi.pop_back();
}
@SkyClouds: you are correct that the worst case of any one execution of that loop is in fact O(K). However, consider that each element can be inserted and removed at most once. This means that even though any one execution of the loop could be O(K), the total runtime of all the executions of that loop is bounded by O(N). In other words, there can be some very slow executions of that loop, but you can't hit the worst case every time.
def findMaxinK(a,k):
max_ = a[0]
for i in range(len(a)):
if max_<a[i]:
max_=a[i]
if (i+1)%k==0:
print max_
if i!=len(a)-1:
max_ = a[i]
The complexity of DashDash's solution is O(nlog(k)), Jack's complexity is O(nk). Is there solution with complexity O(n)?
I'm wondering the same.
Your question essentially becomes: is there a data-structure where we can store k-elements, have the ability to remove one, add one, *and* find the min in O(1). I think the answer there is no: if you add or remove in O(1), the data cannot possible have any ordering/structure applied to it, so we can't get the min in O(1). If we want min in O(1), we're going to have to store it in some fashion that lets us extract that information quickly, and I think a min-heap is the best at just log(k) (as you said).
I agree with @jay, but I could just be lacking imagination. It's pretty easy to construct tricky scenarios for k=5:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
11 12 13 14 15 80 90 100 70 60 6 7 8 9 10
My hunch is that if you design a data structure that performs well on the former, it's probably gonna churn on the latter, and vice versa.
public class test{
public static void main(String[] args){
// ArrayList<Integer> a=new ArrayList<Integer>();
int max=Integer.MIN_VALUE, index=-1;
int[] a={6,5,2,3,1,0};
int k=2;
System.out.println(a.length-k);
for (int i=0; i<a.length-k;i++){
if (index<i){
max=Integer.MIN_VALUE;
for (int j=0;j<k;j++)
if (a[i+j]>max){
max=a[i+j];
index=(i+j);
}
}
else
if(a[i+k]>a[index]){
max=a[i+k];
index=i+k;
}
System.out.println(max);
}
// System.out.println();
}
}
static void Main(string[] args)
{
int[] parentArray = new int[] {11, 12, 13, 14, 15, 80, 90, 100, 70, 60, 6, 7, 8, 9, 10};
int subArraySize = 0;
Console.Write("Enter the sub array size: ");
bool result = int.TryParse(Console.ReadLine(), out subArraySize);
if (subArraySize <= 0 || subArraySize >= parentArray.Length)
{
Console.WriteLine("Size out of bounds");
return;
}
for (int i = 0; i < (parentArray.Length - subArraySize + 1); i++)
{
int temp = parentArray[i];
for (int j = 0; j <= subArraySize-1; j++)
{
temp = Math.Max(parentArray[j+i], temp);
}
Console.Write(temp.ToString() + " ");
}
}
wi this could be the better soln for this????
#include<stdio.h>
struct list
{
int data;
struct list *next;
}*root=NULL;
int sorted_insertion(int n)
{
struct list *node=root,*temp;
if(root==NULL){
node=new list;
node->data=n;
node->next=NULL;
root=node;}
else
{
if(n>root->data)
{
node=new list;
node->data=n;
node->next=root;
root=node;
}
else
{
temp=root;
while((temp->next!=NULL)&&(temp->next->data>n))temp=temp->next;
if(temp->next==NULL){
node=new list;
node->data=n;
node->next=NULL;
temp->next=node;}
else
{
node=new list;
node->data=n;
node->next=temp->next;
temp->next=node;
}
}
}
return 0;
}
int display()
{
struct list *temp=root;
int count=0;
while(temp&&count<3)
{
printf("\t%d",temp->data);
temp=temp->next;
count++;
}
return 0;
}
int main()
{
int a[10],n,m,b[10],k=0,i,j,temp;
printf("enter the number of elements in the array");
scanf("%d %d",&n,&m);
printf("\nenter the array elements:\n");
for(i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]<=m)
sorted_insertion(a[i]);
}
printf("thus the nearest elements are:\n");
display();
return 0;
}
Here is an O(nk) solution. But this is obvious solution. I am looking for more efficient solution.
package array;
import java.util.Arrays;
public class MaxEachSub {
public static int[] findMax(int[] a, int k) {
if (k > a.length) {
return new int[] { Integer.MIN_VALUE };
}
int[] output = new int[a.length - k + 1];
for (int i = 0; i <= a.length - k; i++) {
output[i] = max(a, i, i + k - 1);
}
return output;
}
private static int max(int[] a, int beg, int end) {
int max = a[beg];
for (int i = beg + 1; i <= end; i++) {
if (a[i] > max) {
max = a[i];
}
}
return max;
}
}
#include <stdio.h>
int findmax(int a[], int start, int end);
int main()
{
int arr[] = {8,9,2,5,0,8,1,3,5};
int n = sizeof(arr)/sizeof(arr[0]);
int i, j, k, max;
i = 0;
printf ("Enter k\n");
scanf ("%d", &k);
j = i + k;
while (j <= n)
{
//printf ("\ni : %d\nj : %d\n", i, j);
max = findmax(arr, i, j);
printf ("%d ", max);
i++;
j++;
}
return 0;
}
int findmax(int a[], int start, int end)
{
int i;
int max = a[start];
for (i = start + 1; i < end; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
return max;
}
#include <stdio.h>
int findmax(int a[], int start, int end);
int main()
{
int arr[] = {8,9,2,5,0,8,1,3,5};
int n = sizeof(arr)/sizeof(arr[0]);
int i, j, k, max;
i = 0;
printf ("Enter k\n");
scanf ("%d", &k);
j = i + k;
while (j <= n)
{
max = findmax(arr, i, j);
printf ("%d ", max);
i++;
j++;
}
return 0;
}
int findmax(int a[], int start, int end)
{
int i;
int max = a[start];
for (i = start + 1; i < end; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
return max;
}
Use a max heap of size 3. Add the next element to the position where the first element is and then call heapify
private static void FindElements(int[] a, int k)
{
int count = 0;
while (count <= a.Length-k)
{
int max = int.MinValue;
for (int i = count; i < count + k; i++)
{
if (a[i] > max) max = a[i];
}
Console.Write(max + " ");
count = count +1 ;
}
}
This can be done in O(n) using a deque whose front will always hold maximum in current window. Space Complexity - O(k)
------------------------------------------------------------------------------------------------------------
- Nitin Gupta March 19, 2013void maxInWindow(int* arr, int k) { std::deque<int> Qi(k); int i; for(i = 0; i < k; i++) { while(!Qi.empty() && arr[i] >= arr[Qi.back()]) { Qi.pop_back(); } Qi.push_back(i); } for( ; i < length; i++) { std::cout << arr[Qi.front()] << std::endl; while(!Qi.empty() && i - k >= Qi.front()) { Qi.pop_front(); } while(!Qi.empty() && arr[i] >= arr[Qi.back()]) { Qi.pop_back(); } Qi.push_back(i); } std::cout << arr[Qi.front()] << std::endl; }