Search This Blog

Friday, December 6, 2013

Algorithm - Search - Find the Median

Find the Median

The following is the solution to Hacker Rank problem Find the Median using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

Score: 10/10
/**
 *
 */


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

/**
 * @author Arun.G
 *
 */
public class Solution{

       /**
        * @param args
        */

       public static void main(String[] args) {
              /*
               * Enter your code here. Read input from STDIN. Print output to STDOUT.
               * Your class should be named Solution.
               */
              Scanner sc = new Scanner(System.in);
              int n = sc.nextInt();
              int[] ar = new int[n];
              for (int i = 0; i < n; i++) {
                     ar[i] = sc.nextInt();
              }
              Arrays.sort(ar);

              int median = ar[ar.length / 2];
              System.out.println(median);

              sc.close();
       }

}       

Monday, November 25, 2013

Algorithm - Linked Lists - Insert a node at the tail of a linked list

Insert a node at the tail of a linked list

The following is the solution to Hacker Rank problem Insert a node at the tail of a linked list using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

Score: 5/5
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct Node
{
                int data;
                Node *next;
};/*
  Insert Node at the end of a linked list
  head pointer input could be NULL as well for empty list
  Node is defined as
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* Insert(Node *head,int data)
{
  // Complete this method
    Node *headPtr = new Node();
    headPtr = head;
    if(head!=NULL)
    {
        while(head->next!=NULL)
        {
            head = head->next;
        }
        Node *tail = new Node();
         tail->data = data;
        tail->next = NULL;
        head->next = tail;               
    }
    else
    {
        Node *tail = new Node();
         tail->data = data;
        tail->next = NULL;
        headPtr = tail;
    }
       
   
    return headPtr;
}void Print(Node *head)
{
                Node *temp = head;
                while(temp!= NULL){ cout<<temp->data<<"\n";temp = temp->next;}
}
int main()
{
                int t;
                cin>>t;
                Node *head = NULL;
                while(t-- >0)
                {
                                int x; cin>>x;
                                head = Insert(head,x);
                }
                Print(head);
}

Algorithm - Linked Lists- Insert a node at the head of a linked list

Insert a node at the head of a linked list

The following is the solution to Hacker Rank problem  Insert a node at the head of a linked list using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.
Score: 5/5
#include <iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

struct Node
{
                int data;
                Node *next;
};/*
  Insert Node at the begining of a linked list
  Initially head pointer argument could be NULL for empty list
  Node is defined as
  struct Node
  {
     int data;
     struct Node *next;
  }
return back the pointer to the head of the linked list in the below method.
*/
Node* Insert(Node *head,int data)
{
     Node *newHead = new Node();
  // Complete this method
    if(head!= NULL)
    {     
        newHead->data = data;
        newHead->next = head;
    }
    else
    {     
        newHead->data = data;
        newHead->next = NULL;
    }
    return newHead;
}void Print(Node *head)
{
                Node *temp = head;
                while(temp!= NULL){ cout<<temp->data<<"\n";temp = temp->next;}
}
int main()
{
                int t;
                cin>>t;
                Node *head = NULL;
                while(t-- >0)
                {
                                int x; cin>>x;
                                head = Insert(head,x);
                }
                Print(head);
}

Algorithm - Linked Lists- Print the elements of a linked list

Print the elements of a linked list
The following is the solution to Hacker Rank problem Print the elements of a linked list using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

Score: 5/5
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

struct Node
{
                int data;
                Node *next;
};/*
  Print elements of a linked list on console
  head pointer input could be NULL as well for empty list
  Node is defined as
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
void Print(Node *head)
{
  // This is a "method-only" submission.
  // You only need to complete this method.
     if(head != NULL)
     {
         std::cout<<head->data<<"\n";
   if(head->next != NULL)
        Print(head->next);
     }
   
}Node* Insert(Node *head,int x)
{
   Node *temp = new Node();
   temp->data = x;
   temp->next = NULL;
   if(head == NULL)
   {
       return temp;
   }
   Node *temp1;
   for(temp1 = head;temp1->next!=NULL;temp1= temp1->next);
   temp1->next = temp;return head;
}
int main()
{
                int t;
                cin>>t;
                while(t-- >0)
                {
              
                                int x; cin>>x;
                                 Node *head = NULL;
                while(x--)
                {
                                                                                 
                    int y;cin>>y;
                                           head = Insert(head,y);
                }
                Print(head);
                                                free(head);
                }

}

Saturday, November 23, 2013

Hacker Rank Problem - Algorithm - Search- Encryption

Encryption 
The following is the solution to Hacker Rank problem Encryption using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

Score:25/25
/**
 *
 */
package hackerRank;

import java.util.Scanner;

/**
 * @author Arun.G
 *
 */
