First Bad Version

Problem:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        return BS(0, n);
    }
    int BS(int low, int high) {
        int mid = low + (high-low)/2;
        if (!isBadVersion(mid - 1) && isBadVersion(mid)) {
            return mid;
        } else if (isBadVersion(mid - 1)) {
            return BS(low, mid - 1);
        } else {
            return BS(mid + 1, high);
        }
    }
};

========== Another attempt ====

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {

        int left = 1, right = n;
        int mid;
     
        while (left <= right) {
            mid = left + (right - left)/2;
            if (isBadVersion(mid)) {
                if (mid > left && !isBadVersion(mid - 1)) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else {
                if (mid < right && isBadVersion(mid + 1)) {
                    return mid + 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return isBadVersion(1) ? 1: n;
    }
};

============  Efficient one ========

int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

Moves Zero

Problem:

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        int iter = 0;
        for (int zero_iter = 0; zero_iter < size; zero_iter++) {
            if (nums[zero_iter] != 0) {
                nums[iter++] = nums[zero_iter];
                if (iter - 1 == zero_iter) {
                    // Iter == zero_iter means base case: no zero till now.
                    continue;
                }
                nums[zero_iter] = 0;
            }
        }
        return;
    }
};

===== Another =====

void moveZeroes(vector<int>& nums) {
        int count = 0, iter = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                nums[iter++] = nums[i];
            }
        }
        for (int i = iter; i < nums.size(); i++) {
            nums[i] = 0;
        }
        return;
    }

Sum of Two integers

Problem:

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Credits:
Special thanks to @fujiaozhu for adding this problem and creating all test cases.

Solution:

class Solution {
public:
    int getSum(int a, int b) {
        // Simpler solution.
        /*
        int sum = a, carry = 0;
        while (b) {
            carry = sum & b;
            sum ^= b;      // xor operator take care of summing except 1 ^ 1.
            carry <<= 1;   // All carries will be adding up in next position.
            b = carry;     // So, make it new number to add.
        }
        return sum;
        */
        // Another Solution.
        int size = (8 * sizeof(int)), ans = 0, a_i, b_i, carry = 0, loc;
        for (int i = 0; i < size; i++) {
            loc = 1 << i;
            a_i = a & loc;
            b_i = b & loc;
            ans ^= a_i ^ b_i ^ carry;
            carry = (a_i & b_i) | (carry & a_i) | (carry & b_i);
            carry <<= 1;
        }
        return ans;
    }
};

Intersection of Two Arrays II

