Print boundary or edge node of tree in anti-clockwise order

This question was asked in amazon interview. we all know that, binary tree is applicable only for numeric values, and each node has left and right node as child node and last node in tree is called leaf node(node doesn't have left and child node). 


Lets look at the below binary tree

Solution:-

Traverse and print all the left-boundary from root node in top-down direction(22,16,8), then leaf node of all the left-sub tree from left to right direction(6,10,21), then left node of the all the right-sub tree from left to right direction(23,31,33) and finally print right boundary from bottom to top direction(32,24). If you see the printed node, it doesn't print the node 20, because it's not a boundary node).

The above solution will break into 4 steps.

1. Traverse and print all the left-boundary(except leaf node 6) from root node in top-down direction(22,16,8).
2. Print leaf node of all left-sub tree from left to right direction (6,10,21).
3. Print lead node of all right-sub tree form left to right direction(23,31,33).
4. Finally print all right boundary from bottom to top direction(32,24).

Code:-

class Node 

{

    int data;

    Node left, right;

  

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTreeBoundary 

{

    Node root;

  

    // function to print leaf node of a binary tree

    void printLeaf(Node node) 

    {

        if (node != null) 

        {

        printLeaf(node.left);

  

            // Print if it is a leaf node

            if (node.left == null && node.right == null)

                System.out.print(node.data + " ");

            printLeaf(node.right);

        }

    }

  

    // Print all left boundry nodes, except a leaf node in TOP DOWN manner

    void printLeftBoundary(Node node) 

    {

        if (node != null) 

        {

            if (node.left != null) 

            {

                  

                // to ensure top down order, print the node before calling itself 

                System.out.print(node.data + " ");

                printLeftBoundary(node.left);

            } 

            else if (node.right != null) 

            {

                System.out.print(node.data + " ");

                printLeftBoundary(node.right);

            }

        }

    }

  

    // Print all right boundry nodes, except a leaf node in BOTTOM UP manner

    void printBoundaryRight(Node node) 

    {

        if (node != null) 

        {

            if (node.right != null) 

            {

                // to ensure bottom up order, print the node before calling itself 

                printBoundaryRight(node.right);

                System.out.print(node.data + " ");

            } 

            else if (node.left != null) 

            {

                printBoundaryRight(node.left);

                System.out.print(node.data + " ");

            }

        }

    }

  

    // Function to do boundary traversal in anti-clock wise direction

    void printBoundary(Node node) 

    {

        if (node != null) 

        {

            System.out.print(node.data + " ");

  

            // Step 1:- Print the left boundary in top-down manner.

            printLeftBoundary(node.left);

  

            // Step 2:- Print all leaf nodes of left-subtree from left-right direction

            printLeaf(node.left);

            // Step 3:- Print all leaf nodes of right-subtree from left-right direction            

            printLeaf(node.right);

  

            // Step 4:- Print the right boundary in bottom-up manner

            printBoundaryRight(node.right);

        }

    }

       

    public static void main(String args[]) 

    {

        BinaryTreeBoundary tree = new BinaryTreeBoundary();

        tree.root = new Node(22);

        tree.root.left = new Node(16);

        tree.root.left.left = new Node(8);

        tree.root.left.left.left = new Node(6);

        tree.root.left.left.right = new Node(10);

        tree.root.left.right = new Node(20);

        tree.root.left.right.right = new Node(21);

        

        tree.root.right = new Node(24);

        tree.root.right.left = new Node(23);

        tree.root.right.right = new Node(32);

        tree.root.right.right.left = new Node(31);

        tree.root.right.right.right = new Node(33);

        tree.printBoundary(tree.root);

  

    }

}

output:-

22 16 8 6 10 21 23 31 33 32 24 

Time Complexity: O(n). Traversing all the elements in array

Click to Read more Data structure questions and answer

If you like the above solution . Please share this blog

Amazon question: Calculate total amount of rain water trapped between the towers.

This question was asked by amazon , to calculate the amount of water trapped between the  towers with the help of given array which consists of height of the each tower.

For example: input : int tower = {4,2,3,5,2,3,4,5};

For the above example , the output, i.e.Total amount of the water is the summation of water stored in the tower 2,3,5,6 and tower 7. i.e (2+1+3+2+1=9).

The logic should work for all the scenario, means tallest tower can be located anywhere, it can be first, last or in any position. Lets see the below towers.

Example 2:- input: int tower = {5,0,5,2,5,3,4,5}

Logic :-
  
The logic would be, for every tower calculate the highest height of the tower from left and highest height of tower from the right and then use minimum height of these two tower, to calculate the amount of water. For example:- 

From the above figure 1:- For tower 2, highest height of the tower from left is tower 1(4) and highest height of the tower from right is tower 4(5), then take minimum height of this two tower(4), and subtract the height of tower 2(2) from this minimum tower(4), this will be the amount of water trapped for the tower 2. The output will be (4-2) = 2. Repeat the above step for all the tower and add the output of water trapped for each tower. This will be the total amount of rain trapped between the towers.


Algorithm:-

Step 1: Declare left and right array to store the highest height from left and right side of the each tower and waterAmount to calculate the total amount of water trapped between the towers.
Step 2: Traverse the input array(height of all the towers) and  calculate the maximum height of tower from the left and from the right of each tower and assign to left and right array respectively.
Step 3: Again traverse the input array and calculate the amount of trapped water for all the tower and add the result to waterAmount value.

Code:-

import java.util.Arrays;
public class RainwaterStorage{

public static void main(String[] args) {
int tower[] = {4,2,3,5,2,3,4,5}; // height of all the tower
System.out.println(findWaterAmount(tower, tower.length));
}

public static int findWaterAmount(int tower[], int count)
{
   int left[] = new int[count];
   int right[] = new int[count];
   int waterAmount = 0;   
   // Fill left array (contain maximum height tower value from the left of each tower)
   left[0] = tower[0];
   for (int i = 1; i < count; i++)
      left[i] = Math.max(left[i-1], tower[i]);

   // Fill right array (contain maximum height tower value from the right of each tower)
   right[count-1] = tower[count-1];
   for (int i = count-2; i >= 0; i--)
      right[i] = Math.max(right[i+1], tower[i]);

   // below code is to find the amount of trapped water for all the tower and add the result to waterAmount value. 
   for (int i = 0; i < n; i++) 
       waterAmount+= Math.min(left[i],right[i]) - tower[i];

   return waterAmount;
}
}

Output:-
9

Performance:- 
Time Complexity: O(n). Traversing all the elements in array
Auxiliary Space: O(n). Additional aray to store maximum value of the tower from the left and from right.

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

why java doesn't allow to create object for abstract class and interface ?

In interview, most of the people will explain about abstraction and interface, when interviewer ask why java doesn't allow to create object for abstract class and interface, all got struck. Here i  am gonna explain the reason with real time example.

The abstract class and interface represents the  more generic form or abstract entity, for example animal,vehicle and shape(It doesn't represent real entity). These abstract entity doesn't stand on its own. Because each animal (cat, lion,tiger, elephant, etc) ,vehicle(car, bus, aeroplane, train, etc) , Shape (circle, square, rectangle) which define its own property and behavior.  There's no such thing as a "pure" animal - there are specific types of animals . And you cannot call car as vehicle, does it make any sense in real time.

And also technically in java, abstract method may contain abstract method and implementation method. Just think, if java allowed you to create object, when you are calling the abstract method ,  what result it will deliver ? The same concept applicable for interface also.

Both the concept will be used to make proper design in the application in order to achieve more flexible and expandable.

Also you can use abstract and interface as template, sub class or real time entity can extend and built on it before you can use it.

Also some people say, abstract class and interface are incomplete class, so JVM doesn't know how much memory is required to create object. So it doesn't allow to create objects. This answer also acceptable.  But definitely, this is not a exact answer interviewer will look. So please give some real time example and explain in detail.

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

Design LRU cache and explain with real time example in java

Least Recently Used Cache - The limited or LRU caching technique is used to stored only the recently used data and expires the one which is least recently used whenever the new entry into the cache.

Cache removes least recently used item while making entry for a new one.

Let's see the below scenario. In a trading system, they want to maintain the 5 recently used product to do future analysis. LRU is used in this case.

For example :  From above scenario, trading system want to store 5 recently executed product from the list of 10 products(A,B,C,D,E,F,G,H,I,J). Trading system execute first five product in the order A,B,C,D and E. The below picture depict the LRU cache
                   E -- D -- C -- B -- A  

Where 'E' is the recently used and 'A' is the least recently used. Now, trading system execute another product 'F', now LRU cache has to remove 'A' and add 'F' to the cache. Now the above cache looks like below
                   F -- E -- D -- C -- B 

What happen if trading system execute the product 'C' which is already in the LRU cache. The cache has to remove the 'C' product and add it to the beginning of the cache
                  D -- F -- E -- C -- B 

if system execute new product 'G', then B is removed.
                  G -- D -- F -- E -- C 

if system execute again product 'D' , then 'D' is removed and added to the beginning of the cache.
                   D -- G-- F -- E -- C 

if system execute new product 'H',  then 'C' is removed. Now the cache looks like below.
                    H -- D -- G-- F -- E    

By repeating the above logic, LRU store recently used 5 product in the cache.

Click to Read more Data structure questions and answer

If you like the above solution . Please share this blog

How array is giving better performance while retrieving element based on its index?

The answer is array stores all the element in the Contiguous Memory Allocation. Based on the base memory address (address of first element in the array),  array increase its pointer by adding the index which is passed.  For example: array[4] , index 4 will be added to the pointer and now pointer will be pointing fourth element of array.  Lets see the below explanation.

we all know that, array is a list of  element's of same data type. It can be primitive data type such as int, char, double, float or it can be user defined data type such as Objects.

we can access those elements based on the index(starts with 0 - first element). So each element in a array is sequentially associated with the index of the array.  For example:

     int a[] = {12,13,17,15,18,19}

    12 = index 0
    13 = index 1
    17 = index 2
    15 =    ...    3
    18 =    ...    4
    19 = index 5

  Array size is 6 

In JVM, there are different type of approach is followed while allocating memory based on the data type. Array is based on contiguous memory allocation(one of the oldest memory allocation scheme), memory is allocated sequentially for all the elements in array. Lets see how the memory allocation is done for the above array.

In java, int variable takes 4 byte as size, the above array need 24 bytes (size*4 bytes = 6*4 = 24 bytes) in memory.  The below image depicts the allocation in memory.

In the above chart, memory allocation starts from 1000 and allocating 4 bytes for each elements from the array. Base pointer always store the starting address of the array. While accessing, based on the index, array pointer will take summation of base pointer with (index * size of data type) to fetch the exact value of the array element.

For example:-
      int fourthElement = a[3];


The above code will have below logic in the system code.
            int array_pointer = (index*byte of int) + Base pointer
            int array_pointer = (3*4)+1000 = 1012 (Fourth element address).

The same logic is applicable for all the data types. Because of this logic, array doesn't traverse through all the elements  in the array.  

This implementation gives more performance while retrieving the element based on its index.

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

              
  




   
   

     

who is responsible to allocate memory while creating objects in java ?

The answer is Object class.

We all know, in java, Object class is a super class of all user defined class. That means all the user defined class extends Object class by default.

And also we know whenever we are creating the sub class object, super class constructor will get called first, this is because in java, the object creation are done by using top down approach. That means, JVM allocates memory from parent class to sub class. The reason behind is, memory is allocated to sub class based on property inherited from parent and also based on its own property. 

So initially, Object class constructor will get execute first whenever you are creating object for all user defined class. If you look at the constructor of Object class.

public class Object {
     private transient Class<?> shadow$_klass_;
     public Object() {             //   constructor of Object class
        if (shadow$_klass_.isFinalizable()) {
              java.lang.ref.FinalizerReference.add(this);
        }
    }
}

The above code clearly explain the role of Object class, it is allocating memory for object in heap using native call and also add the object to FinalizeReference to make it available for garbage collection. After certain amount of time or cycle, GC will run and check the object of the reference still exist , if not it will remove from the heap memory.

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

Difference between static block and empty block in java

Static block

1. Static block will be called when class loader is loading the class.
2. Always static block will get execute irrespective of object creation.
3. Only static variable can be initialized in static block. 
4. It can used for initialization purpose when your application is starting.
5. Instance method cannot be called from static block but you can call static method inside static block.
6. Your application initial parameter can be initialized here, for example logger, property file and mapping file.

Example:

  static {

      // initialization of static variable

      //  only can call another static method

  }

Empty block or Object Block

1. Empty block will be called when you are creating the object with new keyword.
2. Empty block will not get execute if you are not creating the object.
3. Both static and not static variable can be initialized in empty block.
4. It will be called before your default constructor, so  preinitialization can be done here.
5. Instance method and static method can be called form empty block.

Example:

      {
        //  initialization of static and non-static variable
        //  can call both static and non static method
      }


Java Example Program.

public class StaticClass {

static int count=0;     // static variable
 int a=0;                     //  non static variable

 static {                  // static block
   System.out.println(" staticblock ");
count++;          // initialization of  static variable
// instanceMethod();      // compile time error
     // a++;                      // compile time error
staticMethod();
}

 {         // empty block or object block
   System.out.println(" empty block ");
count++;     // valid
instanceMethod();  //valid
staticMethod();   // valid
}

StaticClass() {    // constructor
System.out.println(" default constructor");
}

public void instanceMethod() {
System.out.println(" instanceMethod");
}

public static void staticMethod() {
System.out.println(" staticMethod ");
}

public static void main(String args[]) {
System.out.println(count);
StaticClass object = new StaticClass();
System.out.println(count);
}
}

output:-

 staticblock 
 staticMethod 
1
 empty block 
 instanceMethod
 staticMethod 
 default constructor
2

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

final keyword and its uses related to performance of the application

There many places in java final keyword is more useful.

1. final variable and its static binding
2. final method
3. final class

1) final variable and its static binding

The value of the final variable cannot be changed once it is initialized.

