implement a function to sort list

The most efficient sorting algorithm in general, quicksort, is applicable to arrays because elements in arrays can be accessed in O(1) time based on indexes. It takes more time to locate a node in a list, so we have to utilize other algorithms to sort lists.

Let’s take a list with four nodes as an example to analyze the process of the insert sort algorithm (Figure 3-6(a)). A list is split into two parts. The first part contains nodes already sorted, and the second part is not sorted yet. The node pointed by P1 is the last sorted node, which is initialized to the first node, and the node pointed to by P2 is the next one to be sorted.
When node 1 is the next node to be sorted, there is only one node (node 2) in the sorted list. Because the value 1 is less than the value in the list head, node 1 becomes the new head of the sorted list, and node 2 is linked to the next node of the previous node 1, which is node 4 (Figure(b)). Node 2 is still the last node in the sorted list, so it does not move P1, and only moves P2 to the next node of node 2.
The next node to be sorted is node 4. It traverses from the head node in order to find an appropriate location in the sorted list. Since the value 4 is greater than the value 2 in the last node of the sorted list, it is not necessary to relink nodes. Node 4 becomes the new last node of the sorted list, so it is pointed to by P1 (Figure(c)).
Now the next node to be sorted is node 3. It traverses from the head node again in order to find an appropriate location in the sorted list. Node 3 is linked between node 2 and node 4. Node 4 is still the last node in the sorted list. Since there are no nodes left after node 4, the whole list is sorted (Figure(d)). 

 

The process to sort a list with four nodes. P1 points to the last node in the sorted list, and P2
points to the next node to be inserted into the sorted list, which always follows P1. (a) P1 is initialized to the first node, and P2 is initialized to the second one. (b) The node with value 2 is inserted into the sorted list. (c) The node with value 4 is inserted into the sorted list. (d) The node with value 3 is inserted into the sorted list.
The insert sort algorithm for lists can be implemented in C++, as shown in bellow

C++ Code to Sort a List

void Sort(ListNode** pHead) {
    if(pHead == NULL || *pHead == NULL)

return; 

    ListNode* pLastSorted = *pHead;
    ListNode* pToBeSorted = pLastSorted->m_pNext;
    while(pToBeSorted != NULL) {

        if(pToBeSorted->m_nValue < (*pHead)->m_nValue) {
            pLastSorted->m_pNext = pToBeSorted->m_pNext;
            pToBeSorted->m_pNext = *pHead;
            *pHead = pToBeSorted;

}
else {

            ListNode* pNode = *pHead;
            while(pNode != pLastSorted

                && pNode->m_pNext->m_nValue < pToBeSorted->m_nValue) {

                pNode = pNode->m_pNext;
            }

            if(pNode != pLastSorted) {
                pLastSorted->m_pNext = pToBeSorted->m_pNext;
                pToBeSorted->m_pNext = pNode->m_pNext;
                pNode->m_pNext = pToBeSorted;

} else

                pLastSorted = pLastSorted->m_pNext;

}

        pToBeSorted = pLastSorted->m_pNext;
    }

}
Because it has to scan O(n) nodes on the sorted list in order to find an appropriate location to insert a new node, it costs O(n2) time to sort a list with n nodes.
Test Cases:

• Sort a list with multiple nodes, with/without duplicated values
  
• The input list has only one node
  
• The input head node of a list is NULL
  

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

implement a function to print a list from its tail to head-interview question

 implement a function to print a list from its tail to head-interview question.

When meeting this question, many candidates' intuition is to reverse links between all nodes and to reverse the direction of a list. It fulfills the requirement if all nodes in the reversed list are printed from head to tail. However, it has to modify the structure of the input list. Is it OK to do so? It depends on the requirement in an interviewers’ minds. You should ask your interviewers to clarify their requirement before you describe your solution.

Usually, printing is a read-only operation, and it is not allowed to modify the content to be printed. Supposing interviewers disallow to reverse the direction of lists here.Nodes in a list are linked from the head to the tail, but the printing order is from the tail to the head. That is to say, the first node in the list is the last one to be printed, and the last node is the first one to be printed. It is typical “Last In, First Out,” so a stack can help to solve this problem. Every node is pushed into a stack when it is visited. After all nodes are visited and pushed into the stack, they are printed from the top of the stack and popped one by one. The printing order is opposite to the order in the list.

