LeetCode 402. Remove K Digits in Java

In this post we will solve the LeetCode 402 Remove K Digits problem.

Given string num representing a non-negative integer num, and an integer k, 
return the smallest possible integer after removing k digits from num.

Constraints:

o 1 <= k <= num.length <= 10^5
o num consists of only digits.
o num does not have any leading zeros except for the zero itself.

If interested in this problem I suggest you read the current description in the LeetCode website. The requirements may be refined since this post. Continue reading “LeetCode 402. Remove K Digits in Java”

LeetCode 75. Sort Colors in Java

In this post we will solve the LeetCode 75. Sort Colors problem using the Java programming language and the VSCode IDE on a Windows computer.

Given an array nums with n objects colored red, white, or blue, 
sort them in-place so that objects of the same color are adjacent, 
with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Constraints:

o n == nums.length
o 1 <= n <= 300
o nums[i] is 0, 1, or 2.

We are given an integer array with values 0, 1, and 2 which represent colors red, white and blue respectively. We must solve the problem without the use of any library sort function. That makes sense because we would only have to sort the input array and return. Continue reading “LeetCode 75. Sort Colors in Java”

LeetCode 229. Majority Element II in Java

In this post we will solve the LeetCode 229. Majority Element II problem using two approaches.

Given an integer array of size n, find all elements that appear more than floor(n/3)times.

Constraints:

o 1 <= nums.length <= 5 * 10^4
o -10^9 <= nums[i] <= 10^9

We are given an array of integer values. We need to find all elements whose values are larger than floor(n / 3), where `n` is the number of elements in the input array. Continue reading “LeetCode 229. Majority Element II in Java”

Block Storage vs. File Storage – Part 1

In this post we will not be solving a problem yet. This post is about code I wrote to experiment with differences between file and block storage.

In this post we will start by writing some data into individual files. This will set the ground for some differences that arise when you access similar data in block mode possibly in a cloud storage setting.

This code has been written in C on a Windows platform. For my benefit regarding ease of development, I have used some previous code found in a set of libraries which at this point I am not allowed to disclose. That said; when we encounter such calls I will suggest ways you can replace them with much simpler code. Sorry for the inconvenience this may cause. Continue reading “Block Storage vs. File Storage – Part 1”

Codility_ problem Fish in Java

In this post we will attempt to solve the Codility_ problem Fish (https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/) in which we are given N voracious fish are moving along a river. Calculate how many fish are alive. Continue reading “Codility_ problem Fish in Java”

Find Leaf Nodes in a Tree for which the Sum of the Root Path Matches a Target Value

I did not find this problem on a website. The requirements came up during a conversation with a software engineer. I wish I could have taken some notes but I did not. The problem had a single diagram of a sample general tree and there was no class definition for the nodes.

We are given a general binary three in which a node may have none, one or more children.
In addition each node has an integer value.
The values may repeat.

Our tasks if to come up with a function 
that will display the leaf nodes 
for which the sum of all node values in the path from the root 
add up to a defined target.

As far as I can remember that was the gist of the problem. Continue reading “Find Leaf Nodes in a Tree for which the Sum of the Root Path Matches a Target Value”

Brackets

Good day! In this post we will attempt to solve the Brackets problem from Codility_.

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

o S is empty;
o S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
o S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function such that given a string S consisting of N characters, 
returns 1 if S is properly nested and 0 otherwise.

Write an efficient algorithm for the following assumptions:

o N is an integer within the range [0..200,000];
o string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

We are presented with a string. We need to determine if the different types of brackets match. If interested in this problem I suggest you read the current and full description at Codility_. Continue reading “Brackets”

Sum of Nodes Between Two Nodes in Binary Tree

Good day!! Hope all is going well for you. It is Friday and has been a very stressful week for me. Glad that the weekend is just around the corner.

Today we are going to cover a problem which a software engineer and I discussed earlier this week, but for some reason or the other, we did not generate code at the time. We just talked about it.

