312. Burst Balloons

This is a similar problem to matrix chain multiplication. This can be solved by divide-and-conquer with memorization. The basic idea behind is:

Let dp[i][j] to record the maximum sum for interval nums[i, j]. So for subinterval nums[start, end], if we need to pop out nums[k] in nums[start, end], the maximum sum for poping out nums[k] is dp[start][i-1] + nums[k]*nums[start-1]*nums[end+1]+dp[i+1][end]. Note nums[k] is the last element that need to pop out from nums[start, end], so the product should be nums[k]*nums[start-1]*nums[end+1]. dp[i][j] can be calculated recursively.

1:  class Solution {  
2:  public:  
3:    int maxCoins(vector<int>& nums) {  
4:      // let nums to have nums[-1] = nums[n] = 1  
5:      nums.insert(nums.begin(), 1);  
6:      nums.push_back(1);  
7:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), INT_MIN));  
8:      return helper(dp, nums, 0, nums.size()-1);  
9:    }  
10:    // note start "s" and end "e" constructs an exclusive interval (s, e)  
11:    int helper(vector<vector<int>> &dp, vector<int> &nums, int s, int e) {  
12:      if (dp[s][e] != INT_MIN) return dp[s][e];  
13:      if (e - s == 1) { dp[s][e] = 0; return 0; }  
14:      int res = 0;  
15:      for (int i = s + 1; i < e; i++) {  
16:        res = max(res, helper(dp, nums, s, i) + helper(dp, nums, i, e) + nums[i]*nums[s]*nums[e]);  
17:      }  
18:      dp[s][e] = res;  
19:      return res;  
20:    }  
21:  };  

321. Create Maximum Number

We need to compute the maximum number of length i from vector one and the maximum number of length k-i from vector two and then merge them together. After enumerating all possible i's, we'll get the maximum number. Therefore, there are two steps to achieve the goal:

1. create maximum number of lengths varying from 0 - k per input vector. This can be done dynamically. For example, for [9, 1, 2, 5, 8, 3], with length  = 5, we remove 1 and get [9, 2, 5, 8, 3]. When computing maximum number of length 4, we don't have to restart computing from the original input. Instead, given maximum number of length 5, we can compute maximum number of length 4 on top of it, i.e. remove 2 and get [9, 5, 8, 3].

2. merge the two maximum numbers. It's similar to merge linked list but with exception. When there are identical numbers in the two maximum numbers, we should move the pointer in the maximum number that hasn't reached the end or has larger digit in the end.

When I revisited this problem, I made mistake in
Line 28: I didn’t carefully think of the case where two numbers are equal. I should move i only when there is no more numbers after equal sequence or the first number after equal sequence in list1 is larger than that in list2.
Line 38: I moved the if-else clause into the while loop.

However, with following solution, I still got TLE. The problem is in line 8-13. Since list1 and list2 contains lists of size from 0 to k and we only care about the merged list of size k, so we only need to check pairs in list1 and list2 that can be merged to size k. Instead of traversing all pairs in list1 and list2, we only need to check pairs of nums of size i in list1 and nums of size k-i in list2.

1:  class Solution {  
2:  public:  
3:    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {  
4:      vector<vector<int>> dp1(k+1), dp2(k+1);  
5:      vector<int> res(k), tmp_result(k);  
6:      genDP(nums1, dp1, k);  
7:      genDP(nums2, dp2, k);  
8:      for (int i = 0; i <= k; i++) {  
9:        if (dp1[i].size() + dp2[k-i].size() < k) continue;  
10:        merge(dp1[i], dp2[k-i], tmp_result);  
11:        if (compare(tmp_result, res)) res = tmp_result;  
12:      }  
13:      return res;  
14:    }  
15:  private:  
16:    void genDP(vector<int>& nums, vector<vector<int>> &dp, int k) {  
17:      int start, i = 0;  
18:      for (start = 0; nums.size() > 0; start = (i == 0 ? 0 : i-1)) {  
19:        if (nums.size() <= k) {  
20:          dp[nums.size()] = nums;  
21:        }  
22:        for (i = start; i+1 < nums.size() && nums[i] >= nums[i+1]; i++);  
23:        nums.erase(nums.begin() + i);  
24:      }  
25:    }  
26:    void merge(vector<int> &nums1, vector<int> &nums2, vector<int> &res) {  
27:      int i = 0, j = 0, k = 0;  
28:      int ii = 0, jj = 0;  
29:      for (; i < nums1.size() && j < nums2.size(); k++) {  
30:        for (ii = i, jj = j; ii < nums1.size() && jj < nums2.size() && nums1[ii] == nums2[jj]; ii++, jj++);  
31:        if (jj == nums2.size() || ii < nums1.size() && nums1[ii] > nums2[jj]) {  
32:          res[k] = nums1[i];  
33:          i++;  
34:        } else {  
35:          res[k] = nums2[j];  
36:          j++;  
37:        }  
38:      }  
39:      while (i < nums1.size()) {  
40:        res[k++] = nums1[i++];  
41:      }  
42:      while (j < nums2.size()) {  
43:        res[k++] = nums2[j++];  
44:      }  
45:    }  
46:    int compare(vector<int> &nums1, vector<int> &nums2) {  
47:      int i = 0;  
48:      for (;i < nums1.size() && nums1[i] == nums2[i]; i++);  
49:      if (nums1[i] > nums2[i]) return 1;  
50:      else return 0;  
51:    }
52:  };  