The sample code in bellow is based on stack in the C++ standard template library. 
C++ Code to Print a List Reversely (Iterative Version)

void PrintListReversingly_Iteratively(ListNode* pHead) {
    std::stack<ListNode*> nodes;
    ListNode* pNode = pHead;
    while(pNode != NULL) {

        nodes.push(pNode);

        pNode = pNode->m_pNext;
    }

    while(!nodes.empty()) {
        pNode = nodes.top();
        printf("%d\t", pNode->m_nValue);
        nodes.pop();

} }
It can be solved with a stack and since recursion is essentially equivalent to stacks, so it can also be solved recursively. To print a list in reverse, the next nodes are printed first when a node is visited, and then the currently visited node is printed. The recursive code is shown in bellow
 C++ Code to Print a List Reversely (Recursive Version)

void PrintListReversingly_Recursively(ListNode* pHead) {
    if(pHead != NULL) {

        if (pHead->m_pNext != NULL) {
            PrintListReversingly_Recursively(pHead->m_pNext);

}

        printf("%d\t", pHead->m_nValue);
    }

}
The previous recursive code looks more concise, but it has a limitation: the recursive calls may have too many levels to cause call stack overflow errors when the list is very long. The iterative solution with an explicit stack is more robust. More discussion about recursion and iteration are available in the section Recursion and Iteration.
Test Cases:

• Lists with multiple nodes or only one node
  
• The head node of a list is NULL
  www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

Linked Lists in Programming

Arrays are quite useful in all programming languages. However, they also have some limitations. They require creating a new array with bigger size and copying the existing elements from the old array to the new one when the capacity of an array is overrun. Additionally, they have to shift some elements in an array when a new element is inserted because memory of an array is sequentially allocated. Such limitations can be overcome by dynamic structures, such as linked lists.It is not necessary to know the size of a list when it is created, so it is treated as a dynamic data structure. Rather than allocate memory for all elements when a list is initialized, memory is allocated for each node on demand when it is inserted. The space efficiency of lists is better than arrays because there is no vacant memory in lists.Memory allocation of a list is not continuous because nodes are inserted dynamically and their memory is not allocated at the same time. It costs O(n) time to get the ith node in a list since it has to traverse nodes one by one starting from the head node. It only takes O(1) time to get the ith element in an array. Therefore, time efficiency to search lists is not as good as for arrays.

Linked lists are the most frequently met data structures during interviews. It only takes about 20 lines of code to create a list, insert a node into a list, or delete a node from a list. Compared to other complex data structures, such as hash tables and graphs, lists are more suitable for interviews due to their moderate code size. Additionally, lots of pointer operations are required to handle a list. Candidates without qualified programming abilities cannot implement complete and robust code related to lists. Moreover, lists are also flexible and challenging interview questions can be constructed with them. Therefore, many interviewers like questions related to lists.

Most lists met during interviews are single-linked lists, where each node has a link to its successor. For example, “Print a List from Tail to Head”, “Delete a Node from a List in O(1) Time”, “kth Node from the End”, “Reverse Lists”, and “First Intersection Node of Two Lists" are all about single-linked lists.
Not only are single-linked lists popular for interviews, but other types of lists are also frequently met:

• Usually the tail node in a single-linked list does not have a successor. If every node in a finite list has a successor, a loop is formed. The section Loop in List discusses lists with loops.
  
• If there is also a link to a predecessor besides a link to a successor in each node of a list, it is a double-linked list. The interview question “Binary Search Trees and Double-Linked Lists” is in this category.
  
• A complex list is composed if each node has a link to any other node (including the node itself). Please refer to the interview question “Clone Complex Lists” for more details on the complex list.
  

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

String in C/C++, C#, and Java.

String 
A string, which is composed of a sequence of characters, is quite an important data structure. Many programming languages have special rules for strings for the optimization purpose, some of which are highlighted in C/C++, C#, and Java
 Strings in C/C++ 
