## Facebook Interview Question for Java Developers

• 0

Country: United States

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

``````public static int maxProfit(int[] prices) {
int[] max = new int[prices.length];
max[prices.length - 1] = prices[prices.length - 1];

for (int i = prices.length - 2; i >= 0; i--)
max[i] = (prices[i] < max[i + 1] ? max[i + 1] : prices[i]);

int res = 0;
for (int i = 0; i < prices.length; i++)
if (max[i] > prices[i])
res += max[i] - prices[i];
return res;
}``````

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

My O(nlongn) solution (Worse case O(n^2), best case O(n)):
My approach:
1. Find the max value in the array, we will buy all the stocks before the max and sell it at the max price.
2. Treat all elements after the max as a new array and repeat the steps until there is one or no element left.

``````public int maxProfit(int[] prices) {
return maxProfit(prices,0,prices.length);
}
public int maxProfit(int[] prices, int left, int right){
if(right-left <=1)return 0;

int[] cum = new int[prices.length];
int maxPoint = -1;
int maxPointIndex = -1;

for(int i=left;i<right;i++){
cum[i]+=prices[i];
if(i>left)cum[i]+=cum[i-1];
if(maxPoint<=prices[i]){
maxPoint = prices[i];
maxIndex = i;
}
}
return (maxIndex-left+1)*maxPoint-cum[maxIndex]+maxProfit(prices,maxIndex+1,right);
}``````

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

I took a stab at this tonight, to have a nice hour long puzzle to solve. My solution is brute-force, which I think is the only way to do this. I made some key assumptions, as the original question isn't very clear:
1. I can sell multiple times, but each time I sell *ALL* stock accumulated to date is sold. This means, I can "Buy, Buy, Buy, Sell <All>, Buy, Buy, Buy, Sell <All>". This makes things more complicated.
2. I can chose "no-op" for a given day, and neither buy nor sell.
3. All values are int.

``````using System;

namespace Warmups
{
public class StockWarmup
{
public enum Operation { Hold = 0, Buy = 1, Sell = 2 };

/// <summary>
/// Treat the Operation Array as a base-3 number and +1 to it.
/// If the number wraps (all entries 0), then return null marking the end of the sequence.
/// </summary>
/// <remarks>
/// Example of the Base-3 math:
///      = 0 (Hold)
///      = 0 (Hold)
///      = 0 (Hold)
/// Now, +1
///      = 0 (Hold)
///      = 0 (Hold)
/// Now, +1
///      = 2 (Sell)
///      = 0 (Hold)
///      = 0 (Hold)
/// Now, +1
///      = 0 (Hold)  Note: Wrapped, need to carry
///      = 0 (Hold)
/// </remarks>
/// <param name="original"></param>
/// <returns></returns>
public static Operation[] GetNextOperationSequence(Operation[] original)
{
Operation[] newOperations = new Operation[original.Length];
bool carry = true; // Start with this, so the first available digit is bumped.
bool allHold = true; // if all values are 'hold', then we've wrapped and should stop processing
for (int i = 0; i < original.Length; i++)
{
if (carry)
{
if (original[i] == Operation.Hold)
{
carry = false;
}
{
newOperations[i] = Operation.Sell;
carry = false;
}
else if (original[i] == Operation.Sell)
{
newOperations[i] = Operation.Hold;
carry = true;
}
else
throw new InvalidOperationException("Unknown Operation Type");
}
else
{
newOperations[i] = original[i]; // no change. Copy over the field.
}

if (newOperations[i] != Operation.Hold)
allHold = false;
}

return (allHold == true) ? null : newOperations;
}

/// <summary>
/// Problem Statement: Say you have an array for which the ith element is
/// the price of a given stock on day i, you can buy
/// stock at any day, but can only buy once a day, but
/// if you sell the stock, you must sell all of them at once.
/// Maximize Profit
/// </summary>
/// <param name="stockPriceByDay"></param>
/// <returns>
///     First Tuple entry is the max profit found
///     Second item in the tuple is the hold/buy/sell pattern used
/// </returns>
public static (int, Operation[]) MaximizeProfit(int[] stockPriceByDay)
{

// The operation sequence (hold/buy/sell) to try. The empty array defaults
// to "hold" for all values, which is "0" in any base. (Note: Keep in mind
// this array is treated as a giant base-3 number, for calculation purposes).

// The current max profit, and sequence of hold/buy/sell events used to
// calculate that sequence
int maxProfit = 0;

bool keepGoing = true;
while(keepGoing)
{
if (profit > maxProfit)
{
maxProfit = profit;
}

// Get the next periumation of the sequence
keepGoing = false;
}

return (maxProfit, currentMaxProfitSequence);
}

public static int CalculateProfit(int[] stockPriceByDay, Operation[] operationOnEachDay)
{
int profit = 0;
int sharesOwned = 0;

for (int dayNumber = 0; dayNumber < stockPriceByDay.Length; dayNumber++)
{
switch (operationOnEachDay[dayNumber])
{
sharesOwned++;
profit -= stockPriceByDay[dayNumber];
break;
case Operation.Sell:
int currentPrice = stockPriceByDay[dayNumber];
profit += currentPrice * sharesOwned; // Note: Could be negative
sharesOwned = 0;
break;
case Operation.Hold: // No-op
break;
}
}
return profit;
}
}
}``````