First Meeting with Postgres

I had to uninstall Postgres as I forgot the password for default admin user "postgres". What stupid I am. It really makes things difficult. So I have to uninstall the postgres. OK, another bad thing I made is I installed postgres by EnterpriseDB installer. It's always not an easy way to uninstall stuff that was not installed by homebrew. Fortunately, I found the following way to uninstall the postgres:
http://stackoverflow.com/questions/8037729/completely-uninstall-postgresql-9-0-4-from-mac-osx-lion

After the uninstallation, I installed postgres by homebrew:
$brew update
$brew install postgres

OK, now I've installed postgres successfully. It's time to lauch the postgres server by:
$pg_ctl -D /usr/local/var/postgres -l /usr/local/var/postgres/server.log start
and check it is running:

$ps aux | grep postgres

Everything works as expected, and I tried to run rails but got an error:

FATAL:  role "dashboard" does not exist

It seems that I don't have that role created in postgres. Not a problem, it's easy to create a role by:

$createuser -P dashboard

Log into postgres and check the role:

$psql -d postgres -U [login user name]

postgres=# SELECT rolname FROM pg_roles;

       rolname       

---------------------

... 

dashboard

Good! The role "dashboard" has been created successfully. Now try rails again. What? another error again?
PG::InsufficientPrivilege: ERROR:  permission denied to create database
Looks like the role "dashboard" doesn't have the permission to create database. Check the permission for "dashboard" in postgres:
postgres=# \du
                                 List of roles
     Role name      |                   Attributes                   | Member of
---------------------+------------------------------------------------+----------
dashboard |                                                | {}

Yeah, no permission at all for "dashboard". Grant it appropriate permission:
postgres=# ALTER ROLE dashboard CREATEROLE CREATEDB;

Now, run the rails again. Sigh...another error again:
"dashboard_development" does not exist

I see. It's most likely because I didn't do db:create and db:migrate. So, let me do it:

$bundle exec rake db:create db:migrate

Well, finally the website is up and running!

Memory Configuration on STM32F407

1. Stack Overflow

The process maintains its stack and the stack size is configured as following:

1:   ;*******************************************************************************   
2:   ; Amount of memory (in bytes) allocated for Stack   
3:   ; Tailor this value to your application needs   
4:   ; <h> Stack Configuration   
5:   ; <o> Stack Size (in Bytes) <0x0-0xFFFFFFFF:8>   
6:   ; </h>   
7:   Stack_Size  EQU  0x00008000   
8:       AREA STACK, NOINIT, READWRITE, ALIGN=3   
9:   Stack_Mem  SPACE Stack_Size   
10:   __initial_sp   
11:  </code></pre>  

So the code above defines the default stack size as 0x8000 (32Kb). If you have a buffer larger than 32Kb or you have a very deep recursive call, the stack will overflow. Once the overflow happens, the processor will generate an interrupt and jump to the interrupt handler which is HardFault_Handler.
I created a very simple test code shown as below to verify this behavior.

1:  #define BUF_SIZE (32*1024L)
2:  int main( void )  
3:  {  
4:       char buf[BUF_SIZE];  
5:       buf[0] = 'a';  
6:       buf[BUF_SIZE-1] = 'x';  
7:       printf("buf allocated on STACK, buf[%d]=%c, buf[%ld]=%c\r\n",  
8:            0, buf[0], BUF_SIZE, buf[BUF_SIZE-1]);  
9:  }  

If you run this code, nothing will output. If you run the JTAG debugger,  and set a break point in HardFault_Handler, you'll see the code flow reaches the break point.

Note, the reason the printf is not working in HardFault_Handler is the main stack is corrupted.
On the other hand, if you increase the Stack_Size beyond BUF_SIZE or reduce the BUF_SIZE below 32Kb, you'll see the output.

2. STM32F407 on-chip SRAM

By roughly looking at the STM32F407 datasheet, you are aware that you can use up to 192Kb SRAM. And you probably want to allocate the entire SRAM as stack to the processor and thus no heap. So you just increase the Stack_Size to 0x0002ffff and then you compile the code. However, you'll see following errors during the link stage:

1:  assembling startup_stm32f40xx.s...  
2:  linking...  
3:  .\Obj\STM32F407VET.axf: Error: L6406E: No space in execution regions with .ANY selector matching startup_stm32f40xx.o(STACK).  
4:  .\Obj\STM32F407VET.axf: Error: L6407E: Sections of aggregate size 0x30000 bytes could not fit into .ANY selector(s).  
5:  Not enough information to list image symbols.  
6:  Not enough information to list the image map.  
7:  Finished: 2 information, 0 warning and 2 error messages.  

