Find a Mother Vertex in a Graph Java Solution.

Find a Mother Vertex in a Graph?

What is a Mother Vertex?

Ans: A mother vertex in a graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

So now there can be multiple cases such as:

Case 1:- Undirected Connected Graph : In this case, all the vertices are mother vertices as we can reach to all the other nodes in the graph.

Case 2:- Undirected/Directed Disconnected Graph : In this case, there is no mother vertices as we cannot reach to all the other nodes in the graph.

Case 3:- Directed Connected Graph : In this case, we have to find a vertex -v in the graph such that we can reach to all the other nodes in the graph through a directed path.

So for this we can simply do this approach just perform a DFS/BFS on all the vertices and find whether we can reach all the vertices from that vertex. This approach takes O(V(E+V)) time, which is very inefficient for large graphs.

We can fuirther decrease this complexity by using "Kosaraju’s Strongly Connected Component Algorithm" .Simply this algo says mother verices are always vertices of source component in component graph. If there exist mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal).
A vertex is said to be finished in DFS if a recursive call for its DFS is over, i.e., all descendants of the vertex have been visited.

So the Algorithm is:

Algorithm :

1)Do DFS traversal of the given graph. While doing traversal keep track of last finished vertex ‘v’. This step takes O(V+E) time.

2)If there exist mother vertex (or vetices), then v must be one (or one of them). Check if v is a mother vertex by doing DFS/BFS from v. This step also takes O(V+E) time.

Sample Code:

import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency list representation
class Graph
{
    private int V; // No. of vertices

    // Array of lists for Adjacency List Representation
    // an array of linked list
    // in this implementation the graph vertex values will be same array index
    private LinkedList<Integer> adj[];

    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    //Function to add an edge into the graph
    void addEdge(int v, int w)
    {
        adj[v].add(w); // Add w to v's list.
    }

    // A function used by DFS
    void DFSUtil(int v,boolean visited[])
    {
        // Mark the current node as visited and print it
        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext())
        {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // The function to do DFS traversal. It uses recursive DFSUtil()
    void DFS()
    {
        // Mark all the vertices as not visited(set as false by default in java)
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
        {
            visited[i] = false;
        }  
     
        // The vertex that finishes last should be the mother node
        int v = -1;
        for (int i = 0; i < V; i++)
        {
            if (visited[i] == false)
            {
                DFSUtil(i, visited);
                v = i;
            }
        }
     
        // the node that finishes last in DFS can be the mother vertex
        for (int i = 0; i < V; i++)
        {
            visited[i] = false;
        }
     
        System.out.println(" Mother Vertex Detected At:"  + v);
     
        // we found the last finishing node
        // need to validate that
        // consider a individual node in the graph. It may not be the last vertex to finish.
        // to we need to confirm that
        DFSUtil(v, visited);
        for(int i = 0; i < V; i++)
        {
            if(visited[i] == false)
            {
                System.out.println("Not a mother vertex.Node that wasn't connected :" + i);      
                return;
            }
        }
        System.out.println(" Mother Vertex: "  + v);
    }

    public static void main(String args[])
    {
        Graph g = new Graph(7);
        // Graph g = new Graph(8);
     
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(4, 1);
        g.addEdge(6, 4);
        g.addEdge(6, 0);
        g.addEdge(5, 2);
        g.addEdge(5, 6);
        // g.addEdge(7, 7);

        // g.printGraph();
        g.DFS();
    }
 
 
    void printGraph()
    {
        for (int j= 0; j < V; ++j)
        {
            System.out.print("j:" + j + " :  ");
            Iterator<Integer> i = adj[j].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                System.out.print( " " + n + " ");
            }
            System.out.println(" ");
        }  
    }
}

Output: 

Mother Vertex Detected At:5
Mother Vertex: 5

How to stop Singleton Pattern from Reflection, Serialization and Cloning?

How to stop Singleton Pattern from Reflection, Serialization and Cloning?

1)Reflection: Reflection can be a caused to destroy singleton property of singleton class.but what is Reflection? in a short answer is: Reflection is an API which is used to examine or modify the behavior of methods, classes, interfaces at runtime.Let see the code.

import java.lang.reflect.Constructor;

class Singleton
{
    public static Singleton instance = new Singleton();
   
    private Singleton()
    {
        // private constructor
    }
}

