Pages

Friday, April 3, 2015

Largest rectangle in a histogram

The below code finds the rectangle with maximum area in a histogram with O(n) time complexity.

    public static void maxRectArea(int a[], int b[]) {
        // this is a maximization problem
        // irrespective of the height of the the next bar
        // we have to compare the area if including next bar exceeds the current area then we have to include the bar.
        // stop the expansion and proceed further until end of input.
        // 6 2 5 4 5  1 6
        // 6 2 5 8 12 1 6
        int i = 0;
        int max = -1;
        int e = 0;

        while (i < a.length) {
            if (i == 0)
                e = b[i] = a[i];
            else {
                if (a[i] < a[i-1]) {
                    int t = b[i-1] / e;
                    if (((t+1) * a[i]) < b[i-1])
                        e = b[i] = a[i];
                    else {
                        e = a[i];
                        b[i] = (t+1) * a[i];    
                    }
                }
                else if (a[i] == a[i-1]) {
                    b[i] = b[i-1] + e;
                }
                else if (a[i] > a[i-1]) {
                    if ((b[i-1] + e) > a[i]) {
                        b[i] = b[i-1] + e;
                    }
                    else {
                        e = b[i] = a[i];
                    }
                }         
            }
            i++;
        }
    }

Sunday, March 8, 2015

Using recursion

//Substring using recursion

substring("", userinput, 0, userinput.length());

public static void substring(String fixed, String str, int step, int len) {

     if (step < len) {

       System.out.printf("%d :%s \n", ++counter, fixed);

       while (step < len) {

         substring(fixed + str.charAt(step), str, step + 1, len);

         step ++;

       }
     }

     else

     System.out.printf("%d :%s \n", ++counter, fixed);

   }

//Anagram using recursion

  public static void anagram(String str, int len) {

    anagram0("", str, len);

  }

  public static void anagram0(String first, String str,

                              int len) {

    String left = "", right = "";

    if (len == 1) {

      System.out.println(":" + first + str);

    }

    else {

      for (int pos = 0; pos < len; pos++) {

        String temp = "" + str.charAt(pos);

        left = str.substring(0, pos);

        if (pos + 1 == len)

          right = "";

        else

          right = str.substring(pos + 1, len);

        anagram0(first + temp, left + right, len - 1);

      }

    }

  }

Tuesday, July 8, 2014

Imagining our data normalized seamlessly across globe

After the advent of database technology, the quantum of data generated is increasing in exponential fashion. Is all the data being generated is unique, consistent and stored securely? The answer is No. We create multiple accounts in Google, Twitter, Facebook etc and it is more or less redundant. Also it is possible that un-necessary/un-wanted information being used by various Data Analytic firms that holds several billion dollar value. Are we interested in only finding a short term marketing solution by compromising the value of data.

Imagine a world organized with people's data uniformly, consistently and securely. The advantage of this paradigm is that we can reduce disk space consumption (Environment friendly), preserve the integrity of our data (Fraud elimination), avoid entering our name/address/dob etc while requesting for a new online service (Consistent and fool-proof) and most importantly we can limit the spread of our data to malicious users.