We are given a binary tree with integer values and two different nodes in the binary tree,
we must return the sum of the values of the nodes that connect p and q inclusive.

Constraints:

o -1000 &lt;= val &lt;= 1000
o 2 &lt;= n &lt;= 200

As you can see, we are given a binary tree populated with integers. Do not recall if all integers were included. We will assume, since I am writing the requirements as we speak, that the values for the nodes are in the specified range and the number of nodes in the binary tree should not exceed the specified value.

What we need to do is implement an algorithm in which given two nodes from the binary tree, we should return the sum of all nodes in between including the values of the two nodes.

       5
     /   \
    /     \
   3       4
  / \     / \
 /   \   /   \
7     2 1     9

This diagram illustrates a binary tree with 7 nodes. Our first test case will provide us with a similar binary tree and we will be asked to determine the sum of the values between node 7 and node 9 and then between nodes 9 and 7. As we should expect both queries should return the same value. Note that any two pairs of nodes may be selected for a query.

	int sumNodes(TreeNode root, TreeNode[] p, TreeNode[] q) {
	}

We will be attempting to solve this problem using the Java programming language and the VSCode IDE on a Windows platform. No matter what your choices are for the tools you use, the results should match.

Please note that the function of interest requires 3 arguments. The first is the binary tree and the other two are arrays holding single nodes. We did not discuss specifics about the function of interest. I would assume that it would take 3 arguments, but the last two would just be pointers to the `p` and `q` nodes. For reasons that will become apparent shortly, we will put the nodes into arrays. We could implement two functions. The first with `p` and `q` which would call a second function with similar arguments but the last two would be of type TreeNode[] array with a single node each. We will just skip that step.  

We did not have a test scaffold so we will write one here. Please note that the test scaffold IS NOT PART OF THE SOLUTION.

5 3 4 7 2 1 9
2
7 9
9 7
main <<< strVal: [5, 3, 4, 7, 2, 1, 9]
main <<< postOrderTraversal: 7 2 3 1 9 4 5
main <<< number of queries (m): 2
main <<< (7,9) sum: 28
main <<< (9,7) sum: 28


10 8 12 7 9 11 13
3
9 11
7 13
7 12
main <<< strVal: [10, 8, 12, 7, 9, 11, 13]
main <<< postOrderTraversal: 7 9 8 11 13 12 10
main <<< number of queries (m): 3
main <<< (9,11) sum: 50
main <<< (7,13) sum: 50
main <<< (7,12) sum: 37


9 3 -1 6 -2 3 5 7 
7
7 5
5 7
9 3
3 9
7 3
3 7
1 8
main <<< strVal: [9, 3, -1, 6, -2, 3, 5, 7]
main <<< postOrderTraversal: 7 6 -2 3 3 5 -1 9 
main <<< number of queries (m): 7
main <<< (7,5) sum: 29
main <<< (5,7) sum: 29
main <<< (9,3) sum: 11
main <<< (3,9) sum: 11
main <<< (7,3) sum: 27
main <<< (3,7) sum: 27
main <<< pVal: 1 NOT found in binary tree


3 5 1 6 2 0 8 null null 7 4
8
1 5
1 8
2 4
3 1
3 5
5 1
6 4
7 4
main <<< strVal: [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]        
main <<< postOrderTraversal: 6 7 4 2 5 0 8 1 3
main <<< number of queries (m): 8
main <<< (1,5) sum: 9
main <<< (1,8) sum: 9
main <<< (2,4) sum: 6
main <<< (3,1) sum: 4
main <<< (3,5) sum: 8
main <<< (5,1) sum: 9
main <<< (6,4) sum: 17
main <<< (7,4) sum: 13


1 2
2
1 2
2 1
main <<< strVal: [1, 2]
main <<< postOrderTraversal: 2 1
main <<< number of queries (m): 2
main <<< (1,2) sum: 3
main <<< (2,1) sum: 3


