Skip to content

Leetcode Question: Best time to buy and sell stock III

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis:

The idea is from dynamic programming, the max profit at day i is the max profit before day i + max profit after day i. So there is one loop O(n) to compute the max profit before each each day and another loop O(n) to get the final max profit by compute the max profit after each day reversely and combine the “before day” max profit.Let’s take an example:
prices[ ] =  1,2,4,2,5,7,2,4,9(1) we compute the forward max profit and save it.  Forward max profit means for each day i, we want to know the max profit we can make no later than this day. Note that we only need to consider 1 transaction:
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8

(2) Now what we need is two transactions rather than one, easily we can see from the price list, if we are required exact 2 transactions, we must finish one transaction at some day i, and do the 2nd transaction after that. The max profit is the sum of max profit before day i and after day i. Day i might be every day in the price list, so there is a loop in the code.
Similar to the step(1), but in a reverse order, from the last day -1 to first, we already have the max profit before day i, mp[i], and we can compute the max profit every time for i to n-1 days (n is the number of days), similar to step(1).

e.g.
max_profit = mp[i] + mprofit

i
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 6 + (9-4) = 11     (2nd trans. : buy at $4 sell at $9)

i
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 6+ (9-2) = 13    (2nd trans. : buy at $2 sell at $9)

i
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 6+ (9-2) = 13  (max profit after day i not change)

……

i
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 13

The final max profit =13

(If you see the case that sell and buy on the same day, this is equal to the case that only 1 transaction. So the “at most 2 transactions” is satisfied)

 

 

src:http://yucoding.blogspot.com/2012/12/leetcode-question-10-best-time-to-buy.html

Advertisements

Longest Consecutive Sequence

Longest Consecutive Sequence
Total Accepted: 2702 Total Submissions: 10637

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

	public static int longestConsecutive(int[] num) {
	     if(num.length == 1 || num.length == 0){
	    	 return num.length; 
	     }
    	 HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
    	 
    	 for(int i=0; i<num.length; i++){
    		 h.put(num[i],1);
    	 }
    	 int res = Integer.MIN_VALUE;
    	 
    	 int j = 0;
    	 while( j<num.length ){
    		 int max = 0;
    		 int m = num[j];
    		 int n = num[j]+1;
    		 
    		 while(h.keySet().contains(m)){
    			 h.remove(m);
    		 
    			 m--;
    			 max ++;
    		 }
    		 
    		 while(h.keySet().contains(n)){
    			 h.remove(n);
    	 
    			 n++;
    			 max ++;
    		 }
    		 
    		 if(max > res){
    			 res = max;
    		 }
    		 j++;
    	 }
    	 return res;
	  }


Maximum Subarray

Two things need to be pay attention to here.

  • If all the elements in an array are negative, we have to return the largest one
  • If the current sum is negative we need to update it to zero

 


 public int maxSubArray(int[] A) {
         if(A.length == 0 || A == null){
	          return 0;
	      }
	       
	       if(A.length == 1){
	           return A[0];
	       }
	    
	      int curSum = 0;
	      int max = A[0];
	      
	      for(int i=0; i<A.length ; i++){
	          curSum += A[i];
	          //the order of the following cannot be reversed, otherwise we cannot pass the test cases where 
	          // all the numbers are negative
	          if(curSum > max){
	              max = curSum;
	          }
	          if(curSum < 0){
	              curSum = 0;
	         } 
	      }
	      return max;
    }

Leetcode questions

