*i*

^{th}element is the price of a given stock on day

*i*.

*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:

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

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

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

**Dynamic Programming**

**Recursion**

**Binary Search**

**Sequence**

**Linked List**

**Stack**

**Queue**

**Tree**

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

———————————————————

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

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