逆序对问题的基础算法

 Here is the article. 

现在终于可以介绍树状数组（Binary Indexed Tree）。树状数组这个中文名称比英文Binary Indexed Tree好很多，因为树状数组用起来跟普通数组差不多，而对tree进行索引访问很奇怪，如tree[2]=10。树状数组有两个独特性质：

1. 树状数组设置值的复杂度为O(log n)。
2. 对树状数组任意区域求和的复杂度为O(log n)。

基于以上特性，我一般在代码中按其功能写成QuickSumArray，而不是Binary Indexed Tree或中文树状数组。

493. Reverse Pairs

 Here is the discussion link I read after I thought about the solution by myself over 10 minutes. 

Hard level algorithms: Life is tough to work with those hard level algorithms

 Oct. 6, 2020

Introduction

I like to invest time to learn 50 hard level algorithms on Leetcode.com. What I like to do first is to learn ideas how to solve them, and seek some good ideas to build strong analytical skills first. 

Hard level algorithms

I have limit time to work on those hard level algorithms, so I like to figure out how to learn better. 

AMWELL stock: IPO in Sept 2020

 My friend advised us to purchase IPO stock in Sept. Now it is up 50%. 

I should look into the stock early. Be positive and buy some IPO stocks. 

PPSI stock: Gambling 10x more it's capital value in a few hours

 Oct. 6, 2020

Introduction

One of us in wechat group told us that she made $20,000 US dollars on PPSI stock, and get in and out six times. I like to do a short case study on this stock. 

PPSI stock

Capital value is 41.885 Million dollars, today it went up 300%. Original the value is around $15.00 million dollars. The volume is around 319,981,400. More than 10 times more total capital value. 

So many players rushed to buy and sell. 

Website project: Html script extra close div - Remove a menu causing crash

 Oct. 6, 2020

Introduction

It was two weeks ago that I was so busy to make so many changes on the website, I was asked to remove uplight from the website, and then after a while, I was told that website was not responding. 

Nervousness

I was so nervous since I did not have any issue over last 12 months. I went back to check IIS event view log, and also I tried to rollback every change to see which one to cause the problem. 

My coworker reminded me that it happened just after I removed the uplight. 

Code change

I rollbacked the change to remove a row in the table WebsiteMainMenu. I turned off the cache of the table, and Monday morning I went to work, the coworker told me the page was really slow. 

I quickly fixed the cache issue. I also rewrote the code for Main Menu setup written in C#. 

Here is my project folder. 

I like to work on my project management skills, and also I have to review my own code and take some time to make it more robust. 

Stocks with 10% increase: Oct 2 - Oct. 6, 2020

 Oct. 6, 2020

Introduction

I missed 10% increase from Oct. 2 to Oct. 6, 2020. I like to write about 10% increase. 

10% increase

I bet on MRO stock 1000 share, but I failed to get rebound and sold with $180 dollars loss. And MRO price went down last Friday. I thought about purchase back, actually it is time. 

For gambling, it is bet to have a rebound. I tried so many times, and I thought about blackswan, and another 20% pullback, so I did not try to recover my loss. 

Today I checked the following stocks all having 10% rebound:

SU, MRO, OXY, NCLH, AAL, SQ

I think that it is gambling which makes stock market always attractive. It is easy to get addicted. I did try to catch rebound so many times after August 31, 2020, but I failed all the time. I decided to quit, and then it has 10% rebound. 

Behavior problems

I was panic since the market will have another 20% to 30% pullback. In my Ameritrade.com account, all my gains of $3000 from May 2019 to June 8 2020 are gone. I am betting on my capital. 

It takes some risk to make 10% profit. 

I lost over $500 dollars on INTC stock, if I just hold another month, today it went back around $52.20 dollars. I should learn from the lesson to hold longer. 

I did not make profit on 240 shares of NCLH, but if I hold until today at $17.78, then I will make profit $1.1 for each share. I sold too early. Even if it is short term investment, I also need to learn to take risk to hold longer. I should learn sentimental in the market, and take loss and hold longer those position. To be successful, I also need to learn more about renting out those shares if needed. 

Case study: Find maximum number of living people

 Here is the gist. 

Leetcode discuss: 301. Remove Invalid Parentheses

 Here is the link. 

C# Understand difference between return all valid strings and any valid string

Oct. 5, 2020
301. Remove Invalid Parentheses

Introduction
It was my 10:00 PM mock interview on Oct. 4, 2020. I started to prepare Google phone screen, and I have 12 free mock interviews as interviewee on interviewing dot io website. I was asked to solve the similar algorithm as hard level 301 find all valid strings, except only return one valid string. The solution can be super simple and quick to solve using less than 15 minutes.

My approach
I did come out the idea using stack to find invalid paretheses by going through once, but I did not take the hint, and then went for breadth first search and start from removing one char until a valid string is found. The solution to find only one valid string is linear time, but the following breadth first search algorithm time complexity is O((m + 1)! n), m is total number of paretheses, and n is the length of string.

After the mock interview
I quickly modified my code and then submitted as the answer of hard level 301 algorithm. The code passes all test cases. I like to write down some lessons I learned through the practice.

Highlights of discussion in mock interview of my implementation:

1. Time complexity, if the string is 10 of open paretheses, "((((((((((", and then each index position will have to be considered to be removed, 10 substrings will be added to queue, next round each string has length of 9, 9 subsring will be added to queue for each of them, so total is 10 * 9, therefore, the total of string is 10!. The interviewer corrected my estimation of time complexity: not O(m * n), should be O((m + 1)! * n), whereas m is total number of paretheses, n is length of string.
2. Duplicate removal - inside while loop, the second for loop start index should be bigger than previous one - parent string. More detail not "j = 0", should be "j = item2" saved from Queue.
3. Inside while loop, the second for loop, the string to enqueue should start from j, not j + 1, since j position's char is removed.

My performance on mock interview
I did some analysis based on a few simple test cases first, and then I told the interviewer that I like to write code to make sure those few simple test cases working at least.

// bfs -> VALID BRUTE FORCE
// ONCE - SHOULD BE Minimum number
// BFS ->
// ()() -> ok
// (() -> remove one, index 0 or 1 -> find valid (), remove open
// ()(( -> remove two,
// check not valid
// 0 )(( -> queue
// 1 (((
// 2 ()(
// 3 ()( -> queue
// ------------------------
// 0 )(( -> queue
// 1 (((
// 2 () -> valid string found!
// 3 ()( ->
()()))
--
)()))

---

Feedback I like to look into

It takes me long time to master this hard level algorithm: 301. Remove Invalid Parentheses. Without practice and help from interviewers, it will take me more time to understand my weakness. I like to work on my communication skills as well besides coding and analysis, requirement gathering.

Here are some feedbacks I like to think about after the mock interview:
Help your interviewee get better!

1. The interviewee proposed a stack solution, which is in the right direction of the optimal solution, but she then dropped it and proposed a BFS solution. The BFS solution is sub-optimal as it would take more space.
2. Once the interviewer explicitly mentioned the proposed solution makes sense and can go ahead with implementation, it would be better for the interviewee to jump into the implementation instead of spending extra time on explaining the idea more.
3. During implementaion, the interviewee considered the edge cases, such as empty input and 0-length string.
4. The actual implementation is sub-optimal in terms of time complexit.
5. The code can be cleaner. The inconsistent indentation hurts the readability of the code.
6. The interviewee proactively thought of more efficient optimization based on the original solution, though the improvement introduced bugs.
7. The time and space complexity based on the implementation should be at the scale of factorial instead of polynomial.

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

namespace _301_all_valid_paratheses
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = RemoveInvalidParentheses("(a)(b(a)"); 
        }

        /// <summary>
        /// Oct. 5, 2020
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static IList<string> RemoveInvalidParentheses(string s)
        {
            if (s == null || s.Length == 0)
            {
                new string[] { "" }.ToList();
            }
    
            if(isValid(s))
            {               
                return new String[]{s}.ToList() ; 
            }

            var set = new HashSet<string>(); 
            // queue - BFS - save index position of open or close parentheses
            // index - int[], size - 2, index position - second - 0, close 1
            // Tuple<string, int>
            var queue = new Queue<Tuple<string, int>>(); 
            queue.Enqueue(new Tuple<string,int>(s, 0)); 
            
            // (a)b)
            // ()((
            //  - 
            // ((((((( -> 
            // O(m * m * N * N) - 
            // m is how many strings (count of parenthese), n is size of string - 4
            // space -> queue O(m! * n) - m is count of parent chars in string 
            // m + m*(m-1) + m(m-1)(m-2) + ... + m!
            // m* m!= (m+1)! loosely upper bound
            // 10 -> 10*9 -> 10*9*8 
            // 10 -> 10: 9 -> 90: 8
            while(queue.Count > 0)
            {
                // BFS  - every string will be check - O(m) count of parenthese < N
                var count = queue.Count; 
        
                for(int i = 0; i < count; i++)
                {
                    //(a)b)
                    var current = queue.Dequeue(); 
                    var item1 = current.Item1;
                    var item2 = current.Item2;
            
                    //  O(N * N)
                    for(int j = item2; j < item1.Length; j++) // (
                    {
                        var c = item1[j];
                        var isPare = c == '(' || c== ')';
                
                        if(isPare)
                        {
                            var tmp = item1.Substring(0, j) + item1.Substring(j + 1, item1.Length - j - 1);
                            if(isValid(tmp))
                           {
                               set.Add(tmp);                               
                           }
                           else 
                           {  // one char shorter 
                              queue.Enqueue(new Tuple<string, int>(tmp, j)); 
                           }
                       }                       
                    }            
                }

                if (set.Count > 0)
                {
                    break;
                }                                  
            }

            return set.ToList(); 
        }

        // O(N) - N length of S                       
        private static bool isValid(string s)
        {
          if(s == null || s.Length == 0)
            return true;
                           
          int openCount = 0;                           
                           
          for(int i = 0; i < s.Length; i++)
          {
             var c = s[i];
             if(c == '(')
             {
              openCount++;
             }
             else if(c == ')')
             {
                if(openCount == 0)
                {
                  return false;
                }
                                   
                openCount--; 
             }
          }
                           
          return openCount == 0; 
        }
    }
}

NextEra stock: How NextEra Overtook ExxonMobil As The Largest U.S. Energy Company

 Here is the link. 

If you had invested in Florida-based utility NextEra Energy NEE +2% a decade ago, your total return through this week, including dividends, would have been 600%. That is a phenomenal return for an energy company.

I bought FPL stock in 2001, but I sold all of them and held less than two years.