All literal strings in C/C++ end with a special character ‘\0’, so it is easy to find the end of a string. However, there is an extra cost for the special character, and it is easy to make mistakes. 

C/C++ Code for End of a String

char str[10];
strcpy(str, "0123456789");

A character array with length 10 is declared first, and the content of a string “0123456789” is copied into it. It seems that the string “0123456789” only has 10 characters, but its actual length is 11 because there is an extra character ‘\0’ at its end. The length should be at least 11 for a character array to accommodate the string.
Strings in C#
Strings are encapsulated in a class System.String in C#, whose contents are immutable. When we try to modify the content of a string, a new instance will be created. There are many interview questions about immutable strings. For example,

C# Code for Immutable Strings

String str = "hello";
str.ToUpper();
str.Insert(0, " WORLD");

Although there are two operations, ToUpper and Insert, on str, it keeps the original content “hello” unchanged. When we try to modify the content of a string, the modified result is in return value.
If there are multiple editing operations on a string, multiple temporary instances will be created, and it has a negative impact on both time and space efficiencies. A new class related to string, StringBuilder, is defined to accommodate the modified result. Usually, StringBuilder is a better choice if we continue modifying strings many times.
Similar to editing strings, a new instance will be created when we try to assign a literal string to another string. An example is shown inbelow

C# Code to Assign Strings

void ValueOrReference(Type type) {
    String result = "The type " + type.Name;

    if (type.IsValueType)
        Console.WriteLine(result + " is a value type.");

    else
        Console.WriteLine(result + " is a reference type.");

}

void ModifyString(String text) {
    text = "world";

}

void Main(string[] args) {
    String text = "hello";

 ValueOrReference(text.GetType());
    ModifyString(text);
   Console.WriteLine(text);
}

This example checks whether the class String is a value type and reference type first. Since it is defined as public sealed class String {...}, it is a reference type.
It assigns a new string “world” to text in the method ModifyString. A new string instance with content “world” is created here, and it is referenced by text. The variable text references the original string outside the method ModifyString because text is not marked as ref or out in the argument list. Therefore, the output for text is still “hello”. If the expected output is “world”, we have to mark the parameter text with ref or out.
Strings in Java
A section of memory is allocated for literal strings in Java. When a string is created once, it can be referenced by other instances. This optimization mechanism avoids recreation, but it makes identity and equality tests more complicated and confusing.

 Java Code for Equality and Identity of Strings
void testEquality() {
    String str1 = "Hello world.";
    String str2 = "Hello world.";

    if (str1 == str2)
        System.out.print("str1 == str2\n");

    else
        System.out.print("str1 != str2\n");

    if(str1.equals(str2))
        System.out.print("str1 equals to str2\n");

    else
        System.out.print("str1 doesn't equal to str2\n");

    String str3 = new String("Hello world.");
    String str4 = new String("Hello world.");

    if (str3 == str4)
        System.out.print("str3 == str4\n");

    else
        System.out.print("str3 != str4\n");

    if(str3.equals(str4))
        System.out.print("str3 equals to str4\n");

    else
        System.out.print("str3 doesn't equal to str4\n");

} 

When the first line of code String str1 = “Hello world.” executes, a string “Hello world.” is created, and the variable str1 references to it. Another string “Hello world.” will not be created again when the next line of code executes because of optimization. The variable str2 also references the existing “Hello world.”.
The operator == checks the identity of the two objects (whether two variables reference the same object). Since str1 and str2 reference the same string in memory, they are identical to each other. The method equals checks equality of two objects (whether two objects have the same content). Of course, the contents of str1 and str2 are the same.
When code String str3 = new String(“Hello world.”) executes, a new instance of String with content “Hello world.” is created and it is referenced by the variable str3. Then another instance of String with content “Hello world.” is created again, and referenced by str4. Since str3 and str4 reference two different instances, they are not identical, but their contents are the same.
Therefore, the output contains four lines:

str1 == str2
str1 equals to str2
str3 != str4
str3 equals to str4

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

