## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

this can be done by dequeue with time complexity O(n)

``````public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> rst = new ArrayList<> ();
if (nums == null || nums.length == 0) {
return rst ;
}
for (int i = 0 ; i < k ;++i) {
while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
q.pollLast() ;
}
q.offer(i) ;
}
int tail = 0 ;
for (int i = k ; i < nums.length ;++i) {
while (!q.isEmpty() && q.peek() <= tail) {
q.poll() ;
}
while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
q.pollLast() ;
}
q.offer(i);
tail++;
}
return rst ;
}``````

Comment hidden because of low score. Click to expand.
0

Are you sure that this is O(1) average space complexity?

Comment hidden because of low score. Click to expand.
0

Additional data structures are unnecessary and may run out of memory due to the length of the stream

Comment hidden because of low score. Click to expand.
0

Deque is unnecessary because the elements are inserted in one end and extracted from the other end

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

am i missing something? all of the above solutions O(k) space complexity. If K is small, then yes, it is ~ O(1). But then the solution is trivial.

You just need to keep an unsorted array of size K. Keep adding new numbers to it (loop around if array is full). Then you just go through all elements and find the max. that is an O(k) operation too

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby impl. Running time:O(n). Space: O(1).

``````# ascending order
@stream_iter=0
@stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
WIN_SIZE=3
@k_largest=@stream[0] if @stream.kind_of?(Array) && @stream.length >= 1

def has_more?
@stream.kind_of?(Array) && @stream_iter < @stream.length
end

def max_int
return nil if WIN_SIZE <= 0
return @k_largest if !has_more?

if @k_largest.nil? || @stream[@stream_iter] > @k_largest
@k_largest=@stream[@stream_iter]
end

@stream_iter+=1
@k_largest
end

@stream.each do |value|
puts "Max: #{max_int}"
end

puts "Max: #{max_int}"``````

Output:
Max: 1
Max: 4
Max: 4
Max: 7
Max: 9
Max: 15
Max: 15
Max: 26
Max: 96
Max: 96
Max: 96
Max: 96
Max: 96
Max: 96

Comment hidden because of low score. Click to expand.
0

I noticed the solution has to be the last-k integers, like a sliding window. Hence, this max_int function could be tweaked to first run on a range from stream[0] to stream[win_size-1]. Then, if the max int is within the window(i.e. stream_iter), compare the max int with the new integer found and set max int accordingly. Otherwise, if the new integer found is greater than max int, set the new integer as the max int.

Comment hidden because of low score. Click to expand.
0

Correction: if the max int is not in the sliding window, then need to find the largest int in the sliding window. Since win_size-1 ints have already been accessed, it should be possible to compare the new found integer with the 2nd-largest integer from the prior window. This can be done with two vars, max and max_second in constant time.

Comment hidden because of low score. Click to expand.
0

Are you sure? Shouldn't the output after 96 96 96 look like 56 56?

Comment hidden because of low score. Click to expand.
0

The original solution was historical max int. Needs to be max int in a sliding window.

Comment hidden because of low score. Click to expand.
0
of 0 vote

. Use a balanced Binary tree to maintain k numbers in order
. Use a queue to maintain k numbers in sequence
Whenever a new number comes in,
1) remove the old one from the queue(O(1)) and search and remove it from the binary tree O(log k)
2) add the new number to the queue O(1) and add the new number to the binary tree O(log k)

For N numbers,
Time complexity: O(N log k) if k is considered a constant then O(N)
Space complexity: O(2K) if K is considered a constant then O(1)

Comment hidden because of low score. Click to expand.
0

BST will increase running time to O(klogn). Sorting does not add any value to the solution because each element is accessed at least once.

Comment hidden because of low score. Click to expand.
0

O(nlogk)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the correct Ruby impl. Running time: O(n)

``````require 'singleton'

class StreamSimulator
include Singleton

def initialize
@stream_iter=0
@stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
end

def has_more?
@stream_iter < @stream.length
end

def fetch_next_int
if has_more?
@stream_iter+=1
@stream[@stream_iter-1]
end
end
end