Dynamic Programming
Edit Distance
Maximum Subarray
Minimum Path Sum
Unique Paths
Unique Paths II
Longest Palindromic Substring
Interleaving String
Triangle
Distinct Subsequences
Decode Ways
Palindrome Partitioning II
Maximal Rectangle
Recursion
N-Queens
N-Queens II
Balanced Binary Tree
Binary Tree Inorder Traversal
Binary Tree Maximum Path Sum
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree
Flatten Binary Tree to Linked List
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Path Sum
Permutations
Permutations II
Populating Next Right Pointers in Each Node
Pow(x, n)
Same Tree
Subsets
Sum Root to Leaf Numbers
Swap Nodes in Pairs
Symmetric Tree
Valid Palindrome
Validate Binary Search Tree
Restore IP Addresses
Combinations
Interleaving String (dp is the best)
Combination Sum II
Letter Combinations of a Phone Numbers
Word Search
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Generate Parentheses
Surrounded Regions (runtime error)
Palindrome Partitioning
Combination Sum
Sudoku Solver
Unique Binary Search Trees II
Binary Search
Search Insert Position
Search a 2D Matrix
Search for a Range
Search in Rotated Sorted Array
Sqrt(x)
Sequence
Container With Most Water
Count and Say
First Missing Positive
Implement strStr()
Jump Game
Jump Game II
Length of Last Word
Longest Common Prefix
Longest Substring Without Repeating Characters
Merge Sorted Array
Palindrome Number
Plus One
Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array II
Remove Element
Reverse Integer
Search in Rotated Sorted Array II
Sort Colors
Two Sum
3Sum
3Sum Closest
4Sum
Add Binary
Longest Palindromic Substring
Next Permutation
Longest Valid Parentheses
Climbing Stairs
Permutation Sequence
Simplify Path
String to Integer (atoi)
Minimum Window Substring
Longest Consecutive Sequence
Trapping Rain Water
Valid Number
Linked List
Add Two Numbers
Convert Sorted List to Binary Search Tree
Merge Two Sorted Lists
Partition List
Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Remove Nth Node From End of List
Reverse Linked List II
Reverse Nodes in k-Group
Rotate List
Swap Nodes in Pairs
Stack
Binary Tree Inorder Traversal
Binary Tree Level Order Traversal II
Valid Parentheses
Queue
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Populating Next Right Pointers in Each Node II
Symmetric Tree
Surrounded Regions
Word Ladder
Tree
Balanced Binary Tree
Binary Tree Inorder Traversal
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Binary Tree Maximum Path Sum
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree
Flatten Binary Tree to Linked List
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Path Sum
Same Tree
Sum Root to Leaf Numbers
Symmetric Tree
Validate Binary Search Tree

Bit Manipulation Cheat Sheet

Here is a post I found which is interesting and useful for preparing interview questions related with bit manipulation. This is also beneficial for me to prepare for the up-coming computer system midterm…

Original Post: http://allaboutalgorithms.wordpress.com/tag/bit-manipulation/
1. Swap 2 variables without using a temporary variable.

One of the classic silly interview questions that mostly test if you have heard about this problem before. One should point out that there is practically no need for this trick nowadays, this is because most modern compilers will automatically get rid of temp variables for you when you use the normal swapping with a temporary variable. In fact, using an XOR swap can be slower because it is not the expected by the optimizing compilers, and there are severe parallelism problems associated with it.

Another issue is that the XOR swap will cause the variables to be set to zeros when they are the same, so you have to make an extra check and it ended up not being too simple.

Here is the XOR swap:

void xorSwap (int *x, int *y)
{
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}

2. Use a bitmap to represent boolean arrays

When you have an boolean array where each element is either true or false, a good space optimization is to use a bit array to represent you data and use bitmask to work with it. Not only will this allow you to shrink the required space to 1/8 of the original, you can also access your data faster by taking advantage of the CPU’s ability to manipulate multiple bits at the same time. For example, you can count the number of true values in your bit mask 32 or 64 per CPU cycle. (Population count algorithms)

How do we quickly operate on individual bits on a value? For simplicity I will use a single byte “char” as the example to illustrate the basic idea of bit masking. Note though most integers are 4 bytes each.

int a = 0x0010100 //value= 20, boolean={false, false, false, true, false, true, false, false}

2.1 Checking a bit with the bitwise AND

To check whether the fifth boolean value is true is the same as checking wether the 5th bit is 0 or 1, we can do the following.

int bitmask5 = 0x00010000 // create a bit mask with the fifth bit set to 1,value in decimal = 16
int result = a & bitmask5 // using AND to check the 5th bit of our array,if it is 0,result will be 0,else it will be something else.
if (!result) // if your language treat 0 as false you can directly use it as a boolean, otherwise you can use if (result != 0)
do things if the bit is set, if the fifth boolean is true
else
do things if the bit is set, if the fifth boolean is false

2.2 Setting a bit to 1 with the bitwise OR

Setting the 4th boolean to 1 to represent a true value with the following code

