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;

    }

}