How do you find the duplicated number in Array

Q.An array contains n numbers ranging from 0 to n-2. There is exactly one number duplicated in the array. How do you find the duplicated number? For example, if an array with length 5 contains numbers {0, 2, 1, 3, 2}, the duplicated number is 2. 

A.Suppose that the duplicated number in the array is m. The sum of all numbers in the array, denoted as sum1, should be the result of 0+1+...+(n-2)+m. It is not difficult to get the sum result of 0+1+...+(n-2), which is denoted as sum2. The duplicated number m is the difference between sum1 and sum2. The corresponding code in Java is shown in Listing 3-2.
Listing 3-2. Java Code to Get a Duplicated Number in an Array

int duplicate(int numbers[]) {
    int length = numbers.length;

    int sum1 = 0;
    for(int i = 0; i < length; ++i) {

        if(numbers[i] < 0 || numbers[i] > length - 2)
            throw new IllegalArgumentException("Invalid numbers.");

        sum1 += numbers[i];

}
    int sum2 = ((length - 1) * (length - 2)) >> 1;

    return sum1 - sum2;
}

Test Cases:

• Normal case: an array with size n has a duplication
  
• Boundary case: an array {0, 0} with size 2
  
• Some numbers are out of the range of 0 to n-2 in an array of size n 
  
  
  Q. An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How do you find a duplicated number in the array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5, 3}, the implemented function (or method) should return either 2 or 3. A.
  A naive solution for this problem is to sort the input array because it is easy to find duplication in a sorted array. As we know, it costs O(nlogn) time to sort an array with n elements. Another solution is the utilization of a hash set. All numbers in the input array are scanned sequentially. When a number is scanned, we check whether it is already in the hash set. If it is, it is a duplicated number. Otherwise, it is inserted into the set. The data structure HashSet in Java is quite helpful in solving this problem. Even though this solution is simple and intuitive, it has costs: O(n) auxiliary memory to accommodate a hash set. Let’s explore a better solution that only needs O(1) memory. Indexes in an array with length n are in the range 0 to n-1. If there were no duplication in the n numbers ranging from 0 to n-1, we could rearrange them in sorted order, locating the number i as the ith number. Since there are duplicate numbers in the array, some locations are occupied by multiple numbers, but some locations are vacant. Now let’s rearrange the input array. All numbers are scanned one by one. When the ith number is visited, first it checks whether the value (denoted as m) is equal to i. If it is, we continue to scan the next number. Otherwise, we compare it with the mth number. If the ith number equals the mth number, duplication has been found. If not, we locate the number m in its correct place, swapping it with the mth number. We continue to scan, compare, and swap until a duplicated number is found. Take the array {2, 3, 1, 0, 2, 5, 3} as an example. The first number 2 does not equal its index 0, so it is swapped with the number with index 2. The array becomes {1, 3, 2, 0, 2, 5, 3}. The first number after swapping is 1, which does not equal its index 0, so two elements in the array are swapped again and the array becomes {3, 1, 2, 0, 2, 5, 3}. It continues to swap since the first number is still not 0. The array is {0, 1, 2, 3, 2, 5, 3} after swapping the first number and the number with index 3. Finally, the first number becomes 0.

Let’s move on to scan the next numbers. Because the following three numbers, 1, 2 and 3, are all
equal to their indexes, no swaps are necessary for them. The following number, 2, is not the same as its
index, so we check whether it is the same as the number with index 2. Duplication is found since the
number with index 2 is also 2.

 With an understanding of the detailed step-by-step analysis, it is time to implement code. Sample
code in Java is shown in Listing 3-3.

Listing 3-3. Java Code to Get a Duplicated Number in an Array

int duplicate(int numbers[]) {
    int length = numbers.length;
    for(int i = 0; i < length; ++i) {

        if(numbers[i] < 0 || numbers[i] > length - 1)
            throw new IllegalArgumentException("Invalid numbers.");

}

    for(int i = 0; i < length; ++i) {
        while(numbers[i] != i) {

            if(numbers[i] == numbers[numbers[i]]) {
                return numbers[i];

}

            // swap numbers[i] and numbers[numbers[i]]
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;

} }

    throw new IllegalArgumentException("No duplications.");
}

