Productive Innovation @ Google Stalled?

Google may say “Failure is always an option at Google”, but from the recent developments and the kind of closures of businesses/developments coming out of Google, looks like its got a tough road ahead for not only just innovating, but getting profits out of it too! Closure of online Google Nexus store, stoppage of development of Wave, a weak attempt to tackle Twitter with low intensity ‘Buzz’, on-course project to challenge the social networking giants ‘Facebook’ with already a fading app ‘Orkut’ in arsenal! All these don’t look like Google, the one who still reigns in the domain of search! Maybe its because of ever-growing competitors or delay by Google to enter into a particular field. It may be doing huge profits in Search field, but from technology and innovation perspective, it long time due for Google to come out with something big, eye-catching and off-course profitable! Can look out for Google Apps and Android!

Never such a piece of code in life!

while (life) {
    ...
    if(!b.exists())
        self.exit();
    ...
}

The Sieve to detect Primes

Literally, Sieve is “A utensil for separating the finer and coarser parts of a pulverized or granulated substance from each other”. Eratosthenes, a Greek Mathematician, came up with such a sieve to filter out Prime numbers from a given set of integers. The process/algorithm came to be known as Sieve of Eratosthenes!
The Algo is pretty simple, start with number 2, cross all its multiples (till MAX_NUMBER), proceed with the next number 3 and cross all its multiples too and so on. The remaining numbers in the set will be primes. The algo itself brings in some optimizations!

1. All even numbers get cancelled in first iteration for 2. Next number (3) onwards, start directly checking for multiples starting with the square of the number.
2. The multiples need to be crossed for numbers < square root (MAX_NUMBER), because rest of the multiples would have got crossed earlier itself.

The code in Java for the Sieve of Eratosthenes is as follows:

public class SieveEratosthenes {
  private static final int MAX_NUMBER = 1000;
  public static void main(String[] args) {
    boolean[] arr = new boolean[MAX_NUMBER];
    int i, j;
    
    //Initialize the Boolean array to TRUE (i.e. Prime)
    for (i = 0; i < arr.length; i++)
      arr[i] = Boolean.TRUE;
    
    //Finish with all divisors of 2 to optimize code for the remaining
    for (i = 2; 2 * i < MAX_NUMBER; i++)
      arr[2 * i] = Boolean.FALSE;
    
    //Only odd numbers need to be considered in both loops, since
    //   Odd * Even = Even 
    //And all evens are covered as multiples of 2
    for (i = 3; i < (Math.sqrt(MAX_NUMBER)); i += 2) {      
      for (j = i; j * i < MAX_NUMBER; j += 2)
        arr[j * i] = Boolean.FALSE;
    }
    System.out.println("The primes below " + MAX_NUMBER + " are : ");
    int count = 0;
    for (i = 2; i < arr.length; i++)
      if (arr[i]) {
        System.out.println(i);
        count++;        
      }
    System.out.println("The total no of primes till " + MAX_NUMBER +  " are : " + count);
  }
}

Java Books

4 Books you should read if you adore Java!

1. JLS : Java Language Specification, the blue-print of Java. This book gives an in-depth understanding of Java architecture.
2. SCJP : Almost all concepts cleared, from programming point of view.
3. Effective Java and Java Puzzlers : These two are mind-boggling books. If you feel you are a Java-Guru, do give these a try and verify it out for yourself! :)

Please feel free to add-on and share any other master-pieces!

Java Puzzlers

Borrowed from Java Puzzlers. An awesome book BTW!!
Guess the output of the two programs below:

1.
public class SetTest {

    public static final String[] URLNAMES =  {
        "http://javapuzzlers.com",
        "http://apache2-snort.skybar.dreamhost.com",
        "http://www.google.com",
        "http://javapuzzlers.com",
        "http://findbugs.sourceforge.net",
        "http://cs.umd.edu"
    };

    public static void main(String[] args) throws MalformedURLException {
        Set favourites = new HashSet();

        for (String names : URLNAMES) {
            favourites.add(new URL(names));
        }
        System.out.println("Size is : " + favourites.size());
    }
}

2.
public class Elvis {

    public static final Elvis INSTANCE = new Elvis();
    private final int beltSize;
    private static final int CURRENT_YEAR =
            Calendar.getInstance().get(Calendar.YEAR);

    private Elvis() {
        beltSize = CURRENT_YEAR - 1930;
    }

    public int beltSize() {
        return beltSize;
    }

    public static void main(String[] args) {
        System.out.println("Elvis wears a size " +
                INSTANCE.beltSize() + " belt.");
    }
}

Output 1:

