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

LOTR

Break to tech-stuff……
Perfect lines as the year 2010 starts!

All that is gold does not glitter,
Not all those who wander are lost;
The old that is strong does not wither,
Deep roots are not reached by the frost.
From the ashes a fire shall be woken,
A light from the shadows shall spring;
Renewed shall be blade that was broken,
The crownless again shall be king.

TCP/IP Revised

Easy definition and basic intro to TCP/IP (courtesy w3schools.com)

• TCP is for communication between applications. A communication link is established between the applications through a handshake and it persists until one of them closes it.
• IP is for communication between computers. IP is a "connection-less" communication protocol. With IP, messages (or other data) are broken up into small independent "packets" and sent between computers via the Internet. IP is responsible for "routing" each packet to the correct destination.
• When an IP packet is sent from a computer, it arrives at an IP router. The IP router is responsible for "routing" the packet to the correct destination, directly or via another router. The path the packet will follow might be different from other packets of the same communication. The router is responsible for the right addressing, depending on traffic volume, errors in the network, or other parameters.
• TCP is responsible for breaking data down into IP packets before they are sent, and for assembling the packets when they arrive. IP is responsible for sending the packets to the correct destination.
• All over the world, DNS servers are connected to the Internet. DNS servers are responsible for translating domain names into TCP/IP addresses.
• HTTP takes care of the communication between a web server and a web browser.
• HTTPS takes care of secure communication between a web server and a web browser.
• The SSL protocol is used for encryption of data for secure data transmission.
• SMTP is used for transmission of e-mails. SMTP can only transmit pure text. It cannot transmit binary data like pictures, sounds or movies.
• The MIME (Multipurpose Internet Mail Extensions) protocol lets SMTP transmit multimedia files including voice, audio, and binary data across TCP/IP networks.
• POP (Post Office Protocol) is used for downloading e-mails from an e-mail server to a personal computer. If your email program uses POP, all your emails are downloaded to your email program (also called email client), each time it connects to your email server.
• IMAP (Internet Message Access Protocol) is used for storing and retrieving e-mails. The main difference between the IMAP protocol and the POP protocol is that the IMAP protocol will not automatically download all your emails each time your email program connects to your email server. The IMAP protocol allows you to look through your email messages at the email server before you download them. With IMAP you can choose to download your messages or just delete them. This way IMAP is perfect if you need to connect to your email server from different locations, but only want to download your messages when you are back in your office.
• FTP takes care of transmission of files between computers.
• NTP (Network Time Protocol) is used to synchronize the time (the clock) between computers.
• DHCP is used for allocation of dynamic IP addresses to computers in a network.
• SNMP (Simple Network Management Protocol) is used for administration of computer networks.
• LDAP (Lightweight Directory Access Protocol) is used for collecting information about users and e-mail addresses from the internet.
• ICMP (Internet Control Message Protocol) takes care of error-handling in the network.
• ARP (Address Resolution Protocol) is used by IP to find the hardware address of a computer network card based on the IP address.
• RARP is used by IP to find the IP address based on the hardware address of a computer network card.
• BOOTP is used for booting (starting) computers from the network.
• PPTP (Point to Point Tunneling Protocol) is used for setting up a connection (tunnel) between private networks.

Persistence in Java

As I read Java Persistence with Hibernate, compiling few points on what are Object Persistence and Object/Relational Mapping and how Hibernate and JPA specification in EJB 3.0 fit into the role.

·      In an object-oriented application, persistence allows an object to outlive the process that created it.

·        Persistence of data can be thought of in terms of

o       Storage, organization, and retrieval of structured data

o       Concurrency and data integrity

o       Data sharing

·         Object - Relational paradigm mismatch (Problems in the interaction of these layers)

o       Problem of Granularity

§         In relational databases, can’t have the granularity of data that’s possible in Java (in terms of a class having another object reference, an ADT, a basic data type, etc.). UDT (User-defined Datatypes) support is available in relational databases, but there are many limitations of UDT & so not advisable to use them. This leads to less flexible SQL representation upon the object model.

