Tuesday, October 3, 2017

Run-time Stack mechanism in Java

Run-time Stack mechanism in Java

Ans:

For every thread that you create,JVM (Java virtual machine) creates a run-time stack.

1)Each and every call performed in a thread is stored in the stack.

2)Each entry in the run-time stack is known as activation record or stack frame.

3)After completing every method call by the thread then all the corresponding entry of the stack will be removed.

4)After completing all the methods, the stack will be empty and that run-time stack will be destroyed by the JVM before terminating the thread.

Normally:

Construction of run-time Stack : 

1. Firstly, the main thread will call main() method and the corresponding entry will be in the stack.

2. After that main() method is calling fun() method, which will store in the stack.

3. In the fun() method, moreFun() method is called. Therefore at last moreFun() will be stored in stack.

4. Finally, moreFun() is not calling any method and it will print Hello Guys!

Example:

class Test {
public static void main(String[] args)
{
fun();
}
public static void fun()
{
moreFun();
}
public static void moreFun()
{
System.out.println("Hello Guys!");
}
}

Output: Hello Guys!



Destruction of run-time stack : 

After printing Hello Guys!, its corresponding entry will be removed from the stack and it will go to fun() method and there is nothing for execution that’s why the entry of fun() method is removed from the stack and so on.When the stack is empty then the run-time stack is destroyed by the JVM.



Abnormally

Construction of run-time Stack :

1. The example below have ArithmeticException at method moreFun() location, the JVM will check any exception handling code is there. If not, then method moreFun() will be responsible to create exception object because of exception are raised on method moreFun() and corresponding entry from the stack will be removed and the control goes to method fun().

2. JVM again go to the caller method to check if it is having any exception handling code are not. If not JVM terminates the method abnormally and deleted the corresponding entry from the stack.

3. The above process continues until main thread. If the main thread(main method) doesn’t have any exception handling code the JVM also terminates the main method abnormally and default exception handler is responsible to print the exception message to the output screen which is the part of JVM.

Sample Code:

public class Test {
public static void main(String[] args)
{
fun();
}
public static void fun()
{
moreFun();
System.out.println("Method fun");
}
public static void moreFun()
{
System.out.println(10 / 0);
System.out.println("Method moreFun");
}
}

Output:

Exception in thread "main" java.lang.ArithmeticException: / by zero
at Test.moreFun(Test.java:14)
at Test.fun(Test.java:9)
at Test.main(Test.java:5)





Destruction of run-time stack:







Most frequent word in an array of strings? OR Find winner of an election where votes are represented as candidate names?

Question:

Most frequent word in an array of strings?

                                                    OR

Find winner of an election where votes are represented as candidate names?

Solution:

Given an array of names of candidates in an election. A candidate name in array represents a vote casted to the candidate. Print the name of candidates received Max vote. If there is tie, print lexicographically smaller name.

               OR
Given an array of words find the most occurring word in it.

Input : arr[] = {"Abhinaw", "for", "Abhinaw", "Abhinaw",
                "portal", "to", "learn", "can",
                "be", "computer", "science",
                 "zoom", "yup", "fire", "in",
                 "be", "data"}

Output : Abhinaw

"Abhinaw" is the most frequent word as it.
occurs 3 times

So i can think of like this:

Run two loops and count occurrences of every word.

Time complexity of this solution is O(n * n * MAX_WORD_LEN).

Bu i have an another efficient solution also which is below:

Trie data structure: The idea is simple first we will insert in trie. In trie, we keep counts of words ending at a node. We do preorder traversal and compare count present at each node and find the maximum occurring word.

Time Complexity : O(n * MAX_WORD_LEN)

I have  Hashing solution also and which is more efficient solution than above.Have a look into the code.

Sample Code:

import java.util.HashMap;
import java.util.Map;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MostFrequentWordOrElectricVotingApp
{
public static void main(String[] args)
{
String[] votes = { "Abhinaw", "Gaurav", "Abhishek",
"Garima", "babli", "Logesh",
"Lalitha", "Pawan", "Abhinaw",
"Abhinaw", "Garima", "Abhinaw",
"Abhinaw" };

        findWinner(votes);
}

public static void findWinner(String votes[])
       {
        Map<String,Integer> map =new HashMap<String, Integer>();
        for (String str : votes)
        {
            if (map.keySet().contains(str))
                map.put(str, map.get(str) + 1);
            else
                map.put(str, 1);
        }
        int maxValueInMap = 0;
        String winner = "";
 
        for ( Map.Entry<String,Integer> entry : map.entrySet())
        {
            String key  = entry.getKey();
            Integer val = entry.getValue();
            if (val > maxValueInMap)
            {
                maxValueInMap = val;
                winner = key;
            }

            // If there is a tie, pick the
            else if (val == maxValueInMap && winner.compareTo(key) > 0)
                winner = key;
        }
        System.out.println("Winning Candidate is :" +winner);
    }

}

 Output: 

 Winning Candidate is :Abhinaw