As I love to do, I added many tests around this. My test sequences are:

``````using Microsoft.VisualStudio.TestTools.UnitTesting;
using Warmups;
using static Warmups.StockWarmup;

namespace StockTests
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void ProfitCalculatorOneEntry()
{
int[] stocksByDay = { 100 };
Assert.AreEqual(profit, -100);
}

[TestMethod]
public void ProfitCalculatorTwoEntry()
{
int[] stocksByDay = { 100, 200 };
Assert.AreEqual(profit, 100);
}

[TestMethod]
public void ProfitCalculatorThreeEntry()
{
int[] stocksByDay = { 100, 200, 300 };
Assert.AreEqual(profit, 300);
}

[TestMethod]
public void GetNextSequenceOneEntryHold()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold });
Assert.IsTrue(result1.Length == 1);
}

[TestMethod]
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy });
Assert.IsTrue(result1.Length == 1);
Assert.IsTrue(result1 == Operation.Sell);
}

[TestMethod]
public void GetNextSequenceOneEntrySell()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell });
Assert.IsNull(result1);
}

[TestMethod]
public void GetNextSequenceTwoEntryHold()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1 == Operation.Hold);
}
[TestMethod]
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1 == Operation.Sell);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
public void GetNextSequenceTwoEntrySell()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
public void GetNextSequenceThreeSellSellHold()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1 == Operation.Hold);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
public void GetNextSequenceThreeSellSellSell()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Sell });
Assert.IsNull(result1);
}

[TestMethod]
public void MaxProfitTwoEntries()
{
var profitResults = MaximizeProfit(new int[] { 100, 200 });

Assert.IsTrue(profitResults.Item1 == 100);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
}

[TestMethod]
public void MaxProfitTwoEntriesLoseMoney()
{
var profitResults = MaximizeProfit(new int[] { 200, 100 });

Assert.IsTrue(profitResults.Item1 == 0);
Assert.IsTrue(profitResults.Item2 == Operation.Hold);
Assert.IsTrue(profitResults.Item2 == Operation.Hold);
}

[TestMethod]
public void MaxProfitThreeEntries()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 5});

Assert.IsTrue(profitResults.Item1 == 6);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
}

[TestMethod]
public void MaxProfitFourEntriesStaggeredSell()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 1, 2 });

Assert.IsTrue(profitResults.Item1 == 3);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
}
}
}``````

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

I needed a puzzle this evening, so I took a stab at this. Some assumptions:
1. I can buy/sell/no-op on any given day.
2. I can sell multiple times, but must sell ALL stock at each time. So in a 4 day block, for example, I could: Buy / Sell / Buy / Sell