Problem:

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        int size1 = nums1.size(), size2 = nums2.size();
        if (size1 == 0 || size2 == 0) {
            return ans;
        }
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;
        while (i < size1 && j < size2) {
            if (nums1[i] == nums2[j]) {
                ans.push_back(nums1[i]);
                i++; j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};

=============

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

Solution 1, i.e., sorting, would be better since it does not need extra memory.

What if nums1’s size is small compared to num2’s size? Which algorithm is better?

• If two arrays are sorted, we could use binary search, i.e., for each element in the shorter array, search in the longer one. So the overall time complexity is O(nlogm), where n is the length of the shorter array, and m is the length of the longer array. Note that this is better than Solution 1 since the time complexity is O(n + m) in the worst case.

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

• If the two arrays have relatively the same length, we can use external sort to sort out the two arrays in the disk. Then load chunks of each array into the memory and compare, by using the method 1.
• If one array is too short while the other is long, in this case, if memory is limited and nums2 is stored in disk, partition it and send portions of nums2 piece by piece. keep a pointer for nums1 indicating the current position, and it should be working fine~
• Another method is, store the larger array into disk, and for each element in the shorter array, use “Exponential Search” and search in the longer array.

Bulls and Cows

Problem:

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number:  "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number:  "1123"
Friend's guess: "0111"

In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".

You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Solution:

class Solution {
public:
    string getHint(string secret, string guess) {
        string ans;
        int size = secret.size(), bulls = 0, cows = 0;
        if (size == 0) {
            print(ans, 0, 0);
            return ans;
        }
        for (int i = 0; i < size; i++) {
            if (secret[i] == guess[i]) {
                bulls++;
                secret[i] = 'X';
                guess[i] = 'X';
            }
        }
        for (int i = 0; i < size; i++) {
            if (guess[i] != 'X' && secret.find(guess[i]) != string::npos) {
                secret[secret.find(guess[i])] = 'X';
                guess[i] = 'X';
                cows++;
            }
        }
        print(ans, bulls, cows);
        return ans;
    }
    void print(string& ans, int bulls, int cows) {
        stringstream ss;
        ss << bulls << 'A' << cows << 'B';
        ans = ss.str();
    }
};

Cleaner one:

class Solution {
public:
    string getHint(string secret, string guess) {
        int m[256] = {0}, bulls = 0, cows = 0;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) ++bulls;
            else {
                if (m[secret[i]]++ < 0) ++cows;
                if (m[guess[i]]-- > 0) ++ cows;
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

Nim Game

Problem:

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Solution:
class Solution {
public:
    bool canWinNim(int n) {
        /*
        if (n < 4) {
            return true;
        } else if (n == 4) {
            return false;
        } else {
            return !canWinNim(n - 1) || !canWinNim(n - 2) || !canWinNim(n - 3);
        }
        */
        if (n % 4 == 0)
            return false;
        return true;
    }
};

Word Pattern

Problem: Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution:
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> splitString;
        if (str.size() != 0) {
            split(str, splitString);
        }
        if (pattern.size() != splitString.size()) {
            return false;
        }
        int size = pattern.size();
        map<char, string> map1;
        map<string, char> map2;
        for (int i = 0; i < size; i++) {
            if (map1.find(pattern[i]) != map1.end()) {
                if (map1[pattern[i]] != splitString[i]) {
                    return false;
                }
            } else {
                map1[pattern[i]] = splitString[i];
            }
         
            // Backword map check.
            if (map2.find(splitString[i]) != map2.end()) {
                if (map2[splitString[i]] != pattern[i]) {
                    return false;
                }
            } else {
                map2[splitString[i]] = pattern[i];
            }
        }
        return true;
    }
 
    void split(string str, vector<string>& splitString) {
        stringstream s(str);
        string token;
        while (getline(s, token, ' ')) {
            splitString.push_back(token);
        }
        return;
    }
};


============== Another =======
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<char, string> mp1;
        map<string, char> mp2;
       
        vector<string> tmp = split(str, ' ');
        if (tmp.size() != pattern.size()) {
            return false;
        }
       
        for (int i = 0; i < pattern.size(); i++) {
            if (!mp1.count(pattern[i])) {
                mp1[pattern[i]] = tmp[i];
            } else {
                if (mp1[pattern[i]] != tmp[i]) {
                    return false;
                }
            }
            if (!mp2.count(tmp[i])) {
                mp2[tmp[i]] = pattern[i];
            } else {
                if (mp2[tmp[i]] != pattern[i]) {
                    return false;
                }
            }
        }
        return true;
    }
   
    vector<string> split(string str, char delim) {
        vector<string> ans;
        stringstream ss(str);
        string partial;
        while (getline(ss, partial, delim)) {
            ans.push_back(partial);
        }
        return ans;
    }
};

========= Split ======
bool wordPattern(string pattern, string str) { stringstream raw(str); vector<string> strs; string line; while (raw >> line) strs.push_back(line); if (pattern.size() != strs.size()) return false; unordered_map<char, string> PS; unordered_map<string, char> SP; for (int i = 0; i < pattern.size(); i ++ ) { if (PS.count(pattern[i]) == 0) PS[pattern[i]] = strs[i]; if (SP.count(strs[i]) == 0) SP[strs[i]] = pattern[i]; if (PS[pattern[i]] != strs[i]) return false; if (SP[strs[i]] != pattern[i]) return false; } return true; }