Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
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.
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;
}
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[0] };
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> buytime;
deque<int> selltime;
for (int i = 0; i < n; ++i) {
while (!buytime.empty() && i - buytime.front() >= k) buytime.pop_front();
while (!buytime.empty() && nums[buytime.front()] >= nums[i]) buytime.pop_front();
while (!buytime.empty() && nums[i] <= nums[buytime.back()]) buytime.pop_back();
buytime.push_back(i);
while (!selltime.empty() && !buytime.empty() && selltime.front() <= buytime.front()) selltime.pop_front();
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);
pro = nums[selltime.front()] - nums[buytime.front()];
if (maxpro < pro) maxpro = pro;
}
return maxpro;
}
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.
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.
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)
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)
- MehrdadAP July 02, 2015