Loop in a Singly Linked List

Overview : 

A Linked List is considered to have a loop or a cycle , if a node is visited more than once while traversing the list.

Problem :

Given a singly linked list , detect wether it has a loop or not . Note that the head pointer may be 'null' if the list is empty.
( Problem Source : Cracking the coding interview : HackerRank)



Solution :

The solution is based on floyd's cycle finding algorithm , also referred to as the 'Tortoise and Hare' algorithm. It uses two pointers , which move at different speeds.  Let us call them as slow and fast pointers.  Now the fast pointer can move at any speed which should be greater than slow pointer's speed. Simple mathematics* suggests that if we move the fast pointer with speed twice that of slow , and if they meet , the linked list has a cycle .

*Why fast = slow * 2 ?

Below is the java code for the logic .

Array Rotation : Block Swap Algorithm

Problem Statement : 
Rotate a given array of integers by K units .

Example : 

Consider following input array :

A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}

For a given K=3, the rotated array would look like :

{ 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,1, 2, 3,}

Solution : 
There are a couple of solutions.

1. Take an auxiliary array of size k, copy first k elements into the aux array, shift each element in input array by k units and finally copy aux at last into input array .

2. Block Swap algorithm : This algorithm does'nt require any aux array(extra space) .


Step 1. Divide the array into two parts :
A[0..k-1] A[k...L-1] where L is length
Step 2. Rotate A[0...k-1] keeping the remaining array same.
Step 3 . Rotate A[k....L-1] keeping first part same.
Step 4. Rotate A.


Implementation : 

Here is a simple use case implementation :

package com.grv;

public class ArrayRotation {


    public static void main(String args[]) {


        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

        int k = 3;
        int l = arr.length;

        arr = swapBlock(arr, 0, k - 1);
        arr = swapBlock(arr, k, l - 1);
        arr = swapBlock(arr, 0, l - 1);


        // print rotated array

        System.out.println("***************************************");
        System.out.println("rotated array is by block swap algo");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");

    }


    public static int[] swapBlock(int[] a, int start, int end) {


        int i = start;
        int j = end;
        int temp;

        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            i++;
            j--;

        }


        return a;

    }

}

Test Output: 

*******************************************************
rotated array is by block swap algo
4 5 6 7 8 9 10 11 12 13 14 1 2 3 
Process finished with exit code 0

Left View of a Binary Tree

Problem : Given a Binary Tree, print the left view .

Example :

Consider the following Binary Tree :

Left View of above tree : 1, 2, 4

Explanation : The left view of a given tree is nothing but the nodes that one would see when viewing the tree from the left side . For the given binary tree, the Left View shall be 1, 2, 4

Solution : 

There are multiple approach to solve above problem. But the basic idea is level order traversal . 

We will try to identify first node at each level and print it before moving to the next level. Trick is to identify the first element of each level. For this , we add an empty node at the end of each level. 

Implementation :

Following is the core Java implementation of approach :

public static void printLeftView(BinaryTreeNode root) {


    if (root == null) return;

    Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();

    BinaryTreeNode flag = new BinaryTreeNode();        q.add(root);
    q.add(flag);        boolean levelover = false;
    System.out.println(root.data);
    BinaryTreeNode temp;

    //LEVEL ORDER TRAVERSAL
    while (!q.isEmpty()) {


        temp = q.remove();

        if (!temp.equals(flag) && levelover == true) {


            System.out.println(temp.data);
            levelover = false;
        }


        if (temp.equals(flag)) {


            levelover = true;
            if (!q.isEmpty()) q.add(flag);
        }


        if (temp.left != null) q.add(temp.left);
        if (temp.right != null) q.add(temp.right);

    }

}

Height of a Binary tree : Recursive and Iterative Approach

Problem : Given a Binary Tree , find the height of the tree. 

 Example:

Height of above Tree = 3

Explanation:

 Height of a binary tree is  the number of nodes along the longest path from the root node down to the farthest leaf node. The Height of the empty tree is 0, the Height of the tree in the above example is 3

Solution : 

There can be two approach to solve this problem : 

1. Recursive : using recursive calls to find heights of left and right subtress 

2. Iterative : using level order traversal 

Let us have a look at both the approaches one by one : 

A. Recursive Solution :  

   1. if the root ==null , return 0

