Learn Competitive Programming in Java



Java is a high-level programming language originally developed by Sun Microsystems and released in 1995. Java runs on a variety of platforms, such as Windows, Mac OS, and the various versions of UNIX. This reference will take you through simple and practical approaches while solving Java Competitive problems asked in various companies.

Prerequisites : You should have knowledge of Core Java, Collection Frameworks and Data Structures and Algorithms (like Arrays, Linked List, Queues, Stacks, Trees and Graphs, Searching and Sorting.).

Before moving on directly to competitive problems, lets print "Hello, World", because this is the first thing that every programming language demands.
/* This is a simple Java program.
  FileName : "HelloWorld.java". */
  class HelloWorld
  {
    // Your program begins with a call to main().
    // Prints "Hello, World" to the terminal window.
    public static void main(String args[])
      {
        System.out.println("Hello, World");
      }
  }
        
      
Output:
Hello, World
      

 

Topic : Arrays and String


Problem 1 : Check Permutation

Statement :

Given two strings. Write a method to decide if one is a permutation of other.

Approach : The problem seems to be very tough because of the word permutation, but it is very simple. First, input two strings, if one is a permutation of other then their length must be same. After that sort these strings and compare if they are equal. If they are equal after sorting then "One is a permutation of other.", otherwise "One is not a permutation of other."

Solution :
import java.util.Arrays;
import java.util.Scanner;
public class CheckPermutation
{
  public static boolean checkPermutation(String str1,String str2)
  {   
    if(str1.length() != str2.length())
      return false;
    else
    {
      char stringArray1[] = str1.toCharArray();
      char stringArray2[] = str2.toCharArray();
      Arrays.sort(stringArray1);
      Arrays.sort(stringArray2);
      String str1_1 = new String(stringArray1);
      String str2_2 = new String(stringArray2);
      if(str1_1.equals(str2_2))
        return true;
    }
    return false;
  }
    public static void main(String[] args)
    {
      String str1 = "";
      String str2 = "";
      Scanner input = new Scanner(System.in);
      str1 = input.next();
      str2 = input.next();
      boolean result = checkPermutation(str1,str2);
      if(result)
        System.out.println("One is a permutation of other.");
      else
        System.out.println("One is not a permutation of other.");
    }  
}

      
Output:
abcd
cdab
One is a permutation of other.
      

Problem 2 : URLify

Statement :

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string.

Approach : Let's first discuss the main() function, variable str stores string "I am Aakash ". Variable strCopy stores the same string stored in str, because we want to compute the true length of the string. Here true length refers to the length of "I am Aakash" and extra spaces are not counted. If we call function replaceAll() on string str, then our original string will get affected that's why we have taken strCopy. Now we will remove extra spaces from strCopy by using replaceAll() and we store the altered string in rightRemoved and rightRemoved.length() will give the true length i.e "11".

Let's move to the replaceSpaces() function: First, for loop will find no. of spaces. After that we will find newLength i.e length of the string after including '%20' in original string which will give "15". Loop run from i = 10 to i = 0 and each time loop runs, it checks if str[i] is space.

for i = 10,
      str[10] is not equal to space, therefore
      it will go to else,
      it will pick element from the end of str[10] i.e "h" and assign to str[14]. In similar fashion
      for i = 9 , str[13] = str[9] i.e 's' 
      for i = 8 , str[12] = str[8] i.e 'a'
      for i = 7 , str[11] = str[7] i.e 'k'
      for i = 6 , str[10] = str[6] i.e 'a'
      for i = 5 , str[9] = str[5] i.e 'A'
      for i = 4 , now str[4] == space therefore, it will assign str[8] = '0', str[7] = '2', str[6] = '%'.
      for i = 3 , str[5] = str[3] i.e 'm'
      for i = 2 , str[4] = str[2] i.e 'a'
      for i = 1 , now str[1] == space therefore, it will assign str[3] = '0', str[2] = '2', str[1] = '%'.
      for i = 0 , str[1] = str[0] i.e 'I'.
      And in this fashion, this loop runs and give result as "I%20am%20Aakash".

    
Solution :
public class URLify{
    public void replaceSpaces(char[] str, int trueLength){
        int spaceCount = 0, newLength = 0, i = 0;

        for(i = 0; i < trueLength; i++){
            if (str[i] == ' ') 
                spaceCount++;
        }

        newLength = trueLength + (spaceCount * 2);
        str[newLength] = '\0';
        for(i = trueLength - 1; i >= 0; i--){
            if(str[i] == ' ') {
                str[newLength - 1] = '0';
                str[newLength - 2] = '2';
                str[newLength - 3] = '%';
                newLength = newLength - 3;
            }
            else{
                str[newLength - 1] = str[i];
                newLength = newLength - 1;
            }
        }
        System.out.println(str);
    }

    public static void main(String[] args){
        URLify urlify = new URLify();
        String str = "I am Aakash        ";
        String strCopy = str;
        String rightRemoved = strCopy.replaceAll("\\s+$", "");
        char[] charStr = str.toCharArray();
        int length = rightRemoved.length();
        urlify.replaceSpaces(charStr, length);  
    }
}

      
Output:
I%20am%20Aakash
      

In Progress.........

www.000webhost.com