``````using System;

namespace Warmups
{
public class StockWarmup
{
public enum Operation { Hold = 0, Buy = 1, Sell = 2 };

/// <summary>
/// Treat the Operation Array as a base-3 number and +1 to it.
/// If the number wraps (all entries 0), then return null marking the end of the sequence.
/// </summary>
/// <remarks>
/// Example of the Base-3 math:
///      = 0 (Hold)
///      = 0 (Hold)
///      = 0 (Hold)
/// Now, +1
///      = 0 (Hold)
///      = 0 (Hold)
/// Now, +1
///      = 2 (Sell)
///      = 0 (Hold)
///      = 0 (Hold)
/// Now, +1
///      = 0 (Hold)  Note: Wrapped, need to carry
///      = 0 (Hold)
/// </remarks>
/// <param name="original"></param>
/// <returns></returns>
public static Operation[] GetNextOperationSequence(Operation[] original)
{
Operation[] newOperations = new Operation[original.Length];
bool carry = true; // Start with this, so the first available digit is bumped.
bool allHold = true; // if all values are 'hold', then we've wrapped and should stop processing
for (int i = 0; i < original.Length; i++)
{
if (carry)
{
if (original[i] == Operation.Hold)
{
carry = false;
}
{
newOperations[i] = Operation.Sell;
carry = false;
}
else if (original[i] == Operation.Sell)
{
newOperations[i] = Operation.Hold;
carry = true;
}
else
throw new InvalidOperationException("Unknown Operation Type");
}
else
{
newOperations[i] = original[i]; // no change. Copy over the field.
}

if (newOperations[i] != Operation.Hold)
allHold = false;
}

return (allHold == true) ? null : newOperations;
}

/// <summary>
/// Problem Statement: Say you have an array for which the ith element is
/// the price of a given stock on day i, you can buy
/// stock at any day, but can only buy once a day, but
/// if you sell the stock, you must sell all of them at once.
/// Maximize Profit
/// </summary>
/// <param name="stockPriceByDay"></param>
/// <returns>
///     First Tuple entry is the max profit found
///     Second item in the tuple is the hold/buy/sell pattern used
/// </returns>
public static (int, Operation[]) MaximizeProfit(int[] stockPriceByDay)
{

// The operation sequence (hold/buy/sell) to try. The empty array defaults
// to "hold" for all values, which is "0" in any base. (Note: Keep in mind
// this array is treated as a giant base-3 number, for calculation purposes).

// The current max profit, and sequence of hold/buy/sell events used to
// calculate that sequence
int maxProfit = 0;

bool keepGoing = true;
while(keepGoing)
{
if (profit > maxProfit)
{
maxProfit = profit;
}

// Get the next periumation of the sequence
keepGoing = false;
}

return (maxProfit, currentMaxProfitSequence);
}

public static int CalculateProfit(int[] stockPriceByDay, Operation[] operationOnEachDay)
{
int profit = 0;
int sharesOwned = 0;

for (int dayNumber = 0; dayNumber < stockPriceByDay.Length; dayNumber++)
{
switch (operationOnEachDay[dayNumber])
{
sharesOwned++;
profit -= stockPriceByDay[dayNumber];
break;
case Operation.Sell:
int currentPrice = stockPriceByDay[dayNumber];
profit += currentPrice * sharesOwned; // Note: Could be negative
sharesOwned = 0;
break;
case Operation.Hold: // No-op
break;
}
}
return profit;
}
}
}``````

Tests are here:

``````using Microsoft.VisualStudio.TestTools.UnitTesting;
using Warmups;
using static Warmups.StockWarmup;

namespace StockTests
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void ProfitCalculatorOneEntry()
{
int[] stocksByDay = { 100 };
Assert.AreEqual(profit, -100);
}

[TestMethod]
public void ProfitCalculatorTwoEntry()
{
int[] stocksByDay = { 100, 200 };
Assert.AreEqual(profit, 100);
}

