518. Coin Change 2

Here is my discussion post.

It is challenge to find all possible coin change and also avoid duplication. How to remove duplication? I like to do a case study on example 5, coins = [1, 2, 5] and then figure out how to do the work.

Case study 5, [1, 2, 5]
I like to work on example, amount = 5, coins = [1, 2, 5], all coin changes are the following 4 groups,
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

The reason I like to case studay the example because I studied one of solution using dynamic programming and memoization technique.

First, sort all coins in ascending order, so coins = [1, 2, 5].
Now we like to brute force all possible solutions for minimum coin value.
There are three cases, minimum coin is 1, or 2, or 5.

For each case, we like to solve the problem using subproblem,
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

Minimum coin value

The above four group can be put into two groups; one is minimum coin value is 1, the second one is minimm coin value 5.
The minimum coin value is 1:
5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 2 + 2

The minimum coin value is 5:
5 = 5

In order to solve the problem, I have to memorize two things, first is to brute force all minimum coin value in ascending order; inner loop is to exhaust all possible count of minimum coin used in the coin change.
minimum coin value has three options, 1, 2, 5.
For the minimum coin value = 1, there are five options, 1, 2, 3, 4, 5 of coin value = 1;

Subproblem definition
Amount = 5, Coins = [1, 2, 5]
F(Amount, Index)
Case 1: minimum coin is 5, index = 2
We only can use coin 5 to make value 5, so
F(0, 2) = 0
F(1, 2) = 0
F(2, 2) = 0
F(3, 2) = 0
F(4, 2) = 0
F(5, 2) = 1

Case 2 : minimum coin is 2, index = 1
F(0, 1) = 0
F(1, 1) = 0, the result is 2
F(2, 1) = 1
F(3, 1) = 0
F(4, 1) = 1, the result is 2 + 2
F(5, 1) = 0

Case 1: minimum coin is 1, index = 0

The idea is to use combinatorics knowledge to solve it first, and then translate the idea into C# code.

To avoid duplicated calculation, we like to define the subproblem F(amount, index), amount is the sum, index is the index of coin array.

Here is the code I chose to study. I like to write some study notes to help me learn the algorithm quickly.

public class Solution {
    /// <summary>
        /// June 20, 2019
        /// study code 
        /// https://leetcode.com/problems/coin-change-2/discuss/99239/C-DFS-with-memorization-of-course-DP-is-better
        /// </summary>
        /// <param name="amount"></param>
        /// <param name="coins"></param>
        /// <returns></returns>
        public int Change(int amount, int[] coins)
        {
            // order coins in order to prune recursion
            Array.Sort(coins);

            // init memorization to -1 (unvisited)
            var map = new int[amount + 1, coins.Length];

            for (int i = 0; i < map.GetLength(0); i++)
            {
                for (int j = 0; j < map.GetLength(1); j++)
                {
                    map[i, j] = -1;
                }
            }

            // DFS
            return CountUsingDepthFirstSearch(coins, amount, 0, map);
        }

        /// <summary>
        /// depth first search
        /// </summary>
        /// <param name="coins"></param>
        /// <param name="amount"></param>
        /// <param name="index"></param>
        /// <param name="map"></param>
        /// <returns></returns>
        private int CountUsingDepthFirstSearch(int[] coins, int amount, int index, int[,] map)
        {
            if (amount == 0)
            {
                return 1;
            }

            if (index == coins.Length)
            {
                return 0;
            }

            if (map[amount, index] != -1)
            {
                return map[amount, index];
            }

            int count = 0;
            for (int i = index; i < coins.Length; i++)
            {
                if (coins[i] > amount) break;

                // using this coin as many times as possible before going to next coin
                int times = 1;
                while (times * coins[i] <= amount)
                {
                    var nextAmont = amount - times * coins[i];
                    count += CountUsingDepthFirstSearch(coins, nextAmont, i + 1, map);
                    times++;
                }
            }

            // memorize
            map[amount, index] = count;
            return count;
        }
}

10 Year Treasury Rate - YCharts

Here is the article to read.