public class Test
{
    public static void main(String[] args)
    {
        Singleton instance1 = Singleton.instance;
        Singleton instance2 = null;
        try
        {
            Constructor[] constructors = Singleton.class.getDeclaredConstructors();
            for (Constructor constructor : constructors)
            {
                // Below code will destroy the singleton pattern
                constructor.setAccessible(true);
                instance2 = (Singleton) constructor.newInstance();
                break;
            }
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
       
    System.out.println("instance1.hashCode():- "+ instance1.hashCode());
    System.out.println("instance2.hashCode():- "+ instance2.hashCode());
    }
}

Output:

instance1.hashCode():- 366712642
instance2.hashCode():- 1829164700

After running this class, you will see that hashCodes are different that means, 2 objects of same class are created and singleton pattern has been destroyed.

So how to overcome this issue:

 To overcome this issue raised by reflection, enums are used because java ensures internally that enum value is instantiated only once. Since java Enums are globally accessible, they can be used for singletons. Its only drawback is that it is not flexible i.e it does not allow lazy initialization.

public enum Test
{
  INSTANCE;
}

As enums don’t have any constructor so it is not possible for Reflection to utilize it. Enums have their by-default constructor, we can’t invoke them by ourself. JVM handles the creation and invocation of enum constructors internally. As enums don’t give their constructor definition to the program, it is not possible for us to access them by Reflection also. Hence, reflection can’t break singleton property in case of enums.

2)Serialization:

Serialization can also cause breakage of singleton property of singleton classes. Serialization is used to convert an object of byte stream and save in a file or send over a network. Suppose you serialize an object of a singleton class. Then if you de-serialize that object it will create a new instance and hence break the singleton pattern.

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;
import java.io.Serializable;

class Singleton implements Serializable
{
    public static Singleton instance = new Singleton();
   
    private Singleton()
    {
        // private constructor
    }
}

public class Test
{

    public static void main(String[] args)
    {
        try
        {
            Singleton instance1 = Singleton.instance;
            ObjectOutput out= new ObjectOutputStream(new FileOutputStream("file.text"));
            out.writeObject(instance1);
            out.close();
   
            // deserailize from file to object
            ObjectInput in = new ObjectInputStream(new FileInputStream("file.text"));
           
            Singleton instance2 = (Singleton) in.readObject();
            in.close();
   
            System.out.println("instance1 hashCode:- "+ instance1.hashCode());
            System.out.println("instance2 hashCode:- "+ instance2.hashCode());
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
    }
}

Output:

instance1 hashCode:- 1550089733
instance2 hashCode:- 865113938

So how to over this issue .

Overcome serialization issue:- To overcome this issue, we have to implement method readResolve() method.

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;
import java.io.Serializable;

class Singleton implements Serializable
{
    public static Singleton instance = new Singleton();
   
    private Singleton()
    {
        // private constructor
    }
   
    // implement readResolve method
    protected Object readResolve()
    {
        return instance;
    }
}

public class Test
{
    public static void main(String[] args)
    {
        try
        {
            Singleton instance1 = Singleton.instance;
            ObjectOutput out = new ObjectOutputStream(new FileOutputStream("file.text"));
            out.writeObject(instance1);
            out.close();
       
            // deserailize from file to object
            ObjectInput in = new ObjectInputStream(new FileInputStream("file.text"));
            Singleton instance2 = (Singleton) in.readObject();
            in.close();
       
            System.out.println("instance1 hashCode:- "+ instance1.hashCode());
            System.out.println("instance2 hashCode:- "+ instance2.hashCode());
        }
       
        catch (Exception e)
        {
            e.printStackTrace();
        }
    }
}

Output:

instance1 hashCode:- 1550089733
instance2 hashCode:- 1550089733

3)Cloning: 

Cloning is a concept to create duplicate objects. Using clone we can create copy of object. Suppose, we create clone of a singleton object, then it will create a copy that is there are two instances of a singleton class, hence the class is no more singleton.

class SuperClass implements Cloneable
{
  int i = 10;

  @Override
  protected Object clone() throws CloneNotSupportedException
  {
    return super.clone();
  }
}

class Singleton extends SuperClass
{
  public static Singleton instance = new Singleton();

  private Singleton()
  {
    // private constructor
  }
}

