Fed Debate Shifts From Large Cut to Whether to Cut at All

Here is the link.

I like to write and also like to read. I just got an idea from CNBC video first what to search, and then follow up with 5 minutes reading.

The Federal Reserve’s debate shifted from how much to cut interest rates later this month to whether to move at all after hiring in June trumped the expectations of economists.

Yields on two-year U.S. Treasuries jumped to 1.87% from 1.76% the day before, reflecting reduced odds of the Fed aggressively reducing borrowing costs in the near term. Fed funds futures, which had been indicating some possibility of a half-point rate cut in July before the Labor Department’s data, are now pricing a quarter-point reduction this month, and at one point on Friday even showed that outcome was less than 100% certain.

Fed Chairman Jerome Powell, who has said uncertainties in the U.S. outlook could call for lower rates, will give his read on the job market next week in two days of semiannual testimony before Congress. The Federal Open Market Committee on July 30-31 will discuss whether the economy needs an “insurance cut” amid a slowing global economy, trade frictions and low inflation.

Officials will also take pains to stress that they’re not responding to political pressure. Despite what he termed “great jobs numbers,” President Donald Trump on Friday repeated his call for the Fed to cut interest rates, saying it would make growth “be like a rocket ship.”

“It is going to be a pretty well-debated meeting,” said Michael Feroli, chief U.S. economist at JPMorgan Chase & Co. in New York, who said a half-point cut is now off the table. “I think ultimately they ease because they signaled it so strongly. It is an insurance ease. The cost of such of an ease isn’t high because inflation doesn’t present any kind of near-term risk.”

“We continue to see rate cuts as the most likely outcome,’’ with 60% odds of a July quarter-point cut, 15% odds of a half-point reduction, and 25% odds of no policy change.

Fortinet interview questions

1. Maze
2. linked list
3. string manipulate  

1st round, phone interview, 2 hrs, 4 people from the same team, network questions, OS, Linux kernel, some behavior questions.
2nd round, on site interview, 2 hrs, 4 people from the same team, same as the first round, but an on site interview.
3rd round, programming test, linked list delete node, implement a system function, maze.

Multithreading and concurrency.
Memory layout of C program.
TCP implementation, like slow start and selective ack.
Basic L2,L3 load balancing strategy, like VRRP  


what is the typical flag to pass to a common kernel function call.

How to implement STL atoi? itoa?  

C, bit manipulation,.. 

Questions from linked list, string manipulation, balanced binary tree, maze problem, stack, queue.

Here is the link to read. 

Network fundamentals:

• HSRP/VRRP/GLBP and what the differences are and how they operate on an L2/L3 basis
• STP/RSTP/MSTP and what kind of implications there can be
• FabricPath,TRILL,VXLAN (concepts at least)
• vPC,MC-LAG,MLAG,Port-Channels
• Routing (EIGRP,OSPF,BGP at the least)

Security:

• What UTM is and how it works
• How does SSL work, how does SSL interception work
• Proxies (transparent vs explicit)

Troubleshooting:

• (this is one where experience really shines, maybe your internship was in TAC, in which case you may be somewhat ready for this)
• STP problems
• FHRP common problems
• Traceroute, how does it work? What protocol does it use?
• WireShark, learn it, love it, live it
• All the checksums are wrong in my wireshark capture, whats that about?

TCP: <-- prepare to get wrecked if they quiz you on this

Honestly this one is huge. TCP is a monster I've met very few people in my life who were actually good enough to know more than just the three-way handshake. Here's a few fun ones:

• TCP windows, what are they good for, what is the implication of a smaller window, what does it mean when the window is set to zero?
• Sequence numbers, how do they work?
• What are common flags on TCP packets (hint theres more than three)
• How does PMTU work?

This is a pretty short list, but these are some common things you may end up seeing. It is a security product, but it is also a network product so a lot of non-security related things may pop up (for instance I know at least one huge Fortinet customer that uses BGP on their boxes with ECMP).

How to solve algorithms problems?

Here is the link of the article. 

二、刷题
刷题是大部分基础不好的同学最头疼的部分，也是最容易出现误区的部分。我总结了三大影响刷题效率的误区：

• 不管三七二十一，撸起袖子就刷题。只要我有决心，一定可以铁杵磨成针！
• 刷题就是要看量大，只要刷满300题，Offer随我挑！
• 刷题就是啃硬骨头，不会的题想一天也要想出来！ vs 刷题就是背题，把题目背下来有一天自然会懂！

针对这三大误区，我有如下心得：

