2015年10月26日星期一

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Have you met this question in a real interview? 
Yes

Example
Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7
The binary tree A is a height-balanced binary tree, but B is not.

postorder the BST, get the max depth of left and right side and return the value;
if not height-balanced, return -1

Time: O(n)
Space: O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    bool isBalanced(TreeNode *root) {
        // write your code here
        if(helper(root) == -1) return false;
        return true;
    }
    int helper(TreeNode *node){
        if(node == NULL) return 0;
        int left = helper(node->left);
        int right = helper(node->right);
        if(left == -1 || right == -1) return -1;
        if(abs(left - right) > 1) return -1;
        return max(left, right) + 1;
    }
};

Converted Sorted Array to Binary Search Tree


Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
http://blog.csdn.net/linhuanmars/article/details/23904883

Time: O(n)
Space: O(n)+O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) { 
        return helper(nums, 0, nums.size() - 1);
    }
    TreeNode* helper(vector<int>& nums, int left, int right){
        if(left > right) return NULL;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

2015年10月16日星期五

Web Devloper learning

Compared with http, TCP/IP, sockets
http://jingyan.baidu.com/article/08b6a591e07ecc14a80922f1.html

VIM turorial

Official App Engine Python SDK
https://cloud.google.com/appengine/docs/python/gettingstartedpython27/introduction
Quick Tutorial

Server pages: https://appengine.google.com/
Server ID: https://console.developers.google.com/project/optimum-sound-110122

google app engine:

open local:   push run in googleAppEngineLauncher then go to browser and type in url as localhost:port. In local mode, if I change files locally, the changes will be displayed directly in localhost

deploy:
First Create a new application in google app engine website
<way 1> command: appcfg.py -A applicationID update app.yaml
<way 2> click edit button in googleAppEngineLauncher, change application name to application ID, then push deploy button directly.

2015年10月6日星期二

Lintcode: word search ii

Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. 

Have you met this question in a real interview? 
Yes
Example
Given matrix:
doafagaidcan
and dictionary:
{"dog", "dad", "dgdg", "can", "again"}

return {"dog", "dad", "can", "again"}


dog:
doafagaidcan
dad:
doafagaidcan
can:
doafagaidcan
again:
doafagaidcan

Challenge
Using trie to implement your algorithm.


Trie search avoid repetitive search

Reference from some guy's codes, failed to find that web




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
struct TrieNode {
    bool  isEnd;
    TrieNode *children[26];
    
    TrieNode()
    {
        isEnd = false;
        memset(children, 0, sizeof(children));
        // function of memset
        /*   
        for(int i =0; i < 26; i++){
            children[i] = NULL;
        }*/
    }
    
    void Add(string s, int index) {
        if (index == s.length()) {
            isEnd = true;
            return;
        } 
        
        if (children[s[index] - 'a'] == NULL)
            children[s[index] - 'a'] = new TrieNode();
        
        children[s[index]-'a']->Add(s, index+1); 
    }
    
    ~TrieNode() {
        for(int i = 0; i < 26; i++) {
            //it's ok to delete NULL pointer
            delete children[i];
        }
    }
};


class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
        unordered_set<string>  ret;
        TrieNode trie; 
        for(int i = 0; i < words.size(); i++) 
            trie.Add(words[i],0);
        
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        string temp;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j< board[0].size(); j++) {
                helper(board, visited, &trie, i, j, temp,  ret); 
        }
        //create vector from set
        return vector<string>(ret.begin(), ret.end());
    }
    
    void helper(vector<vector<char>> &grid, 
            vector<vector<bool>> &visited,
            TrieNode *trie,
            int i,
            int j,
            string tmp,
           unordered_set<string> &ret)
    {

        if (!trie || i < 0 || i >= grid.size() || j < 0 || j >=grid[0].size())
             return;        
        if (!trie->children[grid[i][j]-'a'] || visited[i][j]) return;
        
        
        TrieNode *nextNode = trie->children[grid[i][j]-'a'];
        tmp.push_back(grid[i][j]);
        if (nextNode->isEnd)  ret.insert(tmp); 
        //avoid path return to nodes that already passed
        visited[i][j] = true;
        
        int x[] ={0, 0, -1, 1};
        int y[] ={-1,1, 0, 0};
        for(int k = 0; k < 4; k++) 
            helper(grid, visited, nextNode, i+x[k], j+ y[k], tmp, ret);  
            
        visited[i][j] = false; 
    } 
};

Lintcode: Data Stream Median

Numbers keep coming, return the median of numbers at every time a new number added.
Have you met this question in a real interview? 
Yes
Example
For numbers coming list: [1, 2, 3, 4, 5], return[1, 1, 2, 2, 3].
For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].
For numbers coming list: [2, 20, 100], return [2, 2, 20].
Challenge
Total run time in O(nlogn).

