Database Input Issues

This was a sample presentation which I created at my workplace to present Database security issues. Most of the content is taken from the book Writing Secure code. Hope it is helpful to someone.

Number to word converter

Q: Take a number and give the equivalent number in British English words e.g.

1 = one

21 = twenty one

105 = one hundred and five

56945781 = fifty six million nine hundred and forty five thousand seven hundred and eighty one

etc.. up to 999,999,999 without using a tokenizer, or any external libraries

Working Code:

import java.text.DecimalFormat;

public class NumberToWord {

    private static final String[] tensWords = { "", " ten", " twenty",
            " thirty", " forty", " fifty", " sixty", " seventy", " eighty",
            " ninety" };

    private static final String[] words = { "", " one", " two", " three",
            " four", " five", " six", " seven", " eight", " nine", " ten",
            " eleven", " twelve", " thirteen", " fourteen", " fifteen",
            " sixteen", " seventeen", " eighteen", " nineteen" };

    // Convert Number to word which is less than one thousand   
    private static String convertLessThanOneThousand(int number) {
        String thousandWord;

        if (number % 100 < 20) {
            thousandWord = words[number % 100];
            number /= 100;
        } else {
            thousandWord = words[number % 10];
            number /= 10;

            thousandWord = tensWords[number % 10] + thousandWord;
            number /= 10;
        }
       
        if (number == 0)
            return thousandWord;
       
        return words[number] + " hundred" + thousandWord;
    }

   
    //Converts any number to word between 0 to 999 999 999 999 billions millions
    public static String convertNumberToWord(long number) throws Exception{

        if(number < 0)
        {
            throw new Exception("Negative numbers not supported");
        }
       
        if (number == 0) {
            return "zero";
        }

        String snumber = Long.toString(number);
        if(snumber.length() > 13)
        {
            throw new Exception("Numbers greater than 999 billion are not supported");
        }

        // pad with "0"
        String mask = "000000000000";
       
        // DecimalFormat converts 50 to 000000000050 based on the given mask
        DecimalFormat df = new DecimalFormat(mask);
        snumber = df.format(number);

        StringBuilder result = new StringBuilder();

        // XXXnnnnnnnnn
        int billions = Integer.parseInt(snumber.substring(0, 3));
        // nnnXXXnnnnnn
        int millions = Integer.parseInt(snumber.substring(3, 6));
        // nnnnnnXXXnnn
        int hundredThousands = Integer.parseInt(snumber.substring(6, 9));
        // nnnnnnnnnXXX
        int thousands = Integer.parseInt(snumber.substring(9, 12));

        String wordBillions;
        switch (billions) {
        case 0:
            wordBillions = "";
            break;
        case 1:
            wordBillions = convertLessThanOneThousand(billions) + " billion";
            break;
        default:
            wordBillions = convertLessThanOneThousand(billions) + " billion";
        }

        result.append(wordBillions);

        String wordMillions;
        switch (millions) {
        case 0:
            wordMillions = "";
            break;
        case 1:
            wordMillions = convertLessThanOneThousand(millions) + " million";
            break;
        default:
            wordMillions = convertLessThanOneThousand(millions) + " million";
        }

        result.append(wordMillions);

        String wordHundredThousands;
        switch (hundredThousands) {
        case 0:
            wordHundredThousands = "";
            break;
        case 1:
            wordHundredThousands = "one thousand ";
            break;
        default:
            wordHundredThousands = convertLessThanOneThousand(hundredThousands)+ " thousand";
        }

        result.append(wordHundredThousands);

        result.append(convertLessThanOneThousand(thousands));

        return result.toString();
    }

    public static void main(String[] args) {
       
        String word = "";
        try {
            word = NumberToWord.convertNumberToWord(999999999999L);
        } catch (Exception e) {
            System.out.println("error: "+e.getMessage());
        }
        System.out.println(word);
    }

}

Serializing a binary tree

Q: Design an algorithm and write code to serialize and deserialize a binary tree.

Advantages of serialization/deserialization include storing a binary into and restoring it for a later point of time, transmitting the tree over a network from one computer and load it in another computer.

One approach for this problem could be the nodes with NULL values using some kind of sentinel so that later nodes can be inserted In correct place while deserialization. Lets use the sentinel as # and we will use preorder traversal here serialization.