Test Cases:

• Normal cases: an array with size n has one or more duplicated numbers
  
• Boundary cases: the array {0, 0} with size 2
  
• Some numbers are out of the range from 0 to n-1 in an array of size n
  
• No duplication in the array
  

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

Data Structures interview point of you

 Data Structures

The primary purpose of most computer programs is to store, retrieve, and process information. Consequently, data structures and algorithms that manipulate information of computer science. For this reason, many interviewers often focus a number of their questions on these aspects. we will cover typical interview questions about the most common data structures, including arrays, strings, lists, trees, stacks, and queues.

Arrays

Arrays might be the most simple data structure. Elements are sequentially stored in continuous memory in arrays. When an array is created, its size should be specified. Even though it may only store one element at first, the size is required because we have to allocate memory for all of the elements. Since there may be vacancies in arrays, they are not efficient in memory utilization.
In order to improve space efficiency, dynamic arrays were developed. The class vector in the standard template library (STL) of C++ is one such example. Memory is allocated for a few elements in dynamic arrays at first. When the number of elements is greater than the capacity of a dynamic array, more memory is allocated (the capacity doubles when it has to enlarge the capacity of a vector in C++), existing elements are copied to the newly allocated space, and the previous memory is released. It reduces waste in memory, but many extra operations are required to enlarge capacity, so it has negative impact on time efficiency. Therefore, it is better to reduce the times needed to enlarge the capacity of dynamic arrays. The type ArrayList in both C# and Java is similar to vector in C++.
Because memory allocation for arrays is sequential, it only costs O(1) time to access to an element based on its index, and it is very efficient. A simple hash table can be implemented with an array to utilize its advantage of time efficiency. Each index is treated as a key and every element in an array is treated as a value, so an index and its corresponding element form a pair of key and value. Many problems can be solved with such a hash table, and examples are illustrated in the section Hash Tables for Characters. It is a practical solution especially when built-in hash tables are not available in some programming languages such as C/C++.
Arrays and pointers are closely related to each other in C/C++ and also different from each other. The C code in Listing 3-1 shows the relationship between them. What is the output of this code?
Listing 3-1. C Code about Arrays and Pointers

int GetSize(int data[]) {
    return sizeof(data);

}
int _tmain(int argc, _TCHAR* argv[]) {

int data1[] = {1, 2, 3, 4, 5};
    int size1 = sizeof(data1);
 int* data2 = data1;
    int size2 = sizeof(data2);

    int size3 = GetSize(data1);

    printf("%d, %d, %d", size1, size2, size3);
}

The output should be “20, 4, 4” in a 32-bit system. data1 is an array, and sizeof(data1) gets its size. There are five integers in the array, and each integer occupies four bytes, so the total size of array is 20 bytes.
The name of an array is the address of the first element in the array, so data2 points to the first element of an array with the statement data2 = data1. data2 is declared as a pointer, and the sizeof operator returns 4 for any pointers in a 32-bit system.
When an array is passed as a parameter in C/C++, the compiler treats it as a pointer. What gets passed is the address of the first element in an array, rather than the whole array. Therefore, the result of sizeof(data) is also 4 in the function GetSize even though data is declared as an array in the parameter list.

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

schedule threads in java programming

 schedule threads in java programming
Java defines methods wait, notify, and notifyAll in the base class Object. The method wait is used when a thread is waiting for some condition that is typically controlled by another thread. It allows us to put a thread to sleep while waiting for the condition to change, and the thread will be wakened up when a notify or notifyAll occurs. Therefore, wait provides a method to synchronize activities between threads, and it is applicable to solve this problem.
A solution based on methods wait and notify is found in Listing 2-19. Listing 2-19. Java code to schedule threads

public class SimpleThread extends Thread {
    private int value;
    public SimpleThread(int num) {

        this.value = num;

start();
}
    public void run() {
        while(true) {

            synchronized(this) {
                try {

                    wait();
                } catch (InterruptedException e) {

                    throw new RuntimeException(e);
                }

                System.out.print(value + " ");
            }

} }
}

