Grid Traveler or Unique Paths

The weather is acting somewhat erratic. Today the forecasted high in the Twin Cities of Minneapolis and St. Paul will be 20F lower than yesterday. Tomorrow it should be 10F lower than today and should be raining. The water level in pond in my backyard is very low. Some rain should help. I noticed that a couple of cranes have made their home for summer the pond. Not sure if they are the same that return every year or they are an offspring of the ones from last year. I do not know much about cranes.

Since the weather will be nice today; my wife and I will go for a walk after the end of the workday. Not sure what we will do tomorrow. Perhaps we will go to the Mall of America.

On a different note, as you might know, I work in 2-hour blocks. After each block I go up and get something to drink. A few minutes later I head back to work. A few weeks ago I moved a stationary bike from a utility room and set it up in the lower level living room. I started biking for 5 minutes after completing a 2-hour block. That is working very well. I get between 20 to 25 minutes biking each workday. Since the bike is indoors I can do it year round. Continue reading “Grid Traveler or Unique Paths”

Sam and Substrings

It is a sunny Tuesday in the Twin Cities of Minneapolis and St. Paul. The earlier forecast was calling for thunderstorms. I just check the revised forecast and it seems that we might have some rain after dark. That is good news because my wife and I are invited to our oldest son’s house today to have the next version of the burgers we had last Saturday as I commented on the Roads and Libraries post. Will let you know tomorrow how it goes.

As I mentioned in a previous post, a few weeks ago I had elective surgery performed on my left knee. All is going very well with the recovery process. So far most of the physical therapy sessions have been on Tuesdays and Thursdays towards the end of the day (04:30 PM or 05:00 PM). Today the session is at 01:30 PM. My wife changed our daily lunch schedule to accommodate it. We will be having lunch after therapy.

Yesterday we spoke over Skype with a couple friends of us that live in Peru. Things are not going well in Peru or Latin America in general. Seems that communism is creeping at alarming rates. In the next presidential elections to be held on June 06, 2021 there are two candidates. One candidate represents the right and the other the left. The left has mandated voters in different places to take a picture of their secret ballot to allow party representatives to verify that the votes are for the communist candidate. If voters refuse their lives would be in danger. Not much to say about a secret and fair election!

Of course the bottom line is always money. In this case some foreign nations will benefit by getting several mines at a much discounted price. It seems like a repeat of what transpired and is still going on in Venezuela. Such is life. Continue reading “Sam and Substrings”

Roads and Libraries

Good morning! It is a foggy Sunday morning in the Twin Cities of Minneapolis and St. Paul. In the past week or so the mornings have been sunny. That said, the forecasted high for the day is 76F. If the fog clears and with sun shine we might be a couple degrees warmer.

Yesterday the high temperature was forecasted to be 70F. My wife and I stopped by our older son place. He lives in Lakeville which is about 15 minutes away by car from our place.

We spent a few hours outside chatting and drinking a couple adult drinks while he was cooking some delicious burgers. He enjoys grilling and smoking meats. In the past couple weeks he decided to meet or better yet, improve on a butter burger sandwich from Culver’s.

I am not going to get into the details but in my opinion the burgers he made were a notch better than the ones from the food chain. That said, my wife and I would have cooked them no more than one minute per side. My son likes burgers very well done while we prefer them just done. He did not only cook the burgers, but in addition served them with all the trimmings and in waxed paper in the shape of a bag. We all had a good time. Today my wife and I will grill steaks but next week, we will do burgers with all the trimmings. We will be skipping the paper bag! Continue reading “Roads and Libraries”

Largest Triple Products – Revisited

!!! UPDATE UPDATE UPDATE !!!

I received a comment indicating an issue with the largestValues() function. The issue has been corrected. The code has been updated. Thanks for noting the issue.

Good morning! It is 04:15 AM and it is a relatively warm day. Last evening before going to bed I decided to hopefully get up a little earlier than usual. I have a permanent alarm on my phone for 06:00 AM. I use it as a fail-safe in case I do not naturally wake up before. Today I wanted to get this post done and take a look at a test I left running overnight. My wife has a doctor’s appointment early today and it is a 45 minute drive from home. She has to fast so I will follow suit. We should be leaving home around 06:45 AM.

