Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).

Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).  This is the question asked in book "Introduction to Algorithm."  I spent some time figuring out the following solution implemented in Java.  The assumption is that we can get random number 0 and 1 which I use Java class Random to generate.

import java.util.Random;
public class RandomGenerator {
    private static Random rand = new Random();

    /**
     * generate a random nubmer between a (inclusive) and b (exclusive)
     */
    public static int random(int a, int b) {
        if (a >= b) {
            throw new UnsupportedOperationException("2nd param must be greater than 1st param");
        }
        return a + generate(b - a);
    }
    /**
     * generate the random between 0 to a (exclusive)
     */
    private static int generate(int a) {
        int run = leastPowerOfTwo(a);

        while (true)  {
            int power = 1;
            int sum = 0;
            for (int i = 0; i < run; i++) {
                sum += random01() * power;
                power *= 2;
            }
            if (sum < a) {
                return sum;
            }
        }
    }

    /**
     * find the least power of 2 which is greater than or equal to the given input a
     */
    private static int leastPowerOfTwo(int a) {
        int power = 0;
        int temp = a;
        while (temp > 0) {
            temp >>>= 1;
            power++;
        }
        //if a is a power of 2
        if ((a & (a - 1)) == 0) {
            power--;
        }
        return power;
    }

    /**
     * a method to randomly generate 0 or 1
     * @return 0 or 1
     */
    private static int random01() {
        return rand.nextInt(2);
    }
}

The trick is to use the binary representation for the generated random number.  For example, to generate a random within [0, 5),  we need to call random(0, 1) 3 times since 2 ^ 3 = 8.  If call random(0, 1) 2 times, we only have 2 ^ 2 = 4 random numbers.  We only need to keep random number less than 5, and if we get a number is greater than 4, we just retry until we get the number is less than 5.   Below is the binary representation for 3 runs of random(0, 1)

#run #3   #2   #1
          0    0     0        0
          0    0     1        1
          0    1     0        2
          0    1     1        3
          1    0     0        4
          1    0     1        5
          1    1     0        6
          1    1     1        7


The informal proof of the above algorithm is that the chance to generate each number is same (1/8).  Since we only keep the number from 0 to 4, the chance to generate the number from 0 to 4 is still same.  Then the above algorithm does generate the correct random numbers.  I ran this program on my machine to generate random number from 7 to 12 (exclusive) for 10 million times, and here is the result:

7:   1997855
8:   2000311
9:   2000140
10: 2000369
11: 2001325

Maximum subarray

This is an interview question:

Given an integer array, find the max sum in any contiguous sub-array.  If all elements are negative, then the sum is 0. The following code just finds the max sum without returning the start and end indexes:

