Find duplicates in a array of elements

You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Algorithm -
1. Read input from startPos

2. If input is within the maxRange or it's not in correct place then it's a candidate to be replaced else incrementStartPos

3. finalPosition for input is input[i]

4. if finalPosition < maxRange then swap input with finalPosition and increment finalPosition with MaxRange

5. else no need to swap as previous instances of this element are recorded at finalPos so just increment finalPosition with MaxRange to record another instance

6. if input at startPos is in correct place or reached zero then increment startPos++ till you go through end of Array

7. Iterate through the array and divide each element with maxRange. The divisor indicates how many times a element was repeated and 0 indicates a missing element

Example 

1. Since the number's are in the range of 1..n

2. Start with a[0] and put that element in the right place and increase the element by n (sg:: if a[0]=8 and n=10 then a[8] = 18) to ensure that this element has been placed correctly.
3. Put a[8] in step1 in a[0] if (a[i] < n ) and repeat step2 till a[0] = 11 (1+n(10) = 11) in which case move to a[1]
4. At any point if you get a[i] > n which means this element is a duplicate increment a[i] +nEg: if an array had
(2, 3, 4, 3, 2}
1. n=5 after step1 we'll get
{3, 7, 4, 3, 2}
2. now a[0] = 3 so again in loop we'll get
{4, 7, 8, 3, 2}
3. now a[0] = 4 so again in loop we'll get
{3, 7, 8, 9, 2}
4. a[0] = 3 so again in loop we'll get { , 7, 13, 9, 2}
5. since a[0] is empty move to a[1] and in loop we find it's at the right place so move to next, 8, 9 are also in place so we move to last element and have the final array as
{ , 12, 13, 9, }
Now to find how many are duplicates divide every element by 5 and take the mod => m = (a[i] mod n) -1
this gives you how many times an element is repeated.
Approach and correctness
--------------------------
since we need to do in 0(n) and numbers are in 1..n we need to put one element in correct location in O(n) time and we also need to identify duplicates so increment that element by 'n'.

Java Code 

 public static void main(String[] args) {
int[] inputArr = {0, 4, 3, 4, 1};
findDuplicates(inputArr, 4);
printDuplicatesAndMissingElements(inputArr);
int[] inputArr1 = {0, 2, 3, 4, 3, 2};
findDuplicates(inputArr1, 5);
printDuplicatesAndMissingElements(inputArr1);
}private static void findDuplicates(int[] inputArr, int maxRange) {
// for simplicity reasons we will assume nothing is there in 0 index of array
// and start from 1
int i = 1;
int maxArrLength = inputArr.length;
while(true) {
if ( i > maxArrLength - 1)
break;
int finalPos = inputArr[i];
System.out.println(" Read :: " + inputArr[i]);
if (finalPos > maxRange) {
//this element is already in final position skip and move further looking for elements within maxRange
i++;
continue;
}
int finalPosElement = inputArr[inputArr[i]];
int startPos = i;
int startPosElement = inputArr[i];
// if startPos element isn't in place and it's within the maxRange..
// then candidate for swap or reaching final pos...
if (inputArr[startPos] != i ||
inputArr[startPos] <= maxRange) {
if (finalPosElement > maxRange) {
// if finalposElement > maxRange then no swapping required
// just add maxRange to denote multiple entry
inputArr[finalPos] += maxRange;
//make startPosElement as 0
inputArr[startPos] = 0;
System.out.println("No swapping required incemented " + inputArr[finalPos] );
}
else {
//swap
int temp = startPosElement;
inputArr[startPos] = finalPosElement;
inputArr[finalPos] = temp + maxRange;
System.out.println("Swapped : " + startPosElement + " with " +finalPosElement);
}
}
printArray(inputArr);
// if the element in current evaluated position isn't still correct repeat the above again
if (inputArr[startPos] == i ||
inputArr[startPos] > maxRange) {
System.out.println(" Read :: "+ inputArr[startPos] + " it's already in place");
inputArr[startPos] += maxRange;
i++;
}
else if (inputArr[startPos] == 0){
i++;
continue;
}
else {
continue;
}
}
}
private static void printArray(int[] inputArr) {
for (int i=1; i < inputArr.length; i++) {
System.out.print(inputArr[i] +",");
}
System.out.println("");
}
private static void printDuplicatesAndMissingElements(int[] inputArr) {
int maxRange = inputArr.length;
for (int i=1; i < inputArr.length; i++) {
if (inputArr[i] == 0) {
System.out.println(" Element [" + i + "] is missing");
}
int input = inputArr[i];
int mod = input / maxRange;
if ( mod > 1) {
System.out.println (" Element [" + i + "] is repeated + [" + mod + "] times");
}
}
}

}

Globalization and Localization

Applications must be designed to accommodate users from various cultures. Users in different parts of the world use different languages and different formatting standards for numbers, currency, and dates. International applications should be customizable according to the preferences of users belonging to different nations, cultures, or regions.

An application uses the locale to identify the preference of a user. The local is the combination of a language and a country. For example, the locale of a user speaking English and belonging to the United States is "en-US". The locale includes information about the formats used for representing time and date, symbols and conventions used for representing currency, and the character encoding scheme being used.

The structure of an internationalized application is divided into two blocks:

• Code Block: Contains the application code or the executable part of an application. This block will remain the same for all locales.
• Data Block: Contains all the resources, such as text and images used by the user interface (UI). This block is locale-specific, and each locale will have one data block.

The process of making  an application ready for customers is called internationalization. It includes three phases:

Globalization: 

Involves writing the executable code for an application in such a way that makes it culture-neutral and language-neutral. While incorporating globalization, you must ensure that the culture-specific details are not hard-coded into the executable code. The primary task in this phase is to identify the various locale-sensitive resources and to isolate these resources from the executable code.

Localizability:

An application that has been globalized must be tested to ensure that its executable code is independent of the culture and language-specific data. This is called localizability testing. The focus of localizability testing is to check how the application adapts itself to different locales.

Localization:

Involves the customization of an application for a specific locale. One major task in this phase is the translation of resources identified during the globalization phase. During this phase, various resources, such as images and text, for the designated locale are created.

• When designing an international application, you should ensure the following factors:

User Interface (UI): The language used to design different UI components, such as menu, message box, static-text holder (label), is not fixed during design phase of the application.
Information Formats: The formats of different elements, such as currency, number, and date, are not fixed during design phase of the application.

The different aspects of an application that should be taken into account while incorporating localization are:

• Formats: The formats used for displaying numbers, time, dates and currency should be considered while incorporating localization.

Graphics: The locale-sensitive graphics, such as maps, traffic signs, and calendar should be considered while incorporating localization.

MVC 1 Vs MVC 2

• Following are the important feature of MVC1 architecture:
  • HTML or JSP files are used to code the presentation. JSP files use java beans to retrieve data if required.
  • MVC1 architecture is page-centric design all the business and processing logic means any JSP page can either present in the JSP or may be called directly from the JSP page.
  • Data access is usually done using Custom tag or through java bean call.Therefore we can say that in MVC1 there is tight coupling between page and model.

• Following are the important feature of MVC2 architecture:
  • This architecture removes the page-centric property of MVC1 architecture by separating Presentation Control logic and Application state
  • In MVC2 architecture there is one Controller which receive all request for the application and is responsible for taking appropriate action in response to each request. Second one is Model which is represented by JavaBeans business object and database. Third one is View or is JSP page it takes the information provided by Controller and Module and presents it to user.

Figure 1: JSP Model 1 architecture

Figure 2: JSP Model 2 architecture

Introduction of Cloud Computing

I have gone through couple of documents but I come across below youtube video which explain about Cloud Computing.

This video explain about :
1. Web Hosting
2. Virtualization
3. Cloud Computing

Difference between shallow cloning and deep cloning of objects

The default behaviour of an object’s clone() method automatically yields a shallow copy. So to achieve a deep copy the classes must be edited or adjusted.

Shallow copy: If a shallow copy is performed on obj-1 as shown in fig-2 then it is copied but its contained objects are not. The contained objects Obj-1 and Obj-2 are affected by changes to cloned Obj-2. Java supports shallow cloning of objects by default when a class implements the java.lang.Cloneable interface.