public class GFG
{
  public static void main(String[] args) throws CloneNotSupportedException
  {
    Singleton instance1 = Singleton.instance;
    Singleton instance2 = (Singleton) instance1.clone();
    System.out.println("instance1 hashCode:- "+ instance1.hashCode());
    System.out.println("instance2 hashCode:- "+ instance2.hashCode());
  }
}

Output :

instance1 hashCode:- 366712642
instance2 hashCode:- 1829164700

So now as you can see two different hashcodes that means two different objects.How to
overcome this issue.

Overcome Cloning issue:- To overcome this issue, override clone() method and throw an exception from clone method that is CloneNotSupportedException. Now whenever user will try to create clone of singleton object, it will throw exception and hence our class remains singleton.

class SuperClass implements Cloneable
{
  int i = 10;

  @Override
  protected Object clone() throws CloneNotSupportedException
  {
    return super.clone();
  }
}

class Singleton extends SuperClass
{
  public static Singleton instance = new Singleton();
  private Singleton()
  {
    // private constructor
  }

  @Override
  protected Object clone() throws CloneNotSupportedException
  {
    throw new CloneNotSupportedException();
  }
}

public class Test
{
  public static void main(String[] args) throws CloneNotSupportedException
  {
    Singleton instance1 = Singleton.instance;
    Singleton instance2 = (Singleton) instance1.clone();
    System.out.println("instance1 hashCode:- "+ instance1.hashCode());
    System.out.println("instance2 hashCode:- "+ instance2.hashCode());
  }
}

Output:

Exception in thread "main" java.lang.CloneNotSupportedException
at Test.Singleton.clone(Test.java:29)
at Test.Test.main(Test.java:38)

Now we have stopped user to create clone of singleton class. If you don't want to throw exception you can also return the same instance from clone method.

class SuperClass implements Cloneable
{
  int i = 10;

  @Override
  protected Object clone() throws CloneNotSupportedException
  {
    return super.clone();
  }
}

class Singleton extends SuperClass
{
  public static Singleton instance = new Singleton();
  private Singleton()
  {
    // private constructor
  }

  @Override
  protected Object clone() throws CloneNotSupportedException
  {
    return instance;
  }
}

public class GFG
{
  public static void main(String[] args) throws CloneNotSupportedException
  {
    Singleton instance1 = Singleton.instance;
    Singleton instance2 = (Singleton) instance1.clone();
    System.out.println("instance1 hashCode:- "+ instance1.hashCode());
    System.out.println("instance2 hashCode:- "+ instance2.hashCode());
  }
}

Output:

instance1 hashCode: 366712642
instance2 hashCode: 366712642

Now, as hashcode of both the instances is same that means they represent a single instance.

Design Pattern: How to design a parking lot using object-oriented principles?

How to design a parking lot using object-oriented principles?

Solution: 

1) The parking lot has multiple levels. Each level has multiple rows of spots.

2) The parking lot can park motorcycles, cars, and buses.

3) The parking lot has motorcycle spots, compact spots, and large spots.

4) A motorcycle can park in any spot.

5) A car can park in either a single compact spot or a single large spot.

6) A bus can park in five large spots that are consecutive and within the same row. It cannot park in small spots.

In the below implementation, we have created an abstract class Vehicle, from which Car, Bus, and Motorcycle inherit.

To handle the different parking spot sizes, we have just one class ParkingSpot which has a member variable indicating the size.

So Solution would be something like this:

public enum VehicleSize { Motorcycle, Compact,Large }

public abstract class Vehicle
{
      protected ArrayList<ParkingSpot> parkingSpots =  new ArrayList<ParkingSpot>();
      protected String licensePlate;
      protected int spotsNeeded;
      protected VehicleSize size;

      public int getSpotsNeeded()
      {
          return spotsNeeded;
      }
      public VehicleSize getSize()
      {
          return size;
      }

      public void parkinSpot(ParkingSpot s)
      {
          parkingSpots.add(s);
      }


      public void clearSpots() { ... }

      /* Checks if the spot is big enough for the
         vehicle (and is available).
         This * compares the SIZE only.It does not
        check if it has enough spots. */
      public abstract boolean canFitinSpot(ParkingSpot spot);
}

public class Bus extends Vehicle
{
    public Bus()
    {
        spotsNeeded = 5;
        size = VehicleSize.Large;
    }

