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;
}
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;
}
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
//The question is equivalent to the following:
// Find i and j that maximizes Aj – Ai, where i < j
//The question is equivalent to the following:
//Find i and j that maximizes Aj – Ai, where i < j
//Brute and Force method O(n^2)
static int maxProfit(int[] prices){
if(prices == null) return 0;
int diff = 0;
for(int i=0;i<prices.length -1 ; i++){
for(int j = i+1; j< prices.length; j++){
if(prices[j] - prices[i] > diff){
diff = prices[j] - prices[i];
}
}
}
return diff;
}
//Efficient way O(n)
static int maxPricesDiff(int [] prices){
int buy = 0;
int sell = 0;
int min = 0;
int maxdiff = 0;
for(int i=0; i<prices.length; i++){
if(prices[i] < prices[min]){
min = i;
}
int diff = prices[i] - prices[min];
if(diff > maxdiff){
buy = min;
sell = i;
maxdiff = diff;
}
}
return maxdiff;
}
// Long Subtraction — Given two arrays A, B,
// each contains elements of digits, return an array of A – B.
// Your machine can only do calculation of less than 20.
// eg. A = [1,2,5,7,5];
// B = [3,4,8,9];
// A – B = [9,0,8,6];
static int[] sub(int[] a, int[] b){
int[] c = new int[a.length];
int i = a.length - 1;
int j = b.length - 1;
int borrow = 0;
while( j >= 0){
if(a[i] >= b[j]){
c[i] = a[i] - b[j] - borrow;
borrow = 0;
}
else{
c[i] = a[i] - b[j] - borrow + 10;
borrow = 1;
}
i--; j--;
}
while(i >= 0){
if(borrow == 1){
c[i] = a[i] - borrow;
borrow = 0;
}
else{
c[i] = a[i] ;
}
i--;
}
return c;
}
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
The things need to be noticed here:
1. Index is not 0 based
2. If we want more efficient algorithm, we need to first sort the array first.
Here is the code I wrote:
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
if(numbers.length < 2){
return result;
}
for(int i=0; i<numbers.length-1; i++){
for(int j=i+1; j<numbers.length;j++){
if(numbers[j] == target-numbers[i]){
result[0] = i+1;
result[1] = j+1;
return result;
}
}
}
return result;
}
Emma's coding practice 