Parijat@SUN: Work hard but think smart

 

 

Master Data is the business context data of entities or objects involved in business transaction. MDM helps in creating complete, consolidated views of information. It also helps in customer data integration and product information management. Some of the entity domains where MDM is largely used are:
- Person (Customer, Patient, Subscriber, Citizen, Employee)
- Business (Client, Vendor, Supplier)
- Products (Parts, Products)

Let's take a case study where we need to consolidate customer data. French Bank B is being merged to an American Bank A. The merged banks must find the common or potentially common customers to provide them certain advantages (like free money orders if total deposits exceeds certain total), report them to agencies toom comply with certain government regulations (hiding black money in foreign account). John Green married Mary Davidson when they were in France and they have moved to USA after marriage. They have a daughter Christine. Note that Mary has changed last name after marriage. John has a different address. John and Mary has accounts in Bank B since the time they were in France. They also have account in Bank A now. Christione has account in Bank A. See how the MDM application will identify them:
- John is an assumed match and will be placed in the common customer list.
- Mary is in the same house hold and a potential match list and should be analyzed by bank individuals.
- Christine is in the same house hold.  

MDM market drivers:

• Proliferation of applications with dispersed data across disparate systems
• Increasing need to be customer-aware to deliver the right customer experience
• Just in time business models require agility and integration across the enterprise
• Ongoing mergers and acquisitions
• Compliance requirements
• Localized governmental requirements
• Focus on data governance - data ownership and data quality

SUN Mural: Open Source Master Data Management is the first and unique of its type. It has the following major components.
Master Index Studio – Provides the capability to create any domain-specific master index as we described above.
Data Integrator –Provides extract-transform-load (ETL) and supports a wide variety of data sources
Data Quality – Features matching, standardization, normalization, profiling, and cleansing capabilities
Data Mashup/Services – Provides server-side data mashup capability
Data Migrator – Provides the ability to migrate database objects across database instances

 

 

Problem Definition:
We need to schedule a fair-schedule for a football tournament played in a round robin league. A fair schedule means every team should have a match after same interval. If we have n teams there will be total of n(n-1)/2 matches. Each team should play a match after a guaranteed interval. Assuming n an even number, we can divide all the n(n-1)/2 matches in (n-1) clusters, each having eaxctly n/2 matches. In these clusters, each team should play exactly one match.Hence at the end of each cluster the total number of matches played by any team will remain the same. For example we have four teams, A, B, C, and D.
There will be 6 matches and 3 clusters and each cluster has 2 matches.
A possible clustering:

A vs B    A vs D     A vs C
C vs D    B vs C     B vs D

See that at the end of each cluster each team has played exactly same number of matches. Hence this is a fair schedule.

However note that this has a problem that team A can play the first match of cluster 1 and then can play the last match in cluster 2. If the number of matches in each cluster is 4, there will be 6 other team matches between the two matches of team A. Again team A could have the last match of cluster 1 and then first match of cluster 2 hence playing two consecutive mathces. Ensuring same number of intervals between all team's matches is the best solution but a costly one two. A suboptimal solution but a very effective one is the scenario described in the beginning.

The algorithm to solve this case should have a nXn table each cell initialized with 0.
As we schedule a match between team[i] and team[j], we replace 0 with scheduled day.

For each of the (n-1) cluster we start with a boolean array of size n, set all to true, indicationg team[i] is available for selection.
As we select a team for scheduling we set available[i] = false;

int teamCount;
int cluster = teamCount -1;
int[][] schedule;

initialize schedule to have 0 in all cells;

for each cluster do  {
            for all team do
                available[j] = true;
            for 1 to teamCount/2 {
                int nextRandom;
                do {
                    nextRandom = randomly select any available team;
                } while (!available[nextRandom]);
                int team1 = nextRandom;
                available[team1]=false;
                do {
                    nextRandom = randomly select any available team;
                } while ((schedule[team1][nextRandom] != 0) && (schedule[nextRandom][team1] != 0) || !available[nextRandom]);
                int team2 = nextRandom;
                available[team2]=false;
               
                if (schedule[team1][team2] == 0) {
                    schedule[team1][team2] = day;                   
                } else if (schedule[team2][team1] == 0) {
                    schedule[team2][team1] = day;                   
                }
                day = nextDay;
            }
}

