NO CODING NO LIFE: 十月 2015

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)

/**
 * 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)

/**
 * 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日星期五

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

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

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年10月26日星期一

Balanced Binary Tree

Converted Sorted Array to Binary Search Tree

2015年10月16日星期五

Web Devloper learning

2015年10月6日星期二

Lintcode: word search ii

Lintcode: Data Stream Median