     final int a=5;

     a=a++;      // compile time error

Once you have declared variable with final keyword, java compiler will identify this as final and replace it with actual value , this is called static time binding. This will improve the your application performance, i.e instead of reading every time from memory, it will replace variable name with its original value. For ex:

    

   final int a=5;

   int b=5;

   int add= a + b;

   int mul=a*b;

   int div=a/b;

The above source code will be converted into below code after compilation. 

   final int a=5;

   int b=5;

   int add= 5 + b;  

   int mul=5*b;

   int div=5/b;

The   java compiler replace the variable 'a' with its original value.

        

 In Real-time application, use final keyword before the  variable which is constant and doesn't change its value in entire flow of application, because it will improve the application performance.

2) final method

Final method cannot be overridden in sub class. You can use final keyword before the method, which you don't want to override in subclass. For ex:

Class Animal  {

   final public void getName() {

       System.out.println(" name ");

   }

}

Class Cat Animal {

   public void getName() {          // compile time error

       System.out.println(" name "); 

   }

}

3) final class

Final class cannot be extend in sub class.  In java, final keyword is used to create immutable class to avoid modification of those properties in sub class. All wrapper class such as Integer, Float , Double are created using final keyword.

final Class Immutable{

    // properties

}

Class Subclass extends Immutable {  // compile time error

}

