[Interview Question ][Data Structure] Two Sum Problem -Array

Two sum problem is one of the most asked data structure questions for a java developer interview. There could be one or more ways to solve the problem but i am trying to give the optimized solution to this problem.

Lets first see the Problem Statement.

Problem Statement - Given an array, We need to find all the possible sets of 2 elements whose sum is equal to the target sum.

Solution: Given an array, lets say [10,-2,5,3,1,7,4] and given a target = 8 , We need to find all the possible 2 elements whose sum is equal to the 8.

the possible output will be 

[10,-2] ,[5,3],[1,7]

Pseudo code- 

• Lets first sort the array.
• After sorting, take 2 pointers, one is leftmost & second is rightmost.
• we will start taking each element from left & right then check some of both the element.
• If the sum is less then the target sum, then move the left pointer by one.
• if the sum is greater than the target sum, then move the right pointer to left by one.
• else if it is equal to target then put the elements one result array and move both left & right pointer by one.

Now let see the Java implementations.

public class TwoSumProblem {
	
	public static void main(String[] args) {
		int[] arr = {10,-2,5,3,1,7,4};
		
		twoSumArray(arr,8);
	}
	
	public static void twoSumArray(int[] arr, int i) {
		
//		sort the array using Arrays  sort
		
		Arrays.sort(arr);
		int size = arr.length;
		int left = 0;
		int right =size-1;
		List<Integer> list = new ArrayList<Integer>();
		
		while(left<right) {
			int diff = arr[left]+arr[right];
			if(diff<i) {
				left++;
			}else if(diff>i) {
				right--;
			}else {
				list.add(arr[left]);
				list.add(arr[right]);
				left++;
				right--;
			}
		}
		
		for(Integer it : list) {
			System.out.println(it);
		}
	}

If you run this program you will get the list of sub set whose sume is equal to 8.

Hope this will help you in your datastructre problem solving.

Thanks for reading.

Read More

Algorithm to find if String contains only Unique characters without using any additional data structure

The string is one of the most asked questions in the Interview of Java developers.

Today we will see one of the most asked questions as to how will you find if String does not contain any duplicate characters.

There are different ways to check them, But we will only discuss the most efficient way to implement this algorithm.

Logic.

We know that characters have only 256 ascii values and there are only 128 values for alphabet characters. 

So what we will do is we will create one array of boolean of size 128 and we will update the index of array as true whenever we find the char value in the string , else if we get the same value in the string , the already true value will make the loop as false.
Also read - Find Longest Common Ancestor(LCA) Program in java

Time Complexity - O(n)

Space Complexity - O(1)

Code -

public class ArraysAndStringDemo {
 
 public static void main(String[] args) {
  
  String str = "programinjava";
  
  System.out.println(isUnique(str));
  
 }
 
 public static boolean isUnique(String str) {
  boolean[] char_set = new boolean[128];
  for(int i =0;i<str.length();i++) {
     int value =str.charAt(i); //getting the ascii value of character
   
     if(char_set[value])     // checking if it is already in the array
   return false;
   
     char_set[value] = true;
  
   
  }
  return true;
 }

}

If you have any issue in understanding the same , Please leave us a comment. Happy to help

Thanks for reading
Noeik

Read More

Thread Pooling In Java Using Executors Class

Most of the Important and most of the developer found one topic in java they perform a task and then they get destroyed. Purpose of multithreading is to perform multiple tasks simultaneously for effective utilization of our resources (time and CPU).

Imagine that there are 10 tasks to perform, so using traditional multithreading mechanism we will need 10 threads. Do you see a drawback in this approach? I see it; creation of a new thread per task will cause resource overhead.

Read More

Find Longest Common Ancestor(LCA) Program in java

Objective : The objective of this problem is to find the Longest Common Ancestor of the Tree.

Longest Common Ancestor is the common node in a tree who is common among the given 2 or more node.

Also see : Program to find the Nth Element of a Singly Linked list from the end in java

Implementation :

import java.util.HashMap;
import java.util.Stack;

public class LCA {
    public static void main(String[] args) {
        // NOTE: The following input values will be used for testing your solution.
        // The mapping we're going to use for constructing a tree.
        // For example, {0: [1, 2]} means that 0's left child is 1, and its right
        // child is 2.
        HashMap<Integer, int[]> mapping1 = new HashMap<Integer, int[]>();
        int[] childrenA = {1, 2};
        int[] childrenB = {3, 4};
        int[] childrenC = {5, 6};
        mapping1.put(0, childrenA);
        mapping1.put(1, childrenB);
        mapping1.put(2, childrenC);

        TreeNode head1 = createTree(mapping1, 0);

        // This tree is:
        // head1 = 0
        //        / \
        //       1   2
        //      /\   /\
        //     3  4 5  6


        HashMap<Integer, int[]> mapping2 = new HashMap<Integer, int[]>();
        int[] childrenD = {1, 4};
        int[] childrenE = {3, 8};
        int[] childrenF = {9, 2};
        int[] childrenG = {6, 7};
        mapping2.put(5, childrenD);
        mapping2.put(1, childrenE);
        mapping2.put(4, childrenF);
        mapping2.put(3, childrenG);

        TreeNode head2 = createTree(mapping1, 5);
        // This tree is:
        //  head2 = 5
        //        /   \
        //       1     4
        //      /\    / \
        //     3  8  9  2
        //    /\
        //   6  7


        // lca(head1, 1, 5) should return 0
        // lca(head1, 3, 1) should return 1
        // lca(head1, 1, 4) should return 1
        // lca(head1, 0, 5) should return 0
        // lca(head2, 4, 7) should return 5
        // lca(head2, 3, 3) should return 3
        // lca(head2, 8, 7) should return 1
        // lca(head2, 3, 0) should return null (0 does not exist in the tree)
    }