Prints 4, if connected to internet and 5 else!! :) Checks for host names and in turn IP addresses for the site names entered as URL objects. Apparently, first and second strings resolve to same IP address. (Haven't verified it though, trusting the author!). URL equal() and hashcode() methods are broken, so, instead use URI objects and URI.create() method to create objects!

Output 2:
-1930
Initializing sequence when an object is created. First, static fields get default values, so INSTANCE defaulted to null and CURRENT_YEAR defaulted to 0. Then static initializers get called, accordingly, new Elvis() gets executed and beltsize gets initialized to 0-1930 = -1930!!!! Hence, the output..

Wonders of HTML5

With the up-coming of HTML5 (Web Applications 1.0), lots of technologies and browsers specializations are expected to suffer setback since it makes the webpage more "lively" as compared to the HTML 4 specification. Went through an introductory talk by Brad Neuberg (Developer Advocate @ Google) on HTML5 and its key features. I was curious about the hype on HTML5 and in the quest to get a jist of the thing, went on an exploration spree. The key features portrayed in the talk were :

1. Canvas/SVG: Interactive drawing on a web-page is being provided through the SVG tags and Canvas API's (javascript). Interesting features that enables dynamic modification of attributes of a graphics element on the screen are provided by the API.

2. Video: This is a feature that may affect the usage of frameworks that provide for Rich Internet Applications (like MS Silverlight, Sun JavaFX, Adobe Flash, etc.) HTML5 will have tags to embed the video along with provision for controls to play/pause/play-next/play-previous/volume/size, etc. Also, attractive javascript events can be defined on the video through its ID. No need for third party RIA players to play the videos!

3. GeoLocation: API's have been provided to get the location of the web-user and it fetches its data from GPS, IP as well as Mobile providers (Cell phone). Useful in Social Apps, Gaming, etc.  

4. App Cache: Create an application manifest to save the state of a web application onto local machine and later load the app from the cache by invoking an API, all through HTML and javascript, without using third party storage API's like Google Gears, etc. Primarily this assists offline usage of files. This may mean lowering of market value for third party extensions. Google, though already has started providing support for HTML5 and porting apps to support this revolutionary language. 

5. Web Workers: This is something, which will further improvise on what Chrome excels in. The latter spawns a separate process to serve each web request in a tab/browser window. This was to remove the situation wherein traditional browsers hang executing a java-script in background. HTML5 on other hand, supports for execution of javascript in separate thread, so that they don't affect the state of browser. But, these threads won't have access to the elements on page from which they were spawned. They can carry on with function execution and return the result back to the invoking page. This serves to remove the overhead due to separate process creation for each webpage request, and also removes the hanging of browser window due to on-going javascript execution.
Though HTML5 is still in draft phase, the support for the tags and API's are already available in the latest releases of Chrome, Firefox, Opera and IE! Looks revolutionary, apps have to be re-written to make HTML self-sufficient to render pages and remove dependency on third-party apps to render elements.

The World is a Matrix

Some interesting programming questions related to Matrices. Firstly, get to know what’s a matrix, inverse of matrix, transpose of matrix.

1.     Input is a matrix of size n x m of 0's and 1's. eg:
1 0 0 1
0 0 1 0
0 0 0 0

If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1

Solution should be with Time complexity = O(n*m) and space complexity = O(1)

use the first row to record columns needed to be set as all 1's
use the first column to record rows needed to be set as all 1's

1. scan through the matrix, if (a[x][y]==1) {a[0][y]=1; a[x][0]=1}; time O(m*n)
2. scan through the matrix again, for a[x][y], if (a[0][y]==1 || a[x][0]==1) a[x][y] = 1; time O(m*n)

overall time O(m*n)
auxiliary space O(1)

2. Imagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum sub-square such that all four borders are filled with black pixel.
3. Given an n X n array with rows sorted and cols sorted; find the number of negative elements in most efficient way.
4. Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.
5. You are given a two dimensional array (say 5*5) in which all the rows as well as the columns are sorted. Describe an efficient algorithm to discover if an element is present or not.
6. Give the algorithm to multiply large matrix on system with very less memory which can not hold even one column or one row.
7. Write a program to rotate a matrix by 90 degrees.
8. Write a code to calculate kth power of a matrix of size NxN. You can assume that matrix multiplication is O(n^3).
9. Print a given matrix in a spiral manner.
10. Suppose you have a NxN matrix of positive and negative integers. Find the submatrix with the maximum sum of its elements.
11. Multiply two given matrices.
12. Given a M x N matrix with 0's and 1's, find the largest square matrix consisting on 1's and also find the largest rectangular matrix consisting of 0's