LIKE CODING: LinkedIn

Showing posts with label LinkedIn. Show all posts

Friday, December 4, 2015

LeetCode [311] Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

Input:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        unordered_map<int, unordered_set<int>> A1, B1;
        int ma = A.size(), na = A[0].size();
        int mb = B.size(), nb = B[0].size();

        for(int i=0; i<ma; ++i){
            for(int j=0; j<na; ++j){
                if(A[i][j]){
                    A1[i].insert(j);
                }
            }
        }

        for(int j=0; j<nb; ++j){
            for(int i=0; i<mb; ++i){
                if(B[i][j]){
                    B1[j].insert(i);
                }
            }
        }

        vector<vector<int>> ret(ma, vector<int>(nb, 0));
        for(int i=0; i<ma; ++i){
            for(int j=0; j<nb; ++j){
                int s = 0;
                if(A1.count(i) && B1.count(j)){
                    for(auto k:A1[i]){
                        if(B1[j].count(k)){
                            s += A[i][k]*B[k][j];
                        }
                    }
                }
                ret[i][j] = s;
            }
        }

        return ret;
    }
};

//Java
class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int am = A.length, an = A[0].length;
        int bm = B.length, bn = B[0].length;
        List<Map<Integer, Integer>> mapA = new ArrayList<Map<Integer, Integer>>(am);
        List<Map<Integer, Integer>> mapB = new ArrayList<Map<Integer, Integer>>(bn);

        for(int i=0; i<am; ++i){
            mapA.add(new HashMap<>());
            for(int j=0; j<an; ++j){
                if(A[i][j]!=0){
                    mapA.get(i).put(j, A[i][j]);
                }
            }
        }

        for(int j=0; j<bn; ++j){
            mapB.add(new HashMap<>());
            for(int i=0; i<bm; ++i){
                if(B[i][j]!=0){
                    mapB.get(j).put(i, B[i][j]);
                }
            }
        }

        int[][] ret = new int[am][bn];
        for(int i=0; i<am; ++i){
            for(int j=0; j<bn; ++j){
                int s = 0;
                for(Map.Entry<Integer, Integer> e : mapA.get(i).entrySet()){
                    int k = e.getKey(), v = e.getValue();
                    if(mapB.get(j).containsKey(k)){
                        s += v*mapB.get(j).get(k);
                    }
                }
                ret[i][j] = s;
            }
        }
        return ret;
    }
}

Monday, October 26, 2015

LeetCode [297] Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

Hard

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Constraints:

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
    void serialize(TreeNode* node, stringstream &ss){
        if(!node)
        {
            ss<<"# ";
        }
        else
        {
            ss<<node->val<<" ";
            serialize(node->left, ss);
            serialize(node->right, ss);
        }
    }
    
    TreeNode* deserialize(stringstream &ss)
    {
        string s;
        ss>>s;
        if(s=="#"){
            return NULL;
        }else{
            TreeNode* node = new TreeNode(stoi(s));
            node->left = deserialize(ss);
            node->right = deserialize(ss);
            return node;
        }
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        serialize(root, ss);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss<<data;
        return deserialize(ss);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String str;
    String[] strs;
    int index = 0;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        str = "";
        sh(root);
        return str;
    }
    
    void sh(TreeNode node){
        if(str.length()>0) str += ",";
        if(node==null){
            str += "#";
        }else{
            str += node.val;
            sh(node.left);
            sh(node.right);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        strs = data.split(",");
        index = 0;
        return dh();
    }
    
    TreeNode dh(){
        TreeNode node;
        String s = strs[index++];
        if(s.equals("#")){
            node = null;
        }else{
            node = new TreeNode(Integer.parseInt(s));
            node.left = dh();
            node.right = dh();
        }
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Saturday, August 22, 2015

MJ [24] Union and Intersection of two sorted arrays

Ref
[1] http://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/
Question

Friday, August 21, 2015

MJ [23] Bipartite Graph

Question:
Check whether a given graph is Bipartite or not

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33034407.html
[2] http://www.geeksforgeeks.org/bipartite-graph/

MJ [21] Who wins IV

Question:
Two players take numbers from a set of numbers nums in turn. A player can only take one number from nums each time. Once a number is taken, it is removed from nums. The sum of all the removed number is denoted by sum. A player wins if sum>target after the player took one number.

Given nums and target, determine whether the first player can win assuming all the numbers is nums and target are positive.

Eg1., if nums = {2,3} and target = 4, the first player loses no matter which number it takes first.

Eg2., if nums = {1,2,3} and target = 4, the first player can win by remove 1 at the 1st step. Then the second can only take 2 or 3. In either case the first player wins by taking the last number left.
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33010083.html

Saturday, August 15, 2015

MJ [9] Design tinyurl

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33026221.html
MJ LinkedIn
[2] http://n00tc0d3r.blogspot.com/2013/09/big-data-tinyurl.html
[3] http://www.careercup.com/question?id=5185808560553984

Friday, August 14, 2015

MJ [8] Longest Palindrome Subsequence

Question:

Given a sequence of numbers, find the length of the longest palindrome subsequence. Eg., if nums = {1,2,2,0,1}, it should return 4 because the longest palindrome subsequence is {1,2,2,1}.

longestCS_rec
"Time complexity of the above naive recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is ."[2]

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/33026221_0_1.html
MJ
[2] http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
Longest Common Subsequence. Very good explanation of DP.

Thursday, August 13, 2015

LeetCode [256] Paint House

Ref
[1] https://leetcode.com/problems/paint-house/
OJ

Wednesday, July 15, 2015

LeetCode [238] Product of Array Except Self

238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int prod = 1, n = nums.size(), tmp = 1;
        vector<int> output(n,1);
        for(int i=1; i<n; ++i)
        {
            output[i] = tmp * nums[i-1];
            tmp = output[i];
        }
        
        tmp = 1;
        for(int i=n-2; i>=0; --i)
        {
            output[i] *= (tmp*nums[i+1]);
            tmp *= nums[i+1];
        }
        
        return output;
    }
};

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] output = new int[n];
        
        for(int i=0; i<n; ++i){
            if(i==0) output[i] = 1;
            else output[i] = output[i-1]*nums[i-1];
        }
        
        int p = nums[n-1];
        for(int i=n-2; i>=0; --i){
            if(i==0) output[i] = p;
            else output[i] = output[i]*p;
            p *= nums[i];
        }
        
        return output;
    }
}