    // Implement your function below.
    public static TreeNode lca(TreeNode root, int j, int k) {
        Stack<TreeNode> pathToJ = pathToX(root, j);
        Stack<TreeNode> pathToK = pathToX(root, k);
        if (pathToJ == null || pathToK == null) {
            return null;
        }

        TreeNode lcaToReturn = null;

        while (!pathToJ.isEmpty() && !pathToK.isEmpty()) {
            TreeNode jPop = pathToJ.pop();
            TreeNode kPop = pathToK.pop();
            if (jPop == kPop) {
                lcaToReturn = jPop;
            } else {
                break;
            }
        }
        return lcaToReturn;
    }

    public static Stack<TreeNode> pathToX(TreeNode root, int x) {
        if (root == null) {
            return null;
        }

        if (root.value == x) {
            Stack<TreeNode> path = new Stack<TreeNode>();
            path.push(root);
            return path;
        }

        Stack<TreeNode> leftPath = pathToX(root.left, x);
        if (leftPath != null) {
            leftPath.push(root);
            return leftPath;
        }

        Stack<TreeNode> rightPath = pathToX(root.right, x);
        if (rightPath != null) {
            rightPath.push(root);
            return rightPath;
        }

        return null;
    }

    // A function for creating a tree.
    // Input:
    // - mapping: a node-to-node mapping that shows how the tree should be constructed
    // - headValue: the value that will be used for the head ndoe
    // Output:
    // - The head node of the resulting tree
    public static TreeNode createTree(HashMap<Integer, int[]> mapping, int headValue) {
        TreeNode head = new TreeNode(headValue, null, null);
        HashMap<Integer, TreeNode> nodes = new HashMap<Integer, TreeNode>();
        nodes.put(headValue, head);
        for(Integer key : mapping.keySet()) {
            int[] value = mapping.get(key);
            TreeNode leftChild = new TreeNode(value[0], null, null);
            TreeNode rightChild = new TreeNode(value[1], null, null);
            nodes.put(value[0], leftChild);
            nodes.put(value[1], rightChild);
        }
        for(Integer key : mapping.keySet()) {
            int[] value = mapping.get(key);
            nodes.get(key).left = nodes.get(value[0]);
            nodes.get(key).right = nodes.get(value[1]);
        }
        return head;
    }
 }

In this Implementation we have used the Stack and hashmap , Also if you see the Comments all the functionality should be clear .

If you have any issue or you are not able to undertand the program, leave us a comment.

Thanks for reading
Noeik

Read More

Program to find the Nth Element of a Singly Linked list from the end in java

Data structure is one of the most asked interview topic for java developer interviews and believe me linked list is one of the most favorite area of data structure , there are so many other interview questions for linked list and one of them we will discuss today in this post.

Read More

Top Course for Data Structures and Algorithms in Java - Job Interview

Most of the People just aware about data structure but when it comes to the in depth knowledge of Data structure , very few of the people stand up to mark.

Data structure itself is one of the most buzz field in the computer science industry and every one once in the life always read data structure either in their college life or while preparing for interview , but few of the people is having good in depth knowledge of data structure.

people things that data structure is very tough field , but believe me its one of the most interesting topic in computer science where actually engineers are solving the day to day problem of human being from creating algorithms and making life digital.

Program of Breadth first Traversal(BFT) AND Depth First Traversal(DST)

Let see how if you dont have good knowledge of data structure , you dont need to be worried there are some online courses which are very good on Udemy.

Before we go further you can also see some of the important course every developer should take.

lets go

1. If you are new to data structure and preparing for job interview below is good course.

Data Structure and Algorithms Analysis - Job Interview

By Hussein Al Rubaye

What you will get from this course

• It is good for beginner , will cover from all the topic important for interview.
• The Instructor will teach you all the topic and then give explain every datastrucure.
• Will highlight all the interview related topics and interview questions can be asked.
• Will clear your doubt and queries.

Topic Covered

• Analysis algorithms like Sorting, Searching,  and Graph algorithms. 
• how to reduce the code complexity from one Big-O  level to another level. 
• Furthermore, you will learn different type of Data Structure for your code.
• Also you will learn how to find Big-O for every data structure, 
• how to apply  correct Data Structure to your problem in Java. 
• how to analysis problems using Dynamic programming. 
• code complexity in Different algorithms like Sorting algorithms ( Bubble, Merge, Heap, and quick sort) ,
• searching algorithms ( Binary search, linear search, and Interpolation), 
• Graph algorithms( Binary tree, DFS, BFS, Nearest Neighbor and Shortest path, Dijkstra's Algorithm, and A* Algorithm). 
• Data Structure like Dynamic Array, Linked List, Stack, Queue, and Hash-Table

Note : This is one of the best course though the english of instructor is not native english man , you might fell difficulties.  

I hope this will help you to get the indepth knowledge of data structure ,and will help you land to dream job.

If you like this aricle please share it with your friend and colleagues.

Thanks for reading
Noeik 

Read More

[Interview Question] Common Elements in Two Sorted Arrays Program in java

Common Element in two sorted array is one of the data structure interview question asked in most of the company now a days .

In this article we will see how to find the Common Element in two sorted array.

Objective: Find the Common Elements in Two Sorted Array

Implementation:

Explanation:

Most of the Logics are written as a Comment in Program . This will help you in understanding the Program.

Other Frequently Asked Interview Questions
Most Frequent Occurring Item in an Array program in java
Program in java for Array Rotation

If you have any issue in the above program and if you need help to understand , please leave us a comment.

Thanks for reading
Noeik

Read More

Most Frequent Occurring Item in an Array program in java

Objective  We need to find the most frequent occurring item or number in given array.

Solution : 

I would recommend you to please practice by yourself before see the program

Implementation 

Other Interview Questions :
Quick Sort Program 
BFS & DFS Program
Heap Sort Program


I hope this program will help you in understanding problem solving. If you have any issue , leave us  comment.

Thanks for Reading
Noeik

Read More

[Interview Question] Program in java for Array Rotation

Objective : We will be given one array and asked to rotate the array by d no. of time 

ex- Input - {1,2,3,4,5} d=2
Output - {3,4,5,1,2} 

Important Interview questions

I will Recommend you to please do it by yourself before see the answer.

Approach 1 : Using temp Array

Pseudo code 

1. We will use one temp array where we will add the element of value d
2. then we will copy the d+1th element to 0th place d+2th element to 1th element and so on .
3. Now we will merge the temp array elements at the end of the array.

Approach 2: Rotate by one to left 

Pseudo Code .

1. We will first store the first element to temp variable.
2. Move all the element to left by one.
3. store the temp variable in last place.

Program Code:

Approach 3 : Reversal Algorithm

Pseudo Code

1. Let suppose we need to rotate the array by d index what we will do is as below
2. we first reverse the (o,d) element of the array 
3. in second we will reverse the (d+1 , length) elements of the array .
4. In third we will reverse (0, length ) element of the array this will give use the required array.

Program Code:

I guess the Code is self explanatory and I you still face any problem and looking for help , Please let me know , will be happy to help

If you like this article please share it with your friends and colleagues

Thanks for reading 
Noeik  

Read More

What is Factory Design Patten and its Code in java

What is Factory Desigen Pattern.also write the code?

A Factory Pattern  define an interface or abstract class for creating an object but let the subclasses decide which class to instantiate. 

In other words, subclasses are responsible to create the instance of the class.

 

Advantage of Factory Design Pattern

1-Factory Method Pattern allows the sub-classes to choose the type of objects to create.

2-It promotes the loose-coupling by eliminating the need to bind application-specific classes into the code. That means the code interacts solely with the resultant interface or abstract class, so that it will work with any classes that implement that interface or that extends that abstract class.

 

Usage of Factory Design Pattern

1-When a class doesn't know what sub-classes will be required to create

2-When a class wants that its sub-classes specify the objects to be created.

3-When the parent classes choose the creation of objects to its sub-classes.

Ex:

Step 1->

Create an interface.

Shape.java

public interface Shape

{

   void draw();

}

Step 2->

Create concrete classes implementing the same interface.

1-Rectangle.java

public class Rectangle implements Shape

{

   @Override

   public void draw()

   {

     System.out.println("Inside Rectangle::draw() method.");

   }

}

2-Square.java

public class Square implements Shape

{

   @Override

   public void draw()

   {

      System.out.println("Inside Square::draw() method.");

   }

}

3-Circle.java

public class Circle implements Shape

{

   @Override

   public void draw()

 {

      System.out.println("Inside Circle::draw() method.");

   }

}

Step 3->

Create a Factory to generate object of concrete class based on given information.

ShapeFactory.java

public class ShapeFactory

{

           

   //use getShape method to get object of type shape

   public Shape getShape(String shapeType)

   {

      if(shapeType == null){

         return null;

      }               

      if(shapeType.equalsIgnoreCase("CIRCLE")){

         return new Circle();

        

      } else if(shapeType.equalsIgnoreCase("RECTANGLE")){

         return new Rectangle();

        

      } else if(shapeType.equalsIgnoreCase("SQUARE")){

         return new Square();

      }

     

      return null;

   }

}

Step 4->

Use the Factory to get object of concrete class by passing an information such as type.

FactoryPatternDemo.java

public class FactoryPatternDemo

{

  public static void main(String[] args)

 {

      ShapeFactory shapeFactory = new ShapeFactory();

      Shape shape1 = shapeFactory.getShape("CIRCLE");

              shape1.draw();

     Shape shape2 = shapeFactory.getShape("RECTANGLE");

                shape2.draw();

      Shape shape3 = shapeFactory.getShape("SQUARE");

             shape3.draw();

   } 

}

If you have any issue in understanding the above article , reach out to us leave us a comment.

Thanks for reading

Noeik

Read More

Design Pattern and Implementation of Singleton Design Pattern in java

What is Desigen  Pattern ?

A design pattern is a well-proved solution for solving the specific problem/task.  We must use the design patterns during the analysis and requirement phase of SDLC(Software Development Life Cycle).

Design patterns ease the analysis and requirement phase of SDLC by providing information based on prior hands-on experiences.

 

Categorization of design patterns:

Basically, design patterns are categorized into two parts:

1.     Core java (or JSE) Design Patterns.

2.     JEE Design Patterns.

What is  Singleton Design Pattern . also write the code?

Singleton Pattern says that just"define a class that has only one instance  

and provides a global point of access to it".

 A class must ensure that only single instance should be created and single object can be used by all other classes.

Advantage of Singleton design pattern

Saves memory because object is not created at each request. Only single instance is reused again and again.

This has advantages in memory management, and for Java, in garbage collection. Moreover, restricting the number of instances may be necessary or desirable for technological or business reasons--for example, we may only want a single instance of a pool of database connections.

Usage of Singleton design pattern

Singleton pattern is mostly used in multi-threaded and database applications. It is used in logging, caching, thread pools, configuration settings etc.

How to create Singleton design pattern?

To create the singleton class, we need to have static member of class, private constructor and static factory method.

1-Static member: It gets memory only once because of static, itcontains the instance of the Singleton class.

2-Private constructor: It will prevent to instantiate the Singleton class from outside the class.

3-Static factory method: This provides the global point of access to the Singleton object and returns the instance to the caller.

Ex:

Ex->

class Demo

{

   private static Demo obj=null;

  

   static

   {

               obj = new Demo();

   }

  

   private Demo()

   {

               System.out.println("Demo");

   }

  

   public static Demo getObject()

   {

               return obj;

   }

}

 public class Demo1 {

             public static void main(String[] args) {

                                    //Demo d1 = new Demo();

                                     Demo d2 = Demo.getObject();

                                     Demo d3 = Demo.getObject();

                                     System.out.println(d2);

                                     System.out.println(d3);

                        }

}

How can be create only 5 object of the class

     A:

    public class MSInt

    {

      private static MSInt instance = null;

      private static int count = 0;

    private MSInt()

    {

       System.out.println("MSINT");

    }

   public static MSInt getInstance()

    {

        if(count < 5){

            instance = new MSInt();

             count++;

             return instance;

        }

        else

        {

            return null;

        }

     }

     public static void main(String[] args)

     {

MSInt m1 =  MSInt.getInstance();

MSInt m2 = MSInt.getInstance();

MSInt m3 = MSInt.getInstance();

MSInt m4 = MSInt.getInstance();

MSInt m5 = MSInt.getInstance();

MSInt m6 = MSInt.getInstance();

System.out.println("m1"+m1);

System.out.println("m2"+m2);

System.out.println("m3"+m3);

System.out.println("m4"+m4);

System.out.println("m5"+m5);

System.out.println("m6"+m6);

    }

}

If you have any concern and any query , leave us comment !!

Thanks for reading

Noeik

Read More