[FB phone interview] Best time to Buy and Sell stock follow up - with transaction fee


  • 8
    E

    I got the FB phone interview today, but failed in the end. The first question is easy, simple buy and sell stock, but the followup seems very difficult to solve, I think it requires a DP solution, but can't figure it out during 10 minutes. Got rejected in the end.

    If you can do unlimited times of buy and sell (can only hold one stock at a time), but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take.

    public int maxProfit(int[] prices, int fee) {
    
    }
    

  • 1
    E

    Sample input { 1, 3, 7, 5, 10, 3 } fee = 3.

    If you do two transactions, the total profit is (7 - 1) - 3 + (10 - 5) - 3 = 5.
    If you only to one transaction, the total profit is (10 - 1) - 3 = 6.
    So obviously, fee matters, it will impact the number of transactions you need to make.


  • 0
    M

    You have to check two cases,
    case 1: The original problem ( but add the fees to each transaction).
    case 2:transaction: largest j_val - i_val where i<j and add fees.
    return max of both cases.


  • 4
    B

    I think it's very similar to LC 188 (Best Time to Buy and Sell Stock IV). I modified this solution a little and the code below should work.

    int maxProfit(vector<int>& prices, int fee) {
    	 if (prices.empty())  return 0;
    	 int n = prices.size(), k = n - 1; //there are at most n-1 transactions
    
    	 vector<vector<int>> t(k + 1, vector<int>(n, 0));
    	 for (int i = 1; i <= k; i++){
    		 int tmpMax = -prices[0];   
    		 for (int j = 1; j<n; j++){
    			 t[i][j] = max(t[i][j - 1], prices[j] + tmpMax - fee); // keep the stock vs. sell the stock
    			 tmpMax = max(tmpMax, t[i - 1][j - 1] - prices[j]);
    		 }
    	 }
    	 return t[k][n - 1];
     }
    

  • 0
    D

    This will work! Let me if this can be done better.

    public class BuySellwithFee {
    	
    	 public static int maxProfit(int[] prices, int fee) {
    	        int maxprofit = 0;
    	        int trans=0;
    	        int prev=0;
    	       
    	        for (int i = 1; i < prices.length; i++) {
    	            if (prices[i] > prices[i - 1]) {
    	                 
    	                 
    	                maxprofit += prices[i] - prices[i - 1];
    	                if(prev+1==i){
    	                    
    	                   prev++;
    	                   
    	                }
    	                else if(prev+1 !=i) {
    	                trans++;
    	                 prev=i;
    	                }
    	                if(trans==0) trans++;
    	            }
    	        }
    	        return maxprofit==0?maxprofit:maxprofit-trans*fee;
    	    }
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
       //int [] a = {9,8,7,1,2,3,0,20};
       int [] a= {2,3,4,1,8,0,9};
        System.out.println(maxProfit(a,3));
    	}
    
    }
    
    
    

  • 0

    @badri2 I don't think this is correct. Consider an example, [9,8,7,1,2], fee = 3. You will get -1.


  • 0
    D

    @jedihy Thanks mate. I update. Let me know if you find any flaw


  • 0
    
    
    public int stock(int[] arr,int tx){
    	if(arr == null || arr.length < 2){
    		throw new IllegalArgumentException();
    	}
    	int[][] dp = new int[2][arr.length];
    	for(int i = 1; i <arr.length; i++){
    		for(int j = 0; j < i; j++){
    			if(arr[i] - tx > arr[j]){//try selling.
    				int prev = Math.max(dp[0][j], dp[1][j]);
    				dp[0][i] = Math.max(arr[i] - tx - arr[j] + prev,dp[0][i]);
    			}
    			
    		}
    		dp[1][i] = Math.max(dp[1][i - 1],dp[0][i - 1]);
    	}
    	return Math.max(dp[0][arr.length - 1],dp[1][arr.length - 1]);
    }

  • 0
    E

    @DotProduct Thanks for sharing, but it is not working at least with the example the author gave as { 1, 3, 7, 5, 10, 3 } fee = 3, answer should be 6, instead of 5.


  • 0

    @eric108 Agree. Fee must be concerned during each iteration or that will be an incorrect rrecurrence relation.


  • 2
    W

    C++ solution modifying Buy Sell Stock 4
    We just need to get the max profit from [1..n-1] transactions. Another difference is that we need to subtract a fee every time we want to sell a stock.

    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<assert.h>
    
    using namespace std;
    
    int maxProfit(vector<int>& prices, int fee) {
            int rt = 0, k = prices.size()-1;
            vector<long> sells(1+k, 0), buys(1+k, (long)INT_MIN);
            for(int p: prices) {
                for(int i = k; i > 0; i--) {
                    sells[i] = max(sells[i], p + buys[i] - fee);
                    buys[i] = max(buys[i], sells[i-1] - p);
                }
            }
            return *max_element(sells.begin(), sells.end());
        }
    
    int main() {
    	vector<int> arr1 = {1, 3, 7, 5, 10, 3}; int fee1 = 3;
    	vector<int> arr2 = {9,8,7,1,2}; int fee2 = 3;
    	vector<int> arr3 = {1,4,6,2,8,3,10,14}; int fee3 = 3; //4 trans --> 10, 3 trans --> 2+3+8, 2 trans --> 4+8=12, 1 tran --> 10
    	assert(maxProfit(arr1, fee1) == 6);
    	assert(maxProfit(arr2, fee2) == 0);
    	assert(maxProfit(arr3, fee3) == 13);
    	return 0;
    }
    
    

  • 1
    A

    Here is my python solution:

    def maxProfit(k, prices, fee):
        """
        :type k: int
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        n = len(prices)
        if n < 2:
            return 0
            
        local_max = [[0] * (k + 1) for i in range(n)]
        global_max = [[0] * (k + 1) for i in range(n)]
        
        for i in range(1, n):
            diff = prices[i] - prices[i - 1]
            for j in range(1, k + 1):
                local_max[i][j] = max(global_max[i - 1][j - 1] + max(diff, 0),
                                      local_max[i - 1][j] + diff)
                global_max[i][j] = max(local_max[i][j] - fee,
                                       global_max[i - 1][j])
        
        return global_max[-1][-1]
    
    assert maxProfit(8, [1, 3, 7, 5, 10, 3], 3) == 6
    

  • 6
    D

    follow the state machine way of thinking,

    def maxProfit(prices, fee):
        if not prices: return 0
        
        cash, hold = 0, -prices[0]
        max_cash = 0
        for i in range(1, len(prices)):
            (cash, hold) = (max(cash, hold+prices[i]-fee),
                            max(hold, cash-prices[i]))
            max_cash = max(max_cash, cash)
            
        return max_cash
    
    # Tests
    prices, fee = [1, 3, 7, 5, 10, 3], 3
    assert maxProfit(prices, fee) == 6
    
    prices, fee = [9, 8, 7, 1, 2], 3
    assert maxProfit(prices, fee) == 0
    
    prices, fee = [1, 4, 6, 2, 8, 3, 10, 14], 3
    assert maxProfit(prices, fee) == 13
    

  • 0
    H

    This can be solved by dynamic programming on all possible buying/selling periods (low/high pairs or intervals as refered in code below). The time complexity is O(n^2).

    public static int maxProfit(int [] prices, int txnFee) {
            Interval[] intervals = getAllBuyingOptions(prices);
            return maxProfit(intervals, txnFee);
        }
    
        public static int maxProfit(Interval [] intervals, int txnFee) {
            int[] dp = new int[intervals.length + 1];
    
            dp[0] = 0;
    
            for(int i = 0; i < intervals.length; i++) {
                int currentMax = 0;
                int maxij;
                for (int j = 0; j <= i; j++) {
                    maxij = dp[j] + intervals[i].high - intervals[j].low - txnFee;
                    if (maxij > currentMax) {
                        currentMax = maxij;
                    }
                }
    
                dp[i + 1] = Math.max(currentMax, intervals[i].high - intervals[i].low - txnFee);
            }
    
            return dp[intervals.length];
        }
    
        public static Interval[] getAllBuyingOptions(int[] prices) {
            List<Interval> intervals = new ArrayList<>();
            boolean hold = false;
            int buy = -1;
            for(int i = 0; i < prices.length - 1; i++) {
                if (hold && prices[i + 1] < prices[i]) {
                    hold = false;
                    Interval interval = new Interval();
                    interval.low = buy;
                    interval.high = prices[i];
                    intervals.add(interval);
                    buy = -1;
                } else if (!hold && prices[i + 1] > prices[i]) {
                    hold = true;
                    buy = prices[i];
                }
            }
    
            if (buy > 0 && prices[prices.length - 1] > buy) {
                Interval interval = new Interval();
                interval.low = buy;
                interval.high = prices[prices.length - 1];
                intervals.add(interval);
            }
    
            Interval[] ints = new Interval[(intervals.size())];
            intervals.toArray(ints);
            return ints;
        }
    
        private static class Interval {
            public int low;
            public int high;
        }
    

  • 0
    M
    public int maxProfit(int[] prices, int fee) {
        int k = prices.length / 2; // maxinum k transactions
        int[] sell = new int[k+1];
        int[] buy = new int[k+1];
        for(int i=0; i<buy.length; i++)  
            buy[i] = Integer.MIN_VALUE;
        for(int p : prices) {  // for each day
            for(int i=k; i>=1; i--) {    
                if (p >=fee) 
                    sell[i] = Math.max(sell[i], buy[i]+ p - fee);
                buy[i] = Math.max(buy[i], sell[i-1] - p);
            }
        }
        return sell[k];
    }

  • 1
    S

    quite difficult question for interview


  • 0
    S

    I wrote this in Python, Kindly let me know if this is useful. I took a cumulative sum of multiple buy and sell and compare it with global max and min stock value

    def max_profit(input,fee):
        min1 = 0
        max1 = -1
        local_val = 0
        print('$$$$$$$$$$$$$$$----',input)
        for i in range(1,len(input)):
            print('Processing...', input[i])
            if (input[i] > input[i-1]):
                local_val = local_val + (input[i] - input[i-1] - fee)
                print('Trade done:{}, buy:{}, sell:{}'.format( local_val, input[i-1],input[i]))
            min1 = min(input[:i+1])
            if input[:i+1].index(min1) < input[:i+1].index(max(input[:i+1])):
                max1 = max(input[:i+1])           
            global_val = max1 - min1 - fee
            print('Min:{}, max:{}, prof:{}'.format(min1,max1,global_val))
            if global_val > local_val:
                local_val = global_val
                print('Global value >Local value: ',local_val)
        if max([local_val, global_val]) > 0:
                print('################################### Max profit:',max([local_val, global_val]) )
        else:
                print('No profit trade can be done!!!!!!!!!!!!!!!!!!')
            
    max_profit([1, 3, 2, 8, 4, 9],2)
    max_profit([1, 3, 7, 5, 10, 3],3)
    max_profit([9,8,7,1,2],3)
    max_profit([20,10,30,50,10,9,8],2)
    

  • 0
    M

    @sha256pki Maybe they wanted to hear your reasoning instead of solving the actual problem.


  • 0
    S

    @Marce666 trade whenever the stock goes up to make a profit. At the same time find out the profit between the local min of stock value and local max of stock value until that point. Whichever profit is greater until a point store the profit in a variable. Do this in each iteration
    Compare the global max versus the accumulated profit from multiple small trades. Max of these two values is the max profit you could make


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.