class SlidingWindow
def initialize(win_size, stream)
@win_size=win_size
@stream=stream
@buffer=Array.new(@win_size)
@buffer_iter=0
@current_iter=0
@k_largest=nil
@largest_position=nil
end

def end_of_window?
@buffer_iter + 1 % win_size == 0
end

def largest_int
@k_largest
end

def set_largest_int
if largest_int.nil? || current_value > largest_int
@k_largest=current_value
@largest_position=@current_iter
end
end

def win_size
@win_size
end

# rotating buffer
def fetch_next_int
@buffer[@buffer_iter]=@stream.fetch_next_int
@current_iter=@buffer_iter
@buffer_iter=@buffer_iter+=1 % win_size

# if window has slided and largest int was not the last input read in the prev window
if @buffer_iter==0 && @largest_position != win_size-1
@largest_position=nil
@k_largest=nil
end
end

def current_value
@buffer[@current_iter]
end

def find_max_int
return nil if win_size <= 0
return largest_int if !@stream.has_more?

fetch_next_int
set_largest_int
largest_int
end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
puts "Max int: #{sliding_win.find_max_int}"
end``````

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 15
Max int: 26
Max int: 96
Max int: 96
Max int: 96
Max int: 96
Max int: 96

Comment hidden because of low score. Click to expand.
0

Just noticed it's actually not sliding...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Corrected Ruby impl...

``````require 'singleton'

class StreamSimulator
include Singleton

def initialize
@stream_iter=0
@stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
end

def has_more?
@stream_iter < @stream.length
end

def fetch_next_int
if has_more?
@stream_iter+=1
@stream[@stream_iter-1]
end
end
end

class SlidingWindow
def initialize(win_size, stream)
@win_size=win_size
@stream=stream
@buffer=Array.new(@win_size)
@buffer_iter=0
@current_iter=0
@k_largest=nil
@largest_position=nil
end

def end_of_window?
@buffer_iter + 1 % win_size == 0
end

def largest_int
@k_largest
end

def set_largest_int
if largest_int.nil? || current_value > largest_int
@k_largest=current_value
@largest_position=@current_iter
end
end

def win_size
@win_size
end

# rotating buffer
def fetch_next_int
# if window has slided and largest int was not the last input read in the prev window
if @buffer_iter==0 && @largest_position != 1
@largest_position=nil
@k_largest=nil
end

@buffer[@buffer_iter]=@stream.fetch_next_int
@current_iter=@buffer_iter
@buffer_iter=(@buffer_iter+=1) % win_size
end

def current_value
@buffer[@current_iter]
end

def find_max_int
return nil if win_size <= 0
return largest_int if !@stream.has_more?

fetch_next_int
set_largest_int
largest_int
end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
puts "Max int: #{sliding_win.find_max_int}"
end``````

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 11
Max int: 26
Max int: 96
Max int: 15
Max int: 15
Max int: 56
Max int: 25

Comment hidden because of low score. Click to expand.
0
of 0 vote

Modified Ruby impl to use queue and hashet. Running time: O(n). Space: O(k).

``````require 'singleton'
require 'set'

class StreamSimulator
include Singleton

def initialize
@stream_iter=0
@stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
end

def has_more?
@stream_iter < @stream.length
end

def fetch_next_int
if has_more?
@stream_iter+=1
@stream[@stream_iter-1]
end
end
end

class SlidingWindow
def initialize(win_size, stream)
@win_size=win_size
@stream=stream
@k_largest=nil
@largest_position=0
@window=SizedQueue.new(@win_size)
@window_lookup=Set.new
end

def largest_int
@k_largest
end

def within_window?(value)
@window_lookup.include?(value)
end

def set_largest_int
@k_largest=nil if !within_window?(@k_largest)
@k_largest=current_value if @k_largest.nil? || current_value > @k_largest
end

def win_size
@win_size
end

def fetch_next_int
if @window.size == win_size
@window_lookup.delete(@window.pop)
end

@input=@stream.fetch_next_int
@window.push(@input)
@input
end

def current_value
@input
end

def find_max_int
return nil if win_size <= 0
return largest_int if !@stream.has_more?

