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.