Weird, right? Does it mean that we can't use the entire memory for stack? The answer is "YES we CAN" but we need to do a little bit more configuration. Looking at the STM32F407 datasheet again, you'll realize that the 192Kb SRAM actually consists of two on-chip SRAM, one of which is 128Kb while the other is 64Kb. By default, the Keil project doesn't include the second 64Kb into memory so you have to opt in that chip.

Now, try to compile the code again and you'll see the errors gone!

Ruby on Rails 2015-06-16

1. Route the pages.
(1) If you want to be able to route to your new view, open config/routes.rb and add the line

get 'view_name/index'

(2) If you want to set the default page to a certain, open config/routes.rb file, add

root 'store#index', as: 'store'

So the index will be routed to the index of controller store. The as: 'store' tells Rails to create a store_path accessor method.

2. yield method in view/layouts/application.html.erb. This method will render the content of the view that user is currently browsing. For example, if the user is browsing http://localhost/store, then the content of views/store/index.html.erb will be rendered in the yield section. Similarly, if the user is browsing http://localhost/products, then the content of views/products/index.html.erb will be rendered.

3. Did "rake test" but encountered five errors:
(1) AbstractController::Helpers::MissingHelperError: Missing helper file helpers//users/alexsun/documents/rubys/workspace/depot/app/helpers/application_helper.rb_helper.rb

(2) ProductsControllerTest#test_should_show_product:
ActionView::MissingTemplate: Missing template products/show, application/show with {:locale=>[:en], :formats=>[:html], :variants=>[], :handlers=>[:erb, :builder, :raw, :ruby, :coffee, :jbuilder]} 

(3) - (5) similar to (2), all are "Missing template"

I didn't see these error when I was using Ruby 2.2.0. But after that I switched back to Ruby 2.0.0 and then these error appears. I fixed them by changing my workspace name "Depot" to "depot" and all errors are gone. It seems to me a Ruby bug which is in Ruby 2.0.0 but fixed in Ruby 2.2.0.

Ruby on Rails 2015-06-15

Object-Relational Mapping

ORM libraries map database tables to classes. If a database has a table called products, the program will have a class named Product. Rows in the table correspond to objects of the class -- a particular product is represented as an object of class Product.

ActiveRecord is the ORM layer supplied with Rails. It closely follows the standard ORM model: tables map to classes, rows to objects, and columns to object attributes. By relying on convention and starting with sensible defaults, ActiveRecord minimizes the amount of configuration that developers perform.

To understand the ActiveRecord, here is the example:
In models/product.rb, a class Product is define:
class Product < ActiveRecord::Base
end

In db/migrate/xxx_create_products.rb, a class CreateProducts is define:
class CreateProducts < ActiveRecord::Migration
    def change
        create_table:products do |t|
        end
    end
end

By this way, Product has been mapped to the prodcuts table in the database. And the cool thing is that the Product calss that wrap the database table provides a set of class-level methods that perform table-level operations. To understand this, here is the example:
(1) find the product with a particular ID
product = Product.find(1)
(2) collect the objects whos name is 'dave'
product = Product.where(name: 'dave')
You don't need to care about how to manipulate the SQL query to get the data. Rails class wraps them for you and all you need to do is code like OO programming.

Ruby on Rails 2015-05-23

1. Rails provides a simple way to do data validation. The model layer is the gatekeeper between the world of code and the database. If a model checks the data before writing to the database, then the database will be protected from bad data. The source code is in app/models/xxx.rb. An example of validation is:
    validates :title, :description, :image_url, presence: true

2. Rails provides a test framework. The framework is in test directory. You can test the entire framework by:
    $ rake test
Unit test cases can be created in test/models directory, and you can test a particular test case file, e.g.:
    $ rake test:models

3. We use assertion to tell the framework whether our code passes or fails.  The simplest assertion is the method assert(), which expects its argument to be true, e.g.:
    assert product.invalid?, "DEBUG COMMENTS"
    assert product.errors[:title].any?

4. Fixture is a specification of the initial contents of a model under test. Fixture data is specified in the test/fixture directory. The name of the fixture file is significant. The base name of the file must match the name of a database table. The default for the test is to load ll fixtures before running the test, but again you can control which fixtures to load by specifying the following line in the test/models/xxx_test.rb:
    class ProductTest < ActiveSupport::TestCase
      fixtures :products
      ...
    end
The name of the fixture file determines the table that is loaded, so using :products will cause the products.yml fixture file to be used.

5. There are three databases that has been created in the configuration that scaffolding provides.
(1) db/development.sqlite3 will be the development database.
(2) db/test.sqlite3 is a test database.
(3) db/production.sqlite3 is the production database.
rake test command automatically gets a freshly initialized table in the test.sqlite3 database loaded from the fixtures we provide. Also we can do it separately by running rake db:test:prepare.