Else : perform 2 -->4

   2. find height of left subtree , say LH 

   3. find height of right subtree , say RH

   4. if LH >RH, return LH +1 , else return RH+1

B. Iterative Solution :

 Do a level order traversal, increment height at each level. Return height at the end.

Implementation : 

Following are the java implementations for both solutions 

A. RECURSIVE :

 int height(Node root){

        

         if(root==null) return 0;

       

       else{

            int lh= height(root.left);

            int rh= height(root.right);

       

       if(lh>rh) return lh+1;

       else return rh+1;

       }

          

    }

B. ITERATIVE :

 int height(Node root)

    {

         if(root==null) return 0;

       Node node=root;

       int height=0;

       Queue<Node> q= new LinkedList<Node>();

       q.add(node);

       

       while(true){

            // nodeCount (queue size) indicates number of nodes

            // at current lelvel.

            int nodeCount = q.size();

            if (nodeCount == 0) {

                return height;

            }

            height++;

            // Dequeue all nodes of current level and Enqueue all

            // nodes of next level

            while (nodeCount > 0) {

                Node newnode = q.peek();

                q.remove();

                if (newnode.left != null) {

                    q.add(newnode.left);

                }

                if (newnode.right != null) {

                    q.add(newnode.right);

                }

                nodeCount--;

            }

        }

           

           

           

       }

    

________________________________________________________________________________

REFERENCES : 

http://cslibrary.stanford.edu/110/BinaryTrees.html

https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree

Least Common Ancestor : Binary Tree

Lowest Common Ancestor:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor (Djidjev, Pantziou & Zaroliagis 1991). In ontologies, the lowest common ancestor is also known as the least common subsumer.

In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from vand w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity.

[SOURCE: https://en.wikipedia.org/wiki/Lowest_common_ancestor]

Problem :

Given a binary tree and two values d1& d2, find the least common ancestor of the two values in the input tree.


Example:
  Consider the following image :

Solution :
We follow a recursive approach where in we recurse through the right and left children of the parameter node .

Return value is root itself if output of each recursion is null , else the we return the value is which in non-null among the two recursive output.

Base and Edge cases are as shown in the code.

Implementation:

Binary Tree Node :

public class BinaryTreeNode {

    private int data;    private BinaryTreeNode left;    private BinaryTreeNode right;
    public int getData() {
        return data;    }

    public void setData(int data) {
        this.data = data;    }

    public BinaryTreeNode getLeft() {
        return left;    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;    }

    public BinaryTreeNode getRight() {
        return right;    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;    }
}

LCA class : 

public class LCA {


    public BinaryTreeNode getLCA(BinaryTreeNode root, int data1, int data2){

    //Base case
        if (root == null){
            return  null;        }

    //edge case
        if (root.getData()==data1 || root.getData() == data2) {
            return root;        }


    BinaryTreeNode leftLCA = getLCA(root.getLeft(), data1, data2);            BinaryTreeNode rightLCA = getLCA(root.getRight(), data1, data2);

    if (leftLCA != null && rightLCA != null){
        return root;    }

    if (leftLCA == null) {
        return rightLCA;    }

    else {
        return leftLCA;    }


    }
}

Graph Theory : Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key) and explores the neighbour nodes first, before moving to the next level neighbour.

BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. Y. Lee as a wire routing algorithm (published 1961).