The last two times the S&P 500 did this, the market topped out

Here is the link.

The markets are having their best month since January.

But those gains have also pushed the S&P 500′s price-to-earnings ratio close to 17 times forward earnings, a valuation level that marked the top in May and last fall.

what is forward earnings? 

for the S&P 500,” Stockton said Monday on CNBC’s “Trading Nation. ” 

The S&P 500 is within 1% of hitting its 2,940 resistance level. It last touched above that level in early May.

There are enough positive catalysts in the market to keep the rally going, though challenges do remain, says John Petrides, portfolio manager at Point View Wealth Management.

“Where interest rates are and where inflation is, we still have room to run. I think we’ve been marinating one year now on tariffs and the earnings season upcoming is going to let us know if companies are able to navigate through the higher costs from tariffs given the slowdown in the global economy,” Petrides said during the same segment.

A potential rate cut from the Federal Reserve could push stocks higher, Petrides says, though the central bank needs to be clear on the reason behind any move.

“The market is already starting to bake in a 25-basis-point cut by the Fed but if they do 50 basis points and really surprise the market, then I do think stocks can go higher, assuming that the language isn’t the Fed is cutting 50 basis points because they see a pending recession,” said Petrides.

The Federal Open Market Committee convenes on Tuesday for a two-day meeting, culminating with a Wednesday afternoon decision. Markets anticipate a 25-basis-point cut at the July meeting, according to the CME Group fed funds futures.

Case study: My Key Largo portfolio on Ameritrade.com IRA

June 19, 2019

Introduction

It is my personal finance research. I was so ashamed of myself to only make $3,000 gain from 1998 to 2019 with total investment $16,000 dollars, I push myself to build a portfolio in less than one month, now the gain is $400 US dollars. I like to do a case study, and think about rebalance.

Case study

It is important for me to take some time to work on my personal finance. I like to spend time to sell 1 share VOO ETF and then purchase BND bond ETF.

Here is the blog I documented my purchase in June 2, 2019.

Docusign - a great company to do a case study

June 19, 2019

Introduction

It is my short study, I compare two public companies, one is I know long time called Ultimate Software, the second one is Docusign. I got contacted by the recruiter from Docusign first time in my life. I just could not believe it.

Case study

I like to spend time to study the public company, and also I like to push myself to learn about USA economy.

Follow up

June 22, 2020

I should purchase 100 share of Docusign stock. Now it is three time more compared to June 19, 2020.

Case study: My Victoria portfolio on questrade.com

June 19, 2019

Introduction

It is my personal finance research. I was so busy but I still made it happen. I set up my Vitoria portfolio less than one month ago. Now it is time for me to review, the return of $460.00 dollars in less than one month, should I rebalance to buy low and sell high?

Case study

Ideas to rebalance portfolio?

I like to sell 10 shares of VFV.TO, and then purchase VAB bond ETF. I like to buy low and sell high. 

Here is the blog I documented on June 4 to setup my portfolio.

Uber Is Going Public: How Today’s Tech I.P.O.s Differ From the Dot-Com Boom

Here is the link.

Fed scraps its 'patient' interest rate approach in prelude to potential cut

Here is the link.

I have to push myself to read more about personal finance and news related to stock market.

Investors have been betting the Fed will reduce rates at its next meeting in late July, though a majority of economists surveyed earlier this month don’t expect a move until December.

Facebook's digital wallet project head speaks with CNBC

Here is the link.

FLAG高频精选面试题讲解 - 31 algorithms

June 18, 2019

Here is the link.

17 Letter combinations of a phone number
23 Merge K sorted lists (hard level)
33 Search in Rotated Sorted array
56 Merge intervals
75 Sorted Colors
76 Minimum window substrings (hard level)
91 Decode ways 
124 Binary tree max path sum (hard level)
138 Copy list with random pointer
161 One edit distance


199 Binary tree right side view
200 Number of islands
219 Contains duplicate II (Easy)
220 Contains duplicate II
224 Basic Calculator (hard)
243 Shortest word distance
244 Shortest word distance II
245 Shortest word distance III
277 Find the celebrity
309 Best time to buy and sell stocks with cooldown