Clarification
What's the definition of Median? - Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n - 1) / 2]. For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.
//codes
http://www.jiuzhang.com/solutions/median-in-data-stream/
//how to use priority queue
https://github.com/kamyu104/LintCode/blob/master/C++/median-in-data-stream.cpp
Use two priority_queue to record input numbers
Time:O(nlogn)
Space: O(n)
p.s. change while in line 23/27, codes also work


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of numbers
     */
     /*
    struct comp{
        bool operator()(int x, int y) const {
            return x > y;
        }
    }; */
     
    vector<int> medianII(vector<int> &nums) {
        vector<int> res;
        priority_queue<int> maxHeap;
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for(int i = 0; i < nums.size(); i++){
            if(maxHeap.empty() || minHeap.empty()) maxHeap.push(nums[i]);
            else if(nums[i] > minHeap.top()) minHeap.push(nums[i]);
            else maxHeap.push(nums[i]);
            
            while(maxHeap.size() < minHeap.size()){
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
            while(maxHeap.size() > minHeap.size() + 1){
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            }
            
            res.push_back(maxHeap.top());
        }
        return res;
    }
};


2015年9月30日星期三

Lintcode: Larget Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
histogram
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
histogram
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Have you met this question in a real interview? 
Yes
Example
Given height = [2,1,5,6,2,3],
return 10.
Tags Expand 

Naive solution 1:
For each element, calculate largest area with the height of itself
Time limit for large data
Time: O(n*n)
Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        int res = 0;
        for(int i = 0; i < height.size(); i++){
            int cur = i;
            int left = 0, right = 0;
            while(cur >= 0){
                if(height[cur] < height[i]) break;
                left += height[i];
                cur--;
            }
            cur = i + 1;
            while(cur < height.size()){
                if(height[cur] < height[i]) break;
                right += height[i];
                cur++;
            }
            res = max(res, left + right);
        }
        return res;
    }
};

 Naive solution 2
Similar solution in converse order: http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html
We just get the minimum area between any possible two indexes:
Time: O(n*n)
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        int maxArea = 0;
        for(int i = 0; i < height.size(); i++){
            int minH = height[i];
            for(int j = i; j < height.size(); j++){
                minH = min(minH, height[j]);
                maxArea = max(maxArea, minH * (j - i + 1));
            }
        }
        return maxArea;
    }
};

Optimized Naive solution 2 with Pruning 
//thought:  http://blog.csdn.net/abcbc/article/details/8943485
Whenever height[k] <= height[k - 1] rectangle formded by k - 1 is larger than k
So we look for the k that height[k] > height[k - 1]

Still cannot pass
Time: O(n*n)
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        int maxArea = 0;
        //int lastH = -1;
        for(int i = 0; i < height.size(); i++){
            if(i > 0 && height[i] <= height[i - 1]) {
                continue;
            }
            int minH = height[i];
            for(int j = i; j < height.size(); j++){
                minH = min(minH, height[j]);
                maxArea = max(maxArea, minH * (j - i + 1));
            }
        }
        return maxArea;
    }
};





O(n) solution -- DP
http://www.acmerblog.com/largest-rectangle-in-histogram-6117.html

O(n) solution -- stack
//Great explanation, even though some problems in pictures
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
//codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-largest-rectangle-in-histogram.html
Create a stack to store all increasing adjacent numbers, when new coming number is more than the top element is stack, just push it to stack; if not, pop elements bigger than new coming number and keep updating area.
Note: set -1 at the beginning and end of height vector:
The -1 at the begin is to help localize the possible maxArea in stack
The -1 at the end is to pop all elements in stack when finish iteration


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        height.push_back(-1);
        height.insert(height.begin(), -1);  //when elements 
        stack<int> s;
        int maxArea = 0;
        
        for(int i = 0; i < height.size(); i++){
            while(!s.empty() && height[i] < height[s.top()]){
                int h = height[s.top()];
                s.pop();
                maxArea = max(maxArea, h * (i - s.top() - 1));
            }
            s.push(i);
        }
        
        return maxArea;
    }
};

Analysis:
However, codes above don't optimize the situation when there are many equal numbers in height, in this case, there are still some repetitive counts.
Below is how to optimize:
euqation in Line 1 avoid to store repetitive numbers in stack
The condition height[i] < h in line 4 avoid the TERMSIG case when height[i] = -1 and s.top() = -1


1
2
3
4
5
while(!s.empty() && height[i]<=height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h);
            }



2015年9月29日星期二

Lintcode: Ugly Number

