Thursday, January 21, 2010

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)

  1. 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.
  2. Given an n X n array with rows sorted and cols sorted; find the number of negative elements in most efficient way.
  3. 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.
  4. 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.
  5. Give the algorithm to multiply large matrix on system with very less memory which can not hold even one column or one row.
  6. Write a program to rotate a matrix by 90 degrees.
  7. Write a code to calculate kth power of a matrix of size NxN. You can assume that matrix multiplication is O(n^3).
  8. Print a given matrix in a spiral manner.
  9. Suppose you have a NxN matrix of positive and negative integers. Find the submatrix with the maximum sum of its elements.
  10. Multiply two given matrices.
  11. 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.

Wednesday, January 20, 2010

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!) :)