Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Assumptions: Generate N transactions (distinct, not duplicate) with buy-sell pairs such that pos of buy is before pos of sell in the quote stream.
The following solution is naive O(N*n^2) but can be improved to O(N*nlogn) by sorting the stream array wrt stock values:
static int findMaxProfit(ArrayList<Integer> stockQuoteStream, int n) {
int totalProfit = 0;
for (int i = 0; i < n; i++) {
int buy = stockQuoteStream.get(0);
int optBuy = 0;
int sell = stockQuoteStream.get(1);
int optSell = 1;
int maxProfit = sell - buy;
for (int j = 1; j < stockQuoteStream.size(); j++) {
if (buy > stockQuoteStream.get(j)) {
buy = stockQuoteStream.get(j);
for (int k = j; k < stockQuoteStream.size(); k++) {
sell = stockQuoteStream.get(k);
int currProfit = sell - buy;
if (currProfit > maxProfit) {
maxProfit = currProfit;
optSell = k;
optBuy = j;
}
}
}
}
totalProfit += maxProfit;
stockQuoteStream.remove(optSell);
stockQuoteStream.remove(optBuy);
}
return totalProfit;
}
Assuming no duplicate transactions, the key is to find, for each time t, the max price after t, so you can sell at that time.
O(nlog(n)). I think it could be improved by only sorting the first maxTrades trades, instead of all of them.
bestTrades(prices, maxTrades) {
// Build table of best selling point after time t
bestSaleAfter = []
int maxPrice = -Infinity;
int maxT = -1
for (t = prices.len - 1; t >= 0; t--) {
bestSaleAfter[t] = { price: maxPrice, time: maxT }
if prices[t] > maxPrice {
maxPrice = prices[t]
maxT = t
}
}
// Build list of the best trades possible when buying at time t
optimalTrades = []
for (t = 0; t < prices.len -1; t++) {
profit = bestSaleAfter[t].price - prices[t]
if profit > 0 { // Omit unprofitable trades
optimalTrades.push({
profit: profit,
buyTime: t,
sellTime: bestSaleAfter[t].time
})
}
}
// Sort to find the very best trades
optimalTrades.sort(
lambda(tradeA, tradeB) : tradeA.profit < tradeB.profit
)
return optimalTrades[0:min(maxTrades, optimalTrades.len)]
}
int optimal_trades(int *prices, int n_prices, int N)
{
int i, j, n;
int **arr;
int max_profit;
arr = (int **)malloc(n_prices * sizeof(int**));
for (i = 0; i < n_prices; ++i) {
arr[i] = (int *)malloc((N+1)*sizeof(int));
memset(arr[i], 0, (N+1)*sizeof(int));
}
arr[n_prices][N];
for (n = 1; n <= N; ++n) {
for (i = n_prices - 1; i >= 0; ++i) {
for (j = i + 1; j < n_prices; ++j) {
if (arr[i][n] < prices[j] - prices[i]) {
arr[i][n] = prices[j] - prices[i];
}
if (arr[i][n] < prices[j] - prices[i] + arr[j][n-1]) {
arr[i][n] = prices[j] - prices[i] + arr[j][n-1];
}
}
}
}
max_profit = arr[0][N];
for (i = 0; i < n_prices; ++i) {
free(arr[i]);
}
free(arr);
return max_profit;
}
there is a m*n*n solution
// n size of A, m #transactions
int maxprofit(int* A, int n, int m)
{
vector<int> profits(n+1, 0);
for(int i=0; i<m; i++)
{
vector<int> nprofits(n+1, 0);
int maxprofit = 0;
for(int j = 0; j < n; j++)
{
int max = A[j];
int maxrightprofit = 0;
for(int k = j-1; k>=0; k--)
{
if (A[k] > max)
{
max = A[k];
}
int rightprofit = max - A[k];
if (rightprofit > maxrightprofit)
{
maxrightprofit = rightprofit;
}
int profit= profits[k] + maxrightprofit;
if (profit > maxprofit)
{
maxprofit = profit;
}
}
nprofits[j+1] = maxprofit;
}
profits = nprofits;
}
return profits[n];
}
test case:
int A[] = {1, 4, 2, 5, 3, 6 };
int p1 = s.maxprofit(A, 6, 1); // 5
int p2 = s.maxprofit(A, 6, 2); // 7
int p3 = s.maxprofit(A, 6, 3); // 9
using dynamic programming language.
int Dp(std::vector<int> & v, int k) {
v.insert(v.begin(), 0);
k += 1;
int n = v.size();
std::vector<int> dp(n, 0);
std::vector<int> pre(n, 0);
int rs = 0;
for (int i = 1; i < k; i++) {
int max = INT_MIN;
for (int j = k; j < n; j++) {
dp[j] = std::max(dp[j - 1], pre[j - 1]) + v[j];
pre[j - 1] = max;
max = std::max(max, dp[j]);
rs = std::max(rs, dp[j]);
}
pre[n - 1] = max;
}
return rs;
}
int MaxProfit(std::vector<int> & price, int n) {
std::vector<int> v;
for (int i = 1; i < price.size(); i++) {
v.push_back(price[i] - price[i - 1]);
}
return Dp(v, n);
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
*
* At each index decide to hold, buy or sell
* maximize profit per unit of stock held
*
*/
public class DayTraderWithPerfectInformation {
static final short BUY = 1;
static final short SELL = -1;
static final short HOLD = 0;
double profit[];
double maxProfit;
public DayTraderWithPerfectInformation() {
maxProfit = 0;
}
// use atmost N trades
public double[] maximize(List<Short> pricesL, short N){
int m = pricesL.size();
Short[] price = pricesL.toArray(new Short[1]);
profit = new double[N];
double profitBeforeLastCycle[] = new double[N];
for(int i = 0; i < N; i++){
profitBeforeLastCycle[i] = 0;
}
double profitBreakdown[][] = new double[N][];
for(int i = 0; i < N; i++){
profitBreakdown[i] = new double[2*(i+1)];
}
double minSinceLastSell[] = new double[N];
for(int i = 0; i < N; i++){
minSinceLastSell[i] = price[0];
}
double maxSinceLastBuy[] = new double[N];
for(int i = 0; i < N; i++){
maxSinceLastBuy[i] = price[0];
}
for(int i = 0; i < N; i++){
profit[i] = 0;
}
for(short i = 1; i < m; i++){
for(short j = 0; j < N; j++){
if(price[i] < minSinceLastSell[j]){
// have a new min can take profit now
// profit from sale before taking new min?
double x = maxSinceLastBuy[j] - minSinceLastSell[j];
x = x + profitBeforeLastCycle[j];
if(x > profit[j]){
profit[j] = x;
profitBreakdown[j][0] = minSinceLastSell[j];
profitBreakdown[j][1] = maxSinceLastBuy[j];
}
minSinceLastSell[j] = price[i];
maxSinceLastBuy[j] = 0;
if(j>0){
profitBeforeLastCycle[j] = profit[j-1];
}
//System.out.println("DEBUG " + x + "\t" + profit[j]);
} else if(price[i] > maxSinceLastBuy[j]){
maxSinceLastBuy[j] = price[i];
}
}
}
for(short j = 0; j < N; j++){
if(maxSinceLastBuy[j] > minSinceLastSell[j]){
double x = maxSinceLastBuy[j] - minSinceLastSell[j];
x = x + profitBeforeLastCycle[j];
if(x > profit[j]){
profit[j] = x;
profitBreakdown[j][0] = minSinceLastSell[j];
profitBreakdown[j][1] = maxSinceLastBuy[j];
}
}
}
maxProfit = profit[0];
for(int i = 0; i < N; i++){
if(maxProfit > profit[i]){
maxProfit = profit[i];
}
}
return profit;
}
public static void main(String[] args){
DayTraderWithPerfectInformation wrapper = new DayTraderWithPerfectInformation();
short a[] = {86, 98, 92, 68, 67, 56, 52, 96};
List<Short> testcase = new LinkedList<Short>();
for(int i = 0; i < 8; i++){
//testcase.add( (short) (Math.random()*50 + 50));
testcase.add(a[i]);
}
//double[] res = wrapper.maximize(testcase, (short) 1);
double[] res = wrapper.maximize(testcase, (short) 2);
System.out.println("quotes:\t" + Arrays.toString(testcase.toArray(new Short[1])));
System.out.println("MAX PROFIT " + wrapper.maxProfit);
System.out.println("DEBUG " + Arrays.toString(res));
}
}
You can make N transactions. Why wouldn't you just solve this problem for N=1 and then execute that transaction N times? If you've found the optimal transaction, you should do that transaction as many times as possible. Is there some sort of limitation where you may only buy or sell one share per unit of time?
I also think a greedy algorithm will give the optimal solution. So, the only thing to find out the optimal solution for one transaction will be to find a pair of values from the stock stream with the largest difference and the pos of the smaller should be lesser than the pos of the larger in the stream array since they are time-sorted (assuming I need to buy a stock before to sell it back later). Any other specific requirement is not clear from the description!
Not sure but is it like this:
Given: 10, 20, 15, 17, 22 and N=2 then
T1 = <10,22> T2 = <15,17> satisfying time constraints i.e., buy(10) before sell(20) int the stream and similarly for T2.
Profit = 12 + 2 = 14 which is the max considering the constraints
@Eugene:
The same transaction cannot be repeated 'n' times because the price of the stock is varying at every instant. A globally optimal solution (MaxStockPrice - MinStockPrice) (subject to condition that occurence of MaxStockPrice is after occurence of MinStockPrice) is not an answer here. In fact, the question asks about how you can continually buy and sell stocks to maximize profit over all time intervals.
@eugene.yarovoi
I think there is a constrains that transactions should be independent, i.e., one should not be able to buy before he sells.
It's an interview question on leetcode.
@nanny: So you can only buy one share and then you have to sell it before buying the next one, and then you have a limit of N such transactions?
int MaxProfit(int dailyStockPrices[], int length) {
int min = dailyStockPrices[0];
int maxProfit = 0;
int profit =0;
int buyDate = 0;
int minDate = 0;
int sellDate = 1;
int i=0;
for(i=1; i < length; i++)
{
if(dailyStockPrices[i] < min)
{
min = dailyStockPrices[i];
minDate = i;
}
else
{
profit = dailyStockPrices[i] - min;
}
if(profit > maxProfit)
{
maxProfit = profit;
buyDate = minDate;
sellDate = i;
}
}
return maxProfit;
}
This could be viewed as a weighted interval scheduling problem. The different pairs of buy and sell points are the intervals and the weight is the difference (profit). Getting all possible pairs would be O(n^2).
- ram October 02, 2012