322 Coin change
450 Delete node in BST
481 Magical string
496 Next great element I
503 Next great element II
516 Longest palindromic subsequence
518 Coin change 2
560 Subarray sum equals K
632 Smallest range ( hard level)
652 Find duplicate subtrees


692 Top K frequent words

Algorithms to work on after Leetcode 377 combinations IV

I like to go over those Leetcode algorithms:

39, 40, 216, 322, 518, 474.

Leetcode 39: combination sum ( medium level)
Leetcode 40: combination sum II (medium level)
Leetcode 216: combination sum III (medium level)
Leetcode 322: coin change (medium level)
Leetcode 518: coin change 2 (medium level)
Leetcode 474: Ones and Zeros (medium level)

1090. Largest Values From Labels

1090. Largest Values From Labels C# Try to solve using greedy algorithm practice in 2019

It is one of medium level algorithms in the contest. The greedy algorithm may work out fine.

Here are highlights:

1. Use SortedDictionary to save all values and their label into SortedDictionary, the key of hashMap is the value, the value of hashMap is list of labels. Since the same value for same label may have duplicate, List is used to store labels;
2. Get all keys in SortedDictionary and save into the array; Iterate one by one using descending order;
3. Fail test case II (see function RunTestcase2()), I have to learn how to break two loops instead of one.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1090_largest_value_from_labels
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase2();
        }

        public static void RunTestcase1()
        {
            var values = new int[] { 5, 4, 3, 2, 1 };
            var labels = new int[] { 1, 1, 2, 2, 3 };

            var result = LargestValsFromLabels(values, labels, 3, 1);
            Debug.Assert(result == 9);
        }

        public static void RunTestcase2()
        {
            var values = new int[] { 5, 4, 3, 2, 1 };
            var labels = new int[] { 1, 3, 3, 3, 2 };

            var result = LargestValsFromLabels(values, labels, 3, 2);
            Debug.Assert(result == 12);
        }

        /// <summary>
        /// 1090 largest value from labels
        /// Use greedy algorithm to solve the problem
        /// Try to simplify the algorithm and do not think generic case
        /// </summary>
        /// <param name="values"></param>
        /// <param name="labels"></param>
        /// <param name="num_wanted"></param>
        /// <param name="use_limit"></param>
        /// <returns></returns>
        public static int LargestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit)
        {
            var sortedMap = new SortedDictionary<int, List<int>>();

            var length = values.Length;
            for (int i = 0; i < length; i++)
            {
                var key = values[i];
                var value = labels[i];

                if (!sortedMap.ContainsKey(key))
                {
                    sortedMap.Add(key, new List<int>());
                }

                sortedMap[key].Add(value);
            }

            var usedCount = new Dictionary<int, int>();

            int index = 0;
            var numbers = sortedMap.Keys.ToArray();
            length = numbers.Length;
            var sum = 0;
            var breakLoops = false;
 
            for (int i = length - 1; i >= 0; i--)
            {
                var key  = numbers[i];
                var list = sortedMap[key];

                foreach (var item in list)
                {
                    if (!usedCount.ContainsKey(item))
                    {
                        usedCount.Add(item, 0);
                    }

                    if (usedCount[item] < use_limit)
                    {
                        index++;
                        sum += key;

                        usedCount[item]++;

                        if (index == num_wanted)
                        {
                            breakLoops = true;
                            break;  // there are two loops 
                        }
                    }
                }

                if (breakLoops)
                    break; // caught by online judge, test case 2
            }

            return sum; 
        }
    }
}

1091. Shortest Path in Binary Matrix

1091. Shortest Path in Binary Matrix C# breadth first search practice in 2019

Breadth first search practice in 2019

It is a medium level algorithm. I came out the idea to use queue to do breadth first search, and also mark visited node in case of deadloop.

The problems I came cross are the following:

1. Read the statement carefully. I think that it should say explicitly that all nodes on the path should have value 0.
2. Minimum path should also be defined clearly. Count nodes not edges.

