Destination: Together : Booking.com backend code sprint

Problem : 

John and Zizi are planning their respective autumn vacations. John has exactly  cities he plans to visit, Zizi has exactly  cities she plans to visit, and they want to have exactly  destination cities in common. Having been a couple for over two years without ever vacationing together, they used  to find a romantic final destination that appeals to both of their passions: marvellous L'viv in the Ukraine.

John and Zizi are software engineers who love creating and solving interesting problems. They want to know the number of different sequences in which they can visit their respective vacation destinations such that they visit each city exactly once and both meet up in L'viv as their final destination. Given , , and , find and print the number of different ways they can do this.

Sample Input:

3 4 2

Sample Output:

24

Solution : 

Number of different ways is simply equal to factorial(total unique cities -1

Implementation: 

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        //Read input
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int m= sc.nextInt();
        int c= sc.nextInt();
        //check constraints
        if(n>0&&n<11&&m>0&&m<11){
            
            if(c<=n && c<=m){
                int uniqueCities= n-c+m-c+c; // total unique cities planned to visit

            // now number of ways to visit these cities is uniqueCities-1! 
            long ways=1;
            for(int i=1;i<uniqueCities;i++){
                ways*=i;

            }
            //print result
            System.out.println(ways); 
            }// end inner if
        }// end outer if
       
    }
}

Making Polygons

Problem : You have  sticks with positive integer lengths, . You want to create a polygon using all  sticks. Because this is not always possible, you can cut one or more sticks into two smaller sticks (they do not necessarily need to be of integer length) and repeat the process of trying to create a polygon using all the sticks. Given the lengths of all  sticks, find and print the minimum number of cuts necessary to make a non-degenerate polygon.

Solution : 

For a polygon to be non degenerate polygon,each side of the polygon must satisfy this condition sum=a1$1$ +a2$2$+........+ann and ai$i$<1/2(sum) wher 1<=i<=n .
Every time above condition is violated , we increase the counter which is nothing but the minimum number of cuts


IMPLEMENTATION: 

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a[] = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        int x= 0;
        int sum=0;
        int count=0;
        //sum=0;
            for(int k:a){
              //  if(k==x)continue;
                sum+=k;
            }
        for(int i=0;i<n;i++){
            x=a[i];
            
            if(x>=sum/2) count++;
            
        }
        
        System.out.println(count);
    }

}

Anagrams : Check if two input strings are anagrams of each other

Anagrams are those pair of Strings which have the same set of characters , in any order

For Example :

Mad, Dam
Madam Curie = Radium came
Dog, God


Anagram: Wiki


Problem : Given two input strings s1, s2 , check wether they are anagrams of each other

Solution 

• Create two  int arrays of size 256 , each holding count of the ascii characters present in s1 and s2 respectively
• [ You will need to convert each letter to lower case before adding count]
• Compare count arrays

Implementation : 

public static Boolean  isAnagram(String s1, String s2){

              int count1[] = new int[256];

              int count2[]= new int[256];

              Boolean flag= true;

              for(int i=0;i<s1.length();i++){

                   Character c= s1.charAt(i);

                   count1[Character.toLowerCase(c)]++;

             }

             for(int i=0;i<s2.length();i++){

                   Character c= s2.charAt(i);

                   count2[Character.toLowerCase(c)]++;

             }

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

                   if(count1[i]!=count2[i]) flag=false;

             }

      return flag;

}

Reverse a singly linked list : Recursively

Following approach can be followed to reverse a singly linked list recursively



Approach : 

1.Divide the list in two parts : first and rest.
2.Recursively call the reverse method with rest.
3.link rest-->first
4.fix the last node

Implementation: 


public node reverse(Node head){

if( head==null) return;

Node first= head;
Node rest= first.next;

if(rest== null) return;

reverse(rest); //recursively call reverse for the rest .

first.next.next= first;// next now points to current

first.next = null; //fix the last node

head= rest;

return head;

}

Complexity :

Time: O(n)
Space: O(1)

Reverse a Single linked list : Iterative method

Following is a simple iterative Method for reversing a singly linked list


public node reverse(Node head){


if(head==null) return;

Node current= head;
Node prev= null;
Node next= null;


while(current!=null){

next= current.next;

current.next= prev;

prev= current;

current= next;
}


head= prev;

return head;

}