public class Scheduler {
    static final int COUNT = 3;
    static final int SLEEP = 37;

    public static void main(String args[]) {
        SimpleThread threads[] = new SimpleThread[COUNT];
        for(int i = 0; i < COUNT; ++i)

            threads[i] = new SimpleThread(i + 1);

        int index = 0;
        while(true){

            synchronized(threads[index]) {
                threads[index].notify();

}

            try {
                Thread.sleep(SLEEP);

            } catch (InterruptedException e) {
                throw new RuntimeException(e);

}

            index = (++index) % COUNT;
        }

} }

 There are four threads in the code above. The first is the main thread in the Java application, which
acts as the scheduler, and it creates three printing threads and stores them into an array. The main thread
awakens threads one by one according to their index in the array via the method notify. Once a thread
wakes up, it prints a number and then sleeps again to wait for another notification.
Source Code:
   004_Scheduler.java

www.cinterviews.com appreciates your contribution please mail us the questions 

you have to cinterviews.blogspot.com@gmail.com so that it will be useful 

to our job search community    
   
  

Data Containers in Java programming language

 Data Containers in Java programming language

The Java programming language provides many useful data containers. Data containers can be divided into two categories: one is collection, such as LinkedList and Stack; and the other is map, such as the type HashMap. Both are commonly used in practical development and also frequently met in interviews. For example, the following is an interview question about HashMap: What is the output of the piece of code in Listing 2-19?
Listing 2-19. Java Code with HashMap

public class MyString {
    public MyString(String data) {

        this.data = data;
    }

    private String data;
}

public static void main(String args[]) {
    Map<String, Integer> map1 = new HashMap<String, Integer>();
    String str1 = new String("Hello World.");
    String str2 = new String("Hello World.");
    map1.put(str1, new Integer(10));
    map1.put(str2, new Integer(20));

    Map<MyString, Integer> map2 = new HashMap<MyString, Integer>();
    MyString str3 = new MyString(str1);
    MyString str4 = new MyString(str2);
    map2.put(str3, new Integer(10));

    map2.put(str4, new Integer(20));

    System.out.println(map1.get(str1));

    System.out.println(map2.get(str3));
}

Java checks the existence of a key in a HashMap via its hash code, which is returned by the method hashCode. The method hashCode is defined in the class Object, and it can be overridden by subclasses. When two keys have the same hash code, it calls the method equals to check their equality. Similar to hashCode, equals is also defined in the class Object and can be overridden by subclasses.

The type of key in the map1 is String, which overrides the method hashCode and equals. The method String.hashCode returns the same hash code when two instances have the same string content. Because the contents in str1 and str2 are the same, they share the same hash code. When it tries to put the record with key str2 to map1, a key str1 exists already with the same hash code. The method equals also shows that these two keys are equal to each other because their contents are the same. Therefore, it just updates the corresponding value of the key str1 to 20, instead of inserting a new record.
The type of key in map2 is MyString, which does not override the methods hashCode and equals. It has to call the method Object.hashCode to compare hash codes of keys, which returns the object addresses. The keys str3 and str4 have different hash codes because they are two different objects and have different addresses. A new record with key str4 is inserted into the map2, and the value responding to the key str3 remains 10.
Therefore, the output of the code above contains two lines: The first line is a number 20, and the second one is a number 10.Java has good support for threads and synchronization.

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

Java programming language

Java programming language 

The Java programming language is a common choice for developing cross-platform applications and systems. Additionally, it has attracted more attention because of the popularity of Android mobile phones in recent years. Therefore, many companies have requirements on their candidates' Java proficiency level.
Java Keywords
Similar to C++ and C#, there are many interview questions on Java keywords or concepts. One of the most frequently met questions is: What are the uses of finalize, finally, and final in Java? The finalize method is related to the garbage collector in Java. Java is a managed programming language, and its runtime periodically reclaims memory occupied by objects that are not referenced by others. If an object is holding some resources besides memory, such as files and network connections, we might want to make sure these resources are released before the object is destroyed. Java provides a mechanism called finalization to handle such situations. We define specific actions in the method of finalize that will occur when an object is about to be reclaimed by the garbage collector.