I think that the example 2 in problem statement should include a picture to show the path instead of just showing 4 as a result. In the contest, I could not figure out why it is 4. I draw the diagram in the following:

The above example 2 the minimum path is 4. So it is counting how many nodes on the path.

Here are highlights:

1. Design a data structure to store values in Queue, int[] is a good choice. I like to explicitly pass level to express minimum steps from (0,0) to the node;
2. Breadth first search, I like to apply search one level a time. All next level nodes are saved in the queue first;
3. Mark visited nodes using original matrix grid to avoid deadloop.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1091_shortest_path_in_binary_matrix
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// 1091 Shortest path binary matrix 
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public static int ShortestPathBinaryMatrix(int[][] grid)
        {
            if (grid == null || grid.Length == 0 || grid[0].Length == 0)
                return -1;

            var rows = grid.Length;
            var columns = grid[0].Length;

            if (grid[0][0] != 0 || grid[rows - 1][columns - 1] != 0)
                return -1;

            var queue  = new Queue<int[]>();

            var numbers = new int[] { 0, 0, 1 };
            queue.Enqueue(numbers);
            var maxLength = -1;
            
            // apply BFS, put next level into the queue, 8 possible neighbors
            applyBFS(grid, rows, columns, queue, ref maxLength);

            return maxLength;
        }

        /// <summary>
        /// visit neighbor with value 0, eight neighbors
        /// using breadth first search, use Queue
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="rows"></param>
        /// <param name="columns"></param>
        /// <param name="queue"></param>
        /// <param name="maxLength"></param>
        /// <returns></returns>
        private static void applyBFS(int[][] grid, int rows, int columns, Queue<int[]> queue, ref int maxLength)
        {
            if (queue.Count == 0)
                return;
            
            while (queue.Count > 0)
            {
                var count = queue.Count;
                int index = 0;

                while (index < count)
                {
                    var numbers = queue.Dequeue();
                    var row    = numbers[0];
                    var column = numbers[1];                    
                    var level  = numbers[2];                                      
                    
                    if (row == rows - 1 && column == columns - 1)
                    {
                        maxLength = level;
                        break;
                    }

                    var nextLevel = level + 1; 
                    // put 8 neighbors into queue
                    visitNeighbors(grid, rows, columns, row,     column - 1, queue, nextLevel);  // left
                    visitNeighbors(grid, rows, columns, row,     column + 1, queue, nextLevel);  // right
                    visitNeighbors(grid, rows, columns, row - 1, column,     queue, nextLevel);  // up
                    visitNeighbors(grid, rows, columns, row + 1, column,     queue, nextLevel);  // down
                    visitNeighbors(grid, rows, columns, row - 1, column - 1, queue, nextLevel);  // left top
                    visitNeighbors(grid, rows, columns, row + 1, column + 1, queue, nextLevel);  // right down
                    visitNeighbors(grid, rows, columns, row + 1, column - 1, queue, nextLevel);  // right top
                    visitNeighbors(grid, rows, columns, row - 1, column + 1, queue, nextLevel);  // left down

                    index++;
                }
            }
        }

        /// <summary>
        /// mark visited using -1 and save the value in grid matrix
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="rows"></param>
        /// <param name="columns"></param>
        /// <param name="row"></param>
        /// <param name="column"></param>
        /// <param name="queue"></param>
        /// <param name="level"></param>
        private static void visitNeighbors(int[][] grid, int rows, int columns, int row, int column, Queue<int[]> queue, int level)
        {
            if (row < 0 || row >= rows || column < 0 || column >= columns || grid[row][column] < 0 || grid[row][column] != 0)
                return;

            var numbers = new int[] { row, column, level };

            grid[row][column] = -1; // mark visited

            queue.Enqueue(numbers); 
        }
    }
}

377. Combination Sum IV

Here is the link.

I think that bottom up dynamic programming solution is best one to solve this algorithm. I need to warm up the algorithm using a simple example.

Case study [1, 2, 3] with target = 4