public class MaxSubArray {
    public static int maxSum(int[] input) {
        int currentSum = 0;
        int maxSum = 0;
        for (int i = 0; i < input.length; i++) {
            currentSum = Math.max(currentSum + input[i], 0);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

The following code returns max sum with starting and ending indexes. If all elements are negative, return start and end indexes as 0 and -1, respectively.

public class MaxSubArray {
    public static MaxSubArrayResult compute(int[] input) {

        MaxSubArrayResult result = new MaxSubArrayResult(0, -1, 0);
        int currentSum = 0;
        int currentStart = 0;
        for (int currentEnd = 0; currentEnd < input.length; currentEnd++) {
            currentSum += input[currentEnd];
            if (currentSum > result.maxSum) {
                result.start = currentStart;
                result.end = currentEnd;
                result.maxSum = currentSum;
            } else if (currentSum < 0){
                currentStart = currentEnd+ 1;
                currentSum = 0;
            }
        }
        return result;
    }

    public static class MaxSubArrayResult {
        public int start;
        public int end;
        public int maxSum;

        public MaxSubArrayResult(int start, int end, int sum) {
            super();
            this.start = start;
            this.end = end;
            this.maxSum = sum;
        }

        @Override
        public String toString() {
            return String.format("start = %d, end = %d, maxSum = %d", start, end, maxSum);
        }
    }
}

The run time for both method is linear (O(n)).

print a column using awk and remove dups

The following command will print the 3rd column in file input.txt:

awk '{print $3}' input.txt

Using redirect to output the result to a file

awk '{print $3}' input.txt > output.txt

To get rid of dups from output.txt and output to file unique.txt:

sort output.txt | uniq -u > unique.txt

We can combine these steps to one:

awk '{print $3}' input.txt | sort | uniq -u > unique.txt

Some important info about awk:

• NR -- The current line's sequential number
• NF -- The number of fields in the current line
• FS -- The input field separator; defaults to whitespace and is reset by the -F command line parameter 

For example, to get the last field of a line:

path=" ../dist/myjar-1.7.jar"
jar_file=`echo $path | awk -F '/' '{print $NF}'`

print the sum of the number in a file:

file test.txt has the following format:

   a=1.2
   bc=2.3
   xyz=1.3

awk -F '=' '{SUM += $NF} END {print SUM/NR}' test.txt

Select a range from oracle, mysql

I talked about how to select first/top n rows from oracle, mysql, and ms sql server. How do we get the range, say from m to n, where m < n?

Oracle

select id, age from (select id, age, rownum as rn from customer order by age) where rn between :m and :n

MySql

select * from customer order by age limit :m, :n - :m

MS SQL

I don't know how to do it with MS sql server yet. I don't have ms sql server installed. If you happen to know it, please post your solution in the comment.

Select first n rows from oracle, MySql and MS Sql

Assume we have table customer with columns id and age. Find first n customers with youngest ages

Oracle

select * from (select * from customer order by age) where rownum < :n

Mysql

select * from customer order by age limit :n

MS Sql

select top :n * from customer order by age

Oracle merge into with only one table

I recently wanted to use oracle MERGE INTO to update a table. With MERGE INTO, it usually works with 2 tables, a source and a target table. However, in my case, I only have one table: update the table if the given id exists, otherwise insert a new row. I initially thought the following should work:

MERGE INTO image i
USING (select id, url from offer_image
WHERE id = :id and url = :url) ii
ON (ii.id = i.id AND ii.url = i.url)
WHEN MATCHED THEN
UPDATE SET
title = :title
WHEN NOT MATCHED THEN
INSERT (i.id, i.url, i.title)
VALUES (:id, :url, :title)

However, it only does update and not insert. I consulted oracle DBA and here is his answer:

"Your source always needs to return a non-empty for the merge to work. In this case your source is returning 0 rows."

Then I came up the following merge statement:

MERGE INTO image i
USING (select 1 from dual) ii
ON (i.id = :id AND i.url = :url)
WHEN MATCHED THEN
UPDATE SET
title = :title
WHEN NOT MATCHED THEN
INSERT (i.id, i.url, i.title)
VALUES (:id, :url, :title)

Note that Oracle table DUAL is a special one row one column table. Here is a good explanation about DUAL

Git cheat sheet

I have been using Git for more than a year. Comparing with SVN, the big difference is how to commit the changes to remote repository. Git requires two steps to do it:

1. commit the changes to local repository (need to add new files explicitly)
2. push the commit to remote repository

When I first used Git, I often forgot to add new files (git add new_file_name) to let Git track new files, and after commit the changes, I didn't push my changes to remote server.

Here are some commands I would like to share:

Create a new local branch from an existing branch and switch to the new branch:

git checkout -b new_branch existing_branch

Push a newly created branch

git push -u origin new_branch_name

-u will make your branch tracked

Push a tag
         git push origin tag_name

Push all tags not in remote server
        git push origin --tags

Delete a local branch

git branch -D branch_name

Delete a remote branch

git push origin :remote_branch_name

Delete a local tag

git tag -d tag_name

Delete a remote tag

git push origin :refs/tags/tag_name

Remove the references to the deleted remote branches

git remote prune origin

Delete last commit (not pushed yet)

git reset --hard HEAD~1

List all key/value pairs for git config

git config -l

Get a value for a key in git config (for example, get git repository url):

git config --get remote.origin.url

Show all file names changed in a single commit:

git show --pretty="format:" --name-only commit_hash

Cherry Pick

git cherry-pick commit-id-from-other-branch