Recursion to Iteration: Fibonacci Sequence

The Fibonacci sequence consists of these numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34…}. Intuitively, one can see that the next number in the sequence will be a summation of the current number and the previous number. The Fibonacci sequence written recursively is:

public static int fibRecursive(int n) {
        if(n < 0){
            throw new IllegalArgumentException("n < 0");
        }
        if (n <= 1)
            return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Behind the scenes, each recursive function call gets pushed on the stack as a stack frame therefore we can emulate recursion calls using a stack:

public static int fibUsingStack(int n) {
        if(n < 0){
            throw new IllegalArgumentException("n < 0");
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(n);
        int sum = 0;
        while (!stack.empty()) {
            Integer next = stack.pop();
            if (next == 0 || next == 1) {
                sum += next;
                continue;
            }
            stack.push(next - 2);
            stack.push(next - 1);
        }
        return sum;
}

This is just a fun learning exercise which helps create understanding on how to convert recursive functions to iterative functions. It wouldn’t make sense to use a stack for this use case.

Google Merchant Center / Google Shopping Content API: “Quota Limit Exceeded” Error Message

I was recently working with the Google Shopping Content API and kept getting the “Quota Limit Exceeded” error message. After much googling, it didn’t seem like there was a definite answer to the problem. I didn’t know if the error message meant that I was sending too many requests per time unit or if there was a finite number of product information rows that could be uploaded to Google servers.

After much troubleshooting and calling Google, it looks like they have a finite cap on the number of product information rows that you can upload. To increase your quota, you must shoot them a phone call and relay the error message to them. In my case, I had to call twice because the number of products that I was working with was too large for one call due to company policy.

tl;dr Call Google.

Java: Generating Random Integers Using Math.random()

Math.random() generates a double between 0 inclusive and 1 exclusive. An easier way to think of this is that Math.random() generates a random double between [0, 1) where “[” is inclusive and “)” is exclusive.

I like this notation better because it helps to make a connection between programming classes and math classes. This connection makes it easier to understand how to generate integers with Math.random() because the experience shifting graphs in math will transfer over to generating random numbers.

So to generate an integer between a certain range, we can just shift the decimal generation and then cast it to an integer. It is important to note that an integer cast will always round down.

//Random decimal between [0, 1)

double randomDecimalBetweenZeroAndOne = Math.random();

//Random integer between [0 * 10, 1 * 10) which equals [0, 10)

int randomIntegerBetweenZeroAndNineInclusive = (int) (Math.random() * 10);

//Random integer between [0*6 + 5, 1*6 + 5) which equals [5, 11)

int randomIntegerBetweenFiveAndTenInclusive = (int)(Math.random() * 6 + 5)

Can you figure out how to write an inclusive method to generate random numbers? Comment below!

LeetCode: 2. Add Two Numbers

LeetCode Prompt:

/** This prompt belongs to LeetCode **/

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

You really have to read this prompt a few times before letting it sink in. I think the most overlooked detail is that “The digits are stored in reverse order….” This is an incredibly important detail because it makes the algorithm a lot more simple; we don’t have to do any backwards carrying. In other words, 2 -> 4 -> 3 really represents the number ‘342’ and so forth for every other ListNode.

Here is the code I came up with:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode tmpL1 = l1;
        ListNode tmpL2 = l2;
        int carryOver = 0;
        while(tmpL1 != null && tmpL2 != null){
            tmpL1.val = tmpL1.val + tmpL2.val + carryOver;
            if(tmpL1.val >= 10){
                carryOver = 1;
                tmpL1.val -= 10;
                if(tmpL1.next == null && tmpL2.next == null){
                    tmpL1.next = new ListNode(carryOver);
                    return l1;
                }
            } else {
                carryOver = 0;
            }
            
            if(tmpL1.next == null && tmpL2.next != null){
                tmpL1.next = new ListNode(0);
            }
            if(tmpL1.next != null && tmpL2.next == null){
                tmpL2.next = new ListNode(0);
            }
            
            tmpL1 = tmpL1.next;
            tmpL2 = tmpL2.next;
            
        }
        return l1;
    }
}

This code is simply iterating over every entry in the first and second ListNode and adding the values together. Following this, the algorithm checks if the summation is greater than or equal to 10 which denotes that we need to carry to the right. Since we only have to deal with digits, the max summation can only total 18 which means that the max carry over is 1. We have to do some conditional checking regarding null pointers due to uneven sizes of the ListNode.

See any improvements to make this faster? Comment below!

Iterative Preorder Binary Tree Traversal

The typical definition of a preorder binary tree traversal is that you will first visit the top node, all nodes left of the tree, and then work your way back up the tree visiting the right nodes.

The typical recursive preorder binary tree traversal is this:

private void preorderTraversal(IntegerNode integerNode) {
    if (integerNode == null) {
        return;
    }
    System.out.print(integerNode.value + "\t");
    preorderTraversal(integerNode.left);
    preorderTraversal(integerNode.right);
}

Notice how we first check the current node, recurse through the left nodes, and then work our way back up the tree visiting the right nodes.

Whenever you have to rewrite recursion to iteration, you should be thinking “Stack”. This is because each recursive function call is really just an element that is pushed onto the stack behind the scenes.

Here is this same algorithm written to use iteration:

private void iterativePreorderTraversal(IntegerNode integerNode){
    Stack<IntegerNode> integerNodeStack = new Stack<>();
    integerNodeStack.push(integerNode);


    while(!integerNodeStack.isEmpty()){
        IntegerNode integerNodeIterator = integerNodeStack.pop();

        System.out.print(integerNodeIterator.value + "\t");

        if(integerNodeIterator.right != null){
            integerNodeStack.push(integerNodeIterator.right);
        }
        if(integerNodeIterator.left != null){
            integerNodeStack.push(integerNodeIterator.left);
        }

    }
}

We can think logically about this algorithm and trace through it to help us achieve a better understanding. First, the first node that will be popped off the stack will be the top of the binary tree (in this case the integerNode method argument). Second, we will keep adding the right and left nodes provided either of them are not null. The most important part to notice at this stage is that all left elements will be popped before any right elements because the stack data-structure guarantees the LIFO (last in first out) property. In our case, the current iteration will always have the left node being pushed into the stack after the right node, provided the left node is not null. After we have exhausted all the left nodes, we will start climbing back up the tree.

Feel free to leave any questions or comments below.