Binary trees interview questions : part 2

******Check if two binary trees are identical *************

  boolean areIdentical(Node root1, Node root2)
    {
 
        /* base cases */
        if (root1 == null && root2 == null)
            return true;
 
        if (root1 == null || root2 == null)
            return false;
 
        /* Check if the data of both roots is same and data of left and right
           subtrees are also same */
        return (root1.data == root2.data
                && areIdentical(root1.left, root2.left)
                && areIdentical(root1.right, root2.right));
    }
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

******Check if a BST tree is subtree of another tree*******

/* This function returns true if S is a subtree of T, otherwise false */
    boolean isSubtree(Node T, Node S)
    {
        /* base cases */
        if (S == null)
            return true;
 
        if (T == null)
            return false;
 
        /* Check the tree with root as current node */
        if (areIdentical(T, S))
            return true;
 
        /* If the tree with root as current node doesn't match then
           try left and right subtrees one by one */
        return isSubtree(T.left, S)
                || isSubtree(T.right, S);
    }
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

******Check if a given Binary Tree is SumTree********

    /* A utility function to get the sum of values in tree with root
     as root */
    int sum(Node node)
    {
        if (node == null)
            return 0;
        return sum(node.left) + node.data + sum(node.right);
    }
 
    /* returns 1 if sum property holds for the given
       node and both of its children */
    int isSumTree(Node node)
    {
        int ls, rs;
 
        /* If node is NULL or it's a leaf node then
           return true */
        if ((node == null) || (node.left == null && node.right == null))
            return 1;
 
        /* Get sum of nodes in left and right subtrees */
        ls = sum(node.left);
        rs = sum(node.right);
 
        /* if the node and both of its children satisfy the
           property return 1 else 0*/
        if ((node.data == ls + rs) && (isSumTree(node.left) != 0)
                && (isSumTree(node.right)) != 0)
            return 1;
 
        return 0;
    }
 :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ******Level Order Tree Traversal******

   /* Given a binary tree. Print its nodes in level order
     using array for implementing queue  */
    void printLevelOrder()
    {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty())
        {

            /* poll() removes the present head. */
            Node tempNode = queue.poll();
            System.out.print(tempNode.data + " ");

            /*Enqueue left child */
            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }

            /*Enqueue right child */
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }

Binary trees interview questions : part 1

*****Program to count leaf nodes in a binary tree*****

getLeafCount(node)
1) If node is NULL then return 0.
2) Else If left and right child nodes are NULL return 1.
3) Else recursively calculate leaf count of the tree using below formula.
    Leaf count of a tree = Leaf count of left subtree +
                                 Leaf count of right subtree

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

****Convert a Binary Tree into its Mirror Tree*****

1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

check:
For two trees ‘a’ and ‘b’ to be mirror images, the following three conditions must be true:

