## Microsoft Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

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

First of all, we can calculate the cumulative sum of changes and then the answer for maxGain would be the two elements with maximum difference in which the bigger element is on the right of the smaller one.

So we could easily iterate over the array from left to right, update the minimum value we've seen so far, and each time update the best answer we could have.

Here's my code for 1.a an d 1.b
O(N)

``````pair<int,int> maxGain(vector<int> changes)
{
vector<int> stock;
int N=changes.size();
stock.push_back(changes);
for (int i=1;i<N;i++)
stock.push_back(stock[stock.size()-1]+changes[i]);
//tmp is the index of minimum stock we've seen so far
int tmp=0,startDay=0,endDay=N-1;

for (int i=1;i<N;i++){
if (stock[i]-stock[tmp] > stock[endDay]-stock[startDay]){ //for maxLost change it to <
startDay = tmp;
endDay = i;
}
if (stock[i]<stock[tmp])//for maxLost, change it to >
tmp = i;
}

return make_pair(startDay,endDay);
}``````

for 1.c, we need to know the minimum value among the last K elements we've seen so far. I used the multiset to storing the values, and if the size of the multiset reaches to K+1, we should remove the first invalid element.In this way we always have the last K valid elements in the multiset.
Also, each time the first element of multiset is the minimum one that we are looking for.
O(N*logK)

``````pair<int,int> maxGainWithLimit(vector<int> changes,int K)
{
vector<int> stock;
int N=changes.size();
stock.push_back(changes);
for (int i=1;i<N;i++)
stock.push_back(stock[stock.size()-1]+changes[i]);
//multiset for keeping possible repeated values
multiset< pair<int,int> > st;
int tmp=0, startDay=0,endDay=N-1;

st.insert(make_pair(stock,0));

for (int i=1;i<N;i++){

//first element of set is the minimum of stocks which are not far from K elements

if ( stock[i] - (*st.begin()).first > stock[endDay] - stock[startDay] ) {
startDay = (*st.begin()).second;
endDay = i;
}

st.insert(make_pair(stock[i],i));
if (st.size()==K+1){
st.erase(make_pair(stock[i-K],i-K));
}
}

return make_pair(startDay,endDay);

}``````

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

1a. We can use largest sum contiguous subarray algorithm like kadane .

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

How about this, 1c.Here the limitation is that minimum number is among the last k-1 elements.So using the windowing approach , we maintain the list of last k-1 minimum elements and then calculate profit by considering the current element as the selling point .We slide the window to the right and then recalculate the profit using the next element as the current element.

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

``````int main(int argc, char** argv) {

const int len = 9;
int data[len] = {-1, -6, 10, 2, -5, 20, 5, -10, 6};

int best_value = 0;
int sum = 0;
int best_start = 0;
int best_end = 0;
int start = 0;

for(int i = 0; i < len; i++)
{
sum = sum + data[i];
if(sum < 0)
{
start = i;
sum = 0;
}
else if(sum > best_value)
{
best_value = sum;
best_start = start;
best_end = i;
}
}
cout << best_start << " " << best_end << " " << best_value;

return 0;
}``````

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

here is an O(N) solution based on finding max and min elements in k window:

``````int maxProfit(vector<int> &nums, int k = 100) {
int n = nums.size();
if (n < 2) return 0;
vector<int> prices{ nums };
for (int j = 1; j < n; ++j) prices.push_back(prices.back() + nums[j]);
int maxpro = 0, maxbuy = 0, maxsell = 0, buy = 0, sell = 0, pro = 0;
deque<int> selltime;
for (int i = 0; i < n; ++i) {
while (!selltime.empty() && nums[selltime.front()] <= nums[i]) selltime.pop_front();
while (!selltime.empty() && nums[i] >= nums[selltime.back()]) selltime.pop_back();
selltime.push_back(i);
if (maxpro < pro) maxpro = pro;
}
return maxpro;
}``````

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

The solution is :
Try to find the non-decreasing runs of array. When such a run is found (lets say [start,end], then set currBestBuy = a[start], currBestSell = a[end].
Also if this is not the first run, then check whether (currBestSell - bestBuy) > (currBestSell- currBestBuy) and if so that update the bestSell = currBestSell.
When the entire array is iterated over entirely the bestbuy and bestSell will store the best buy price and best sell price respectively.

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

Q.1b: solution: to find out the maximum loss just reverse the logic so that you take worstBuy and worstSell price, by finding non-increasing runs of array and then comparing with them with the any last found non-increasing runs of array.

Q.1c: In this case just consider the non-decreasing runs of array of length k only.

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.