The keyword finally is related to the exception handling mechanism. The finally block always executes when the corresponding try block exists. This ensures that the finally block is executed even if an unexpected exception occurs. Usually, the finally block contains code to clean up resources.
The keyword final in the Java programming language is used in several different contexts to define an entity that cannot be modified later:

• No classes can derive from final classes.
  
• A final method cannot be overridden by subclasses.
  
• A final variable can only be initialized once, either via an assignment statement at the point of declaration or a constructor. Some final variables, named blank final variables, are not initialized at the point of declaration. A blank final variable of a class must be definitely assigned in every constructor of the class in which it is declared. Additionally, final arguments, which are declared in argument lists of methods, are similar to final variables.
  The use for final variables gets more complex when they are references. If a final variable is a reference, it cannot be rebound to reference another object. However, the object it references is still mutable.
  
  The piece of code in Listing 2-18 uses final variables. Which methods will cause compile-time errors? Listing 2-18. Java Code to Modify Final Fields
  

  public class WithFinal {
      public final int number = 0;
      public final int[] array;
  

      public WithFinal() {
          array = new int[10];
          for(int i = 0; i < array.length; ++i)
  

  array[i] = i;
  }
  

      public void ModifyFinal1() {
          ++number;
  

  }
  

      public void ModifyFinal2() { 

   for(int i = 0; i < array.length; ++i)

  array[i] += i;

    }   
  public void ModifyFinal3() {
      array = new int[10];

  for(int i = 0; i < array.length; ++i)
              array[i] = i;}
  }
  

  In the class WithFinal, there are two data fields. The field number is a primitive while the field array is a reference and it is also a blank final variable.
  Blank final variables can be initialized in constructors, so the constructor method in the class WithFinal has no problems. It tries to modify the constant primitive number inside the method ModifyFinal1, which is not allowed by the Java compiler. The method ModifyFinal2 modifies the object referenced by array, but it does not modify the reference itself. It is allowed to do so. Inside the method ModifyFinal3, a new array is created and it is rebound to the constant reference array, so it raises compiling errors.
  
  www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

singleton pattern in C# programming language

 singleton patten

A class follows the singleton pattern if it can have one instance at most. Design patterns are very important in object-oriented design and development, so many interviewers like questions related to patterns. Singleton is the only pattern that can be implemented in dozens of lines of code, so it is quite suitable for interviews.

 Single-Threading Applications 

When the constructor is defined as a private method, none of the code outside the class can create its instances. A static method inside the class is defined to create an instance on demand. The class Singleton1 is implemented based on the solution in Listing 2-13.
Listing 2-13. C# Code for Singleton (Version 1)

public class Singleton1 {
    private Singleton1() {
    }

 private static Singleton1 instance = null; public static Singleton1 Instance {

        get {
            if (instance == null)

                instance = new Singleton1();
            return instance;

} }
}
In this class, an instance is created only when static field Singleton1.instance is null, so it does not
have the opportunity to get multiple instances.
Works with Multiple Threads but Is Inefficient
Singleton1 works when there is only one thread, but it has problems when there are multiple threads in an application. Supposing that there are two threads concurrently reaching the if statement to check whether instance is null. If instance is not created yet, each thread will create one separately. It violates the definition of the singleton pattern when two instances are created. In order to make it work in multithreading applications, a lock is introduced as shown in the Singleton2 in Listing 2-14.
Listing 2-14. C# Code for Singleton (Version 2)

public class Singleton2 {
    private Singleton2() {
    }

    private static readonly object syncObj = new object();

    private static Singleton2 instance = null;
    public static Singleton2 Instance {

        get {
            lock (syncObj) {

                if (instance == null)
                    instance = new Singleton2();

}

            return instance;
        }

} }
Suppose there are two threads that are both going to create their own instances. As we know, only one thread can get the lock at a time. When one thread gets it, the other one has to wait. The first thread that gets the lock finds that instance is null, so it creates an instance. After the first thread releases the lock, the second thread gets it. Since the instance was already created by the first thread, the if statement is false. 

