Friday, February 13, 2015

Interleaving String -- LeetCode

[Question]
Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
[Analysis]
The straightforward way is to use recursion. Compare the first letter of s1, s2, s3,

  1. If they are all different, the interleaving does not exist;
  2. If s1[0] ==s3[0], s2[0]!= s3[0], the problem becomes if s3.substr(1, s3.end()) is an interleaving form of s1,substr(1, s1.end()) and s2; 
  3. If s1[0]==s2[0]==s3[0], the code can explore two possibilities in sub-problems.

However it may make the computation complexity exponential.

Using Dynamic Programming, the computation can start from sub-problems, e.g. if the sub-strings of s1, s2, can be interleaved into sub-strings of s3. Like the problem of "Regular Expression Matching", this is 2D DP and can uses a 2D array to solve it.

Define M a matrix of (n+1) by (m+1), where n is size of s1 and m is the size of s2. M[i,j] is true, only when s1[0, i-1], s2[0, j-1] can be interleaved into s3[0.. i+j-1]. Populate M with the following rules:

  1. M[i,j] = false         if s3[i+j-1] != s1[i-1] && s3[i+j-1]!=s2[j-1];
  2. M[i,j]=M[i-1,j]      if s3[i+j-1] ==s1[i-1] && s1[i-1]!=s2[j-1];
  3. M[i,j]=M[i,j-1]      if s3[i+j-1] ==s2[j-1] && s1[i-1]!=s2[j-1];
  4. M[i,j]=M[i-1,j] || M[i,j-1]      if s3[i+j-1] ==s2[j-1] && s1[i-1]==s2[j-1];

In the end, M[n,m] is the answer. The time complexity is O(n * m).

[Solution]
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        if (s3.size() != s1.size()+s2.size() ) return false;
     
        vector<vector<bool>> map(s1.size()+1, vector<bool>(s2.size()+1,false) );
        for (int i=1; i<s2.size()+1; i++)
            map[0][i] = s2[i-1] == s3[i-1];
        for (int i=1; i<s1.size()+1; i++)
            map[i][0] = s1[i-1] == s3[i-1];
     
        for (int i=1; i<s1.size()+1; i++)
            for (int j=1; j<s2.size()+1; j++) {
                char c3 = s3[i+j-1];
                char c2 = s2[j-1];
                char c1 = s1[i-1];
                if (c3!= c2 && c3!=c1) map[i][j] = false;
                else if (c3==c2 && c3==c1) map[i][j] = map[i-1][j] || map[i][j-1];
                else if (c3==c2) map[i][j] = map[i][j-1];
                else map[i][j] = map[i-1][j];
            }
        return map.back().back();
    }
};

Maximum Gap -- LeetCode

[Question]
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
- Try to solve it in linear time/space.
- Return 0 if the array contains less than 2 elements.
- You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

[Analysis]
The problem can be solved by sorting the array first. However, it won't be linear time.
The maximum difference between the successive elements in sorted array, must be larger than (max-min)/ (N-1), where N is the number of elements in the array. Therefore, we can use "bucket sort" and distribute elements into N-1 buckets, whose size is (max-min)/(N-1). The maximum difference between successive elements must be in different buckets. Each bucket needs to store only its the minimal and maximal elements. In this way, the time complexity is O(N).

[Solution]
class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size()<2) return 0;
        if (num.size()==2) return max(num[0], num[1]) - min(num[0], num[1]);
     
        int num_min = *min_element(num.begin(), num.end());
        int num_max = *max_element(num.begin(), num.end());
        int len = (num_max - num_min) / (num.size() - 1) +1; // need ceiling of value;
     
        vector<pair<int, int>> buckets (num.size(), pair<int, int> (INT_MAX, INT_MIN));
     
        for (auto n: num) {
            int index = (n-num_min) / len;
            buckets[index].first = min (buckets[index].first, n);
            buckets[index].second = max(buckets[index].second, n);
        }
     
        int gap = 0;
        int prev = buckets[0].second;
        for (int i=1; i<buckets.size(); i++) {
            if (prev!=INT_MIN && buckets[i].first!=INT_MAX) {
                gap = max(gap, buckets[i].first - prev);
                prev = buckets[i].second;
            }
        }
        return gap;
    }
};