public class Encryption {

       /**
        * @param args
        */
       public static void main(String[] args) {
              // TODO Auto-generated method stub

              Scanner sc = new Scanner(System.in);
              String word = sc.nextLine();
             
              // Remove all white space characters
              word = word.replaceAll("\\s+", "");
             
              //compute the width and height
              int width = (int) Math.ceil(Math.sqrt(word.length()));
              int height = (int) Math.floor(Math.sqrt(word.length()));
             
              int newHeight = 0, newWidth = 0;
              //some times we can fit in the the word with given width find and increase the height
              if (word.length() / height >= width)
                     height += 1;

              String result = "";

              char[][] secret = null;
              //find the correction width and height or not equal
              int correction = Math.abs(width - height);
               // if height is greater, correct the width and make it equal to height
              if (height > width)
              {
                     secret = new char[height][width + correction];
                     newWidth = width + correction;
                     newHeight = height;
              }
              //if width is greater, correct the height and make it equal to width
              else if (width > height)
              {

                     secret = new char[height + correction][width];
                     newHeight = height + correction;
                     newWidth = width;
              }
              //else height and width are equal
              else
              {
                     secret = new char[height][width];
                     newHeight = height;
                     newWidth = width;

              } 
              int index = 0;
              //write down the message in the row major order in array
              for (int i = 0; i < height; i++) {
                     for (int j = 0; j < width; j++) {
                           if (index + 1 <= word.length()) {
                                  secret[i][j] = word.charAt(index);
                                  index++;
                           }
                     }
              }
              //get the message from the array in column major order
              for (int i = 0; i < newHeight; i++) {
                     for (int j = 0; j < newWidth; j++) {
                           //if the character is not null add it to result
                           if ((secret[j][i] != '\0'))
                                  result += Character.toString(secret[j][i]);
                     }
                     result += " ";
              }

              System.out.println(result);
              sc.close();
       }

}

Hacker Rank Problem - Algorithm - Search- Flower

Flower
The following is the solution to Hacker Rank problem Flowers using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

Score: 24/24
/**
 *
 */
package hackerRank;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * @author Arun.G
 *
 */
public class Flowers {

       /**
        * @param args
        */
       public static void main(String[] args) {
              // TODO Auto-generated method stub

              // helpers for input/output
              Scanner in = new Scanner(System.in);

              int N, K;
              N = in.nextInt();
              K = in.nextInt();

              Integer C[] = new Integer[N];
              int bought[] = new int[K];
              for (int i = 0; i < N; i++) {
                     C[i] = in.nextInt();
              }

              int result = 0;
              //sort the array in descending order
              Arrays.sort(C, new Comparator<Integer>() {
                     @Override
                     public int compare(Integer x, Integer y) {
                           return y - x;
                     }
              });
              int index = 0;
              for (int i = 0; i < C.length; i++) {
                     // reset if crossed boundry
                     if (index >= bought.length)
                     {
                           index = 0;
                     }
                     result += ((bought[index] + 1) * C[i]);
                     bought[index] += 1;
                     index++;

              }
             
              System.out.println(result);
              in.close();
       }

}

Saturday, November 9, 2013

Hacker Rank Problem - Algorithm - Regex - IP Address Validation

IP Address Validation
The following is the solution to Hacker Rank problem IP Address Validation using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

Score: 10/10
/**
 *
 */
package hackerRank;

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author Arun.G
 *
 */
public class IPAddressValidation {

       /**
        * @param args
        */
       public static void main(String[] args) {
              // TODO Auto-generated method stub
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        //Regex expression for Ipv4
        String ip4Regex="^(25[0-5]|2[0-4][0-9]|1[0-9][0-9]|[0-9]{1,2})(\\.(25[0-5]|2[0-4][0-9]|1[0-9][0-9]|[0-9]{1,2})){3}$";
        Pattern ip4Pattern = Pattern.compile(ip4Regex);
        //Regex expression for Ipv6
        String ip6Regex="^([0-9A-Fa-f]{1,4}:){7}[0-9A-Fa-f]{1,4}$";
        Pattern ip6Pattern = Pattern.compile(ip6Regex);
           
        Matcher matcher;
        for(int i=0;i<=n;i++)
        {
            String line = sc.nextLine();
            if(!line.equals(""))
            {
                matcher = ip4Pattern.matcher(line);
                //check if it is a Ipv4 Address
                if(matcher.matches())
                    System.out.println("IPv4");
                else
                {
                    matcher = ip6Pattern.matcher(line);
                    //check if it is Ipv6 Address
                    if(matcher.matches())
                        System.out.println("IPv6");
                    else //else it is neither
                        System.out.println("Neither");
                }
            }
        }
        //close the scanner
        sc.close();
       }

}



Labels