fetch_next_int
set_largest_int
largest_int
end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
puts "Max int: #{sliding_win.find_max_int}"
end``````

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 15
Max int: 26
Max int: 96
Max int: 96
Max int: 96
Max int: 56
Max int: 56

Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution for the problem in Javascript. Looking forward for feedback.

``````var windowMax = 0;
var maxFor = 0;
var findMaxInWindow = function (windowSize, value) {
// console.log ("Finding the max in the range with the value" , value);

if (value > windowMax) {
windowMax = value;
maxFor = 1;
} else {
maxFor ++;
}

if (maxFor > windowSize) {
windowMax = value;
maxFor = 1;
}

}

var main = function ( ){
var windowSize = 3;

var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 15, 3, 56, 25];
var numOfValues = stream.length;
for (var i = 0 ; i < numOfValues; i++) {
var num = stream[i];
//console.log (num);
findMaxInWindow (windowSize, num);
//console.log ("The window max is " + windowMax + " maxFor  " + maxFor);
console.log (i + " ) " + stream[i] +" -  MAX : " + windowMax);
}
}

main();``````

The output is :

``````0 ) 1 -  MAX : 1
1 ) 4 -  MAX : 4
2 ) 2 -  MAX : 4
3 ) 7 -  MAX : 7
4 ) 9 -  MAX : 9
5 ) 15 -  MAX : 15
6 ) 11 -  MAX : 15
7 ) 26 -  MAX : 26
8 ) 96 -  MAX : 96
9 ) 15 -  MAX : 96
10 ) 3 -  MAX : 96
11 ) 56 -  MAX : 56
12 ) 25 -  MAX : 56``````

Comment hidden because of low score. Click to expand.
0

This will not work if the sequence is

1,2,10,4,6,5

1,2,10 -> 10
2,10,4 -> 10
10,4,6 -> 10
4,6,5 -> 6 ---> But your code with make 5 as the maximum value

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution to the problem in Javascript.

``````var windowMax = 0;
var maxFor = 0;
var findMaxInWindow = function (windowSize, value) {
// console.log ("Finding the max in the range with the value" , value);

if (value > windowMax) {
windowMax = value;
maxFor = 1;
} else {
maxFor ++;
}

if (maxFor > windowSize) {
windowMax = value;
maxFor = 1;
}

}

var main = function ( ){
var windowSize = 3;

var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 15, 3, 56, 25];
var numOfValues = stream.length;
for (var i = 0 ; i < numOfValues; i++) {
var num = stream[i];
//console.log (num);
findMaxInWindow (windowSize, num);
//console.log ("The window max is " + windowMax + " maxFor  " + maxFor);
console.log (i + " ) " + stream[i] +" -  MAX : " + windowMax);
}
}

main();``````

The output

``````0 ) 1 -  MAX : 1
1 ) 4 -  MAX : 4
2 ) 2 -  MAX : 4
3 ) 7 -  MAX : 7
4 ) 9 -  MAX : 9
5 ) 15 -  MAX : 15
6 ) 11 -  MAX : 15
7 ) 26 -  MAX : 26
8 ) 96 -  MAX : 96
9 ) 15 -  MAX : 96
10 ) 3 -  MAX : 96
11 ) 56 -  MAX : 56
12 ) 25 -  MAX : 56``````

Comment hidden because of low score. Click to expand.
0

Your code does not work with decreasing array.
test with {7,4,4,1} and windowSize=3
You will get 1 when 1 is the input of your function
whereas the solution is 4

Comment hidden because of low score. Click to expand.
0

Hi Alpha,
Thanks for pointing out, I did realise it myself too but feels good that some one is looking at the solution and providing feedback. Thanks for taking the time :)

thanks,
Sarath.

Comment hidden because of low score. Click to expand.
0

Could you please try stream 6, 4, 2, 3 to see if your code would produce the right outcome?

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution for Java.
Notice you have to use TreeMap and not TreeSet in case you get reoccurring values

``````import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