1 2 3 4
2
1 5
5 1
main <<< strVal: [1, 2, 3, 4]
main <<< postOrderTraversal: 4 2 3 1
main <<< number of queries (m): 2
main <<< qVal: 5 NOT found in binary tree
main <<< pVal: 5 NOT found in binary tree


1 3 5 7 9 11 13 -1 -2 -3 -4 -5 -6 -7 -8
3
7 -8
-8 7
-1 -8
main <<< strVal: [1, 3, 5, 7, 9, 11, 13, -1, -2, -3, -4, -5, -6, -7, -8]
main <<< postOrderTraversal: -1 -2 7 -3 -4 9 3 -5 -6 11 -7 -8 13 5 1    
main <<< number of queries (m): 2
main <<< (7,-8) sum: 21
main <<< (-8,7) sum: 21


1 3 5 7 9 11 13 -1 -2 -3 -4 -5 -6 -7 -8
1
-4 -4
main <<< strVal: [1, 3, 5, 7, 9, 11, 13, -1, -2, -3, -4, -5, -6, -7, -8]
main <<< postOrderTraversal: -1 -2 7 -3 -4 9 3 -5 -6 11 -7 -8 13 5 1
main <<< number of queries (m): 1
main <<< (-4,-4) sum: -4

We have several test cases. Each test case describes a binary tree and a number of queries each specifying two nodes which we will use to call the function of interest.

Our test code seems to take multiple input lines. The first line contains a set of integers which represent an ordered list of nodes. The second input line contains the number of queries we will issue. For each query we will have two nodes for which our function of interest will compute the sum between them.

In this case we have 2 queries. The first with nodes 7 and 9 and the second with nodes 9 and 7. If all works well, both queries should return the same value, and it seems to do so.

Based on the previous diagram of the binary tree, we need to sum the values of nodes 7, 3, 5, 4 and 9. This implies 7 + 3 + 5 + 4 + 9 = 28. It seems that both queries are returning the correct values.

There are several test cases. You might want to take a look and make sure that you can follow what we need to do.

The problem did not provide a class for the TreeNode. We will use the following:

/**
 * Auxiliary class to build the binary tree.
 */
class TreeNode {

    // **** members ****
    int         val;
    TreeNode    left;
    TreeNode    right;

    // **** constructor ****
    TreeNode(int x) { val = x;}
}

Each node will be as simple as possible. Each node will hold an integer value and a right and left child which may or may not be `null`. Our constructor will receive an integer value and will return a node with `null` children. That is all we need in the TreeNode class.

    /**
     * Test scaffold.
     * @throws InterruptedException
     * @throws IOException
     * @throws NumberFormatException
     */
    public static void main(String[] args) throws InterruptedException, NumberFormatException, IOException {

        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read the node values and place them in an array of strings ****
        String strVal[] = br.readLine().trim().split(" ");

        // ???? ????
        System.out.println("main &lt;&lt;&lt; strVal: " + Arrays.toString(strVal));

        // **** root for the binary tree ****
        TreeNode root = null;

        // **** populate the binary tree ****
        root = insertLevelNode(strVal, root, 0);

        // ???? print the binary tree in post order traversal ????
        System.out.print("main &lt;&lt;&lt; postOrderTraversal: " + postOrderTraversal(root, new StringBuilder())+ "\n");

        // **** get the number of queries ****
        int m = Integer.parseInt(br.readLine().trim());

        // ???? ????
        System.out.println("main &lt;&lt;&lt; number of queries (m): " + m);

        // ***** loop once per query ****
        for (int i = 0; i &lt; m; i++) {

            // **** read p and q ****
            String[] pAndQ = br.readLine().trim().split(" ");

            // **** convert to integer ****
            int pVal = Integer.parseInt(pAndQ[0]);
            
            // **** convert to integer ****
            int qVal = Integer.parseInt(pAndQ[1]);

            // **** find node p in the binary tree ****
            TreeNode p = find(root, pVal);
            if (p == null) {
                System.out.println("main &lt;&lt;&lt; pVal: " + pVal + " NOT found in binary tree");
                continue;
            } 

            // **** find node q in the binary tree ****
            TreeNode q = find(root, qVal);
            if (q == null) {
                System.out.println("main &lt;&lt;&lt; qVal: " + qVal + " NOT found in binary tree");
                continue;
            }


            // // **** find the LCA of p and q ****
            // TreeNode lca = lowestCommonAncestor(root, p, q);

            // // **** display the LCA ****
            // System.out.println("main &lt;&lt;&lt; lowestCommonAncestor: (" + pVal + "," + qVal + ") lca: " + lca.val);

            // // **** find the LCA of p and q (second attempt; ended being the same as previous) ****
            // lca = lcaPostOrder(root, p, q);

            // // **** display the LCA ****
            // System.out.println("main &lt;&lt;&lt;         lcaPostOrder: (" + pVal + "," + qVal + ") lca: " + lca.val);


            // **** sum node values between p and q and display result ****
            System.out.println("main &lt;&lt;&lt; (" + p.val + "," + q.val + ") sum: " + 
                                sumNodes(root, new TreeNode[] {p}, new TreeNode[] {q}));
        }

        // **** close buffered reader ****
        br.close();
    }