1. Their root node’s key must be same
2. Left subtree of root of ‘a’ and right subtree root of ‘b’ are mirror.
3. Right subtree of ‘a’ and left subtree of ‘b’ are mirror.

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Find the Maximum Depth or Height of a Tree******

 maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e.,
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e.,
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,
                             max depth of right subtree)
                             + 1
     (d) Return max_depth

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Construct Tree from given Inorder and Preorder traversals*****

Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

 Node buildTree(char in[], char pre[], int inStrt, int inEnd)
    {
        if (inStrt > inEnd)
            return null;

        /* Pick current node from Preorder traversal using preIndex
           and increment preIndex */
        Node tNode = new Node(pre[preIndex++]);

        /* If this node has no children then return */
        if (inStrt == inEnd)
            return tNode;

        /* Else find the index of this node in Inorder traversal */
        int inIndex = search(in, inStrt, inEnd, tNode.data);

        /* Using index in Inorder traversal, construct left and
           right subtress */
        tNode.left = buildTree(in, pre, inStrt, inIndex - 1);
        tNode.right = buildTree(in, pre, inIndex + 1, inEnd);

        return tNode;
    }

    int search(char arr[], int strt, int end, char value)
    {
        int i;
        for (i = strt; i <= end; i++)
        {
            if (arr[i] == value)
                return i;
        }
        return i;
    }

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
****Binary tree, print all root-to-leaf paths****

    void printPaths(Node node)
    {
        int path[] = new int[1000];
        printPathsRecur(node, path, 0);
    }

    /* Recursive helper function -- given a node, and an array
       containing the path from the root node up to but not
       including this node, print out all the root-leaf paths.*/
    void printPathsRecur(Node node, int path[], int pathLen)
    {
        if (node == null)
            return;

        /* append this node to the path array */
        path[pathLen] = node.data;
        pathLen++;

        /* it's a leaf, so print the path that led to here  */
        if (node.left == null && node.right == null)
            printArray(path, pathLen);
        else
        {
            /* otherwise try both subtrees */
            printPathsRecur(node.left, path, pathLen);
            printPathsRecur(node.right, path, pathLen);
        }
    }

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Print nodes at k distance from root******

    void printKDistant(Node node, int k)
    {
        if (node == null)
            return;
        if (k == 0)
        {
            System.out.print(node.data + " ");
            return;
        }
        else
        {
            printKDistant(node.left, k - 1);
            printKDistant(node.right, k - 1);
        }
    }
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*******Ancestors of a given node in Binary Tree*******

 boolean printAncestors(Node node, int target)
    {
         /* base cases */
        if (node == null)
            return false;

        if (node.data == target)
            return true;

        /* If target is present in either left or right subtree
           of this node, then print this node */
        if (printAncestors(node.left, target)
                || printAncestors(node.right, target))
        {
            System.out.print(node.data + " ");
            return true;

        /* Else return false */
        return false;
    }

Java: when to use static methods ?

One rule-of-thumb: ask yourself "does it make sense to call this method, even if no Obj has been constructed yet?" If so, it should definitely be static.

Define static methods in the following scenarios only:

1. If you are writing utility classes and they are not supposed to be changed.
2. If the method is not using any instance variable.
3. If any operation is not dependent on instance creation.
4. If there is some code that can easily be shared by all the instance methods, extract that code into a static method.
5. If you are sure that the definition of the method will never be changed or overridden. As static methods can not be overridden.

ConcurrentHashMap : How does ConcurrentHashMap work internally?

ConcurrentHashMap allow concurrent access to the map. The point is to provide an implementation of HashMap that is threadsafe. Multiple threads can read from and write to it without the chance of receiving out-of-date or corrupted data.
ConcurrentHashMap provides its own synchronization, so you do not have to synchronize accesses to it explicitly.

The logic behind ConcurrentHashMap is that your entire table is not getting locked, but only the portion[segments]. Each segments manages its own HashTable. Locking is applied only for updates. In case of of retrievals, it allows full concurrency.

HashTables too offers synchronized access to map, but your entire map is locked to perform any operation.

Another feature of ConcurrentHashMap is that it provides the putIfAbsent method, which will atomically add a mapping if the specified key does not exist. Consider the following code:
myMap.putIfAbsent("key", 3);

How does ConcurrentHashMap work internally?

• Multiple partitions which can be locked independently. (16 by default)
• Using concurrent Locks operations for thread safety instead of synchronized.
• Has thread safe Iterators. synchronizedCollection's iterators are not thread safe.
• Does not expose the internal locks. synchronizedCollection does.

Let's take four threads are concurrently working on a map whose capacity is 32, the table is partitioned into four segments where each segments manages a hash table of capacity. The collection maintains a list of 16 segments by default, each of which is used to guard (or lock on) a single bucket of the map.

This effectively means that 16 threads can modify the collection at a single time. This level of concurrency can be increased using the optional concurrencyLevel constructor argument.

public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel)
As the other answer stated, the ConcurrentHashMap offers new method putIfAbsent() which is similar to put except the value will not be overridden if the key exists.

private static Map<String,String> aMap =new ConcurrentHashMap<String,String>();

if(!aMap.contains("key"))
   aMap.put("key","value");
The new method is also faster as it avoids double traversing as above. contains method has to locate the segment and iterate the table to find the key and again the method put has to traverse the bucket and put the key.

Java Spring framework: applicationContext.xml and spring-servlet.xml

Spring lets you define multiple contexts in a parent-child hierarchy.

The applicationContext.xml defines the beans for the "root webapp context", i.e. the context associated with the webapp.

The spring-servlet.xml (or whatever else you call it) defines the beans for one servlet's app context. There can be many of these in a webapp, one per Spring servlet (e.g. spring1-servlet.xml for servlet spring1, spring2-servlet.xml for servlet spring2).

Beans in spring-servlet.xml can reference beans in applicationContext.xml, but not vice versa.

All Spring MVC controllers must go in the spring-servlet.xml context.

In most simple cases, the applicationContext.xml context is unnecessary. It is generally used to contain beans that are shared between all servlets in a webapp. If you only have one servlet, then there's not really much point, unless you have a specific use for it.

Servlet/JSP java : SendRedirect vs forward