Thursday, February 5, 2015

Longest Valid Parentheses -- LeetCode

[Question]
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

[Analysis]
The length of the valid parentheses substring is: the index of "the next invalid character" - the index of "the last known invalid character" - 1. For example, in the sequence "(()(", the length is 3-0-1 = 2.

Use a stack to trace and remove the valid parentheses from the string. Trace means the stack needs to store the index of each character in the string. "The next invalid character" is the character to push into stack; "the last known invalid character" is the character in the top of stack.

[Solution]
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
       
        int len=0;
        for (int i=0; i<s.size(); i++) {
            if (!st.empty() && s[st.top()]=='(' && s[i]==')' ) {
                st.pop();
                len = max(len, st.empty()?i+1:i-st.top() );
            }
            else
                st.push(i);
        }
        return len;
    }
};

Binary Tree Maximum Path Sum -- LeetCode

[Question]
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
       1
      / \
     2   3
Return 6.
[Analysis]
If the path can be only link (i.e. no both left and right nodes of one node allowed to be in the path), the problem is simple. Suppose path with max single-sided path ending at Node N (from bottom to up),
       SingleSidePathMax(N) = max (N.value,
                                                     N.value+ SingleSidePathMax(N.left),
                                                     N.value+ SingleSidePathMax(N.right) );

Going through all nodes in the tree, this will get the max sum of single-sided path.

To consider the path with a node N, whose both left and right are included in the path, it can calculated by,
      PathMax(N) = max ( SingleSidePathMax(N), N.value+SingleSidePathMax(N.left) + SingleSidePathMax(N.right) );

Therefore, apply post-order traversal in the Binary Tree, and calculate the single-sided path max and dual-sided path max of each node, the max path sum of all paths can be found.

[Solution]
class Solution {
public:
    int maxSinglePath(TreeNode *root, int& maxSum) {
        if (!root)  return 0;
       
        if (!root->left && !root->right) {
            maxSum = max( maxSum, root->val);
            return root->val;
        }
       
        int leftMax = maxSinglePath( root->left, maxSum);
        int rightMax= maxSinglePath( root->right, maxSum);
        int singleMax = max( max(leftMax, rightMax) + root->val, root->val);
        maxSum = max( max(maxSum, singleMax), leftMax+rightMax+root->val);
        return singleMax;
    }
   
    int maxPathSum(TreeNode *root) {
        int max = INT_MIN;
        maxSinglePath(root, max);
        return max;
    }

};

Wednesday, February 4, 2015

LRU Cache -- LeetCode

[Question]

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