Key points 

1. if final variable is not initialized, it is called as blank variable and it will be initialized only in constructor.
2. static blank final variable will be initialized only in static block.
3. if you are using final variable in method arguments, it cannot be changed inside the method.
4. constructor cannot be final.
5. final method can be inherited but it cannot be override.
6. All variable declared inside java interface are implicitly final

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

Amazon interview questions :- How to find a horoscope(relation) between two name by using "FLAMES" in Java.

This question was asked in amazon interview.

First interviewer was asked whether do you know about flames.  I said no, then he started explaining about how the "FLAMES" was working two find a horoscope between two name by giving below example.

Lets take two name "Dany" and "Diana". And strike the common character from the two name.

For Example:

Step 1: To find total length of remaining mismatched character of two name.

The above character check is case insensitive('a' is same as 'A');


Step 2: To strike character from 'FLAMES' based on the length value of Step 1.

Step 3: To find a horoscope relation between two name based on the last character from Step 2.

This can be achieved through default set values of each character of 'FLAMES'.

• F   - Friend
• L   - Love
• A   - Affection
• M  - Marriage
• E   - Enemy
• S    - Sister

In this case the last character is 'F'. So the horoscope relation between two name is 'Friend'
            
For above steps, interviewer wants me to write logic in Java.

Code:

