## Facebook Interview Question for Software Engineer / Developers

• 2

Country: United States
Interview Type: In-Person

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

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).

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

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 sell = stockQuoteStream.get(1);
int optSell = 1;
int maxProfit = sell - buy;
for (int j = 1; j < stockQuoteStream.size(); j++) {
for (int k = j; k < stockQuoteStream.size(); k++) {
sell = stockQuoteStream.get(k);
int currProfit = sell - buy;
if (currProfit > maxProfit) {
maxProfit = currProfit;
optSell = k;
}
}
}

}
totalProfit += maxProfit;
stockQuoteStream.remove(optSell);
}
}

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

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
for (t = 0; t < prices.len -1; t++) {
profit = bestSaleAfter[t].price - prices[t]
if profit > 0 { // Omit unprofitable trades
profit: profit,
sellTime: bestSaleAfter[t].time
})
}
}

// Sort to find the very best trades
)

}``````

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

``````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[N];
for (i = 0; i < n_prices; ++i) {
free(arr[i]);
}
free(arr);
return max_profit;
}``````

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

OMG I ALL NOT UNDERSTAND(

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

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``````

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

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);
}``````

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

``````import java.util.Arrays;
import java.util.List;

/**
*
* At each index decide to hold, buy or sell
* maximize profit per unit of stock held
*
*/

static final short BUY = 1;
static final short SELL = -1;
static final short HOLD = 0;

double profit[];
double maxProfit;

maxProfit = 0;
}

public double[] maximize(List<Short> pricesL, short N){
int m = pricesL.size();
Short[] price = pricesL.toArray(new Short);

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;
}

for(int i = 0; i < N; i++){
}

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] = minSinceLastSell[j];
}

minSinceLastSell[j] = price[i];
if(j>0){
profitBeforeLastCycle[j] = profit[j-1];
}

//System.out.println("DEBUG " + x + "\t" + profit[j]);
}
}
}

for(short j = 0; j < N; j++){
double x = maxSinceLastBuy[j] - minSinceLastSell[j];
x = x + profitBeforeLastCycle[j];
if(x > profit[j]){
profit[j] = x;
profitBreakdown[j] = minSinceLastSell[j];
}
}
}

maxProfit = profit;
for(int i = 0; i < N; i++){
if(maxProfit > profit[i]){
maxProfit = profit[i];
}
}

return profit;
}

public static void main(String[] args){

short a[] = {86, 98, 92, 68, 67, 56, 52, 96};

for(int i = 0; i < 8; 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)));
System.out.println("MAX PROFIT " + wrapper.maxProfit);
System.out.println("DEBUG " + Arrays.toString(res));
}
}``````

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

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?

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

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!

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

Exactly, eugene. The problem is missing something...

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

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

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

@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.

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

@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.

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

@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?

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

@eugene.yarovoi
Yes. And limit of N is the max number of transaction you can make.

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

int MaxProfit(int dailyStockPrices[], int length) {
int min = dailyStockPrices;
int maxProfit = 0;
int profit =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;
sellDate = i;
}
}
return maxProfit;
}

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.