When Yes and No is not enough.

In typical world Boolean works just fine. Every time we need a flag we declare a boolean data type and its over.

But now here comes a situation where yes and no answer is not always enough.

Lets take an example, with following questions?

is this user has a valid credit card? we can answer this with yes or no but typically there should be three answer choices

• yes
• no
• i do not know

i do not know is not definitely equivalent to yes or no.

Java Exception Issue

In java if exception arise while parsing a json token for a boolean it will set as false;

JSONObject response=new JSONObject();
boolean flag=false;
try {
    flag=response.getBoolean("valid_card");
} catch (JSONException e) {
    e.printStackTrace();
}
System.out.println(flag);

if an exception occurs while getting valid_card token and result could be true or false depend on how we initialized it. But that doesn't really represent real case.

Solutions?

Ultimately we can simply avoid whole things by creating an enum which can have three different value

public enum EnumBoolean {
    TRUE(10), FALSE(20), UNDEFINED(30);
    private final int code;
    private static final Map<Integer,EnumBoolean> lookup
            = new HashMap<Integer,EnumBoolean>();
    static {
        for(EnumBoolean w : EnumSet.allOf(EnumBoolean.class))
            lookup.put(w.getCode(), w);
    }
    public int getCode() { return code; }

    EnumBoolean(int value) {
        this.code = value;
    }
    public static EnumBoolean fromInt(int value){
        switch (value){
            case 10:
                return TRUE;
            case 20:
                return FALSE;
        }
        return UNDEFINED;
    }
    public static EnumBoolean get(int code) {
        return lookup.get(code);
    }
}

Now if we rewrite our existing java code

JSONObject response=new JSONObject();
    EnumBoolean flag=EnumBoolean.FALSE;
    try {
        flag=EnumBoolean.fromInt(response.getInt("valid_card"));
    } catch (JSONException e) {
        e.printStackTrace();
    }
    System.out.println(flag);

Now if an error occur while parsing valid_card, final flag value would be undefined.

And, off-course this things to work backend server must consider sending boolean values as an int. and int 10 in this case.

Bottom Up vs Top Down Coding Techniques

First time i was working on Dynamic programming, i was confuse by this Bottom up and top down approach and what it really means.  Later after spending some time with it, this is what i understood. Although these approaches has nothing to do with Dynamic Programming but these terminologies mostly heard when we work on DP problems. 

Lets take fibonacci series as an example

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

Another way to put it,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

In case of first five fibonacci number

Bottom(first) number :1
Top (fifth) number: 5 

Now lets take a look of recursive Fibonacci series algorithm as an example

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

Now if we execute this program with following commands

rcursive(5);

if we closely look into the algorithm, in-order to generate fifth number it requires 3rd and 4th numbers. So my recursion actually start from top(5) and then goes all the way to bottom/lower numbers. This approach is actually top-down approach. We can even say this is Top Down recursive approach. 

Bottom-Up

But, question is, can we start from bottom, like from first fibonacci number then walk our way to up. Lets rewrite it using this techniques,

public int fibonacci(int n) {
        int first = 1; //first fibonacci number
        int seccond = 1; //seccond fibonacci number
        int count = 2;
        int result = 0;
        int temp;
        if ((n == 1) || (n == 2)) {
            return 1;
        }
        while (count < n) {
            result = first + seccond;
            temp = seccond;
            seccond = result;
            first = temp;
            count++;
        }
        return result;
}

Now if we look into this algorithm it actually start from lower values then go to top. If i need 5th fibonacci number i am actually calculating 1st, then second then third all the way to up 5th number. This techniques actually called bottom-up techniques.

Last two, algorithms meet the criteria of generating Nth Fibonacci series. But one is top-down and another one is bottom-up.

To avoid doing same calculation multiple times we can reuse some previously calculated values. We store previously store and reuse it. This technique is called memoization. In next part, i am improving recursive approach by this techniques. 

Top-Down (Memoized)

Lets rewrite our original recursive algorithm and add memoized techniques.

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

And we execute this method like following

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

This solution is still top-down as algorithm start from top value and go to bottom each step to get our top value.

Bottom-Up (Memoized)

But, question is, can we start from bottom, like from first fibonacci number then walk our way to up. Lets rewrite it using this techniques,

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

Now if we look into this algorithm it actually start from lower values then go to top. If i need 5th fibonacci number i am actually calculating 1st, then second then third all the way to up 5th number. This techniques actually called bottom-up techniques.