Sunday, April 5, 2015

LeetCode [72] Edit Distance

72. Edit Distance

Hard

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

//C++: 28ms method1 space O(m*n);
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1));
        for(int j=0; j<=n2; ++j) dp[0][j] = j;
        for(int i=0; i<=n1; ++i) dp[i][0] = i;
        
        for(int i=1; i<=n1; ++i){
            for(int j=1; j<=n2; ++j){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }
        
        return dp[n1][n2];
    }
};

//C++: 20ms method2 space O(min(m, n));
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        if(n2>n1) return minDistance(word2, word1);
        
        vector<int> row_old(n2+1, 0), row(n2+1, 0);
        for(int j=0; j<=n2; ++j) row_old[j] = j;

        for(int i=1; i<=n1; ++i){
            row[0] = i;
            for(int j=1; j<=n2; ++j){
                if(word1[i-1]==word2[j-1]){
                    row[j] = row_old[j-1];
                }else{
                    row[j] = 1+min(min(row_old[j], row[j-1]), row_old[j-1]);
                }
            }
            row_old = row;
        }

        return row[n2];
    }
};

//Java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];

        for(int j=1; j<=n; ++j) dp[0][j] = j;
        for(int i=1; i<=m; ++i) dp[i][0] = i;

        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }

        return dp[m][n];
    }
}

//Java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];

        for(int j=1; j<=n; ++j) dp[0][j] = j;
        for(int i=1; i<=m; ++i) dp[i][0] = i;

        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }

        return dp[m][n];
    }
}

Wednesday, February 25, 2015

LeetCode [47] Permutations II

47. Permutations II

Medium

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        bt(nums, ret, 0, nums.size());
        return ret;
    }

    //nums cannot be reference so that nums[pos+1..n-1] is in increasing order
    void bt(vector<int> nums, vector<vector<int>> &ret, int pos, int n){
        if(pos==n){
            ret.push_back(nums);
        }else{
            for(int i=pos; i<n; ++i){
                if(i>pos && nums[i]==nums[pos]) continue;
                swap(nums[pos], nums[i]);
                bt(nums, ret, pos+1, n);
                //cannot swap back; otherwise nums[pos+1..n-1] will not be in increasing order
            }
        }
    }
};

===========

Note
It is important to keep the increasing order of the non-determined portion of the vector, ie., nums[pos+1, n-1], such that we can conveniently skip the duplicate cases by line 17.

An example for the recursion of nums. pos=0. Note that nums[1, 4] are in increasing order.
0 1 2 3 4 -- index
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4

If nums is swapped back at line20. nums[1, 4] are no longer in increasing order.
0 1 2 3 4 -- index
1 2 3 4 5
2 1 3 4 5
3 2 1 4 5
4 2 3 1 5
5 2 3 4 1