Ugly number is a number that only have factors 35 and 7.
Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...
Have you met this question in a real interview? 
Yes
Example
If K=4, return 9.

Challenge
O(K log K) or O(K) time.

Thoughts:
http://blog.csdn.net/nisxiya/article/details/46767595


Naive solution:
Try every number and judge whether it is ugly until get the kth

Priority_queue solution:
Created a min heap and kept multiplying the minimum ugly number with 3, 5, 7 and put result into the heap. To avoid repetition, used a hashset to mark elements already in the heap
Time: O(klogk)
Space: O(k)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
     struct compNode{
         bool operator()(long long a, long long b)const{
             return a > b;
         }
     };
    long long kthPrimeNumber(int k) {
        priority_queue<long long, vector<long long>, compNode> pq;
        long long cur;
        //vector<int> res;
        unordered_set<long long> hashset;
        pq.push(1);
        for(int i = 0; i <= k; i++){
            cur = pq.top();
            pq.pop();
            if(!hashset.count(cur * 3)) {
                pq.push(cur * 3);
                hashset.insert(cur * 3);
            }
            if(!hashset.count(cur * 5)){
                pq.push(cur * 5);
                hashset.insert(cur * 5);
            }
            if(!hashset.count(cur * 7)){
                pq.push(cur * 7);
                hashset.insert(cur * 7);
            }
        }
        return cur;
    }
};

Normal Solution:
Thought: http://www.cnblogs.com/EdwardLiu/p/4322664.html
Generate ugly number through competition:
Time: O(n)
Space: O(n)
There are repeatations like 15 = 3 * 5 = 5 * 3, in this case, the i3 and i5 will proceed at the same time. So no repetations in result array.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
     
    long long kthPrimeNumber(int k) {
        vector<long long> res(k + 1);
        res[0] = 1;
        int i3 = 0, i5 = 0, i7 = 0;
        for(int i = 1; i <= k;i++){
            long long cur = min(min(res[i3] * 3, res[i5] * 5), res[i7] * 7);
            if(cur == res[i3] * 3) i3++;
            if(cur == res[i5] * 5) i5++;
            if(cur == res[i7] * 7) i7++;
            res[i] = cur;
        }
        return res[k];
    }
   
};

2015年9月28日星期一

Lintcode: Merge k sorted lists


Codes and Thoughts reference:
http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html

Priority queue solution:

Introduction to data structure of priority_queue:
http://m.zgxue.com/197/1977189.html

Great Explanation of how to rewrite compare function of priority_queue
http://www.cnblogs.com/iammatthew/archive/2010/08/19/1803935.html

C++ operator overloading
http://c.biancheng.net/cpp/biancheng/view/215.html

Time: O(nk*logk)
Space: O(k)



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};



Merge two lists -- basic solution
n -- the maximum len of each list  k -- the number of sorted lists
for merge two list O(m+n)   ==> Portal to my leetcode Merge two sorted lists solution
here: n + 2n + 3n + ... + kn =((k+1)*k/2 - 1)*n

Time: O(nk^2)
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *res = NULL;
        for(int i = 0; i < lists.size(); i++){
            res = merge(res, lists[i]);
        }
        return res;
    }
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

Bisection:
//thoughts
http://www.cnblogs.com/TenosDoIt/p/3673188.html

Time: O(nk*logk)    ---- each level is O(nk) and there are logk levels
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int end = lists.size() - 1;
        while(end){
            int begin = 0;
            while(begin < end){
                lists[begin] = merge(lists[begin], lists[end]);
                begin++;
                end--;
            }
        }
        return lists[0];
    }
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};



Lintcode: Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
Have you met this question in a real interview? 
Yes
Example
Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1

Note
min operation will never be called if there is no number in the stack


Reference my leetcode solution for the same problem:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MinStack {
private:
    vector<int> data;
    int minV;
public:
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        if(data.size() == 0) minV = number;
        else{
            int prev = minV + data.back();
            if(prev < minV) minV = prev;
        }
        data.push_back(number - minV);
    }

    int pop() {
        // write your code here
        int res = data.back() + minV;
        data.pop_back();
        if(data.back() < 0) minV = minV - data.back();
        return res;
    }

    int min() {
        // write your code here
        return ((data.back() + minV) < minV)?(data.back() + minV) : minV;
    }
};

Lintcode second:
Space: O(n)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MinStack {
public:
    vector<int> data;
    vector<int> minData;
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        data.push_back(number);
        if(minData.empty() || number <= minData.back()) minData.push_back(number);
    }

    int pop() {
        // write your code here
        if(data.back() == minData.back()) minData.pop_back();
        int res = data.back();
        data.pop_back();
        return res;
    }

    int min() {
        // write your code here
        return minData.back();
    }
};