int bitmask = 0x00001000 //make a bitmask with the 4th bit set to 1, others set to false, you can set multiple bit to true if you use a bit mask with multiple 1s
int a = a | bitmask //set the bits in the original bitmap to 1 with the bit mask.

2.3 Clearing a bit to 0

Clear the 3rd bit with the following

int bitmask = 0x00000100 //Make a bit mask with the bit you want to clear set to 1
int bitmask = ~bitmask // 0x11111011,using the bitwise not to reverse the mask(make sure you use the bitwise NOT(~) instead of the logical NOT(!))
int a = a & bitmask //using AND and the reversed mask to set the 3rd bit to zero and clear it

2.3 Inverting a bit

If you don’t care what a bit is but only want to flip it, you can use an XOR operation

Flip the 3rd bit:

int bitmask = 0x00000100
int a = a ^ bitmask // 0x00010100 ^ 0x00000100 = 0x00010000 = 16

Flip the 2rd bit:

int bitmask = 0x00000010
int a = a ^ bitmask // 0x00010000 ^ 0x00000010 = 0x00010010 = 18

Making the bit masks, and other considerations

Always be careful about overflows and signed-ness of your value using bit manipulation. For example, bit shift operator “>>” will cause the bit to drop off in case of an overflow. Also, some language(C) requires you handle the signed integers in inverted notation yourself, while others (Java) will handle this for you.

You can create the bit mask by writing a method to generate them using the bit shift operator “>>”, though it may be faster to save the values in memory because they wont take up a lot of space. Another way is to make them into constants, if you are dealing with 32 bit integers you will need 32 of those, if you are dealing with 64 bit integers, you need 64.

const int bitmask1 = 0x00000001
const int bitmask2 = 0x00000010
const int bitmask3 = 0x00000100


const int bitmask8 = 0x10000000

Lastly, a cheat sheet:

BIT OPERATIONS CHEAT SHEET
———————————————————
SET NTH BIT TO 1 : value = value | bitmapN
SET NTH BIT TO 0 : value = value & ~bitmapN
INVERT NTH BIT : value = value ^ bitmapN
QUERY NTH BIT : boolean isset = (value & bitmapN != 0)
DIVIDE BY 2^n : value = value << n // careful about OVERFLOW MULTIPLY BY 2^N : value = value >> n // careful about OVERFLOW
INVERT ALL BITS: value = ~value
LEAST SIGNIFICANT SET BIT : lsb = value & – value
———————————————————

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

int l1 = word1.length();
		 int l2 = word2.length();
		 if(l1 == l2 && l2==0){
		     return 0;
		 }
		 if(l1 == 0)    return l2;
		 if(l2 == 0)    return l1;
		 //Here we need a matrix larger than the original one
		 //Since in the matrix, we start from [1][1], but in the two strings, we start from
		 //char index at i-1 and j-1(0,0);
		 int[][] m = new int[l1+1][l2+1];
		 
		 m[0][0] = 0;
		 
		 for(int i=1; i<=l2; i++){
			 m[0][i] = i;
		} 
		 for(int j=1; j<=l1; j++){
			 m[j][0] = j;
		 }
		 
		 for(int i=1; i <= l1; i++ ){
			 for(int j=1; j <= l2; j++ ){
				 if(word1.charAt(i-1) == word2.charAt(j-1)){
					 m[i][j] = m[i-1][j-1]; 
				 }
				 else{
					 m[i][j] = Math.min(Math.min(m[i-1][j-1], m[i][j-1]),m[i-1][j]) + 1;
				 }
			 
			 }
			 
		 }
	        return m[l1][l2];
	 }

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

public static HashSet<String> get(int n) {
        HashSet<String> result = new HashSet<String>();
        if(n == 0){
            result.add("");
            return result;
        }
        for(String sub:generateParenthesis(n-1)){
            for(int j=0; j<sub.length();j++){
            	if(sub.charAt(j) == '('){
            		String newformedString = insert(j, sub, "()");
                    result.add(newformedString);
            	}
            }
            result.add("()" + sub);
        }
        
        
        return result;
        
    }
    
    
    public static String insert(int pos, String s, String pare){
        String s1 = s.substring(0,pos+1);
        String s2 = s.substring(pos+1);
        return s1+pare+s2;
    }