On a separate note, I visited the ProtonMail web site. As we all know there are companies that offer free email services. They have redefined what the word free means. The cost is quite heavy regarding your privacy. In the past couple weeks I have been reading about email services. My wife and I are contemplating on opening accounts on a service in the near future. When that happens, you will see a new email address at the bottom of the posts. Continue reading “Largest Triple Products – Revisited”

Halloween Party in Java

Today is January 21, 2021. Yesterday was the United States presidential inauguration. As you know I do not like politics. That said; I like facts so later when something does not seem right I will be able to make my own educated decision as to what the real reasons were for  the results we are observing. That said; I would invite you to find out about the executive orders signed yesterday by Joe Biden. Then put aside your political associations, and think what would the effects of the executive orders be for the future of the USA and for the citizens of the USA and the free and democratic world?

As I was generating this post I checked and the blog has exceeded the 6,000 followers mark!!! Thank you all for making this happen. Hopefully it is having some type of positive impact on your learning journey. Continue reading “Halloween Party in Java”

Can you solve it? Java Solution

Good morning. Hope you are doing well. It is a dark, foggy and cold morning in the Twin Cities of Minneapolis and St. Paul. I woke up around 05:00 AM. I finished reading the article Does Facebook Use Sensitive Data for Advertising Purposes? article in the Communications of the ACM magazine. I though the article was interesting. Apparently Facebook has a set of several thousand categories of which up to 1000 can be applied to each user. Not sure if there is an opt out setting. The authors of the paper suggested a tool that can be used in a couple browsers to check and delete the advertising labels assigned to your account. Continue reading “Can you solve it? Java Solution”

Spiral Matrix – Revisited

Good morning. Hope your day is starting on the right note. Yesterday was a long and busy day. Something at work stated on Saturday extended at least through yesterday. I spent a lot of time on the phone, browsing code and looking at log files. It seems we know what is causing the problem. Currently I am in the midst of formulating approaches to address the issue. Hopefully all will be solved by tomorrow.

On a separate note, yesterday I had the opportunity to meet on-line a software engineer that works at a large software company. You never know what the future has reserved for you. Continue reading “Spiral Matrix – Revisited”

Inorder Successor in BST

As you might know, I work on 2-hour blocks. At the end of a block I go upstairs and get something to drink. I chat with my wife for a few minutes and then head downstairs to my office for the next 2-hour block. I just got back and was about to start a new task when I noticed that I had not finished a post I started earlier today. Will finish it right now and will post it. Then I will move on to the next task.

This morning we woke up to a balmy 11 F degrees. The good thing about the COVID-19 pandemic is that we can work from home and do not have to deal with the car and parking. I fully understand that is nothing to what other people are going through. Hopefully we will be getting a vaccine in the next few months. If all goes well we might start going back to something that resembles how things were before the pandemic. Continue reading “Inorder Successor in BST”

Sherlock and GCD

It is a Monday morning and it is garbage collection day so I had to put out on the driveway both bins. The company that provides our development with the service collects every week both garbage and recycle bins. All previous companies that I am familiar with collect garbage every week and recycle every other week. To be honest with you, my wife and I would be fine with recycling once a month and if it was not for the potential for smell during summer, garbage every other week.

Earlier this morning, I saw in my inbox a recommendation for a problem from HackerRank named Sherlock and GCD which maybe solved with a Dynamic Programming approach. Continue reading “Sherlock and GCD”

Number of Visible Nodes

!!! UPDATE – UPDATE – UPDATE !!!

I have been asked several questions on this post. Given that you are not able to submit your solution and be tested against dozens of test cases in order to determine [1] if you have properly understood the problem or [2] generated an acceptable solution to the properly understood problem.

Since there is no interviewer at hand that you can ask questions to clarify the problem, please read the requirements and decide what the requirements are.

There is a binary tree with N nodes.
You are viewing the tree from its left side and can see only the leftmost nodes at each level. 
Return the number of visible nodes.

Note: You can see only the leftmost nodes, but that doesn't mean they have to be left nodes. 
The leftmost node at a level could be a right node.

Input
The root node of a tree, where the number of nodes is between 1 and 1000, 
and the value of each node is between 0 and 1,000,000,000