1. 刷题是以“数据结构和算法”相关知识为基础的
我看过很多地里的“刷题心得”，鼓吹勤奋至上论，号召一切找工作的人每天刷三题，坚持下去就有offer。我相信过，但实践效果很差。仔细思考之后，我认为是一种典型的不科学学习法。
我们学了这么多年习，都是先讲课再写作业。写作业从来都只是课堂知识的巩固。课堂知识是系统的，有层次递进的，相当于给房子打好地基和框架结构，而写作业是添砖加瓦。刷题就是写作业，对基本的数据结构和算法理解不深，只是知道个大概就刷题，实在是效率低。
我们可以先做一个大致的评估：请人在Leetcode所有分类tag里都随机抽取三道easy题（你并不知道题目类型），尝试一下：

• 题目都能做出来么？
• 如果做不出来，能看出来该用什么数据结构和算法么？
• 如果看不出来，到discussion看一遍高票回答，能看懂么？看懂了能独立再写一遍么？

如果做到了第一层，可以直接刷题，在刷题中学习；做到了第二、三层，还应该再复习一遍Cracking the Coding Interview或者相关资料，再动手刷题；第三层也做不到，应该在学校里面选一门经典入门的数据结构与算法相关课程，认认真真上一遍，再来刷题。

事实上，我认为第二层及以下，都可以考虑再上一遍数据结构与算法相关课程，有一个坚实的基础。没有拿到A，都不能算是学通了这门课。. 1point3acres
2. 刷题和量没有任何必然关系
我直到找到正职，一共只刷了162道题，其中Easy 64，Medium 83，Hard 15。这当然是有运气成分在里面的，但也侧面说明数目不应该被拿来衡量刷题的掌握程度。我个人认为按照这样的原则刷题是效率最高的：

• 刷一道题，会一道题。会一道题，是指这道题再出现在你面前千万次，你都能顺利的写出来，并且能够准确的分析时间复杂度和空间复杂度。
• 刷一道题，掌握一道题。掌握，不仅是能AC，而是要掌握最优解和经典解。比如一道题DP是最优解，你还应该用DFS写一遍，因为这也属于经典解。我身边有不止一个人面试的时候想写DP，被面试官要求用DFS，或者想用DFS，被面试官要求写DP。如果做题的时候没有融会贯通，这个时候就容易卡壳，追悔莫及。
• 针对薄弱类别集训。我刚开始刷题的时候，就是打开Facebook tag，按频率题。刷了一定量之后，发现自己的Tree和DP特别垃圾，又将这两个tag下的题集训了一波，每一题都想：这个Tree题跟上一个Tree题都什么不同？为什么不能用相同的方法？坑都在哪里？之后遇到这两个类型，解题率就高了很多。

如果按照以上原则，每天啥也不干就刷题，也不可能刷很多道。我状态不好的时候一天只能刷三道题，状态好的时候也就能刷七、八道。虽然刷题量很可怜，但我能感觉到我的AC率在以很快的速度上升。

3. 刷题不能死磕，也不能硬背
对不起说了一句废话……这其实因人而异啦，我觉得最适合我的高效刷题流程是这样的：

• 看题后思考5~10分钟：用什么数据结构？用什么算法？空间和时间复杂度是多少？是不是最优解？
• 如果有信心能写出最优解，或者觉得自己的解法值得一试：写题10分钟，debug最多5分钟
• 如果写不出来或感觉没想清楚：立刻看Discussion里面的最优解和经典解：分析空间时间复杂度，为什么是最优解，为什么能想到用这样的数据结构和算法
• 看完解答之后独立写一遍，不设时间，写到AC为止。期间如果想不清楚了，再重复上一步骤。
• 写完还是觉得懵懵懂懂，加入一个list，准备二刷

另外，背题也是可以有很大作用的，但硬背的效率就太低了，我的背题方法如下：. 1point3acres

• 实在连解答也看不太懂，就照着最优解敲一遍，或者一步一步的过一遍代码
• 在重要面试的前一天/几天疯狂背做过的tag题：不是背答案，是把每一题的思路和坑都过一遍，相当于在脑子里重新做一遍。这个方法对我来说相当管用。有些做过的题乍一看又不会了，但只要提醒一小点我就能想起来，那这“一小点”就是这题的关键，一定要记住。我面Facebook前一天背了一百五十多道做过的题，背到凌晨两点半，感觉比我刷半个月的题学得还多……毕竟温故知新嘛。

4.讲题比刷题更重要

光会做题不会讲，面试就容易出现“我的题目都做完了，也没有bug，但是没拿到offer”这样闻者伤心听者流泪的悲伤故事。讲题是有套路的，坚持以下这个流程：