public class Flames {
private static void CalCulateFlames(String first, String second) {
String flames = "flames";
for (int i = 0; i < first.length(); i++) {   // logic to strike the common letter.
String c1 = first.substring(i, i + 1);
for (int j = 0; j < second.length(); j++) {
String c2 = second.substring(j, j + 1);
if (c1.equalsIgnoreCase(c2)) {
first = first.replaceFirst(c1, "");
second = second.replaceFirst(c2, "");
i = 0;
j = second.length();
}
}
}
int total = first.length() + second.length(); // total length of remaining mismatched character.
int c = 1;
while (flames.length() != 1) {   // logic to strike the "flames" letter based on total length.
int l = 0;
while (l < flames.length()) {
if (c == total) {
flames = flames
.replaceFirst(flames.substring(l, l + 1), "");
c = 1;
} else {
c++;
l++;
}
}
}
if (flames.equalsIgnoreCase("f")) {     // logic to find horoscope relation between two name
System.out.println(" Friend ");
} else if (flames.equalsIgnoreCase("l")) {
System.out.println(" Love ");
} else if (flames.equalsIgnoreCase("a")) {
System.out.println(" Affection ");
} else if (flames.equalsIgnoreCase("m")) {
System.out.println(" Marriage ");
} else if (flames.equalsIgnoreCase("e")) {
System.out.println(" Enemy ");
} else {
System.out.println(" Sister ");
}
}

public static void main(String[] args) {
CalCulateFlames("Dany", "Diana");
}
}