public class MaxK {

private TreeMap<Integer, Integer> tree;
private Queue<Integer> queue;
private final int k;

public MaxK(int k) {
if (k <= 0) {
throw new IndexOutOfBoundsException();
}
tree = new TreeMap<Integer, Integer>();
this.k = k;
}

public int getMaxK(int num) {
if (queue.size() >= k) {
Integer lastNum = queue.poll();
int refCount = tree.get(lastNum);
if (refCount <= 0) {
tree.remove(lastNum);
} else {
tree.put(lastNum, refCount - 1);
}

}

if (tree.containsKey(num)) {
tree.put(num, tree.get(num) + 1);
} else {
tree.put(num, 0);
}

int maxK = tree.lastKey();
return maxK;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

public class MaxK {

private TreeMap<Integer, Integer> tree;
private Queue<Integer> queue;
private final int k;

public MaxK(int k) {
if (k <= 0) {
throw new IndexOutOfBoundsException();
}
tree = new TreeMap<Integer, Integer>();
this.k = k;
}

public int getMaxK(int num) {
if (queue.size() >= k) {
Integer lastNum = queue.poll();
int refCount = tree.get(lastNum);
if (refCount <= 0) {
tree.remove(lastNum);
} else {
tree.put(lastNum, refCount - 1);
}

}

if (tree.containsKey(num)) {
tree.put(num, tree.get(num) + 1);
} else {
tree.put(num, 0);
}

int maxK = tree.lastKey();
return maxK;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution to the problem in C++.

``````#include <iostream>
#include <queue>
#include <set>

using namespace std;

class MaxInWindow {
private:
queue<int> orderByInput;
multiset<int> orderByValue;
public:
int findMaxInWindow(int windowSize, int value) {
orderByInput.push(value);
orderByValue.insert(value);

if (orderByInput.size() > windowSize) {
orderByValue.erase( orderByInput.front() );
orderByInput.pop();
}

return *orderByValue.rbegin();
}
};

int main(int argc, char* argv[]) {
MaxInWindow mw;
int arr[] = {1, 4, 2, 7, 9, 15, 11, 26, 96, 56, 3, 15, 25};
int i;

for (i = 0; i < 13; i++) {
cout << mw.findMaxInWindow(3, arr[i]) << "\n";
}

return 0;
}``````

Result

``````1
4
4
7
9
15
15
26
96
96
96
56
25``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I changed test case.
[..., 15, 3, 56, ...] -> [..., 56, 3, 15, ...]

My solution to the problem in JavaScript.

``````var orderByInput = [];
var orderByValue = [];

var findMaxInWindow = function (windowSize, value) {
var maxInWindow = orderByValue[0] || value;

orderByInput.push(value);
if (maxInWindow > value) {
orderByValue.push(value);
} else {
orderByValue.splice(0, 0, value);
maxInWindow = value;
}

if (orderByInput.length > windowSize) {
var removeIndex = orderByValue.indexOf( orderByInput.shift() );
orderByValue.splice(removeIndex, 1);
if (removeIndex == 0) {
orderByValue.sort(function(a, b){return b - a});
maxInWindow = orderByValue[0];
}
}

return maxInWindow;
}

var main = function ( ){
var windowSize = 3;
var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 56, 3, 15, 25];

for (var i = 0 ; i < stream.length; i++) {
console.log (i + " ) " + stream[i] +" -  MAX : " + findMaxInWindow(windowSize, stream[i]));
}
}

main();``````

Result:

``````0 ) 1 -  MAX : 1
1 ) 4 -  MAX : 4
2 ) 2 -  MAX : 4
3 ) 7 -  MAX : 7
4 ) 9 -  MAX : 9
5 ) 15 -  MAX : 15
6 ) 11 -  MAX : 15
7 ) 26 -  MAX : 26
8 ) 96 -  MAX : 96
9 ) 56 -  MAX : 96
10 ) 3 -  MAX : 96
11 ) 15 -  MAX : 56
12 ) 25 -  MAX : 25``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the runtime bigO/bigTheta is denoted with respect to both N and K, then the question seems to me to be impossible to satisfy.

imagine stream like this 0, -1 , -2 , -3, ... (keeps going down)

You cannot make both space O(1) and getMax operation O(1).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code:

``````class TS{
int wsize;
queue<int> window;
deque<int> maxRec;

public:
TS(int n): wsize(n){};

int maxElem(int num){
window.push(num);

if (window.size()>wsize)
{
int victim= window.front();
window.pop();
if (victim==maxRec.front())
maxRec.pop_front();
}

while(!maxRec.empty()&&num>maxRec.back())
maxRec.pop_back();

maxRec.push_back(num);

return maxRec.front();
}
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int main()
{
int i=0,max=0;
while(i!=-999)
{
scanf("%d",&i);
if(i>max)
max=i;
}
printf("Max=%d",max);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <deque>
using namespace std;

struct stream{
int key;
int index;
};

int main(){

int k,key,n,i = 0;
stream s;
deque< stream > Q;
cin >> k >> key;

while ( i < k-1 && key != -1 ){
while ( !Q.empty() && key >= Q.back().key )
Q.pop_back();
s.key = key;
s.index = i++;
Q.push_back( s );
cin >> key ;
}

while ( key != -1 ) {
cout<< Q.front().key<<"\n";
cin >> key;
while ( !Q.empty() && key >= Q.back().key )
Q.pop_back();
while ( !Q.empty() && ( Q.front().index <= i- k ) )
Q.pop_front();
s.key = key;
s.index = i++;
Q.push_back( s );
}

return 0;
}``````

This will work in O(N) time and O(k) space and it's taking input one by one .

Comment hidden because of low score. Click to expand.
0
of 0 vote

C# solution.

``````class Program
{
static void Main(string[] args)
{
Console.WriteLine(ln.FindMaxinWindow(1,1));
Console.WriteLine(ln.FindMaxinWindow(2, 2));
Console.WriteLine(ln.FindMaxinWindow(-6, 1));
Console.WriteLine(ln.FindMaxinWindow(33, 3));
Console.WriteLine(ln.FindMaxinWindow(4, 8));
Console.WriteLine(ln.FindMaxinWindow(9, 2));
Console.WriteLine(ln.FindMaxinWindow(8, 2));
Console.WriteLine(ln.FindMaxinWindow(99, 8));
Console.WriteLine(ln.FindMaxinWindow(8, 2));
}

}
{
int bufferCount = 0;
public int FindMaxinWindow(int input, int windowSize)
{
bufferCount++;
if (windowSize <= 0)
return 0;
else if (windowSize > bufferCount)
windowSize = bufferCount;
int tempMax = input;
foreach (var item in buffer)
{
if (windowSize > 0)
{
if (item > tempMax)
tempMax = item;
}
windowSize--;
}
return tempMax;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

create a max heap of size k - O(n) space
insert would be O(logn) time
return max from heap- O(1)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MaxWithinARangeFinder {
private static int k;
private static int[] arr = new int[100];
private static int maxIdx = 1, currIdx;

private static int doFind(int i) {
arr[currIdx] = i; // {10, 9, 52, 13, 53} 2
if(k == 1) return arr[currIdx];
maxIdx = calculateMax(currIdx);
++currIdx;
return maxIdx;
}

private static int calculateMax(int currIdx) {
// 1. check if current max is -1, if so - assign the first element and return
int maxIdxLocal = maxIdx;
if(maxIdx == -1) maxIdxLocal = 0;
else {
// check if prev max is within range
if(currIdx - k < maxIdx) {
// return max of prevMax and currIdx
maxIdxLocal = max(maxIdx, currIdx);
} else {
// prev Max is gone out of the window size, calculate new max
maxIdxLocal = calculateNewMax(currIdx);
}
}
maxIdx = maxIdxLocal;
return maxIdxLocal;
}

private static int max(int maxIdx, int currIdx) {
return (arr[maxIdx] > arr[currIdx]) ? maxIdx : currIdx;
}

private static int calculateNewMax(int currIdx) {
int cnt = k;
int mIdx = currIdx;
while(cnt > 0) {
if(arr[currIdx] > arr[mIdx]) mIdx = currIdx;
--currIdx;
--cnt;
}
return mIdx;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello. In order to solve this problem we can use a queue implemented on two stacks with additional operation getMax() defined both on queue and stack. In that case amortized query time will be O(1).

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.

### 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.