• 拿到题，先问问题。没有问题也要憋出问题，比如数据类型，要不要考虑corner case，数据量多大，有没有时间要求blablabla
• 分析题：一般是暴力解 + 最优解的分析顺序。先说你拿到这道题之后的直觉解法，说完之后再“灵光一现”，说出最佳解法。如果你不确定这题怎么做，这个过程就更加宝贵，你要充分和面试官讨论这道题，征求他的意见和建议，直到讨论出一个双方都满意的解法。
• 写题：千万不要埋头苦写，每写完一个子模块都要跟面试官说一遍写了啥，为什么这么写。我曾经还用过一个小trick：有一道原题，之前刷题的时候有一个很细节的bug，我思考了很久才想清楚为什么要这样处理。写题的时候，我想像面试官展示这个细节的精妙之处，就故意写了bug，写完这个小模块之后假装沉思一下，再一副恍然大悟的样子跟面试官说“我突然发现这样处理虽然看起来是对的，但其实有个corner case……”。面试官其实根本就没注意到这有个bug，我解释了一会儿，还举了例子，他才发现这个处理的有趣之处。我相信这样他对我的印象更深刻了。
• 主动跑test case：写完之后，不要让面试官开口，而是主动说“那么现在我写完了，让我们来跑几个test cases，看看这个算法对不对”，面试官好感度立刻增加。

15-year-old tennis star upsets 5-time Wimbledon champ Venus Williams

Here is the link.

215. Kth Largest Element in an Array

I like to work on the algorithm in short future.

How Do Interest Rates Affect the Stock Market?

I plan to read the article when I have 10 minutes break.

I am thinking about stock market and my portfolio.

416. Partition Equal Subset Sum (similar to subset II)

I like to write a solution shared in the link.

416. Partition Equal Subset Sum (backtracking + pruning)

I like to write a solution based on this sharing.

Here is my C# practice usng backtracking and pruning.

It is kind of brute force solution, we like to try all combinations and then search the sum to see if it is the half.

The challenge part is to avoid time out. The idea to avoid time out is to sort numbers first, and then filter out extra search options based on current value compared to previous value.

I need to write a small case stduy to take about the analysis and design.

Run into time out limit exceeded error

The code ran into timout, and test case is [1, 1, ...., 1, 100], why it time out? Why should we skip the number if it is same as previous one?

Case study: [5, 1, 1, 1]

The idea is to sort the array first, and then start to work on depth first search. The array will be sorted as [1, 1, 1, 5], and then search a subset with sum = 4, start from index = 0.

One argument based on [1, 1, 1, 5] is that if the first integer 1 with smaller index = 0 cannot make it to find the sum, then second integer 1 will definitely not make it as well. Since the second one is subset of the previous one.

Here are highlights:

1. Work on DFS search, the idea is to sort the numbers first in order to avoid timeout;
2. Challenging task is to argue that the same integer can be skipped;
3. Only need to return true or false, no need to save the list of numbers to make the half of total sum.

I like to look into the issue why pruning is a must. Sorting takes O(NlogN) time, and then every integer can be selected or not selected, so it is O(2^N) time complexity to search the result.

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

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

        public bool CanPartition(int[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return false;
            }

            int total = numbers.Sum();
            if (total % 2 != 0)
            {
                return false;
            }
           
            Array.Sort(numbers); // write down a few words why sorting helps

            return runDFS(numbers, 0, 0, total);
        }

        /// <summary>
        /// a few words about the design
        /// DFS - depth first search
        /// Backtracking 
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="list"></param>
        /// <param name="position"></param>
        /// <param name="sum"></param>
        /// <param name="total"></param>
        /// <returns></returns>
        public bool runDFS(int[] numbers, int position, int sum, int total)
        {
            if (total == 2 * sum)
            {
                return true;
            }

            if (total < 2 * sum)
            {
                return false;
            }

            var result = false;
            var length = numbers.Length;

            for (int i = position; i < length; i++)
            {
                var current = numbers[i];
                if (i == position || current != numbers[i - 1])
                {
                    // add current to the selected numbers
                    result = runDFS(numbers, i + 1, sum + current, total);
                    if (result)
                    {
                        return true;
                    }                                        
                }
            }

            return false;
        }
    }
}

416. Partition Equal Subset Sum (2D DP)

I like to write a two dimension dynamic programming solution based on this discuss post.

416. Partition Equal Subset Sum

Here is my discussion post.

I have to review 0-1 Knapsack problem, so I google the topic and find two algorithms to review, Leetcode 518 and 416. I solved both of them, but I have not shared my practice yet.

I have some concerns about reasoning by reading my comment in the code. I should have written a small test case and explain the idea, and also prove that it is correct.