    public boolean canFitinSpot(ParkingSpot spot)
    {... }
}

public class Car extends Vehicle
{
    public Car()
    {
        spotsNeeded = 1;
        size = VehicleSize.Compact;
    }

    /* Checks if the spot is a Compact or a Large. */
    public boolean canFitinSpot(ParkingSpot spot)
    { ... }
}

public class Motorcycle extends Vehicle
{
    public Motorcycle()
    {
        spotsNeeded = 1;
        size = VehicleSize.Motorcycle;
    }
    public boolean canFitinSpot(ParkingSpot spot)
    { ... }
}


The ParkingSpot is implemented by having just a variable which represents the size of the spot. We could have implemented this by having classes for LargeSpot, CompactSpot, and MotorcycleSpot which inherit from ParkingSpot, but this is probably overkilled. The spots probably do not have different behaviors, other than their sizes.

public class ParkingSpot
{
    private Vehicle vehicle;
    private VehicleSize spotSize;
    private int row;
    private int spotNumber;
    private Level level;

    public ParkingSpot(Level lvl, int r, int n,
                         VehicleSize s)
    { ... }

    public boolean isAvailable()
    {
        return vehicle == null;
    }

    /* Check if the spot is big enough and is available */
    public boolean canFitVehicle(Vehicle vehicle) { ... }

    /* Park vehicle in this spot. */
    public boolean park(Vehicle v) {..}

    public int getRow()
    {
        return row;
    }
    public int getSpotNumber()
    {
        return spotNumber;
    }

    /* Remove vehicle from spot, and notify
      level that a new spot is available */
    public void removeVehicle() { ... }
}

Leaders in an array Java Solution

 An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

Sample Code:

/**
 *
 */
/**
 * @author Abhinaw.Tripathi
 *
 */
public class LeadersInArray
{

public void printLeaders(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
        {
            int j;
            for (j = i + 1; j < size; j++)
            {
                if (arr[i] <= arr[j])
                    break;
            }
            if (j == size)
                System.out.print(arr[i] + " ");
        }
}

public void printLeadersMoreOptimized(int arr[], int size)
     {
       int max_from_right =  arr[size-1];
       System.out.print(max_from_right + " ");
   
       for (int i = size-2; i >= 0; i--)
       {
           if (max_from_right < arr[i])
           {          
             max_from_right = arr[i];
             System.out.print(max_from_right + " ");
           }
       }  
     }

public static void main(String[] args)
{
   LeadersInArray lead = new LeadersInArray();
       int arr[] = new int[]{16, 17, 4, 3, 5, 2};
       int n = arr.length;
       lead.printLeaders(arr, n);
     
     /*  LeadersInArray lead = new LeadersInArray();
       int arr[] = new int[]{16, 17, 4, 3, 5, 2};
       int n = arr.length;
       lead.printLeadersMoreOptimized(arr, n);*/
}
}

Output: 17 5 2

Time Complexity: O(n*n)

but if you use my 2nd method then time complexity will be reduced  to O(n).

Exponential Search Algorithm and its implementation in java

Exponential Search

It works in O(Log n) time.We have discussed, linear search, binary search for this problem.

Exponential search involves two steps:

1)Find range where element is present

2)Do Binary Search in above found range.

How to find the range where element may be present?

The idea is to start with subarray size 1 compare its last element with x, then try size 2, then 4 and so on until last element of a subarray is not greater.

Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i (Why i/2? because we could not find a greater value in previous iteration).

Sample Code:

import java.util.Arrays;

class ExponentialSearchApp
{

static int exponentialSearch(int arr[], int n, int x)
{

if (arr[0] == x)
return 0;

int i = 1;
while (i < n && arr[i] <= x)
i = i*2;

return Arrays.binarySearch(arr, i/2, Math.min(i, n), x);
}

public static void main(String args[])
{
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr, arr.length, x);

System.out.println((result < 0) ? "Element is not present in array" :
"Element is present at index " + result);
}
}

Output: Element is present at index 3.

Time Complexity : O(Log n)

Auxiliary Space : The above implementation of Binary Search is recursive and requires O()Log n) space.
Iterative Binary Search, we need only O(1) space.

Applications of Exponential Search:

Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite.

Please google search about Unbounded Binary Search.

It works better than Binary Search for bounded arrays also when the element to be searched is closer to the first element.

