House Robber III

Question:
http://www.lintcode.com/en/problem/house-robber-iii/
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Answer:
~~~c++
class Solution {
public:
    int houseRobber3(TreeNode* root) {
        unordered_map<TreeNode*, int> m;
        return dfs(root, m);
    }
    int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {
        if (!root) return 0;
        if (m.count(root)) return m[root];
        int val = 0;
        if (root->left) {
            val += dfs(root->left->left, m) + dfs(root->left->right, m);
        }
        if (root->right) {
            val += dfs(root->right->left, m) + dfs(root->right->right, m);
        }
        val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));
        m[root] = val;
        return val;
    }
};
~~~

House Robber II

Question:
http://www.lintcode.com/en/problem/house-robber-ii/
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Answer:
~~~c++
class Solution {
public:
     /*
     * @param nums: An array of non-negative integers.
     * @return: The maximum amount of money you can rob tonight
     */
    int houseRobber2(vector<int> nums) {
        if (nums.size() <= 1)
            return nums.empty() ? 0 : nums[0];
        vector<int> nums_inf = nums;
        vector<int> nums_inl = nums;
        nums_inf.pop_back();
        nums_inl.erase(nums_inl.begin());
        return max(houseRobber(nums_inf), houseRobber(nums_inl));
    }

    /*
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        if (as == 0)
          return 0;
        if (as == 1)
          return A[0];
        if (as == 2)
          return max(A[0], A[1]);
        vector<long long> dp(as);
        dp[0] = A[0];
        dp[1] = max(A[0], A[1]);
        for (size_t i = 2; i < as; i++)
          dp[i] = max(dp[i-1], dp[i-2] + A[i]);
        return dp[as-1];
    }
};
~~~

PS:
if houseRobber(vector<int> &A) use memory O(1) method in [house-robber](http://acm.errong.win/house-robber/),
   
~~~c++
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        long long odd, even;
        odd = even = 0;
        for (size_t i = 0; i < as; i++)
          if (i % 2)
            odd = max(odd+A[i], even);
          else
            even = max(even + A[i], odd);
        return max(odd, even);
    }
~~~

houseRobber2 will exceed the time limit.
it seems like i%2 operation will take more time.

House Robber

Question:
http://www.lintcode.com/en/problem/house-robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Answer:
time:O(N)
~~~c++
class Solution {
public:
    /*
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        if (as == 0)
          return 0;
        if (as == 1)
          return A[0];
        if (as == 2)
          return max(A[0], A[1]);
        vector<long long> dp(as);
        dp[0] = A[0];
        dp[1] = max(A[0], A[1]);
        for (size_t i = 2; i < as; i++)
          dp[i] = max(dp[i-1], dp[i-2] + A[i]);
        return dp[as-1];
    }
};
~~~
  
time:O(N)
memory:O(1)
~~~c++
class Solution {
public:
    /*
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        long long odd, even;
        odd = even = 0;
        for (size_t i = 0; i < as; i++)
          if (i % 2)
            odd = max(odd+A[i], even);
          else
            even = max(even + A[i], odd);
        return max(odd, even);
    }
};
~~~
                                 
                                 

Developer install & setup with Ghost, step by step

# Install Pre-requisites: node.js yarn grunt
install node.js lts version
wget https://nodejs.org/dist/v8.9.0/node-v8.9.0-linux-x64.tar.xz
tar -xvf node-v8.9.0-linux-x64.tar.xz
vim ~/.bashrc
export PATH="$HOME/node-v8.9.0-linux-x64/bin:$PATH"
source ~/.bashrc
check node version
node -v
v8.9.0

install yarn
curl -o- -L https://yarnpkg.com/install.sh | bash

install grunt
npm install -g grunt-cli

# Initial Setup
git clone https://github.com/TryGhost/Ghost.git  && cd Ghost
yarn run init

Could not start watchman
Visit https://ember-cli.com/user-guide/#watchman for more info.
$ git clone https://github.com/facebook/watchman.git
$ cd watchman
$ git checkout v4.9.0  # the latest stable release
$ ./autogen.sh
$ ./configure
$ make
$ sudo make install

knex-migrator init

# Develop Ghost
grunt dev
grunt dev --server
grunt prod
.....

# Refers
https://docs.ghost.org/v1/docs/working-with-ghost

Fix up watchman issue with Ghost

# Issue
>>     >>     at BunserBuf.<anonymous> (/home/errong_leng/Ghost/core/client/node_modules/fb-watchman/index.js:95:23)
>>     at emitOne (events.js:116:13)
>>     at BunserBuf.emit (events.js:211:7)
>>     at BunserBuf.process (/home/errong_leng/Ghost/core/client/node_modules/bser/index.js:292:10)
>>     at /home/errong_leng/Ghost/core/client/node_modules/bser/index.js:247:12
>>     at _combinedTickCallback (internal/process/next_tick.js:131:7)
>>     at process._tickCallback (internal/process/next_tick.js:180:9)
>> A non-recoverable condition has triggered.  Watchman needs your help!
>> The triggering condition was at timestamp=1509698956: inotify-add-watch(/home/errong_leng/Ghost/core/client/node_modules/ember-cli-node-assets/node_modules/broccoli-funnel/node_modules/.bin) -> The user limit on the total number of inotify watches was reached; increase the fs.inotify.max_user_watches sysctl
>> All requests will continue to fail with this message until you resolve
>> the underlying problem.  You will find more information on fixing this at
>> https://facebook.github.io/watchman/docs/troubleshooting.html#poison-inotify-add-watch
>> Error: A non-recoverable condition has triggered.  Watchman needs your help!
>> The triggering condition was at timestamp=1509698956: inotify-add-watch(/home/errong_leng/Ghost/core/client/node_modules/ember-cli-node-assets/node_modules/broccoli-funnel/node_modules/.bin) -> The user limit on the total number of inotify watches was reached; increase the fs.inotify.max_user_watches sysctl
>> All requests will continue to fail with this message until you resolve
>> the underlying problem.  You will find more information on fixing this at
>> https://facebook.github.io/watchman/docs/troubleshooting.html#poison-inotify-add-watch
>>

# Solution
sudo su -
echo 8192000 > /proc/sys/fs/inotify/max_user_watches

be entrusted with the gospel

For the appeal we make does not spring from error or impure motives, nor are we trying to trick you.  (1 Thessalonians 2:3 NIV)
我们的劝勉不是出于错误，不是出于污秽，也不是用诡诈。  (帖撒罗尼迦前书 2:3 和合本)
On the contrary, we speak as those approved by God to be entrusted with the gospel. We are not trying to please people but God, who tests our hearts.  (1 Thessalonians 2:4 NIV)
但　神既然验中了我们，把福音托付我们，我们就照样讲，不是要讨人喜欢，乃是要讨那察验我们心的　神喜欢。  (帖撒罗尼迦前书 2:4 和合本)

knapsack problem

knapsack problem
Question:
give two integer n and m, select rand numbers from 1,2,3,...,n-1, n, 
let the sum of the combination is equal to  m.

print out all possible combinations.

Examples:
n = 8 m = 10
8 2
7 3
7 2 1
6 4
6 3 1
5 4 1
5 3 2
4 3 2 1

Answer:
#include <iostream>
#include <vector>

using namespace std;

void printNumbersWithSum(int n, int m, vector<int>& numbers) {
  if (m <= 0 || n <= 0)
    return;
  if (m == n) {
    for (int number : numbers)
      cout << number << " ";
    cout << n << endl;
  }
  numbers.push_back(n);
  printNumbersWithSum(n-1, m - n, numbers);
  numbers.pop_back();
  printNumbersWithSum(n-1, m, numbers);
}

int main() {
  vector<int> numbers;
  int n, m;
  cin >> n >> m;
  printNumbersWithSum(n, m, numbers);
  return 0;
}