543. Diameter of Binary Tree

Here is my discussion post.

Lowest common ancestor in binary tree - Summary of interviews

July 4, 2019

Introduction 

I chose the tree algorithm called longest univalue path from August 2018. I spent three months to work on the algorithm in mock interview with a lot of engineers. But starting from May 2019, I choose the algorithm Lowest common ancestor instead. I have interviewed more than 15 times, I like to write some summary notes.

One tree algorithm

I have tried so many ideas to work on my problem solving skills. I hired a coach last June 2018 for two weeks, my friend told me that it is too expensive. She joined Facebook this May 2019. I know that the idea to work with a coach may not be a good idea. I have to be independent, be a problem solver. My friend just sent me an email through Linkedin.com, and ask me if I like to practice with her in 2018 when she prepares for Facebook interview. Being frugal is also very important in decision making.

I choose lowest common ancestor tree algorithm to interview on interviewing.io starting from May 2019. Since I could not learn backtracking and find the bug in my own code, I start to investigate how good people are in this industry.

I believe that this algorithm helped me tremendously. One thing I can do is to work on more algorithms, solve more problems. But learning and sharing experience through those mock interview hours are great.

I still remembered the feedback from hiring manager in top 100 software company I interviewed, he said that he does not ask the hard question like this in his interview.

I am getting better to interview senior engineers using this algorithm. Let me know if you like to practice together in the future, try this famous tree algorithm - Lowest common ancestor. I will help you find your weakness in tree algorithm problem solving.

How many hours to master a tree algorithm called lowest common ancestor?

July 4, 2019

Introduction

It is so interesting to add all those hours I have spent on Leetcode 236: Lowest common ancestor. I also learn to work on so many things related to tree algorithm, backtracking, recursive function design. Most exciting is to work with so many talent people in software industry in those mock interviews.

Lowest common ancestor

I have interviewed so many engineers in Sillicon Valley and Seattle area using lowest common ancestor algorithm. I just could not believe that I also learn so many things through interview practice.

516. Longest Palindromic Subsequence

Here is my post on Leetcode.com.

Two node's distance in binary tree

July 4, 2019

I like to share my practice on this algorithm related to lowest common ancestor. Here is the post I updated on Leetcode 236: Lowest common ancestor in binary tree.

Two node's distance in binary tree, the post is here.
My solution is written here. The idea is to find lowest common ancestor, and then calculate the distance between two nodes indirectly both to lowest common ancestor.
C# Lowest common ancestor -> two node's distance practice (upward)
C# Lowest common ancestor -> two node's distance practice

Minimum number of swaps required to sort an array

Here is the graph algorithm to learn. I just could not believe that it is a graph algorithm.

Minimum swaps to make two arrays identical

Here is the graph algorithm's link on geeksforgeek.com.

Graph problem is tough for me to figure out. I spent 10 minutes to think about, but I could not figure out how to convert it to a graph problem.

Here is the post I read on Leetcode.com about this algorithm, which is one of onsite algorithms in Amazon, Seattle.

• Write a program that given two anagram strings, returns the minimum number of swaps to turn one to the other. Similar to https://www.geeksforgeeks.org/minimum-swaps-to-make-two-array-identical/

Shortest path in an unweighted graph

Here is the link on geeksforgeek.com.

140. Word Break II

Here is my post I wrote based on my first practice back in 2018.

July 5, 2019

C# DFS with memoization practice in July 2019. Here is my C# practice.

139. Word Break

Here is my post on Leetcode.com. I learn that it is important for me to write something to share my practice.

Here is the copy of transcript of the post:

It is time for me to review the algorithm in July 2019. My first practice was in 2016.

Case study

I like to do a quick case study how to approach the algorithm using dynamic programming.
s="leetcode", wordDict = ["leet","code"].

dp = new bool[9]
empty string: "", return true; dp[0] = true
dp[1], "l", break into all possible suffix string, ""+"l", but "l" is not in dictionary. dp[1] = false;
dp[2],"le", work on "e", "le", both fails, dp[2] = false;
dp[3], "lee", work on "e","ee","lee", all of three fails, dp[3] = false;
dp[4], "leet", work on "e","ee","lee","leet", last one success, fp[4] = true;
...

Here are highlights:

1. It can be solved using dynamic programming solution with bottom up approach;
2. Search every possible suffix string from longest one to smallest on to see if it is in the word dictionary, and subproblem return true or not;
3. The code is not readable. Need to remove unused variable left, and also write very meaningful comment.