Output:-

friend

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

Flipkart interview questions : How to merge two sorted array and final array should be in descending order with O(n) performance.

Lets see the above questions in detail.

There two integer array int a[] = {12,45,67,89,100} and int b[]={1,13,46,65,88,90,101} and resulted array would be int result[]={101,100,90,89,88,67,65,46,45,13,12,1}

And also interviewer wants the solution should be the best among all.


The above question was asked by one of the interviewer from flipkart.  Initially my friend gave lot of solution with less than the performance of O(N^2). But interviewer not convinced with his approach and ask him to do with O(N) performance. He was very strong in logical analytic, so tried and came up with the solution O(N) performance. 

Let's see the solution.

If you look at the above two sorted array, we know either one of the first array element will be placed at the last index of result array, this can be achieved by comparing the element of both the array.
The remaining element array also follow the same logic but it will be placed before the last element of result array.


Algorithm:

Step 1: Initialize two counter variable i and j to traverse a and b array.
Step 2: Initialize k=length of the result array(a.length+b.length)
Step 3: Compare each element of both the array and minimum value will be place at the end of the array and increase (i and j) or decrease(k) the respective counter variables.
Step 4: Repeat the step until the comparison of all the elements of array of a and b.
Step 5: Print the result array.

Code:

public class MergeArraySample {

public static void main(String[] args) {
int a[] = {12,45,67,89,100};    // array 1st
int b[] = {1,13,46,65,88,90,101}; // array 2nd
int len = a.length+b.length;  //  result array
int result [] = new int[len];
int i=0,j=0;  //  intialize counter to traverse 1st and 2nd array
int k= len-1;
while(i<a.length || j<b.length) {
if(i<a.length && j<b.length) {  // compare logic
if(a[i]<b[j]) {
result[k] = a[i];
i++;
} else {
result[k] = b[j];
j++;
}
} else if(i<a.length){
result[k] = a[i];
i++;
} else {
result[k] = b[j];
j++;
}
k--;
}
for(int v: result) {
System.out.print(v+",");
}
}
}

Output:-

101,100,90,89,88,67,65,46,45,13,12,1,

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog

Binary search and its performance

Binary search requires that the array or collection is already sorted. 

Binary search checks the element in the middle of the collection. If the search element is smaller or greater than the found element, then a sub-array is defined which is then searched again. If the searched element is smaller than the found element, then the sub-array is searched from the start of the array until the found element. If the searched element is larger than the found element, then the sub-array is searched from the found element until the end of the array. Once the searched element is found or the collection is empty then the search is over.

It can be done by using divide and conquer method or recursive method

1) Divide and conquer method

public class BinarySearch {

public static boolean binarySearch(int[] input, int element) {   

       int start = 0;

       int end = input.length - 1;

       while (start <= end) {

           int mid = (start + end) / 2;

           if (element == input[mid]) {

               return true;

           }

           if (element < input[mid]) {

               end = mid - 1;

           } else {

               start = mid + 1;

           }

       }

       return false;

   }

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};

System.out.println(binarySearch(arr, 12));

System.out.println(binarySearch(arr, 200));

}

}

output:

true

false

2) Recursive method

public class RecursiveBinarySearch {

public static boolean binarySearch(int[] input, int start, int end, int element) {

   

   if (start < end) {

       int mid = start + (end - start) / 2;  

       if (element < input[mid]) {

           return binarySearch(input, start, mid, element);

           

       } else if (element > input[mid]) {

           return binarySearch(input, mid+1, end , element);

           

       } else {

           return true;   

       }

   }

   return false;  

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};

System.out.println(binarySearch(arr, 0, arr.length, 16));

System.out.println(binarySearch(arr, 0, arr.length,200));

}

}

output:

true

false

Performance

Best case :- O(1) if the element found in the middle element (pivot element).

Average and worst case :- O(log n) for each check it divides array into sub array. For example if there is a 100 element in a array. Total element search is 10. 

Disadvantage:- 

Binary search cannot be applied on the array which is not sorted.

Click to view more:-  Algorithms and its performance