sendRedirect()

method is declared in HttpServletResponse Interface as void sendRedirect(String url) 
Redirect sends a header back to the client browser on transfer of control to a different server or domain. Header contains the resource url , the browser needs for redirection. Using this url information, the browser now initiates a new connection and in this process, the old connection and response object are lost.

Forward

method is declared in RequestDispatcher Interface as forward(ServletRequest request, ServletResponse response) 
Transfer of control is done internally, hence browser/ client in not involved. Request is forwarded to resources available within the same server where the request is made. On forward, the original request and response objects are transferred to the resource along with any parameters available.

Also, in forward the browser does not display the forwarded address in the address bar as it is done internally in the same server while in redirect, the redirected address is visible in the address bar.

Hence, redirect can be used when resource is in different domain/ server, otherwise forward is faster than redirect.

java : serializable interface #interview

1. When should i implement serializable interface?

It lets you take an object or group of objects, put them on a disk or send them through a wire or wireless transport mechanism, then later, perhaps on another computer, reverse the process: resurrect the original object(s). The basic mechanisms are to flatten object(s) into a one-dimensional stream of bits, and to turn that stream of bits back into the original object(s).

Like the Transporter on Star Trek, it's all about taking something complicated and turning it into a flat sequence of 1s and 0s, then taking that sequence of 1s and 0s (possibly at another place, possibly at another time) and reconstructing the original complicated "something."

So, implement the Serializable interface when you need to store a copy of the object, send them it to another process on the same system or over the network.

2. Why do we do that?

Because you want to store or send an object.

3. Does it give any advantages or security?

It makes storing and sending objects easy. It has nothing to do with security.

Java : volatile keyword #interview #singelton

The volatile keyword is a type qualifier used to declare that an object can be modified in the program by something such as the operating system, the hardware, or a concurrently executing thread.

This means every time the variable is requested inside the program, each time the value is read from the source memory location(hard-drive,devices.etc). normal variables are stored in virtual memory of the processor. They are synced with source memory location only twice. Once during first read and second termination write.
This is useful when the variable is used as a control condition in multthreaded or RT applications.

java : Why doesn't Map extend Collection? #interview

Why doesn't Map extend Collection?
This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa).

If a Map is a Collection, what are the elements? The only reasonable answer is "Key-value pairs", but this provides a very limited (and not particularly useful) Map abstraction. You can't ask what value a given key maps to, nor can you delete the entry for a given key without knowing what value it maps to.

Collection could be made to extend Map, but this raises the question: what are the keys? There's no really satisfactory answer, and forcing one leads to an unnatural interface.

Maps can be viewed as Collections (of keys, values, or pairs), and this fact is reflected in the three "Collection view operations" on Maps (keySet, entrySet, and values). While it is, in principle, possible to view a List as a Map mapping indices to elements, this has the nasty property that deleting an element from the List changes the Key associated with every element before the deleted element. That's why we don't have a map view operation on Lists.

Java : Overloading vs Overriding

HashMap, TreeMap and LinkedHashMap

╔══════════════╦═════════════════════╦═══════════════════╦══════════════════════╗
║   Property   ║       HashMap       ║      TreeMap      ║     LinkedHashMap    ║
╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                      ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order   ║
║              ║      over time      ║    ordering       ║                      ║
╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
║  Get/put     ║                     ║                   ║                      ║
║   remove     ║         O(1)        ║      O(log(n))    ║         O(1)         ║
║ containsKey  ║                     ║                   ║                      ║
╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
║              ║                     ║   NavigableMap    ║                      ║
║  Interfaces  ║         Map         ║       Map         ║         Map          ║
║              ║                     ║    SortedMap      ║                      ║
╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
║              ║                     ║                   ║                      ║
║     Null     ║       allowed       ║    only values    ║       allowed        ║
║ values/keys  ║                     ║                   ║                      ║
╠══════════════╬═════════════════════╩═══════════════════╩══════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed       ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of      ║
║   behavior   ║           unsynchronized concurrent modification               ║
╠══════════════╬═════════════════════╦═══════════════════╦══════════════════════╣
║              ║                     ║                   ║                      ║
║Implementation║      buckets        ║   Red-Black Tree  ║    double-linked     ║
║              ║                     ║                   ║       buckets        ║
╠══════════════╬═════════════════════╩═══════════════════╩══════════════════════╣
║      Is      ║                                                                ║
║ synchronized ║              implementation is not synchronized                ║
╚══════════════╩════════════════════════════════════════════════════════════════╝