[Analysis]
The LRU cache will remove the most aged item in the cache (http://en.wikipedia.org/wiki/Cache_algorithms).

There are many ways to implement LRU. The focus is to select the right data structure so that every get() and set() can be executed in constant time. Doubly linked list, which allows delete a node by the pointer pointing to the node, and Hashtable, which allows direct access to the node by given key, will give a constant-time operations to get() and set().

The data structure looks like:


[Solution]
class LRUCache{

    struct Node {
        int key;
        int val;
        Node* prev;
        Node* next;
        Node(int k=0, int v=0) : key(k), val(v), prev(NULL), next(NULL) {};
    };
 
    Node* cache_head;
    Node* cache_tail;
    unordered_map<int, Node*> map;
    int count;
    int limit;

    void insert_node(int key, int value) {
        if (map.find(key)!=map.end()) return;
     
        Node *node = new Node(key,value);
        map[key] = node;
        if (cache_head==NULL) {
            cache_head = cache_tail = node;
            count = 1;
        }
        else {
            node->next = cache_head;
            cache_head->prev = node;
            cache_head = node;
            count++;
        }
    }
 
    void remove_node(int key) {
        if (map.find(key)==map.end()) return;
        Node* node = map[key];
     
        if (cache_head == node) cache_head= node->next;
        if (cache_tail == node) cache_tail= node->prev;
     
        if (node->prev)
            node->prev->next = node->next;
        if (node->next)
            node->next->prev = node->prev;
        node->next = node->prev=NULL;
     
        delete node;
        map[key] = NULL;
        map.erase(key);
        count--;
    }

public:
    LRUCache(int capacity) : cache_head(NULL), cache_tail(NULL), count(0), limit(capacity) {
    }
 
    int get(int key) {
        if (map.find(key)==map.end())
            return -1;
     
        int value = map[key]->val;
        remove_node(key);
        insert_node(key, value);
        return value;
    }
 
    void set(int key, int value) {
        if (map.find(key) == map.end()) {
            if (count == limit)
                remove_node(cache_tail->key); //Remove the aged node from cache.
        }
        else {
            remove_node(key);
        }
        insert_node(key, value);      
    }
};

Clone an Undirected Graph -- Leetcode

 [Question]

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/

[Analysis]
This problem is similar with "Clone a Directed Acyclic Graph (DAG)". The basic approach is to use Breadth First Search.

The things to notice include: it may contains circles; it may have duplicated edges -- for example, two edges between node 1 and node 2. Those can be resolved by tracking the nodes cloned completely (edges and neighbors).

Update: DFS can provide more concise code.

[Solution]

//
// -- BFS --
//
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return node;
       
        unordered_map<int, UndirectedGraphNode *> map;
        unordered_set<UndirectedGraphNode*> visited;
        queue<UndirectedGraphNode*> que;
       
        que.push(node);
        UndirectedGraphNode* new_node = new UndirectedGraphNode( node->label );
        map[node->label] = new_node;
       
        while (!que.empty()) {
            UndirectedGraphNode* front = que.front();
            que.pop();
            if (visited.find(front)!=visited.end())
                continue;
               
            for (auto p : front->neighbors) {
                if (map.find(p->label)==map.end()) {
                    UndirectedGraphNode* new_node = new UndirectedGraphNode( p->label );
                    map[p->label] = new_node;
                }   
                map[front->label]->neighbors.push_back(map[p->label]);
                if (p!=front && visited.find(p)==visited.end()) que.push(p);
            }
            visited.insert(front);
        }
        return new_node;
    }
};

//
//-- DFS --
//
class Solution {
    unordered_map<int, UndirectedGraphNode*> mNodes;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return node;
        if (mNodes.count(node->label)) return mNodes[node->label];
       
        mNodes[node->label] = new UndirectedGraphNode(node->label);
        for (auto x: node->neighbors)
            mNodes[node->label]->neighbors.push_back( cloneGraph(x) );
           
        return mNodes[node->label];
    }
};

Monday, February 2, 2015

Max Points on a Line -- Leetcode

[Question]
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

[Analysis]
The points on a line share the same slope: i.e. if point (x,y) is on the line formed by point (x1, y1) and (x2, y2), (y-y1) / (x-x1) = (y2-y1)/(x2-x1). For a given point, explore each slope (with other points) then we can find the result.

Corner cases to consider: 1) duplicated points; 2) points in a horizontal line, i.e. x1 = x2.

[Solution]
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        if (points.size()<3) return points.size();
     
        int num = 2;
     
        for (int i=0; i<points.size(); i++) {
            unordered_map<float, int> slopes;
            int horizonal_cnt =0;
            int same_points = 1;
            for (int j=i+1; j<points.size(); j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    same_points ++;
                }
                else
                if (points[j].x == points[i].x) {
                    horizonal_cnt++;
                }
                else {
                    float sl = (float) (points[j].y - points[i].y) / (points[j].x - points[i].x);
                    slopes[sl] ++;
                }
            }
            num = max(num, same_points);
            num = max(num, horizonal_cnt + same_points);
            for (auto pair: slopes) {
                num = max(num, pair.second + same_points);
            }
        }
        return num;
    }
};