Assume we have a binary tree below:

The preorder traversal of the above tree can be written as 

30 10 50 # # # 20 45 # # 35 # #

Finding Unique number

Q: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
Fastest way to find that single integer

eg:
Input: {1,1,1,3,3,3,20,4,4,4};

Answer: 20

The logic is similar to finding the element which appears once in an array - containing other elements each appearing twice. There we do XOR all the elements and the result will be the unique number.

To apply the similar logic to this problem we maintain 2 variables

ones - This variable holds XOR of all the elements which have appeared only once.
twos - This variable holds XOR of all the elements which have appeared twice.

The algorithm goes as follows…

1. A new number appears - It gets XOR' ed to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twos".
3. A number appears for the third time - It gets removed from both "ones" and "twos".

The final answer will be in "ones" as it holds the unique element.

Working Java code:

Multiplication of numbers

Q: There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}

Since we should not use, division operator, Brute force approach would be O(n^2)

Other approach is by storing the result temporarily in an array.

Let’s define array B where element B[i] = multiplication of numbers from A[0] to A[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then, we scan the array A from right to left, and have a temporary variable called product which stores the multiplication from right to left so far. Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.

Above approach requires O( n ) time and also O( n ) space.

We can actually avoid the temporary array. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left.

Robot Unique Paths

Q: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

We can solve this problem using backtracking approach.

Other approach is using dynamic programming with memorization.

Longest Palindrome in a string

Brute force Algorithm.

1. Have 2 for loops
   for i = 1 to i less than array.length -1
   for j=i+1 to j less than array.length
2. This way you can get substring of every possible combination from the array
3. Have a palindrome function which checks if a string is palindrome
4. so for every substring (i,j) call this function, if it is a palindrome store it in a string variable
5. If you find next palindrome substring and if it is greater than the current one, replace it with current one.
6. Finally your string variable will have the answer

Brute force approach for this problem takes O(n3) time.

Another approach is

1. Reverse the string and store it in different string
2. Now find the largest matching substring between both the strings

This too will take O(n2) time

We can solve this problem using suffix trees, but constructing the suffix tree itself seems to be more complex in terms of both time and space complexity.

We can solve this problem using a better approach which will revolve around with a center for every single character.

For each position in the string we store an upper and lower pointer that tracks the upper and lower bounds of the largest palindrome centered at that position.

For instance, position 2 in the string "racecar" would start as:

At this point, the longest known palindrome at position 2 is the single character 'c'. We then increment the upper pointer and decrement the lower pointer and compare their respective values.

Since the upper and lower values are not the same, we stop and now know that the longest palindrome centered at position 2 is 'c'. We then start the process again at the next string position, 3.

We increment and decrement the upper and lower pointers and see that they are equal. Our current longest palindrome centered at position 3 is now 'cec'.

Since they were equal, we increment and decrement the pointers again and see that they are still equal. Our new longest palindrome centered at position 3 is now 'aceca'.

We continue incrementing and decrementing the upper and lower pointers until they don't match or they hit one of the ends of the string.

Since our pointers are equal, we increment and decrement them again. We hit an end of the string and the pointers are equal so we know that our longest palindrome centered at position 3 is 'racecar'.

We're done with position 3 and continue this same process again at position 4. We'll do this until we've covered every position in the string.

NOTE: We initially assumed that the palindrome had an odd length. This algorithm works for even palindromes as well. The only change we make is that when we initialize the pointers, instead of having the lower and upper pointer point to the same position we have the upper pointer point at the next position. Everything else with the algorithm remains the same. i.e. The initial pointers for an even palindrome 'centered' at position 3 would look like:

Runtime:

Worst-Case: O(N^2)

Best-Case: O(N)

The worst case is achieved when the string is a single repeated character because every substring is a palindrome.

The best case is achieved when the string contains no palindromes.

Typically if a string only contains a single palindrome (the fewer the better), the closer to O(N) it will run. This is because every time it checks a position in the string, it checks the character before and after that position, and if they don't match then it stops looking for the palindrome. Positions in the string can be discarded after only one lookup if that position doesn't have a palindrome, so if there are no palindromes you only do N comparisons.

JavaCode: