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


  • 5
    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) {
    
    }
    

  • 0
    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.


  • 1
    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.


  • 1
    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
    

  • 1
    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];
    }

Log in to reply
 

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