Our test scaffold is as simple as we need. We start by reading the first input line and putting the integer numbers in a String[] array. We do so because a utility I wrote a few years ago is able to take `null` values to represent `null` children. Note that our test scaffold displays the String[] array `strVal` so we can verify that we were able to generate an array which will be used to create and populate a binary tree. Please note that generating the binary tree IS NOT PART OF THE SOLUTION. Our function of interest will be called with a binary tree and how it is created is out of the scope of this problem.

Our test scaffold then reads the int `m` which holds the number of queries we will be asked to process. The value of `m` is then displayed so we can verify that all is well so far.

Our test code enters a loop which should process one query at a time.

The loop reads the values of the `p` and `q` nodes. It then finds the associated nodes in the binary tree. If the values are not available as nodes in the binary tree, a message is displayed and the query is ignored.

Following is a set of commented out statements. Such code is not relevant for our solution. I left it for development and testing. In production it is not a good idea to leave code commented out. It should be removed.

The last line in the loop calls the function of interest with the two nodes and returns the sum of the values in the nodes of interest.

Please note that the `find` function used to look up the `p` and `q` nodes in the binary tree IS NOT PART OF THE SOLUTION.

This is a good time to stop further development and think about what we need to do to get the results we need to return by our function of interest.

It was my opinion that the problem could be solved using some type of binary tree traversal with modifications. I suggested using a post order tree traversal.

We could possibly have figured the LCA (Least Common Ancestor) for the two nodes and the sum in a single pass. We will go with two separate functions.

    /**
     * Sum the node values between specified nodes in the binary tree.
     * 
     * o Gets LCA (Lowest Common Ancestor) node.
     * o Computes sum of node values between p and q.
     * 
     * !!! This is the function of interest !!!
     * 
     * Execution: O(n) - Space: O(1)
     */
    static int sumNodes(TreeNode root, TreeNode[] p, TreeNode[] q) {

        // **** get the LCA between specified nodes - O(n)****
        TreeNode lca = lcaPostOrder(root, p[0], q[0]);

        // **** get the sum of the node values between specified nodes - O(n) ****
        int sum = lca.val + rangeSum(lca, p, q);

        // **** return sum ****
        return sum;
    }

The `lcaPostOrder` function returns the LCA node. Once we have the node we will call a second function named `rangeSum` which implements a separate post order tree traversal to compute the sum of the values of the nodes between `p` and `q`.