[TestMethod]
public void ProfitCalculatorThreeEntry()
{
int[] stocksByDay = { 100, 200, 300 };
Assert.AreEqual(profit, 300);
}

[TestMethod]
public void GetNextSequenceOneEntryHold()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold });
Assert.IsTrue(result1.Length == 1);
}

[TestMethod]
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy });
Assert.IsTrue(result1.Length == 1);
Assert.IsTrue(result1 == Operation.Sell);
}

[TestMethod]
public void GetNextSequenceOneEntrySell()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell });
Assert.IsNull(result1);
}

[TestMethod]
public void GetNextSequenceTwoEntryHold()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1 == Operation.Hold);
}
[TestMethod]
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1 == Operation.Sell);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
public void GetNextSequenceTwoEntrySell()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
public void GetNextSequenceThreeSellSellHold()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1 == Operation.Hold);
Assert.IsTrue(result1 == Operation.Hold);
}

[TestMethod]
public void GetNextSequenceThreeSellSellSell()
{
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Sell });
Assert.IsNull(result1);
}

[TestMethod]
public void MaxProfitTwoEntries()
{
var profitResults = MaximizeProfit(new int[] { 100, 200 });

Assert.IsTrue(profitResults.Item1 == 100);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
}

[TestMethod]
public void MaxProfitTwoEntriesLoseMoney()
{
var profitResults = MaximizeProfit(new int[] { 200, 100 });

Assert.IsTrue(profitResults.Item1 == 0);
Assert.IsTrue(profitResults.Item2 == Operation.Hold);
Assert.IsTrue(profitResults.Item2 == Operation.Hold);
}

[TestMethod]
public void MaxProfitThreeEntries()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 5});

Assert.IsTrue(profitResults.Item1 == 6);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
}

[TestMethod]
public void MaxProfitFourEntriesStaggeredSell()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 1, 2 });

Assert.IsTrue(profitResults.Item1 == 3);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
Assert.IsTrue(profitResults.Item2 == Operation.Sell);
}
}
}``````

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

You can put all the stock prices in a maxHeap with index as value. So the root is day when the price is max. Now, start to first day and keep buying until you hit the root idx. When you hit root idx, sell and also pop(). Then continue until you reach last day. That would do it in O(nlogn).

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

My solution in PHP (recursive function)

``````<?php
\$stock = array(100, 180, 260, 310, 40, 535, 695);

getMaxProfit(\$stock,array(),0,\$max,\$op);

echo "Max Profit is : ".\$max;
if(is_array(\$op)) echo " With the following actions : ".implode(",",\$op);

function getMaxProfit(\$stock,\$operations,\$currentDay,&\$maxReached,&\$bestOperations){
if(\$currentDay == sizeof(\$stock)){
\$profit = calculateProfit(\$stock,\$operations);
if(!\$maxReached) \$maxReached=0;
if(\$profit <> null && \$profit > \$maxReached){
\$maxReached=\$profit;
\$bestOperations=\$operations;
}
return;
}

for(\$day=\$currentDay;\$day<sizeof(\$stock);\$day++){
foreach(\$operationsArray as \$operationValue){
\$operations[\$day]= \$operationValue;
getMaxProfit(\$stock,\$operations,\$day+1,\$maxReached,\$bestOperations);
}
}
}

function calculateProfit(\$stock,\$operations){
\$profit=0;
\$bought=0;
for(\$i=0;\$i<sizeof(\$stock);\$i++){
if(key_exists(\$i,\$operations))
{
\$bought=1;
\$profit-=\$stock[\$i];
}
elseif(\$operations[\$i] == 'Sell'){
if(\$bought){
\$profit+=\$stock[\$i];
\$bought=0;
}
else return null;
}
}
}
return \$profit;
}
?>``````

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

I don't believe I could write so much code in an interview. Here's my solution in 50 lines:

``````class Solution {

public static void main(String[] args) {
int[] array = {4,4,7,4,4,9,1,8};

Solution s = new Solution ();
int profit = s.maxProfit(array);
System.out.println("p="+profit);
}

int maxProfit(int[] prices) {

int peakDay = prices.length-1;
int peakPrice=prices[peakDay];

Transaction maxT = new Transaction();

for(int now=peakDay-1; now>=0 ; now--)
{
int currentPrice = prices[now];
if(currentPrice<peakPrice)
{
Transaction t = new Transaction();
for(int start = 0; start<peakDay; start++)
{
if (prices[start]<peakPrice)
{
t.profit += peakPrice-prices[start];
}
}

if(t.profit>maxT.profit)
{
maxT = t;
}
}

peakDay = now;
peakPrice = currentPrice;
}

return maxT.profit;
}
}

class Transaction {
int profit;

Transaction(){
profit = 0;
}

}``````

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

``````public static int maxProfit(int[] a) {
int[] m = new int[a.length];
m[a.length - 1] = a[a.length - 1];

for (int i = a.length - 2; i >= 0; i--)
m[i] = (a[i] < m[i + 1] ? m[i + 1] : a[i]);

int r = 0;
for (int i = 0; i < a.length; i++)
if (m[i] > a[i])
r += m[i] - a[i];
return r;
}``````

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

``````public static int maxProfit(int[] prices) {
int[] max = new int[prices.length];
max[prices.length - 1] = prices[prices.length - 1];

for (int i = prices.length - 2; i >= 0; i--)
max[i] = (prices[i] < max[i + 1] ? max[i + 1] : prices[i]);

int res = 0;
for (int i = 0; i < prices.length; i++)
if (max[i] > prices[i])
res += max[i] - prices[i];
return res;
}``````

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

If I say maxProfit(n) the max profile we can achieve in day n, and we hold 0 stock on day n.
and maxOneTimeProfit(i,j) is the max profit we can buy between i and j but sell only happened on day j.
then maxProfit(n+1) would be:
int max = 0;
for each i in 1..n:
max = math.max(max, maxProfit(i)+ maxOneTimeProfit(i..n+1))
maxProfit(n+1) = max;

``````static int maxOneTimeProfit(int[] prices, int i, int j)
{
int sum = 0;
for (int k=i; k<j; k++)
{
sum+= Math.max(prices[j] - prices[k], 0); // only buy at k if prices[j] > prices[k]
}
}
public static int maxProfit(int[] prices) {
int[] f = new int[prices.length];
f = 0;
for (int j=1; j<prices.length; j++)
{
int max = 0;
for (int i=0; i<j; i++)
{
max = Math.max(f[k]+maxOneTimeProfit(prices, i, j), max);
}
}
return f[prices.length-1];
}``````

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

Simple and easy!

``````public int maxProfit(int[] prices)
{
Stack<Integer> stack = new Stack<Integer>();
int result =0;
for(int i=prices.length-1; i>=0; iii)
{
if(stack.isEmpty() || stack.peek() < prices[i])
{
stack.push(prices[i]);
}
}
for(int i =0; i<prices.length; i++)
{
if(prices[i] == stack.peek())
stack.pop();
else
{
result+= stack.peek() - prices[i];
}
}
return result;
}``````

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

sdV

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

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

public class StockMaxProfit {
public static void main(String[] args){
int[] testcase1 = {1,2,10,9,100,6,20};

int actual = maxProfit(testcase1);
System.out.println("test " + Arrays.toString(testcase1) + " actual " + actual);
}

public static int maxProfit(int[] price){
int n = price.length;
int outlook[] = new int[n];
Arrays.fill(outlook, 0);

outlook[n-1] = price[n-1];
for (int i = n-2; i >= 0; i--){
if (price[i] > outlook[i+1]){
outlook[i] = price[i];
} else {
outlook[i] = outlook[i+1];
}
}

System.out.println(Arrays.toString(outlook));

int s = 0;
for (int i = 0; i < n; i++){
if (price[i] < outlook[i]){
s += (outlook[i] - price[i]);
}
}

return s;
}
}``````

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.