Let me work on example [1, 2, 3], given target = 4, how to solve the problem (The answer is 7)? l like quickly to go over each step and find the answer. I believe that will help me warm up dynamic programming solution bottom up, and master the algorithm.
number:
[1, 2, 3],
target = 4
all combinations:
(1,1,1,1)
(1,1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Observations

The order is important.

Two one, one two has three combinations; one is (1, 1, 2), another one is (1, 2, 1), and the third one is (2, 1, 1).
One one, one three has two combinations; one is (1, 3), another one is (3, 1).

First, given target = 4, let us declare dp (prefer a short name to explain) array with size 5, why? Since target has five values, 0, 1, 2, 3, 4.

Bottom up

Let us set dp[0] = 1, why? Because empty set is only option for value 0.
what is dp[1]?
We can exhaust all numbers in original array, which one can be added to set and then increase the value to 1, based on dp[0] = 1.
Only second element is value 1, so dp[1] = 1;
dp[2] has two options, element 2 with dp[0] or element 1 with dp[1], so dp[2] = 2;
dp[3] has three options, element 3 with dp[0] or element 2 with dp[1] or element 1 with dp[2], so dp[3] = dp[0] + dp[1] + dp[2] = 4;
dp[4] has three options, we only have 3 values, [1, 2,3], 4 is not in the array; Element 3 with dp[1] or element 2 with dp[2] or element 1 with dp[3], so dp[4] = dp[1] + dp[2] + dp[3] = 1 + 2 + 4 = 7.
In other words, I can write down those bottom up formulas in the following using F function:
F(0) = 1
F(1) = F(0)
F(2) = F(0) + F(1)
F(3) = F(0) + F(1) + F(2)
F(4) = F(1) + F(2) + F(3)

Top down

In other words, I can write down those bottom up formulas in the following using F function:
F(4) = F(1) + F(2) + F(3)
F(3) = F(0) + F(1) + F(2)
F(2) = F(0) + F(1)
F(1) = F(0)
F(0) = 1

I believe that the above exercise will help me to find pattern to apply dynamic programming using bottom up, and also I can quickly write a solution to match the example in the following.

Here are highlights:

1. Declare dynamic programming target array int[target + 1];
2. Set base value dp[0] = 1;
3. Go over target value i variable from 1 to target, bottom up, find all ways to form sum with value i, how to do the work?
4. Step 3, go over every element in the array, check if the element can be last one to be added, if it true, then subproblem with sum value is found.
5. Warm up the dynamic programming using simple example, shown my above analysis.

public class Solution {
    /// <summary>
        /// Leetcode 377 - combination sum 
        /// bottom up - dynamic programming 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int CombinationSum4(int[] nums, int target) {
            var combinations = new int[target + 1];

            combinations[0] = 1;

            // go over all options
            for (int i = 1; i < combinations.Length; i++)
            {
                for (int j = 0; j < nums.Length; j++)
                {
                    var number = i - nums[j];

                    if (number >= 0)
                    {
                        combinations[i] += combinations[number];
                    }
                }
            }

            return combinations[target];
        }        
}

Why it is so important to be frugal?

June 17, 2019

Introduction

It is my personal finance research. I like to write a topic about frugal leads to a happy life.

Case study

I am working hard to build wealth. But I am over 50 years old, still rent a small bedroom in the city of Vancouver starting from June 2010 to June 2019.

377. Combination Sum IV

Here is my post.

It is time for me to learn how to master a dynamic programming algorithm called 377 Combination Sum IV. What I can do is to list all practices I have practiced in 2019, and later on, I will ask the algorithm in mock interview on interviewing.io, so I can explore more solutions and learn better from top talents in the world.

Recursive solution with timeout issue, here is the link.

Dynamic programming, top down, memoization, here is the link.

Dynamic programming, bottom up, here is the link.

These stocks are ‘undervalued,’ Wall Street analysts say

Here is the link.

BUSINESS LEADERS RICH & POWERFUL Peter Lynch

Here is the link.

10 Tips for Successful Long-Term Investing

Here is the link.

How To Double Your Money Every 6 Years

Here is the link.

How to build real-time applications using WebSockets with AWS API Gateway and Lambda

Here is the article to read.