Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Pretty much its finding sequential periods where is consecutively going up
List<Tupple<int, int>> findMaxProfit(List<int> stockvalues) {
List<Tupple<int, int>> transactions = new List<Tupple<int, int>>()
int currentStart = 0;
for (int i=1; i < stockvalues.length; i++) {
if(stockvalues[i-1] > stockvalues[i]) {
if(currentStart != i-1) // If its not the same data
{
transactions.add(new Tuple<int, int>(currentStart, i-1))
}
currentStart = i;
}
}
// Handling when even the last day was still going up
if(stockvalues[currentstart] < stockvalues[stockvalues.length - 1]) {
transactions.add(new Tuple<int, int>(currentstart, stockvalues.length - 1)
}
return transactions;
}
public static int findProfit(List<Integer> transactions){
int profit = 0;
if(transactions==null || transactions.size()<2){
return profit;
}
int buyPrice = transactions.get(0);
for(int currentPrice : transactions){
if(currentPrice>buyPrice){
profit = profit + (currentPrice - buyPrice);
buyPrice = currentPrice;
}else {
buyPrice = currentPrice;
}
}
return profit;
}
public static int findProfit(List<Integer> transactions){
int profit = 0;
if(transactions==null || transactions.size()<2){
return profit;
}
int buyPrice = transactions.get(0);
for(int currentPrice : transactions){
if(currentPrice>buyPrice){
profit = profit + (currentPrice - buyPrice);
buyPrice = currentPrice;
}else {
buyPrice = currentPrice;
}
}
return profit;
}
public static int findProfit(List<Integer> transactions){
int profit = 0;
if(transactions==null || transactions.size()<2){
return profit;
}
int buyPrice = transactions.get(0);
for(int currentPrice : transactions){
if(currentPrice>buyPrice){
profit = profit + (currentPrice - buyPrice);
buyPrice = currentPrice;
}else {
buyPrice = currentPrice;
}
}
return profit;
}
public static int findProfit(List<Integer> transactions){
int profit = 0;
if(transactions==null || transactions.size()<2){
return profit;
}
int buyPrice = transactions.get(0);
for(int currentPrice : transactions){
if(currentPrice>buyPrice){
profit = profit + (currentPrice - buyPrice);
buyPrice = currentPrice;
}else {
buyPrice = currentPrice;
}
}
return profit;
}
l = [7,5,6,3,5,5,6,4,6,7,1]
import random
#l= [random.randrange(1,10) for l in range(10)]
ser=[]
#i=0
i=0
s=[l[i]]
mp=0 #stores highest possible profit for whole session
lp=0 #stores profit for a single series
print ('i=%d l[i]=%d lp=%d mp=%d' %(i,l[i],lp, mp))
#0< i < len -1
while i<len(l)-1:
i+=1
if l[i-1]<=l[i]:
s.append(l[i])
lp+=l[i]-l[i-1]
mp+=l[i]-l[i-1]
else:
ser.append((lp,s))
s=[l[i]]
lp=0
print ('i=%d l[i]=%d lp=%d mp=%d' %(i,l[i],lp, mp))
#i=len-1
ser.append((lp,s))
print ('i=%d l[i]=%d lp=%d mp=%d' %(i,l[i],lp, mp))
print(ser) #list of buys series with local profits
def maxProfit(arr):
''' Return an array of (buy_day, sell_day) tuples that maximize profit '''
if len(arr) == 0 or len(arr) == 1:
return []
l = []
p = 0
q = 1
in_position = False
while True:
if arr[q]>arr[q-1]:
if in_position:
q+=1
else:
in_position = True
q+=1
else:
if in_position:
in_position = False
l += [(p,q-1)]
p = q
q += 1
if q == len(arr):
if in_position:
l += [(p,q-1)]
in_position = False
break
return l
def maxProfit(arr):
''' Return an array of (buy_day, sell_day) tuples that maximize profit '''
if len(arr) == 0 or len(arr) == 1:
return []
l = []
p = 0
q = 1
in_position = False
while True:
if arr[q]>arr[q-1]:
if in_position:
q+=1
else:
in_position = True
q+=1
else:
if in_position:
in_position = False
l += [(p,q-1)]
p = q
q += 1
if q == len(arr):
if in_position:
l += [(p,q-1)]
in_position = False
break
return l
public class FindBestStockTransaction {
static class Result {
public Result(List<Integer> transactions, int sum) {
this.transactions = transactions;
this.sum = sum;
}
public Result(int startPrice, int endPrice, int sum) {
this.transactions = new LinkedList<Integer>();
this.transactions.add(startPrice);
this.transactions.add(endPrice);
this.sum = sum;
}
List<Integer> transactions;
int sum;
@Override
public String toString() {
return "Result [transactions=" + transactions + ", sum=" + sum + "]";
}
}
static public Result find(int[] prices, int start) {
if (prices == null || prices.length - start < 2) {
return null;
}
if (prices.length - start == 2) {
if (prices[start] >= prices[start + 1]) {
return null;
}
return new Result(prices[start], prices[start + 1], prices[start + 1] - prices[start]);
}
Result bestResult = null;
for (int end = start; end < prices.length; end++) {
Result firstResult = null;
if (end > start && prices[end] > prices[start]) {
firstResult = new Result(prices[start], prices[end], prices[end] - prices[start]);
}
Result nextResult = find(prices, end + 1);
Result newResult = combineResults(firstResult, nextResult);
if (bestResult == null || newResult != null && bestResult.sum < newResult.sum) {
bestResult = newResult;
}
}
return bestResult;
}
private static Result combineResults(Result result1, Result result2) {
if (result1 == null && result2 == null) {
return null;
}
if (result1 == null) {
return result2;
}
if (result2 == null) {
return result1;
}
result2.transactions.add(0, result1.transactions.get(0));
result2.transactions.add(1, result1.transactions.get(1));
return new Result(result2.transactions, result1.sum + result2.sum);
}
}
You can see it as a path:
(Formatting is giving me a hard time.. but you know what i mean)
- Poozmak February 22, 2020If the last transaction is BUY - as long as its going up you keep the stock and the moment it starts going down (arr[i] < arr[i-1]) you have to SELL (on the previous day - i-1)
If the last transaction is SELL - as long as its going down you wait and the moment it starts going up again (arr[i] > arr[i-1]) you BUY at the cheapest price (on the previous day - i-1)
An edge case is on the last day - if you still hold the stock and the last day is higher than the day before - you just sell it.