Please take a look at the comments section of this function. Looks like our implementation will run in O(n) time.

    /**
     * Finds and returns the LCA (Lowest Common Ancestor) node 
     * in the specified binary tree.
     * Modified post order traversal recursive call.
     * 
     * Execution: O(n) - Space: O(1)
     */
    static TreeNode lcaPostOrder(TreeNode root, TreeNode p, TreeNode q) {

        // **** base case ****
        if ((root == null) || (root == p) || (root == q)) return root;

        // **** visit the left child ****
        TreeNode left = lcaPostOrder(root.left, p, q);

        // **** visit the right child ****
        TreeNode right = lcaPostOrder(root.right, p, q);

        // **** p and q in the current root of the binary tree ****
        if ((left != null) && (right!= null)) return root;

        // **** p or q found but not both ****
        if (left != null)
            return left;
        else 
            return right;
    }

This function which uses a modified post order tree traversal is a recursive call. We first visit the left child and then the right child. If one of the nodes of interest is in the current path we return it to the caller. Since our test scaffold made sure that `p` and `q` are in the binary tree we will always be able to find them.

    /**
     * Given the root node of a binary tree and two nodes, 
     * return the sum of values of all nodes between p and q (inclusive).
     * 
     * Modified post order traversal recursive call.
     * 
     * Execution: O(n) - Space: O(1)
     */
    static int rangeSum(TreeNode root, TreeNode[] p, TreeNode[] q) {
        
        // **** base case ****
        if (root == null) return 0;

        // **** initialize sum ****
        int sum = 0;

        // **** traverse left tree ****
        if (root.left != null)
            sum += rangeSum(root.left, p, q);
    
        // **** traverse right tree ****
        if (root.right != null)
            sum += rangeSum(root.right, p, q);

        // **** update sum, p and q (as needed) ****
        if (root.left != null && root.left == p[0]) {
            sum += root.left.val;
            p[0] = root;
        }
        else if (root.left != null && root.left == q[0]) {
            sum += root.left.val;
            q[0] = root;
        }

        if (root.right != null && root.right == p[0]) {
            sum += root.right.val;
            p[0] = root;
        }
        else if (root.right != null && root.right == q[0]) {
            sum += root.right.val;
            q[0] = root;
        }

        // **** return sum ****
        return sum;
    }

The `rangeSum` function which is also based on a post order tree traversal algorithm, checks the right and then the left child trees. If needed it updates the sum and the values for `p` and / or `q`. This is the reason we used a couple of arrays to wrap the `p` and `q` nodes. In Java arguments are passed by value unless it is a collection. We have used this array technique in multiple posts in this blog.

That is the implementation of the function of interest.

Before we start the implementation of the two functions that make up the solution, we could perform a post order tree traversal on the binary tree to help us visualize our algorithm,

    /**
     * Perform a post order traversal of a binary tree.
     * 
     * !!! NOT PART OF SOLUTION !!!
     */
    static public StringBuilder postOrderTraversal(TreeNode root, StringBuilder sb) {
        if (root != null) {

            // **** visit left child ****
            postOrderTraversal(root.left, sb);

            // **** visit right child ****
            postOrderTraversal(root.right, sb);

            // **** visit root ****
            sb.append(root.val + " ");

            // **** return ****
            return sb;
        } else return null;
    }

I thought it would be nice to have such a handy function around. Our test scaffold makes a call to this function to display the sequence of nodes during a post order tree traversal.

Please note that we first thought about what to do. We then implemented the two functions we needed. If we would have more time we could attempt to condense the two functions into one. The result would be more complex and harder to maintain. I like functions that work and are as simple as possible to maintain.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode). In this case you are out of luck. That said; if you find this problem on a web site, please let me know. Would like to compare it to what we have written.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

Stone Wall

Good day! Hope all is well in your neck of the woods. My wife left lunch in the oven and ran to the dentist office. She left the oven on. Not sure when I should shut it down. I think I will do it right now before the food gets burned. When she gets back we can turn on the oven back if needed.

OK, the oven is off. It is 01:00 PM. I am starving. Hope my wife returns shortly so we can have lunch. Continue reading “Stone Wall”

Slow Sum – Revisited

Good morning. I received a comment from Dmytro regarding the post Slow Sum suggesting the use of a priority queue instead of a stream. I appreciate the comment and suggestion. Continue reading “Slow Sum – Revisited”