int randomlySelectOnlyUnselected (boolean[] available) {

        int[] indexArray = new int[available.length];
        int count =-1;
        for (int i=0; i < available.length; i++) {
            if (available[i])
                indexArray[++count] = i;
        }
        if (count == -1 ) return -1;
        if (count == 0) return indexArray[0];

        Random R = new Random();
        int nextRandom = R.nextInt(count+1);
        return indexArray[nextRandom];
    }

Analyzing the time complexity:

The first of the do-while has a complexity of O(n). The secong do-while can explore almost all cells in schedule based on a fair random number generator
should be O(n²).
The outer-most for loop runs n-1 time and the inner for loop runs n/2 times.
Hence an expected time complexity O(n*(n/2)*(n+n²)) = O(n³)

Remember that the search space is all possible permuation (ordering) of all the matches being [n(n-1)/2]! and we know  [Stirling's approximation].

Problem Size	Time (ms)
10	15
12	32
16	47
20	78
24	94

  

 

Let's find a more efficient algorithm than this. Also need to discuss the additional steps required when n is an odd number.

We have a golf club parking lot with multiple entrances and exits. The parking lot has fixed number of parking spaces, say N. Some spaces are reserved for VIP (n₁) and club members (n₂). Rest (n₃) are general parking spaces. n₁ and n₂ are smaller percentage of N.  n₁ < n₂ << n₃.

The parking rule is that VIP should attempt to park in VIP space if available. If not then tries to park in club member space. Even if that is not available then parks in a general space. The club members first tries to park in a club member space and if not any such available then parks in a general space. Any other car should park only in general spaces. If no space is found following the rule, the requesting car is notified that no space is available.

We design the parking lot as a singleton with three queues implementing the parking space pool. The first queue Q₁ has all the available spaces marked VIP category, Q₂ has all the available spaces marked club member category and Q₃ has all the available general category parking spaces. If you are using Java, you can use ArrayBlockingQueue, which is a synchronized queue. We need synchronized queues as we have mutiple entrances and exits in this parking lot.

Note that the enque and deque functions are O(1) hence this solution is more efficient than having a single queue (popularly known as Priority Queue) or a simple array as the searching a space of a type will be O(n). For Priority Queues you should have either insertion O(n) or the retrieval O(n).

Here is a UML class diagram followed by the Parkinglot class.

package Parkinglot;

import java.util.concurrent.ArrayBlockingQueue;
import Vehicle.Vehicle;
/**
 *
 * @author Parijat Kar
 */
public class Parkinglot {

    private static Parkinglot P = new Parkinglot();

    private ArrayBlockingQueue<Space> q1;
    private ArrayBlockingQueue<Space> q2;
    private ArrayBlockingQueue<Space> q3;

    private Parkinglot() {

        int count = 0;
        q1 = new ArrayBlockingQueue(10);
        for (int i=0; i < 10; i++)
            q1.add(new Space(count++, 1));
        q2 = new ArrayBlockingQueue(20);
        for (int i=0; i < 20; i++)
            q2.add(new Space(count++, 2));
        q3 = new ArrayBlockingQueue(70);
        for (int i=0; i < 20; i++)
            q3.add(new Space(count++, 3));

    }

    public Space park (Vehicle v) throws ParkingException {

        Space next = null;
        switch (v.getType()) {
            case 1: next = q1.poll();
                    if (next != null) break;
            case 2: next = q2.poll();
                    if (next != null) break;
            case 3: next = q3.poll();
                    if (next != null) break;
            default:  throw new ParkingException("Not a know vehicle type " + v.getType());
        }

        return next;

    }

    public void exit (Vehicle v) throws ParkingException {

        Space free = v.getS();
        switch (v.getType()) {
            case 1: q1.add(free); break;
            case 2: q2.add(free); break;
            case 3: q3.add(free); break;
            default:  throw new ParkingException("Not a know vehicle type " + v.getType());
        }

    }

    public static Parkinglot getRef() {
        return P;
    }

}

If you are not interested in the transaction history, a lot of database space could be saved for a Master Index project if the BLOB field which captures the delta for each transaction is not saved in the transaction table.

You can live without this delta if you are not doing and unmerge and not trying to recreate transaction objects from the transaction history.

To achieve a no-history mode for Master Index, as MIDM by default shows the transaction history tab, we need to hide that. Second as we are not interested in saving the delta we should not compute the delta or save that on the table. The first one will save some CPU time and second one will improve the database performance and the overall performance.

To prevent calculation of the delta, we should stop all the TransactionObject.setDelta(TransactionLog.getLogs("Enterprise", eo)) calls in the TransactionMgrImpl.java. We should do this for all public APIs in TransactionMgrImpl.

The transaction record update in the transaction table is two step. The first update writes everything in the transaction table except the delta and the second step is to update the delta for the same transaction record. This is done in individual createTransactionObjectDB method of the particular DBAdapter implementation of the project (could be Oracle, MySQL or SQLServer).
This is done in two steps as the writing back the BLOB to the database requires additional processing. To optimize the performance in no-history mode we must check such mode and stop the delta to be saved to the database.

However the idea of simply deleting the BLOB fields from the database could result in set of serious problems as several methods in TransactionMgrImpl are public and all the basic Master Index functionality invokes these APIs. Whenever such APIs are invoked to set delta or recreate a transaction object from transaction log, there will be severe exceptions as those APIs will try to access the BLOB which does not exist any more.

Conclusion: No-history can be introduced as a project property but has to be carefully handled as described above in the various level of implementation, to prevent functionality failure, optimization, performance and scalability.

Programmatic login is used with context settings for getting a Mastercontroller handle from MDM client program.

The following parameter needs to be passed to the JVM

-Djava.security.auth.login.config=/appclientlogin.conf

If you are using Netbeans 6.5 and Windows, go to the project properties, at the "run" settings put

-Djava.security.auth.login.config=C:\JavaCAPS6\appserver\lib\appclient\appclientlogin.conf as the VM option.

where PATH is the fully qualified path to the appclientlogin.conf. You can get this file from your glassfish installation. This file should be shipped with your client code.

public MDMClient() {
        init();
        mc = getMasterController();
    }
    
public void init() {
       
        Hashtable env = new Hashtable();
        env.put("org.omg.CORBA.ORBInitialHost", "localhost");
        env.put("org.omg.CORBA.ORBInitialPort", "3700");
        try {
            ic = new InitialContext(env);
        } catch (Exception e) {
            System.out.println("Can not load the initial context");
        }       
    }
   
    public MasterControllerRemote getMasterController() {
       
        MasterControllerRemote mcr = null;
        try {
            ProgrammaticLogin programmaticLogin = new ProgrammaticLogin();           
            Boolean login = programmaticLogin.login("ui", "ui", "file", false);
            mcr = (MasterControllerRemote) ic.lookup("ejb/PersonMasterController");
        } catch (NamingException ex) {
            Logger.getLogger(MDMClient.class.getName()).log(Level.SEVERE, null, ex);
        } catch (Exception ex) {
            System.out.println("Failed programmatic login or getting MC");
        }
        return mcr;
       
    }

Question: Can we achieve nested transaction in EJB 3 using a single connection, supporting different databases as Oracle, MySQL and SQLServer?

Use case:

1. Start a stateless session bean.

2. Get a connection

3. Update table A. (Transaction 1)

4. Update table B. (Transaction 2)

5. Commit the Transaction 2.

6. Based on some logic commit or rollback Transaction 1.

7. Close connection.

Problem: If we have XA mode, rolling back at step 6 will enforce Transaction 2 to roll back as well?

A solution using Oracle feature: PRAGMA AUTONOMOUS TRANSACTION in oracle actually can make a stored procedure or function independent transaction even if it is nested inside another transaction. For example the sequence ID generator in MDM.

CREATE  OR

REPLACE FUNCTION SEQMGR (Seq_Name_In IN VARCHAR2, Chunk_Size_In IN INTEGER)

RETURN INTEGER

IS

PRAGMA AUTONOMOUS_TRANSACTION;

Count_out INTEGER := 0;

BEGIN

Count_out := 0;

UPDATE SBYN_SEQ_TABLE SET seq_count = seq_count+Chunk_Size_In WHERE seq_name = Seq_Name_In;

SELECT seq_count-Chunk_Size_In INTO Count_out FROM SBYN_SEQ_TABLE WHERE seq_name = Seq_Name_In;

COMMIT;

RETURN Count_out;

EXCEPTION WHEN OTHERS THEN RETURN 0;

END SEQMGR;

Problem 2: MySQL does not support AUTONOMOUS. There could be other databases too which do not support this.

Possible Solution Exploration: java.sql.Savepoint  Interface does not help. It would have helped if the outer transaction committed and the inner transaction rolled back. Use of two UserTransactions does not help if we have the same connection source if we use the XA mode.

Condition: Max connection pool size 10
and running 10 threads each invoking different MasterControllerEJB APIs. All of these APIs fetch a connection from the connection pool. Hence we used up 10 connection. At this point if any one of these threads need to get a new sequence ID from the database, we need another connection. But we can not get this connection as all the connections from the application server pool are exhausted. So this thread will continue to wait here. But as this method to get the ID is a synchronized block on a HashMap, all other threads will continue to wait for the lock on the HashMap to be released and that will never happen. So we are in a deadlock.

synchronized(hashmap) {

    get some value from the hashmap;

    if value meets some codition get a connection from the application server pool;

    use this connection to update some table in database and reload the hashmap;

}

Solution: If you have n threads, always set your minimum connection pool size to n + 2 or higher.

Exploring: java.util.concurrent.atomic.AtomicInteger

How to migrate from eView513 to eView 6.

1. Create a Master Index project in NB6 via MDM wizard.
2. Overwrite master.xml, object.xml, mefa.xml, query.xml, update.xml, validation.xml in NB6 project with corresponding files from 5.x project.
    - edm.xml has changed considerably since there will be entirely new EDM. We are working on the details for upgrade.
    - there are some new options in master.xml regarding XA, that should be taken into consideration when overwriting.
3. Ensure that Master Index source classes in these xml configuration files,  uses new package prefix (com.sun.mdm.index) - So overwrite 5.x class prefix "com.stc.eindex" with "com.sun.mdm.index"
4. If there are any plugin classes in 5.x, move them over to $Project-ejb/source-packages. Ensure  new Master Index class name prefix is used in these plugin classes.
5. Use Sun Application server JDBC connection pool configuration instead of Oracle/SQLserver eways. Connection pool configuration is same as in 5.1.3
6. Outbound Topic - In Sun Appserver, create a topic of naming convention <ObjectName>Topic. During run time, this will then publish outbound messages to this topic.
7. 5.x OTD methods (that are invoked from BPEL/JCD) - During Master Index project generation, An <ObjectName>EJB webservice is created during generate.
   Use these methods in the old BPEL/JCD, if these need to be invoked in 5.x environment.
8. Matching - replace the matchconfigfile.cfg with 5.x matchconfigfile.cfg.

9. Standardization - If there is no modification in standardization stuff, then does not require any changes.
Otherwise more details will be spelled out.

10. Generate and deploy to Glassfish.

Additional Requirements:

1. Use MI wizard to create a new Master Index project that mirrors the old eView project, e.g "Person".
2. Copy old edm.xml contents to midm.xml, change 3 edm references to midm:

<edm xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="schema/EDM.xsd">
</edm>

<midm xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="schema/midm.xsd">
</midm>

3. Bring up MI Configuration Editor, make changes to force "Save" action.  Conversion will occur in save action.

4. Check what are converted:
<node-xxxx>  ->  <node> <name>xxxx</name>
<field-xxxx>  ->  <field> <name>xxxx</name>

                            <dashboard> added
<eo-search>  ->  <record-details>
<create-eo> removed
<history>  ->  <transactions>
<matching-review>  -> <duplicate-records> and <assumed-matches>
                       <source-record> added
<reports>  ->  <reports>  //with sub screens
<audit-log>  ->  <audit-log>  //with more atributes

For more details see http://developers.sun.com/docs/javacaps/upgrading/jcapsupgrd.jcapsupgrd.html

We have an array of N-1 numbers which holds numbers from 1 to N but a missing one. The array is unsorted and in random order. What is the fastest way we can find the missing number?

If we do the best sorting it will be of order n log n. Then we can do a linear search of order n.

Is there a faster way to find the number? We can use another array of size N. For each number in the first array as we do a linear traversal we can set a flag in the second array in that position to true and finally the only index not set to true should be the missing number.

What about not even using the extra memory? Using some maths. Some of first N natural numbers is N(N+1)/2. We can add all the numbers in the array. That should be of order n. Then we subtract that from the previous sum and that is the number. 

Three Pandits (priests/missionaries) and three Asuras (villains/cannibals) come to a river. A rowboat that seats two is available. If the villains ever outnumber the priests on either bank of the river, the priests will be eaten. How shall they cross the river?

This is a nice game on one Durga Puja website (www.anandautsav.com).

For many of us who have studied a bit in Artificial Intelligence, is a First Order Logic problem which was nicely represented by Amarel (1971). While the circumscription or non-monotonic propositional logic.

Once again this is old wine in blog-bottle but with a different and less tried approach. I was modeling this problem using reinforcement learning. Those who are not much familiar with it, here is a definition:

Reinforcement Learning model consists of:

1. a set of environment states S;
2. a set of actions A; and
3. a set of scalar reward in R.

At each time t, the program perceives its state and the set of possible actions A(s_t). It chooses an action and receives from the environment the new state

s_{t + 1} and a reward r_{t + 1}. Based on these interactions, the reinforcement learning agent must develop a policy  which maximizes the quantity

I have the program which does the solution. I have a depth first search, a depth-limited search and finally the reinforcement version.

For the reinforcement approach, I define the state with a pair count of villains and priests on the both origin and destination banks. Initially [{3,3};{0,0}] and the goal state is [{0,0};{3,3}]. Actions are divided in two groups. Action type a[0] and a[1]. The first one is for origin side to destination side and the other one is for the reverse direction.

We have three possible actions in a[0], the boat can be occupied by

1. One pandit and one asura.

2. Two pandits.

3. Two asuras

We have only two possible actions in a[1], the boat can be occupied by

1. One pandit
2. One asura

It can not return empty.

The reward is defined as,

If count of pandits >= count of asuras in origin side = + 10* difference

Else if  count of pandits < count of asuras in origin side = (-100* difference)

+

If count of pandits >= count of asuras in destination side = + 10* difference

Else if  count of pandits < count of asuras in destination side = (-100* difference)

+

20*(total number of asuras and pandits on destination side)

So, in the first action, if we send one asura and one pandit to the other side, the reward is

0 + 0 + 40 =40.

And the new state is [{2, 2};{1,1}]

Next the pandit comes back to the origin side.

So after the second action the reward is

10 + 0 + 20 = 30

The point is that you have to chose the reward values carefully, so that the program converges.

Most of us try divide and conquer techniques in effort of optimization of the time complexity. But few simpler examples becomes so complex when divided right but not conquered properly.

Lets find the max and min from an unsorted array. There is a linear solution, O(n), which all of us will try. Go through all the elements, save the latest min and max, compare with the next array element and update the latest if you find a better one.

The problem is created when you are told that can you do any better than O(n)? First thing which comes in our mind is may be divide and conquer. But can we get a solution in a general two node tree (not a binary search tree) without traversing each and every node? And if we traverse each and every node what is the complexity?

Last month we saw the table problem. This time a harder one. Some of you who graduated high school in West Bengal, India, probably have seen this problem many times. In that sense this is old wine in blog's bottle. But I could not stop myself to dig into this problem as I came into a customer scenario in message queues which closely resembled this one. Here is it: five letters (for different addresses) and five envelops (with printed addresses). What is the probability that at least one of them will be in the wrong envelop? What is the probability that all of them will be in the wrong envelop?

This one is tricky. I was doing some trial and error to improve some performance issues in eView. This question just came into my mind. We have four objects in a relational database system. Each object is related to each other in a many to many relationship. How many tables do we need to maintain a third normal form for this database?

Those who do not remember third normal form, here is some definition: No non-prime attribute of the table is transitively dependent on a candidate key.

Most of you can probably guess that this is more about permutation and combination. But how exactly we can derive the equation?

My guess the answer is ⁿ C ₂. To prove this, take n=2 and show that this is true. Then assume that this is true for n and if so, then there is a way to show that this is true for n + 1. Hmm.. what about that?

This is a simpler problem but the data structure could be complex. We need a Hashmap design, from which we can always can find the order the elements were inserted. Don't ask me what this special hashmap will be used for.

Java has a LinkedHashMap. This is a combination of LinkedList and a HashMap. This data structure has a O(1) retrieval time. But what about insertion and deletion from this data structure.

Suppose we have three processors, and several tasks, which we want to run on these processors. The time, which a task requires, may very from processor to processor. The problem is to decide what order to run these tasks in so that they will all be finished as soon as possible. We assume that processes will not be interrupted. That is, once a task begins running on a processor, it will continue running to completion. 

More formally, we need some algorithm, which takes as input a list of sequences of three positive integers r1, r2, and r3. Each triplet corresponds to one task, and the integers are the runtimes for that task on each of the three processors. The output should be a schedule of the tasks to be run on each processor, together with the total run time for the entire job.

Here, we have tried to make a general solution to the problem, i.e. instead of three processors; we are trying to solve it for P processors. We are also generating all possible solutions.

Data Structure:

A Boolean Matrix of size no of tasks X no of processors.

Boolean Schedule[NO_OF_PROCESSORS][NO_OF_TASKSS];

if task i has been scheduled for processor j then
we assign Schedule[i][j]=true,
else Schedule[i][j]=false.                                                                              

A Cost Matrix of size no of tasks X no of processors.

int Cost[NO_OF_TASKS][NO_OF_PROCESSORS];
Cost[i][j]=time required to complete task i on processor j. 

A Bounding value of scheduling time.

The Algorithm:           

int Bound;

typedef    Schedule=array[1..NO_OF_PROCESSORS][1..NO_OF_TASKS]  of Boolean;

Linked List bestSchedule of Schedule;
int BoundingTime=minimum of the column sums in the task matrix; 

DFSTS(Boolean currentSchedule, integer  processor, integer task)

begin
            if (task = NO_OF_TASKS)
            begin
                        if(cost(currentSchedule) <= cost(bestSchedule))
                        begin
                                    Save(currentSchedule);
                                    BoundingTime=cost(currentSchedule)
                        end
            end;
            else
            begin
                        repeat
                                    Schedule[processor][task]:=true;
                                    if (cost(currentSchedule) < BoundingTime)
                                                DFSTS(currentSchedule, 0, task + 1);
                                    else
                                                Schedule[processor][task]:=false;
                                    processor:=processor + 1;
                        until(processor > NO_OF_PROCESSORS)
            end
end;

Time Complexity:

The worst-case time complexity for this algorithm is same as that of the brute force DFS. If we don’t have a good bounding function, the algorithm will traverse the whole tree hence resulting in an exponential time complexity O(PT), where P is the number of Processors and T is the number of tasks.

Memory Requirement:                       

We are using a linked list of a Boolean Matrix. So if we have maximum S solutions at any time of the tree expansion. The size of memory is O(S). But in practical case maximum value of S is 300 or 400. So we have almost constant size of memory.  

In 1769 British explorer Captain James Cook discovered Australia and New Zealand. In 2007 Captain Kar started his voyage from US for the same destination to verify Captain Cook's discovery. No worries!! We still invent and sell computer technologies.

Traveling for job has become part of life now a days. But this particular one was special to me as this was the first time I was in southern hemisphere. Coming straight to my findings in Australia and New Zealand, I will mostly elaborate south island in New Zealand, Cairns in Australia and briefly Sydney, Auckland and Rotarua.

The first major challenge I had after reaching New Zealand is the left hand driving. After quite some effort and instance based learning I found the indicators and wipers in the right place. Several times I sprinkled the cleaning liquid instead of left or right indicator and vice versa. On undivided highway corrected the wrong side seeing the traffic coming from opposite side. Adjusted to 'give way' instead of 'yield'. Keeping left to the 'white' median instead of keeping right to 'yellow' median. This median was quite confusing as I used to understand white line to be only a lane divider.

 

It is almost eight hours drive from Christchurch to Te Anau, a small town in the south west part of the south island. Almost any drive in New Zealand is very beautiful. Absolute green every where. Lambs rambling on the green looks like flowers from the roads. The other thing I should mention is the relentless rain in the south island. It does not come down in bucket but a nice drizzle is always there.

I have not seen any sheep-dog in life before a huge sheep herd was crossing our road towards Mount Cook. We were taking a detour on the way to Te Anau. These sheep-dogs are very smart and was driving large number of sheeps very efficiently. 

Aoraki/Mount Cook is the highest mountain in New Zealand, a peak in the Southern Alps range, which runs the length of the West Coast of the South Island. A popular tourist destination, it is also a favourite challenge for mountain climbers. The Tasman Glacier and Hooker Glacier flow down its slopes.

We stayed at a place Cromwell on the way to Te Anau as we got late because of the Mount Cook detour. Cromwell is a small town. Tourism is the bread and butter for these small towns. I have to say hotels are luxury in New Zealand. You can get a great suit for 200 NZD. We also stopped at a place on the way to Te Anau to buy ice cream made of fresh fruit. And I must mention lamb pie. It was awesome. Lamb with mint jelly is a specialty in New Zealand and no one should miss. It tastes like ice cream. Believe me or not, the meat melts inside mouth. However Madhu told me that how we can think about eating lamb after seeing them grazing on the fields. Hmm....

South west part of the south island is known as Fiordland National Park. Fiords (origin Norwegian Fjord) are very long inlets from the sea with high steeply sloped walled sides. A fjord (or fiord) is a landform created during a period of glaciations.  But in New Zealand the early explorers thought that these fiords were sounds and named them as sound - Milford sound and Doubtful sound namely. In geography a sound is a large sea or ocean inlet larger than a bay.

The road to Milford Sound is considered to be one of the world’s best alpine drives. If you aren't up for that, there are plenty of tour operators providing travel to Milford. Most visitors to Milford Sound opt for a cruise because it is the best way to see all of the sound. You get to admire the mountain peaks and the waterfalls that
are flowing all year round. On our cruise, there were dolphins swimming alongside and we also saw seals laying on rocks along the fiord.

Doubtful Sound is the second longest in Fiordland at 40 km long. On a cruise down Doubtful Sound you will experience more shades of lush green than you knew existed, while you drift over 400 meter deep water. In both Milford and Doubtful Sounds, you will experience a host of wildlife; seals and crested penguins (remember Lovelin in Happy Feet?)  gather on the shores, and sometimes bottlenosed dolphins can be sighted playfully swimming along side the boat.

Individuals have their own favourites but there can be no doubting of Lake Manapouri’s supreme and unique beauty, a beauty that only begins to be fully revealed and appreciated by taking a trip on the lake itself. Brooding, tranquil, tempestuous, serene, glowering - these are all true of Lake Manapouri in one or more of its compelling moods. To drift quietly along in the North Arm, on a clear Fiordland day, is to experience sights and sounds of exquisite beauty. A feature of the lake is the number of coves, bays and islands, set in astonishingly pure water. Thirty five wooded islands dot the lake, and the shoreline extends for 150 km, with dense bush and interspaced with lovely beaches.

It would not complete Te Anau if I miss the glow worm cave.  They take you in small boats inside the cave, inside which seemed to be a perfect black body and the glow worms are beautiful at an intimate end of the cave. We started moving towards the north along the west cost. The drive on the highway 6 through Wanaka and Haast is extremely beautiful. Winding roads, shades of green, frequent roadside falls and fountains are associated with narrow road, single lane wooden bridge. It is difficult for the driver. You have plenty to see but need to concentrate absolutely on the pavement. We stopped at several falls. Went close to the river, touched the water. Water in the river is absolutely transparent and cool.

Wanaka has the world's famous puzzle house. Leaving Wanaka, we continued towards Haast, the heart of west coast and Westland National Park. Due to bad weathers we had to stop at Makarora. We stayed at a wilderness resort. This was an 'A-frame', you can say a better version of tent. Absolutely amidst wilderness where no light outside and you will keep on hearing a humming noise of insects. A wild hare stopped in front of our car.

Ancient forest, bush clad lakes, glistening glaciers, and impetuous rivers make Westland an area of imposing beauty. Nextmorning we travelled up the wild and wet West Coast on avenues framed by the green lushness of rainforest. In the afternoon we visited the famous Franz Josef and Fox Glacier regions, with excellent views of Mt. Cook.

This is the other work I am doing at SUN. SWIFT OTDs and eWays provide financial solutions to banks for funds transfer information. Here is a publicly available summary.

The Sun JavaTM Composite Application Platform Suite (Java CAPS) has been awarded the SWIFTReady Financial EAI Gold label by SWIFT. This is the eighth year Sun CAPS has won the award. The certification award indicates adherence to established guidelines for Straight Through Processing (STP), including transformation and routing, for reliable, secure and assured messaging.

SWIFT is the Society for Worldwide Interbank Financial Telecommunications, an industry-owned co-operative supplying secure, standardized messaging services and interface software to over 7,800 financial institutions in more than 200 countries. The standards in STP have lowered operating costs for members of the SWIFT global financial community. SWIFT participants can integrate new SWIFT services with their existing applications and infrastructure. New services from Sun include the Sun SeeBeyond eWay Adapter for SWIFT Alliance Gateway for Java CAPS. Sun has also developed a new SWIFT message monitoring solution.

Java CAPS offers a highly flexible and scalable integration solution for financial institutions. It is a suite of infrastructure software formed by Sun's acquisition of SeeBeyond's business integration software and the JavaTM Enterprise System (JES).

I have worked on many different searches in past, particularly, in graduate school, working on Artificial Intelligence. Backtracking, Branch and bound and dynamic programming... I remember some of those techniques.

Here is the current problem. We have a mXn matrix (say pixels). Some of the pixels are red and some of them are white and it is a random distribution. We are interested only in those red pixels, which does not have any adjacent red pixel. Any pixel in the middle (not on the edge) has eight adjacent pixels. Our target pixels are those one which has no adjacent pixel which is of the same color.

What is your best estimate on the time complexity.

One dumb solution:

For each of the mn pixels do  {
     note current color; 
     flag = true;                                                                                                                                  

     For each of the 8 adjacent pixel {
                If color is same set flag false and break;
      }

      If flag is true add this pixel to solution list.
}

This solution is clearly O(8mn). Considering n >> 8 and m close to n, O(n ²). Any idea how we can approach something in linear or log-linear?   

This problem might sound very simple to most of you but I wanted to post this as there could be several variations in the solution. Also I can remember from my previous job how a candidate gave a much convoluted answer to this problem. Well, first the problem. I have an array A of T numbers, not sorted. I also have a magic number N.  N can be obtained by adding several smaller numbers, but there is no limit on the count of the numbers which are being added. So, a1 + a2 + ..+an=N, where n <=T. For example N is 65. So 65 can be obtained as 65, 10 + 55, 5 + 7 + 12 + 41 etc. and in this case all these numbers 5, 7, 10, 12, 41 and 65 are memebrs of the unsorted array A.

The problem is that we need all such sets which adds up to N. Definitely this is a NP complete problem. But how do you approach with minimum number of temporary memory and the best O function.