public class Solution {
    public bool WordBreak(string s, ISet<string> wordDict) {
         if (s == null || s.Length == 0)
                return false;

            int len = s.Length;

            bool[] cache = new bool[len + 1];
            cache[0] = true; // "" empty string 
           
            for (int i = 0; i < len; i++)
            {
                // "ab", "abc"
                // "a"
                // right string start position point index 
                for (int pos = i; pos >= 0; pos--)
                {
                    string left  = pos == 0 ? "" : s.Substring(0, pos);
                    //string right = s.Substring(pos, len - left.Length);   // bug001 - not len, should be i
                    string right = s.Substring(pos, i + 1 - left.Length);

                    if(cache[pos] && wordDict.Contains(right))
                    {
                        cache[i + 1] = true;
                        break;
                    }
                }
                
            }

            return cache[len]; 
    }
}

Case study: Victoria portfolio update

Case study: Portfolio Key Largo update

Case study: How to do a good research in six month?

July 4, 2019

Introduction

It is an interesting topic and I like to write about the good research. I believe that I did good research on personal finance from Dec. 2018 to July 4 2019. It is 9 month research, which involves a simple task to watch youtube.com video, review my bank statement, search all possible income last 24 years, and then frugality, minimalist, retirement, investment.

Case study

I like to put together something here to show case my research.

Case study: I got a message from Fortinet

July 4, 2019

Introduction

It is my personal finance research. I am so busy to work on algorithm practice and try to push hard to complete more algorithms, and I got a message from Fortinet. Amazing! I finally got contacted after 9 years in the city of Vancouver.

Case study

I like to write a case study what I should learn from this update.

Amazon phone screen - find shortest distance between two nodes in binary tree

July 4, 2019

I will write the solution, and also document how long it takes me to write the solution as well. Ideally I should be able to finish coding in less than 15 minutes.

My idea is the following:

There is more simple idea. Use post order to find all nodes on the path from given node p to root node, and save it into a hashset, and also a hashmap, key is treeNode, value is the distance to given node p; second call using given node q, and then do the same work as given node p, but this time, check all nodes from node q to root to see if it is in hashmap or not, if it is, then lowest common ancestor is found. Add current distance to distance from hashmap. Once the lowest common ancestor is found, do not forget to terminate search right away. It is deep in stack, need to return early.

Time complexity: O(N)

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

namespace binary_tree_two_node_distance
{
    class Program
    {
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        static void Main(string[] args)
        {
            var node0 = new TreeNode(0);
            var node1 = new TreeNode(1);
            var node2 = new TreeNode(2);
            var node3 = new TreeNode(3);
            var node4 = new TreeNode(4);
            var node5 = new TreeNode(5);
            var node6 = new TreeNode(6);
            var node7 = new TreeNode(7);
            var node8 = new TreeNode(8);

            node3.left = node5;
            node3.right = node1;
            node5.left = node6;
            node5.right = node2;
            node2.left = node7;
            node2.right = node4;
            node1.left = node0;
            node1.right = node8;

            var result = CalculateDistance(node3, node6, node4);
            Debug.Assert(result == 3);

            var result2 = CalculateDistance(node3, node7, node8);
        }

        public static HashSet<TreeNode> nodes = new HashSet<TreeNode>();
        public static Dictionary<TreeNode, int> map = new Dictionary<TreeNode, int>();
        public static int distance = -1;
        public static int countToP = 0; 

        /// <summary>
        /// July 4, 2019
        /// calculate two node's distance in binary tree
        /// write the answer for the post on Leetcode.com
        /// https://leetcode.com/discuss/interview-question/125084/Amazon-Distance-between-2-nodes
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public static int CalculateDistance(TreeNode root, TreeNode p, TreeNode q)
        {
            nodes.Clear();
            map.Clear();
            distance = -1;            

            postOrderTraversal(root, p);                     
            postOrderTraversal(root, q);

            return distance; 
        }

        private static bool postOrderTraversal(TreeNode root, TreeNode search)
        {
            if (root == null || distance > 0)
            {
                return false;
            }

            var left  = postOrderTraversal(root.left, search);
            var right = postOrderTraversal(root.right, search);

            if (root == search)
            {
                countToP = 0; 

                if(nodes.Contains(root))
                {
                    distance = 0;                    
                }
                else 
                {
                    nodes.Add(root);
                    map.Add(root, countToP);                    
                }

                return true; 
            }

            if (left == true || right == true)
            {
                countToP++;
                if (nodes.Contains(root))
                {
                    var value = map[root];
                    distance = countToP + value;
                    return false; // terminate early, protect distance value, caught by debugger
                }
                else
                {                    
                    nodes.Add(root);
                    map.Add(root, countToP);
                }

                return true; 
            }

            return false;
        }
    }
}