Interpolation Search Algo and its implemenation in java

Interpolation Search

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to middle element to check. On the other hand interpolation search may go to different locations according the value of key being searched.

For example if the value of key is closer to the last element, interpolation search is likely to start search toward the end side.

Linear Search finds the element in O(n) time,

Jump Search takes O(√ n) time and Binary Search take O(Log n) time.

The whole formula is:

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

where lo,x and hi is an int value.

Step1: In a loop, calculate the value of “pos” using the probe position formula.
Step2: If it is a match, return the index of the item, and exit.
Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right subarray.
Step4: Repeat until a match is found or the sub-array reduces to zero.

Sample Code:

class InterpolationApp
{
static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,24, 33, 35, 42, 47};

static int interpolationSearch(int x)
{
int lo = 0, hi = (arr.length - 1);

while (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
int pos = lo + (((hi-lo) /
(arr[hi]-arr[lo]))*(x - arr[lo]));

if (arr[pos] == x)
return pos;

// If x is larger, x is in upper part
if (arr[pos] < x)
lo = pos + 1;

// If x is smaller, x is in lower part
else
hi = pos - 1;
}
return -1;
}

public static void main(String[] args)
{
int x = 18;
int index = interpolationSearch(x);

if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}

}

Output: Element found at index 4.

Time Complexity : 

If elements are uniformly distributed, then O (log log n)).
In worst case it can take up to O(n).


Auxiliary Space : O(1)

Jump Search Algorithm and Implementation in java

Jump Search

A jump search or block search refers to a search algorithm for ordered lists.Like Binary Search, Jump Search is a searching algorithm for sorted arrays.It works by first checking all items and m is the block size, until an item is found that is larger than the search key. To find the exact position of the search key in the list a linear search is performed on the sublist L[(k-1)m, km].

 So,the basic idea is to check fewer elements by jumping ahead by fixed steps or skipping some elements in place of searching all elements.


 Algorithm JumpSearch

  Input: An ordered list L, its length n and a search key s.
  Output: The position of s in L, or nothing if s is not in L.

  a ← 0
  b ← ⌊√n⌋

  while Lmin(b,n)-1 < s do
    a ← b
    b ← b + ⌊√n⌋
    if a ≥ n then
      return nothing

  while La < s do
    a ← a + 1
    if a = min(b,n)
      return nothing

  if La = s then
    return a
  else
    return nothing


For example, 

suppose we have an array arr[] of size n and block (to be jumped) size m. Then we search at the indexes arr[0], arr[m], arr[2m]…..arr[km] and so on. Once we find the interval (arr[km] < x < arr[(k+1)m]), we perform a linear search operation from the index km to find the element x.

Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). Length of the array is 16. Jump search will find the value of 55 with the following steps assuming that the block size to be jumped is 4.
STEP 1: Jump from index 0 to index 4;
STEP 2: Jump from index 4 to index 8;
STEP 3: Jump from index 8 to index 16;
STEP 4: Since the element at index 16 is greater than 55 we will jump back a step to come to index 9.
STEP 5: Perform linear search from index 9 to get the element 55.

What is the optimal block size to be skipped?

In the worst case, we have to do n/m jumps and if the last checked value is greater than the element to be searched for, we perform m-1 comparisons more for linear search. Therefore the total number of comparisons in the worst case will be ((n/m) + m-1). The value of the function ((n/m) + m-1) will be minimum when m = √n. Therefore, the best step size is m = √n.

Sample Code:

public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;

// Finding block size to be jumped
int step = (int)Math.floor(Math.sqrt(n));

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;

// If we reached next block or end of
// array, element is not present.
if (prev == Math.min(step, n))
return -1;
}

// If element is found
if (arr[prev] == x)
return prev;

return -1;
}

public static void main(String [ ] args)
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,34, 55, 89, 144, 233, 377, 610};
int x = 55;

// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x);

// Print the index where 'x' is located
System.out.println("\nNumber " + x +" is at index " + index);
}
}

Time Complexity : O(√n)
Auxiliary Space : O(1)

Important points:

1)Works only sorted arrays.

The optimal size of a block to be jumped is O(√ n). This makes the time complexity of Jump Search O(√ n).

The time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) ).

Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be search is the smallest element or smaller than the smallest). So in a systems where jumping back is costly, we use Jump Search.