Amazon Interview Question
SDE1sCountry: India
By solving this you have essentially solved the problem of finding the maximum sum sub-array!
O(n) time and space complexity. Maintain an array (lets say dp[]), where dp[i] holds the profit made if we decide to sell the share on i'th day. Also keep a variable "min" which holds the minimum price of the share seen so far. Final answer is max(dp[]).
#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
#define MAX 10e+7
int
find_max(vector<int> &ip) {
int max = ip[0];
for(int i=1; i<ip.size(); i++) {
if(ip[i] > max) {
max = ip[i];
}
}
return max;
}
int
calculate(vector<int> &ip) {
vector<int> dp(ip.size(), -1);
int min = ip[1];
dp[0] = 0;
for(int i=1; i<ip.size(); i++) {
if(ip[i] > min) {
dp[i] = ip[i] - min;
} else {
dp[i] = 0;
if(ip[i] < min) {
min = ip[i];
}
}
}
return find_max(dp);
}
int main() {
int N;
cin >> N;
vector<int> x(N);
int i=0;
while(N--) {
cin >> x[i++];
}
cout << calculate(x) << endl;
}
I assume the money I have with me to invest in stocks. Now that I already know how the stocks fluctuated during the given time period, all I have to do is find the time period where the stock prices increased the most and buy and sell accordingly.
public int PickStocks(int[] input)
{
const int moneyIHave = 100;
int maxDiff = 0;
for (var i = 0; i < input.Length;i++)
{
for (var j = i+1; j < input.Length; j++)
{
if(input[j] - input[i] > maxDiff)
{
maxDiff = input[j] - input[i];
}
}
}
if(maxDiff == 0)
return 0;
else
{
return moneyIHave * maxDiff;
}
}
Given array "price":
double logProfits = 0;
for ( int i = 0; i < max; i++ ) {
if ( price[i] > price[i-1] && price[i] > price[i+1] ) {
sell[i] = true;
logProfits += log(price[i]);
}
if ( price[i] < price[i-1] && price[i] < price[i+1] ) {
buy[i] = true;
logProfits -= log(price[i]);
}
}
profit = initialInvestment*exp(logProfits);
Assume n elements in array.
1. Sort the array from min to max.
2. Subtract the value at array[0] from array[n-1].
3. If profit is > 0, sum it and continue.
4. Subtract array[1] from array [n-2] and so on until profit is 0 or negative.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StockSeller
{
class Program
{
static void Main(string[] args)
{
int[] a = { 5, 2, 8, 9, 1 };
int start = a[0], end = a[1];
for (int i = 0; i < a.Length; i++)
{
if (a[i] <= start)
start = a[i];
else if (a[i] > end)
end = a[i];
}
Console.WriteLine(string .Format("start={0} end={1} diff={2}", start, end, end - start));
Console.ReadLine();
}
}
}
void find(int a[], int size){
int min = a[0];
int max = a[0];
int min_index = 0;
int max_index =0;
int i = 0;
int diff = 0;
int max_index_result = 0;
int min_index_result = 0;
for(i=1;i<size;i++){
if(min>a[i]){
min_index = i;
min = a[i];
}
else if(max<a[i]){
max_index = i;
max = a[i];
}
if(diff< max - min && min_index<max_index){
diff = max - min;
min_index_result = min_index;
max_index_result = max_index;
}
}
printf("%d - %d",a[min_index_result],a[max_index_result]);
getch();
return 0;
}
public static void getMaxProfit(int[] A)
{
int len = A.length;
int buy = 0;
int sell = 1;
int tmpBuy = 0;
int tmpSell = 0;
for(int i = 1; i < len; i++)
{
if (A[tmpBuy] > A[i])
{
tmpBuy = i;
}
if (i > buy && A[tmpSell] < A[i])
{
tmpSell = i;
}
if (tmpBuy < tmpSell)
{
buy = tmpBuy;
sell = tmpSell;
}
}
System.out.println("Buying Price :" + A[buy] + " Selling Price :" + A[sell]);
System.out.println("PROFIT :" + (A[sell] - A[buy]));
}
{{public void findStockRange(int[] input)
{
int tempMinPos=0, tempMaxPos=0;
int minPos=0, maxpos=0;
int diff=Integer.MIN_VALUE;
for(int i=1;i<input.length;i++)
{
if(input[tempMinPos]>input[i])
{
tempMinPos=i;
}else if (input[tempMaxPos]<input[i] && i>tempMinPos)
{
tempMaxPos=i;
if((input[tempMaxPos]-input[tempMinPos]) >diff)
{
diff= (input[tempMaxPos]-input[tempMinPos]);
minPos=tempMinPos;
maxpos=tempMaxPos;
}
}
}
System.out.println("Buy :" + minPos);
System.out.println("Sell :" + maxpos);
System.out.println("profit "+ diff);
}}}
You tried to use the code formatting {, but forgot one.
Here is the formatted code. I ran it through an online formatter.
public void findStockRange(int[] input)
{
int tempMinPos=0, tempMaxPos=0;
int minPos=0, maxpos=0;
int diff=Integer.MIN_VALUE;
for(int i=1;i<input.length;i++)
{
if(input[tempMinPos]>input[i])
{
tempMinPos=i;
}else if (input[tempMaxPos]<input[i] && i>tempMinPos)
{
tempMaxPos=i;
if((input[tempMaxPos]-input[tempMinPos]) >diff)
{
diff= (input[tempMaxPos]-input[tempMinPos]);
minPos=tempMinPos;
maxpos=tempMaxPos;
}
}
}
System.out.println("Buy :" + minPos);
System.out.println("Sell :" + maxpos);
System.out.println("profit "+ diff);
Satyajeet can u also describe your logic please.
- ANONU March 27, 2013