[Source :https://en.wikipedia.org/wiki/Breadth-first_search ]

BFS of above tree would give : 1 -->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12

Solution : 

In order to implement BFS , we use a queue data structure (Similar to level order traversal of a tree). We also maintain a boolean array to mark all the visited nodes with value='true'

We start with root , and add it to queue. 

Now we iterate through the queue as follows , until the queue is empty and do following :

• fetch a node from q,
• print it
• fetch all its adjacent nodes, mark them visited and add them in queue

Implementation :

// 1. Graph Class : 

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

class Graph {

private int v; // no of vertices in the graph
List<Integer> adj[]; // adjacency list

public Graph(int v) {

this.v = v;
adj = new ArrayList[v];

for (int i = 0; i < v; i++)
adj[i] = new ArrayList<Integer>();
}

public int getV() {
return v;
}

public void setV(int v) {
this.v = v;
}

public List<Integer>[] getAdj() {
return adj;
}

public void setAdj(List<Integer>[] adj) {
this.adj = adj;
}

public void addEdge(int v, int w) {
this.adj[v].add(w);
}

}

// 2. BFS CLASS 

class BFS {



public void printBFS(int v, Graph g) {

// mark all vertices as non visited

boolean visited[] = new boolean[g.getV()];
LinkedList<Integer> q= new LinkedList<Integer>();


visited[v]=true;
q.add(v);



while (!q.isEmpty()) {

v = q.poll();
System.out.print(v+"==>");

Iterator<Integer> it = g.adj[v].iterator();
while(it.hasNext()){
int n = it.next();
               if (!visited[n])
               {
                   visited[n] = true;
                   q.add(n);
               }


}
}


}


}


//TESTER CLASS : 

public class GraphTester {

    public static void main(String args[]){

        Graph g=new Graph(4);
        g.addEdge(0,1);
        g.addEdge(0, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(1, 2);
        g.addEdge(3, 3);



        BFS bfs= new BFS();
        System.out.println("BREADTH FIRST SEARCH TRAVERSAL OF INPUT GRAPH ");

        bfs.printBFS(2, g);
}

}


****************************************************************************

OUTPUT :

BREADTH FIRST SEARCH TRAVERSAL OF INPUT GRAPH 

2==>0==>3==>1==>

Coupling Passions : Booking.com backend code Sprint

Problem:

Mariana and Pedro are a young couple that loves to travel. Pedro is passionate about surfing, while Mariana is a wine lover. Like many couples, Mariana and Pedro always plan their trips together, choosing only those destinations that best satisfy their passions!

Since Booking.com launched the Destination Finder, Mariana and Pedro started using it to look for new places all over the world where they can travel and enjoy as many of their collective passions as possible. Can you help groups of guests like Mariana and Pedro find some hidden gems?

For this challenge, we'll provide you with the following:

• A list of guests and, for each guest, a list of their respective passions.
• A list of destinations and, for each destination, a list of passions that the destination is known to be good for.

Given the data above, find the two destinations satisfying the maximum number of the group's collective passions and print them as two space-separated strings on a single line. If more than one destination satisfies a maximum number of passions, then choose the pair of such destinations having the shortest distance between them. Use theLaw of Cosines for Spherical Trigonometry to calculate distances, as demonstrated by the following pseudocode:

function distance_between(point1, point2) {
    var EARTH_RADIUS = 6371;//in km
    var point1_lat_in_radians  = degree2radians( point1.latitude );
    var point2_lat_in_radians  = degree2radians( point2.latitude );
    var point1_long_in_radians  = degree2radians( point1.longitude );
    var point2_long_in_radians  = degree2radians( point2.longitude );

    return acos( sin( point1_lat_in_radians ) * sin( point2_lat_in_radians ) +
                 cos( point1_lat_in_radians ) * cos( point2_lat_in_radians ) *
                 cos( point2_long_in_radians - point1_long_in_radians) ) * EARTH_RADIUS;
}

Input Format

The first line contains a single integer, , denoting the number of guests traveling together. 
Each line  of the  subsequent lines lists guest 's passions as a sequence of space-separated values:

• The first value is an integer, , denoting the number of passions that the guest has.
• Each of the  subsequent space-separated strings describes one of the guest's passions.

The next line contains a single integer, , denoting the number of potential destinations. 
Each line  of the  subsequent lines describes destination  as a single line of space-separated values:

• The first value is a string denoting the destination name.
• The second value is a floating-point number denoting the destination's latitude.
• The third value is a floating-point number denoting the destination's longitude.
• The fourth value is an integer, , denoting the number of passions available at the destination.
• Each of the  subsequent space-separated strings describes a passion available at the destination.

Constraints

• Assume the value of pi is 

Output Format

Print a single line with  space-separated destination names that cover the largest number of passions held by the group. These destinations must be ordered alphabetically; if two or more pairs of destinations cover the same number of passions, choose the pair having the shortest distance between cities.

Sample Input

2
3 surfing yoga walking
3 wine relaxation beach
3
amsterdam 52.374030 4.889690 4 museums canals nightlife walking
sagres 37.129665 -8.669586 3 beach surfing relaxation
biarritz 43.480120 -1.555580 6 surfing nightlife beach food wine walking

Sample Output

biarritz sagres

Explanation

There are two guests having the following passions:

1. Guest : surfing, yoga, and walking.
2. Guest : wine, relaxation, and beach.

There are three possible vacation destinations (passions appealing to the above guests are highlighted for emphasis):

1. amsterdam: museums, canals, nightlife, and walking.
2. sagres: beach, surfing, and relaxation.
3. biarritz: surfing, nightlife, beach, food, wine, and walking.

There are three possible vacations:

1. amsterdam and sagres: This trip satisfies  distinct guest passions (i.e., surfing, beach, relaxation, and walking).
2. amsterdam and biarritz: This trip satisfies  distinct guest passions (i.e., walking, surfing, beach, wine).
3. sagres and biarritz: This trip satisfies  distinct guest passions (i.e., beach, surfing, relaxation, wine, walking).

Because the sagres-biarritz vacation satisfies the maximum number of passions, we print biarritz and sagres as two alphabetically-ordered space-separated values on a new line.

Solution

I am providing the solution implementation  for now . Explanation  shall be added later. 

Implementation

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

private static double [][] coordinates;

    private static ArrayList<ArrayList<Integer>> listOfPassions = new ArrayList<ArrayList<Integer>>();

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int a=Integer.parseInt(br.readLine());

        ArrayList<String> guests = new  ArrayList<>();

        for(int i=0;i<a;i++){

            String str1 = br.readLine();

            String[] str = str1.split(" ");

            int b = Integer.parseInt(str[0]);

            for(int j=0;j<b;j++){

                guests.add(str[j+1]);

            }

        }

        a=Integer.parseInt(br.readLine());

        String [] cities = new String[a];

        coordinates = new double[a][2];

        for(int i=0;i<a;i++){

            String str1 = br.readLine();

            String[] str = str1.split(" ");

            cities[i]=str[0];

            coordinates[i][0]=Double.parseDouble(str[1]);

            coordinates[i][1]=Double.parseDouble(str[2]);

            int b = Integer.parseInt(str[3]);

            ArrayList<Integer> passions = new  ArrayList<>();

            for(int j=0;j<b;j++){

                if(guests.contains(str[j+4])){

                    passions.add(guests.indexOf(str[j+4]));

                }

            }

            listOfPassions.add(passions);

        }

        int d1=0;

        int d2=1;

        double min= getDistance(d1,d2);

        int maxPassions = totalNoOfPassions(d1,d2);

        for(int i=0;i<a;i++){

            for(int j=i+1;j<a;j++){

                double distance = getDistance(i,j);

                int noOfTotalPassion = totalNoOfPassions(i,j);

                if(noOfTotalPassion > maxPassions){

                    maxPassions=noOfTotalPassion;

                    min=distance;

                    d1=i;

                    d2=j;

                }else if(noOfTotalPassion == maxPassions){

                    if(min>distance){

                        min=distance;

                        d1=i;

                        d2=j;

                    }

                }

            }

        }

        int bigString = cities[d1].compareToIgnoreCase(cities[d2]);

        if(bigString>0){

            System.out.print(cities[d2]+" "+cities[d1]);

        }else{

            System.out.print(cities[d1]+" "+cities[d2]);

        }

    }

    private static double getDistance(int city1, int city2){

        int EARTH_RADIUS = 6371;

        double point1_lat_in_radians  = degree2radians( coordinates[city1][0] );

        double point2_lat_in_radians  = degree2radians( coordinates[city2][0] );

        double point1_long_in_radians  = degree2radians( coordinates[city1][1] );

        double point2_long_in_radians  = degree2radians( coordinates[city2][1] );

        return Math.acos( Math.sin( point1_lat_in_radians ) * Math.sin( point2_lat_in_radians ) +

                Math.cos( point1_lat_in_radians ) * Math.cos( point2_lat_in_radians ) * Math.cos( point2_long_in_radians - point1_long_in_radians) ) * EARTH_RADIUS;

    }

    private static double degree2radians(double value){

        return value*(0.01745329252);

    }

    private static int totalNoOfPassions(int city1, int city2){

        ArrayList<Integer> passions1 = listOfPassions.get(city1);

        ArrayList<Integer> passions2 = listOfPassions.get(city2);

        int count = 0;

        if(passions1.size()>passions2.size()){

            for (Integer aPassions2 : passions2) {

                if (passions1.contains(aPassions2)) {

                    count++;

                }

            }

        }else{

            for (Integer aPassions1 : passions1) {

                if (passions2.contains(aPassions1)) {

                    count++;

                }

            }

        }

        return passions1.size()+ passions2.size() - count;

    }

}