Interview Note - Examples
6 minutes read
Tags:
Single Number
XOR features: a ^ b = c a ^ c = b b ^ c = a a ^ 0 = a a ^ a = 0 (a ^ b) ^ c = a ^ (b ^ c)
- I: all the numbers appear twice except one XOR all the numbers, and the result is the one
- II: all the numbers appear three times except one
Use a
int[32]to store each bit, if the number of this bit can be mod by 3, we set it as 0, otherwise we set it as 1. - III: all the numbers appear twice except two
XOR all the numbers so we can get the
twoby XOR. Since these two elements are not the same, there is at least one bit that different. We find thisdifferentposition and XOR all the elements which have 1 on positiondifferent, the result is one of the two. Finally, we XOR the found one with XOR-edtwo, we can get another one.
Majority Number
- I: find the number appears more than half
Since it is a strict majority number, we only need to maintain a variable
resultand acounter. Initially, when thecounterfaces with a different number, minus one of counter and change theresultto this new number, otherwise we only need to add 1 to thecounter. And finally, theresultwe maintained is the result. (We need to do another pass to make sure this number is the one we are looking for) - II: find the number appears more than 1/3 Similar with I, we maintain two variables and two counters so that we can get most appeared two numbers. And then we put these two numbers back to the array to find out which one appears more than 1/3. (We can't use counter to find out, because counters have minus operation during the traversal)
- III: find the number appears more than 1/k
We maintain a
HashMap<number, counter>. Since if majority, each k different numbers should have more than one element. When we get k entries in the map, we remove entries which values are 1. Finally, find the entry that have highest value(count), that key should be the majority number. In this way, we can implement this inO(n)time andO(k)extra space.
public class Solution {
public int majorityNumber(ArrayList<Integer> nums, int k) {
if(nums == null || nums.size() == 0) {
return -1;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int num : nums) {
if(map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
// if there are k entries, check if there are any entries that
// its value == 1, that is not satisfied with "more than 1/k"
if(map.size() == k) {
Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry<Integer, Integer> entry = iter.next();
if(entry.getValue() - 1 == 0) {
// can't use: map.remove(entry.getKey());
// above wrong code would lead the iter can't find its next !!!
iter.remove();
} else {
map.put(entry.getKey(), entry.getValue() - 1);
}
}
} else {
map.put(num, 1);
}
}
}
// find the one that have highest value(count), that key should be the majority number
int value = 0;
int result = -1;
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue() > value) {
value = entry.getValue();
result = entry.getKey();
}
}
return result;
}
}
Best Time to Buy and Sale Stock
- I: one time operation
Maintain two variables,
localandglobal. Thelocal = Math.max(prices[i] - prices[i - 1] + local, 0), means when we sell the stock on dayi, our max profit is this much. Theglobalis the max of itself andlocal. - II: any times operation
Our goal is to find all the increasing segments in the array. So if we face an increasing, we add the difference to the
maxProfit. - III: two times operation (--> k times)
Maintain two
int[3], one islocal[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff), wherediff = prices[i + 1] - prices[i]. This variable means at day i, we can get the max profit by j operation(s). The first half means we sell the stock on day j instead of onglobal[j - 1], the second half means we sell it on day j anyway. And theglobal[j] = Math.max(local[j], global[j])as before.
Follow Up: k operations
public class Solution {
public int maxProfit(int[] prices) {
return max(prices, 2);
}
// k: k times transactions
public int max(int[] prices, int k) {
int len = prices.length;
if(len == 0) {
return 0;
}
int[][] local = new int[len][k+1];
int[][] global = new int[len][k+1];
for(int i=1; i<len; i++) {
int diff = prices[i] - prices[i-1];
for(int j=1; j<=k; j++) {
/*
* local[i][j]: max profit till i day, j transactions, where there is transaction happening on i day
* global[i][j]: max profit across i days, j transactions
*/
local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff,0), local[i-1][j]+diff);
global[i][j] = Math.max(global[i-1][j], local[i][j]);
}
}
return global[len-1][k];
}
}
Maximum Subarray
public class Solution {
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
public int maxSubArray(ArrayList<Integer> nums, int k) {
// write your code
if(nums == null || nums.size() == 0 || k < 1) {
return Integer.MIN_VALUE;
}
int[][] dp = new int[k][nums.size()];
/* init the dp[][]:
eg. -7,1,-1,-3,-4,-10,2,-100,-51,-12
after first for loop:
-7 0 0 0 0 0 0 0 0 0
0 -6 0 0 0 0 0 0 0 0
0 0 -7 0 0 0 0 0 0 0
0 0 0 -10 0 0 0 0 0 0
after second for loop:
-7 1 0 -3 -4 -10 2 -98 -51 -12
0 -6 0 0 0 0 0 0 0 0
0 0 -7 0 0 0 0 0 0 0
0 0 0 -10 0 0 0 0 0 0
*/
int sum = 0;
for(int i = 0; i < k; i++) {
sum += nums.get(i);
dp[i][i] = sum;
}
for(int i = 1; i < nums.size(); i++) {
dp[0][i] = Math.max(nums.get(i), dp[0][i - 1] + nums.get(i));
}
for(int i = 1; i < k; i++) {
for(int j = i + 1; j < nums.size(); j++) {
int curMax = dp[i][j - 1] + nums.get(j);
for(int m = i - 1; m < j; m++) {
if(dp[i - 1][m] + nums.get(j) > curMax) {
curMax = dp[i - 1][m] + nums.get(j);
}
}
dp[i][j] = curMax;
}
}
/*
after the main loops:
-7 1 0 -3 -4 -10 2 -98 -51 -12
0 -6 0 -2 -3 -9 3 -97 -49 -10
0 0 -7 -3 -4 -10 2 -97 -48 -9
0 0 0 -10 -7 -13 -1 -98 -49 -10
*/
int result = Integer.MIN_VALUE;
for(int i = k - 1; i < nums.size(); i++) {
if(dp[k - 1][i] > result) {
result = dp[k - 1][i];
}
}
return result;
}
}