An int representing the number of visible nodes.

MY INTERPRETATION is that when I view the tree from the left side I will be looking at the first visible node in each level. The node may be a right or a left child. The note in the description seems to corroborate my thoughts.

MY APPROACH is to perform a DFS traversal. The node we can see from the left will be the first non-null node at each level. In addition, we could get the depth of the tree and it should provide the SAME answer given that no matter which side we look from (left or right) the same number of nodes should be visible.

3,null,5,7,null
main <<< arr: [3, null, 5, 7, null]
main <<< bfs:
3
null 5
7 null
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
3
5
7
main <<<        level: 3


3,2,5,1,4
main <<< arr: [3, 2, 5, 1, 4]
main <<< bfs:
3
2 5
1 4 null null
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
3
2 5
1 4
main <<<        level: 3


8
3 10
1 6 null 14
null null 4 7 null null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
8
3 10
1 6 14
4 7
main <<<        level: 4


1,2,3,null,5,null,7
main <<< arr: [1, 2, 3, null, 5, null, 7]
main <<< bfs:
1
2 3
null 5 null 7
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
1
2 3
5 7
main <<<        level: 3


5
4 8
11 null 17 4
7 null null null 5 null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
main <<<        level: 4


5
4 8
11 null 17 4
7 null null null 5 null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
main <<<        level: 4


5,4,8,11,null,17,4,7,null,null,null,5,null,null,null,20,30
main <<< arr: [5, 4, 8, 11, null, 17, 4, 7, null, null, null, 5, null, null, null, 20, 30]       
main <<< bfs:
5
4 8
11 null 17 4
7 null null null 5 null
null null 20 30
main <<< visibleNodes: 5
main <<<        depth: 5
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
20 30
main <<<        level: 5


5,4,8,11,null,17,4,7,null,null,null,5,null,null,null,20,30,100,101,102,103
main <<< arr: [5, 4, 8, 11, null, 17, 4, 7, null, null, null, 5, null, null, null, 20, 30, 100, 101, 102, 103]
main <<< bfs:
5
4 8
11 null 17 4
7 null null null 5 null
null null 20 30
100 101 102 103
main <<< visibleNodes: 6
main <<<        depth: 6
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
20 30
100 101 102 103
main <<<        level: 6


1,2,3,4,5,6,7,null,null,null,null,null,null,null,8,null,9,10,null
main <<< arr: [1, 2, 3, 4, 5, 6, 7, null, null, null, null, null, null, null, 8, null, 9, 10, null]
main <<< bfs:
1
2 3
4 5 6 7
null null null null null null null 8
null 9
10 null
main <<< visibleNodes: 6
main <<<        depth: 6
main <<< bfs (no null nodes):
1
2 3
4 5 6 7
8
9
10
main <<<        level: 6