Deep copy: If a deep copy is performed on obj-1 as shown in fig-3 then not only obj-1 has been copied but the objects contained within it have been copied as well. Serialization can be used to achieve deep cloning. Deep cloning through serialization is faster to develop and easier to maintain but carries a performance overhead.

For example, invoking clone() method on a HashMap returns a shallow copy of HashMap instance, which means the keys and values themselves are not cloned. If you want a deep copy then a simple method is to serialize the HashMap to a ByteArrayOutputSream and then deserialize it. This creates a deep copy but does require that all keys and values in the HashMap are Serializable. Its primary advantage is that it will deep copy any arbitrary object graph.

Memory allocation in Java

Each time an object is created in Java it goes into the area of memory known as heap. The primitive variables like  int and double are allocated in the stack, if they are local method variables and in the heap if they are member  variables (i.e. fields of a class). In Java methods local variables are pushed into stack when a method is invoked and stack pointer is decremented when a method call is completed. In a multi-threaded application each thread will have its own stack but will share the same heap. This is why care should be taken in your code to avoid any concurrent access issues in the heap space. The stack is threadsafe (each thread will have its own stack) but the heap is not threadsafe unless guarded with synchronisation through your code.

A method in stack is re-entrant allowing multiple concurrent invocations that do not interfere with each other. A function is recursive if it calls itself. Given enough stack space, recursive method calls are perfectly valid in Java though it is tough to debug. Recursive functions are useful in removing iterations from many sorts of algorithms. All recursive functions are re-entrant but not all re-entrant functions are recursive. Idempotent methods are methods, which are written in such a way that repeated calls to the same method with the same arguments yield same results. For example clustered EJBs, which are written with idempotent methods, can automatically recover from a server failure as long as it can reach another server.

Find nth last element from linked list

Problem : How do we find the nth element from the right of a singly linked list? Would reversing the link list and traversing n elements be the only possible solution?

Solution : Take two pointer's

1. Keep a distance of (n-1) between the two pointers.
2. Increment the first then by 1 and second also by 1
3. When second reaches end of list first is pointing to the desired node.

Difference Between ArrayList and Linklist

The LinkedList and ArrayList represent some of the widely used data structures of the Java Collections Framework. You might have had a chance to already use both classes several times so far; however, if you have wondered on what makes them fundamentally different, then continue reading.

Although both the LinkedList and ArrayList classes implement the List interface, they differ on the following 3-key issues: 1) Data Storage, 2) Data Access, 3) Data Management.

DATA STORAGE: Linked-list versus Array

• LinkedList uses the design of a linked-list data structure (from where it get its name) to store data elements (i.e. objects). In this manner, each data element -- depending on the position of the list -- has a link to the previous and next element. This storage approach proves to be very efficient, as it uses only as much memory as it needs; no more, no less.
• ArrayList uses an Object array for storing the data elements. By default the array starts with a capacity of 10; unless otherwise specified at the time of instantiation. For example, if we want to instantiate an ArrayList of strings with an initial capacity of 1024 then we would use:

ArrayList<String> stringArrayList = new ArrayList<String>(1024);

Thus, by default the ArrayList can be more wasteful as far as the memory allocation goes.

DATA ACCESS: Sequential Access versus Random Access

• LinkedList due to the nature of its data storage, has a sequential access approach. Thus, if we want to retrieve an element at a specific index through the public E get(int index) method, we would have to iterate either from the beginning or the end, depending if the requested index is greater than or less than half the length of the list. It can easily be seen how this sequential access can become quite timely as we deal with longer and longer lists. As the public E get(int index)method uses the Node node(int index) method for data retrieval, we can see the implications of LinkedList's sequential access in the following code:

570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587

/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

• ArrayList supports random access as it has an internal array for data storage. Thus, when we call the public E get(int index) method in an ArrayList instance, we get forwarded to the E elementData(int index) method which simply returns the element located at the specified position within the array, i.e.:

333 334 335 336 337 338

// Positional Access Operations @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }

Needless to say, ArrayList's random access approach is far more efficient, as it doesn't have to waste computing cycles on iteration.

DATA MANAGEMENT: Linking and Unlinking versus Array Copying

• LinkedList can very efficiently undergo any changes in its collection of data elements. For example, if we want to remove a specific data element from the LinkedList instance -- through the public boolean remove(Object o) method -- then we go ahead and link the neighbors (i.e. previous and next data elements) of the unwanted data element, and the Garbage Collector will take care of the rest. Thus, if we have a linked-list structure with three string data elements (with previous and next links), as follow:

["A"] <-> ["B"] <-> ["C"]

Then, when we request removal of the "B" string data element, "A" and "C" get linked together, and "B" is left alone, thus becoming eligible for Garbage Collection:

["A"].next = ["B"].next => ["A"].next = ["C"]
["C"].prev = ["B"].prev => ["C"].prev = ["A"]

The Java implementation behind this pseudo-code looks like the following:

213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240

/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }

Do note that the code displayed above is for the E unlink(Node x) method on which LinkedList's public boolean remove(Object o) method relies. In addition to the efficiency of the remove method, LinkedList is very flexible when it comes to enlarging or shrinking its collection of data elements. In a LinkedList instance whenever we need to add to the collection, a call is made to the void linkLast(E e) method, which simply appends the new data element to the end of the list, as seen below:

144 145 146 147 148 149 150 151 152 153 154 155 156 157

/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<E>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

• ArrayList due to the usage of its internal array it copies all of the elements to a new array every time there's a removal request, or when there's not enough room to add a new element. Thus, for every new addition or removal from our ArrayList collection a call is made to the public void ensureCapacity(int minCapacity) method, which carries out the necessary copying and shifting of the elements, as seen below:

171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188

/** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }

Needless to say, you can imagine how much work these operations carry out, especially when dealing with very large arrays.

In conclusion, we can see that both the LinkedList and ArrayList have their positives and negatives; however, by having a good understanding of these issues you can make a better decision on what implementation should you use, based on the data size and usage requirements.

Synchronous JMS Communication

Here are few easy steps to create synchronous JMS communication.

The solution is like :

- Sender class which sends a message to permanent input queue and create a temporary 

queue and waits for response.

connection = jmsTemplate.getConnectionFactory().createConnectio n();
Session session = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);
MessageProducer producer = session.createProducer(queue);
connection.start();
TemporaryQueue outDest = session.createTemporaryQueue(); // return destination 

// Create message
TextMessage message = session.createTextMessage("Hello World");
message.setJMSReplyTo(outDest);
producer.send(message);

// Get a response
MessageConsumer consumer = session.createConsumer(outDest);
Message msgBack = null;
msgBack = consumer.receive(12000);

and here is code for the receiver class which extends

org.springframework.jms.listener.SessionAwareMessa geListener;..

String messageId = message.getJMSMessageID();
TextMessage textMessage = (TextMessage) message;
System.out.println(" Sending response to OUT QUEUE ");
ApplicationContext ac = new ClassPathXmlApplicationContext("com\\cisco\\iam\\a ac\\config\\JmsServerClientClasses.xml");
SendResponseBackToInputQueue recMessage = (SendResponseBackToInputQueue)ac.getBean("recMessa ge");
recMessage.sendResponseFromTheReceivingQueue(messa ge, session);

In this approach the request queue is permanent and the response queue is temporary.

Now here is the code for the sender class which sends a message to a permanent request queue and waits for response on a another permanent queue.

jmsTemplate.send(queue,msg);//msg is a instance of MessageCreator class
Message message = msg.getMsg();

String messageId = message.getJMSMessageID();
System.out.println("Message id is "+messageId);

System.out.println(" Receiving response at the OUT Queue ");
Message msg1 = jmsTemplate.receiveSelected(responseQueue,"JMSCorr elationID='"+messageId+"'");
if(null == msg1)
System.out.println("Receive Timeout -- ");
if(null != msg1){
TextMessage messageText = (TextMessage)msg1;
System.out.println("JMS Coorelation id is "+msg1.getJMSCorrelationID());
System.out.println("****************************** *************");
}