An instance will not be recreated again. Therefore, it guarantees that there is one instance at most when there are multiple threads executing concurrently.
The class Singleton2 is far from perfect. Every time Singleton2.Instance.get executes, it has to get and release a lock. Operations to get and release a lock are time-consuming, so they should be avoided as much as possible.
Double-Check around Locking
Actually a lock is needed only before the only instance is created in order to make sure that only one thread get the chance to create an instance. After the instance is created, no lock is necessary. We can improve performance with an additional if check before the lock as shown in Listing 2-15.
Listing 2-15. C# Code for Singleton (Version 3)

public class Singleton3 {
    private Singleton3() {
    }

    private static object syncObj = new object();

    private static Singleton3 instance = null;
    public static Singleton3 Instance {

        get {
            if (instance == null) {

                lock (syncObj) {
                    if (instance == null)

                        instance = new Singleton3();

} }

            return instance;
        }

} }
In the class Singleton3, it locks only when instance is null. When the instance has been created, it is returned directly without any locking operations. Therefore, the time efficiency of Singleton3 is better than Singleton2.
Singleton3 employs two if statements to improve time efficiency. It is a workable solution, but its logic looks a bit complex, and it is error-prone for many candidates during interviews.

Utilization of Static Constructors
It is guaranteed that a static constructor in a C# class is called only once at most. If it only creates an instance in the static constructor, there is one instance at most. A concise solution for the singleton pattern with a static constructor is shown in Listing 2-16.
Listing 2-16. C# Code for Singleton (Version 4)

public class Singleton4 {
    private Singleton4() {
    }

    private static Singleton4 instance = new Singleton4();
    public static Singleton4 Instance {

        get {
            return instance;

} }
}
In the class Singleton4 above, an instance is created when the static field instance gets initialized. Static fields in C# are initialized when the static constructor is called. Since the static constructor is called only once by the .NET runtime, it is guaranteed that only one instance is created even in a multithreading application.
The time to execute the static constructor is out of the programmers' control. When the .NET runtime reaches any code of a class the first time, it invokes the static constructor automatically. Therefore, the time to initialize instance is not the first time to invoke Singleton4.Instance. If a static method is added into Singleton4, it is not necessary to create an instance to invoke such a static method. However, the .NET runtime invokes the static constructors automatically to create an instance when it reaches any code for Singleton4. Therefore, it is possible to create an instance too early, and it impairs the space efficiency.
Creating an Instance When Necessary
In the last implementation of the singleton pattern in Listing 2-17, Singleton5, it creates the only instance on demand.
Listing 2-17. C# Code for Singleton (Version 5)

public class Singleton5 {
    Singleton5() {

}

    public static Singleton5 Instance {
        get {

            return Nested.instance;
}

class Nested {
        static Nested() {
        }

        internal static readonly Singleton5 instance = new Singleton5();
    }

}
There is a nested private class Nested in the code for Singleton5. When the .NET runtime reaches the code of the class Nested, its static constructor is invoked automatically, which creates an instance of type Singleton5. The class Nested is used only in the property Singleton5.Instance. Since the nested class is defined as private, it is inaccessible outside of the class Singleton5.
When the get method of Singleton5.Instance is invoked the first time, it triggers execution of the static constructor of the class Nested to create an instance of Singleton5. The instance is created only when it is necessary, so it avoids the waste associated with creating the instance too early.
Solution Comparison
Five solutions are introduced in this section. The first solution is workable only in a single-threading application. The second one works in a multiple-threading application, but it is inefficient because of unnecessary locking operations. The first two solutions are not acceptable from an interviewer's perspective. In the third solution, it employs two if statements and one lock to make sure it works in a multiple-threading application efficiently. The fourth one utilizes the static constructor to guarantee only an instance is created. The last solution improves space efficiency with a nested class to create the instance only when it is necessary. The last two solutions are recommended for interviews.
Source Code:

    003_Singleton.cs

 www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community