8,3,10,1,6,null,14,null,null,4,7,13
main <<< arr: [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
main <<< bfs:
8
3 10
1 6 null 14
null null 4 7 13 null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
8
3 10
1 6 14
4 7 13
main <<<        level: 4


8,3,10,1,6,null,14,null,null,4,7,13,15
main <<< arr: [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13, 15]
main <<< bfs:
8
3 10
1 6 null 14
null null 4 7 13 15
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
8
3 10
1 6 14
4 7 13 15
main <<<        level: 4


10,null,15,null,5
main <<< arr: [10, null, 15, null, 5]
main <<< bfs:
10
null 15
null 5
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
10 
15
5
main <<<        level: 3

The test cases contain tree values. The first is the one returned by performing a BFS tree traversal and counting the number of levels. The second is a method that returns the depth of the tree. The third pass is a BFS traversal so we can count the nodes we see from the right or left in the binary tree. The null values are no longer displayed because they do not exist as far as nodes in a binary tree. Unless I am missing something; all values should be the same.

    /**
     * Test scaffolding.
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered stream ****
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        // **** read and split input line ****
        String[] strArr = input.readLine().split(",");

        // **** close buffered reader ****
        input.close();

        // **** create and populate integer array (may contain null) ****
        Integer[] arr = new Integer[strArr.length];
        for (int i = 0; i < strArr.length; i++) {
            if (strArr[i].equals("null"))
                arr[i] = null;
            else
                arr[i] = Integer.parseInt(strArr[i]);
        }

        // ???? ????
        System.out.println("main <<< arr: " + Arrays.toString(arr));

        // **** create and populate binary tree ****
        TreeNode root = populateTree(arr);

        // ???? ????
        System.out.println("main <<< bfs:");
        System.out.print(bfsTraversal(root));

        // **** compute and display number of visible node ****
        System.out.println("main <<< visibleNodes: " + visibleNodes(root));

        // **** find and display the depth of the BT ****
        System.out.println("main <<<        depth: " + maxDepth(root));

        // **** find and display level of BT ****
        System.out.println("main <<< bfs (no null nodes): ");
        System.out.println("main <<<        level: " + levelOrderTraversal(root));
    }

This is the test case. I believe this is the same as in the original post but with an additional computation.

    /**
     * Count visible nodes in binary tree.
     * Recursive call.
     * O(n)
     */
    static int visibleNodes(TreeNode root) {

        // **** base condition ****
        if (root == null) return 0;

        // **** recursive call(s) ****
        return Math.max(visibleNodes(root.left) + 1, visibleNodes(root.right) + 1);
    }

This is the same code as in the original post. It returns the number of visible nodes including some of the null values which indicate the place of a missing node.

    /**
     * Given a binary tree, find its maximum depth.
     * Recursive function O(log(n)).
     */
    static int maxDepth(TreeNode root) {
        
        // **** base condition ****
        if (root == null)
            return 0;

        // **** initialize the BT max depth ****
        int depth = 0;

        // **** visit left node ****
        depth = Math.max(depth, maxDepth(root.left) + 1);

        // **** visit right node ****
        depth = Math.max(depth, maxDepth(root.right) + 1);

        // **** return the max depth ****
        return depth;
    }

Compute the max depth of a binary tree.

    /**
     * Display the nodes in a binary tree per level.
     * This function returns the number of levels in the
     * specified binary tree.
     */
    static int levelOrderTraversal(TreeNode root) {

        // **** ****
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Queue<TreeNode> t = new LinkedList<TreeNode>();
        int level = 0;

        // **** prime q ****
        q.add(root);

        // **** loop while q is not empty ****
        while (!q.isEmpty()) {
 
            // **** remove head node ****
            TreeNode tempNode = q.poll();

            // **** display the value of this node ****
            System.out.print(tempNode.val + " ");

            // **** enqueue left child ****
            if (tempNode.left != null)
                t.add(tempNode.left);
 
            // **** enqueue right child ****
            if (tempNode.right != null)
                t.add(tempNode.right);

            // **** check if q is empty (end of level) ****
            if (q.isEmpty()) {

                // **** end the current level ****
                System.out.println();

                // **** increment level ****
                level++;

                // **** swap queues ****
                q = t;
                t = new LinkedList<TreeNode>();
            }
        }

        // **** return binary tree level ****
        return level;
    }

This method performs a BFS depth traversal of the tree. It displays the values of existing nodes. The placeholders for null nodes are not displayed. In addition the function counts the levels in the tree. When done the number of levels are returned. This value should match the other two values generated by the previous functions.

Looking at the output of this last function you can see that when looking at the tree from the left or from the right the number of levels should be the same. What may change is the value of the nodes when looked from the left or right sides. Note that the requirements do not make reference to the actual values of the nodes; we just care for the count.

In addition you may draw the circumferences representing the nodes in a 2D space. If you look at the binary tree from the left of the right you should just see the end lines of the end nodes which represent the diameter of the nodes. At that time disregard the links connecting nodes and count the number of nodes you see from either side. They should be the same and match all three results per test case.

Hope this is of help!

!!! NOW BACK TO THE ORIGIONAL POST!!!

Good day! Hope you are doing well. Apparently the number of COVID-19 cases in the Twin Cities of Minneapolis and St. Paul has risen. In addition it seems that the number of free ICU beds had dropped closely to 0. This implies that a person who falls sick and needs intensive care might have a tough time finding an available bed. For our own sake, please follow distancing rules and keep safe. We all will benefit from such behavior.

I have been looking at some problems in a Facebook portal. They are intended as exercises for technical interviews. Continue reading “Number of Visible Nodes”