o       Problem of Subtypes

§        Java has type inheritance (subclass and superclass), but a table isn’t a type, so notion of supertables and subtables is questionable. If they do implement it, they don’t follow a standard syntax and usually lead to data integrity problems.

§        SQL databases also lack an obvious way (or at least a standardized way) to represent a polymorphic association. A foreign key constraint refers to exactly one target table; it isn’t straightforward to define a foreign key that refers to multiple tables. We’d have to write a procedural constraint to enforce this kind of integrity rule.

o       Problem of Identity

§        In Java, object identity is established by either comparing memory locations (a == b) or by return value of ‘equals’ method [a.equals(b)]

§         In SQL, identity is established using primary key value.

§         Neither equals() nor == is naturally equivalent to the primary key value.

o       Problems related to Associations

§        Object-oriented languages represent associations using object references; but in the relational world, an association is represented as a foreign key column, with copies of key values.

§        Object references are inherently directional; the association is from one object to the other. They’re pointers. If an association between objects should be navigable in both directions, you must define the association twice, once in each of the associated classes.

§        On the other hand, foreign key associations aren’t by nature directional. Navigation has no meaning for a relational data model because you can create arbitrary data associations with table joins and projection.

§        Java associations can have many-to-many multiplicity. Table associations, on the other hand, are always one-to-many or one-to-one. If you wish to represent a many-to-many association in a relational database, you must introduce a new table, called a link table. This table doesn’t appear anywhere in the domain model.

o       Problem of data navigation

§        In Java, when you access a user’s billing information, you call a User.getBillingDetails().getAccountNumber() or something similar. This is the most natural way to access object-oriented data, and it’s often described as walking the object network.

§         Unfortunately, this isn’t an efficient way to retrieve data from an SQL database. You may have to query the tables in some way like this

select *

from USERS u

left outer join BILLING_DETAILS bd on bd.USER_ID = u.USER_ID

where u.USER_ID = 123

·        Serializations can’t be used for persistent layer. A serialized network of interconnected objects can only be accessed as a whole; it’s impossible to retrieve any data from the stream without deserializing the entire stream. Thus, the resulting byte stream must be considered unsuitable for arbitrary search or aggregation of large datasets. It isn’t even possible to access or update a single object or subset of objects independently. Loading and overwriting an entire object network in each transaction is no option for systems designed to support high concurrency.

·         Object/relational mapping is the automated (and transparent) persistence of objects in a Java application to the tables in a relational database, using metadata that describes the mapping between the objects and the database.

·         An ORM solution consists of the following four pieces:

o       An API for performing basic CRUD operations on objects of persistent classes.

o       A language or API for specifying queries that refers to classes and properties of classes.

o       A facility for specifying mapping metadata

o       A technique for the ORM implementation to interact with transactional objects to perform dirty checking, lazy association       fetching, and other optimization functions.

·        The new EJB 3.0 specification comes in several parts: The first part defines the new EJB programming model for session beans and message-driven beans, the deployment rules, and so on. The second part of the specification deals with persistence exclusively: entities, object/relational mapping metadata, persistence manager interfaces, and the query language. This second part is called Java Persistence API (JPA).

·        Hibernate is an open source ORM service implementation.

·        Hibernate is about 80,000 lines of code, some of which is much more difficult than  typical application code, along with 25,000 lines of unit test code.

·        Hibernate is part of the JBoss Application Server (JBoss AS), an implementation of J2EE 1.4 and Java EE 5.0. A combination of Hibernate Core, Hibernate Annotations, and Hibernate EntityManager forms the persistence engine of this application server

About the Weblog

I just thought of starting off with a tech blog, which has been long pending. And what better than to start it off with the commence of a new year, 2010. The year looks good with ample opportunities to sharpen my technical skills. And accordingly, will be sharing all bits and pieces of knowledge as I read about various technologies. Hence, what I read is what you get (to read over here!) :)