Sudo Placements geeks for geeks Solution in Java

FOR THE SOLUTION YOU MAY GET TLE- error(Exceeding timelimit error) it's just because Java is slower than cpp/c

Ques-

If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings. 

For example: 
Input: "1123". You need to general all valid alphabet codes from this string.

Output List 
aabc //a = 1, a = 1, b = 2, c = 3 
kbc // since k is 11, b = 2, c= 3 
alc // a = 1, l = 12, c = 3 
aaw // a= 1, a =1, w= 23 
kw // k = 11, w = 23

Solution -

public class JavaApplication3 {

    /**

     * @param args the command line arguments

     */

    

    public static Set<String> decode(String prefix, String code) {

Set<String> set = new HashSet<String>();

if (code.length() == 0) 

                {

set.add(prefix);

return set;

}

if (code.charAt(0) == '0')

return set;

set.addAll(decode(prefix + (char) (code.charAt(0) - '1' + 'a'),

code.substring(1)));

if (code.length() >= 2 && code.charAt(0) == '1') {

set.addAll(decode(

prefix + (char) (10 + code.charAt(1) - '1' + 'a'),

code.substring(2)));

}

if (code.length() >= 2 && code.charAt(0) == '2'

&& code.charAt(1) <= '6') {

set.addAll(decode(

prefix + (char) (20 + code.charAt(1) - '1' + 'a'),

code.substring(2)));

}

return set;

}

    

    public static void main(String[] args) {

        Set s = decode("", "9999");

        System.out.println(s);

    }    

}

Immediate Smaller Element

Given an integer array of size N. For each element in the array, check whether there exist a smaller element on the next immediate position of the array. If such an element exists, print that element. If there is no smaller element on the immediate next to the element then print -1.

Input:
The first line of input contains an integer T denoting the number of test cases. T testcases follow. Each testcase contains 2 lines of input:

The first line contains an integer N, where N is the size of array.
The second line contains N integers(elements of the array) sperated with spaces.

Output:

For each test case, print the next immediate smaller elements for each element in the array.

Constraints:

1 ≤ T ≤ 200
1 ≤ N ≤ 107
1 ≤ arr[i] ≤ 1000

Example:

Input
2
5
4 2 1 5 3
6
5 6 2 3 1 7

Output
2 1 -1 3 -1
-1 2 -1 1 -1 -1



Explanation:
Testcase 1: Array elements are 4, 2, 1, 5, 3. Immediate smaller of 2 is immediate smaller of 4, 1 is immediate smaller of 2,no immediate smaller of 1, 3 is immediate smaller of 5, and no immediate smaller for last element exists. So ouput is : 2 1 -1 3 -1.



CODE- SOLUTION

import java.util.*;

import java.lang.*;

import java.io.*;



class GFG {
 public static void main (String[] args) {
  //code
  Scanner kb=new Scanner(System.in);
  int times=kb.nextInt();
  for(int i=0;i<times;i++)//testcases
  {

      int size_arr=kb.nextInt();

      int arr[]=new int[size_arr];

      for(int j=0;j<size_arr;j++)

      {
          arr[j]=kb.nextInt();
      }

   

      try{

      for(int j=0;j<size_arr;j++)
      {
          if(arr[j]>arr[j+1])
          {
              System.out.println(arr[j+1]);
          }
          else
          {
              System.out.println("-1");
          }

       
      }
      }

      catch(Exception e)

      {
          System.out.println("-1");
      }


  }//testcases

 }


}


Rotating an Array
Given an array of N size. The task is to rotate array by d elements where d is less than or equal to N.

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of three lines. The first line of each test case consists of an integer N, where N is the size of array.
The second line of each test case contains N space separated integers denoting array elements. The third line of each test case contains "d" .

Output:
Corresponding to each test case, in a new line, print the modified array.

Constraints:
1 ≤ T ≤ 200
1 ≤ N ≤ 200
1 ≤ A[i] ≤ 1000

Example:
Input
1
5
1 2 3 4 5
2

Output
3 4 5 1 2

Solution-

/*package whatever //do not write package name here */

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
//code
Scanner kb=new Scanner(System.in);
int times=kb.nextInt();
for(int i=0;i<times;i++)
{
    int sizearr=kb.nextInt();
    int arr[]=new int[sizearr];
    for(int j=0;j<sizearr;j++)
    {
        arr[j]=kb.nextInt();
      
    }
    int by_ro = kb.nextInt();
    for(int j=by_ro;j<sizearr;j++)
    {
        System.out.print(arr[j]);
    }
    for(int j=0;j<by_ro;j++)
    {
        System.out.print(arr[j]);
    }
    
}//times

}

}

Leaders in an array


Given an array of positive integers. Your task is to find the leaders in the array.
Note: An element of array is leader if it is greater than or equal to all the elements to its right side. Also, the rightmost element is always a leader. 

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of array.
The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output:
Print all the leaders.

Constraints:
1 <= T <= 100
1 <= N <= 107
0 <= Ai <= 107

Example:
Input:
3
6
16 17 4 3 5 2
5
1 2 3 4 0
5
7 4 5 7 3
Output:
17 5 2
4 0
7 7 3

Explanation:
Testcase 3: All elements on the right of 7 (at index 0) are smaller than or equal to 7. Also, all the elements of right side of 7 (at index 3) are smaller than 7. And, the last element 3 is itself a leader since no elements are on its right.

import java.io.*;
import java.util.*;

class GFG {
    
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim()); //Inputting the testcases
while(t-->0){
    int n = Integer.parseInt(br.readLine().trim());
    int arr[] = new int[n];
    String inputLine[] = br.readLine().trim().split(" ");
    for(int i=0; i<n; i++){
        arr[i] = Integer.parseInt(inputLine[i]);
    }
    int maxEle = arr[n-1];
    StringBuffer str = new StringBuffer();
    ArrayList<Integer> res = new ArrayList<Integer>();
    for(int i=n-1; i>=0; i--) {
        if(arr[i] >= maxEle){
            maxEle = arr[i];
            res.add(maxEle);
        }
    }
    for(int i=res.size()-1; i>=0; i--){
        str.append(res.get(i)+" ");
    }
    System.out.println(str);
}
}

}



Print an array in Pendulum Arrangement

Write a program to input a list of n integers in an array and arrange them in a way similar to the to-and-fro movement of a Pendulum.

The minimum element out of the list of integers, must come in center position of array. If there are even elements, then minimum element should be moved to (n-1)/2 index (considering that indexes start from 0)
The next number (next to minimum) in the ascending order, goes to the right, the next to next number goes to the left of minimum number and it continues like a Pendulum.
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. Then next line contains N space separated integers forming the array.

Output:
Output the array in Pendulum Arrangement.

Constraints:
1<=T<=500
1<=N<=100
1<=a[i]<=1000

Example:
Input:
2
5
1 3 2 5 4
5
11 12 31 14 5

Output:
5 3 1 2 4
31 12 5 11 14

Solution-

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class test {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int times=Integer.parseInt(br.readLine());
        while(times-->0)
        {
           int size=Integer.parseInt(br.readLine());
           int arr[]=new int[size];
           String line=br.readLine();
           String [] strs=line.trim().split("\\s+");

           for(int i=0;i<size;i++)
               arr[i]=Integer.parseInt(strs[i]);

            Arrays.sort(arr);
            StringBuffer sb=new StringBuffer();
            int mid_point=(size-1)/2;
            sb.append(arr[0]+" ");
            int j=1;
            for(int i=0;i<size/2;i++)
            {
                sb.append(arr[j++]+" ");
                sb.insert(0,arr[j++]+" ");

            }
            if(size%2==0)
                sb.append(arr[arr.length-1]+" ");

            System.out.println(sb);


        }//times

    }
}

SP BIT MAGIC JAVA SOLUTIONS

Binary representation

Write a program to print Binary representation of a given number N.


Input:
The first line of input contains an integer T, denoting the number of test cases. Each test case contains an integer N.

Output:
For each test case, print the binary representation of the number N in 14 bits.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 5000

Example:
Input:
2
2
5

Output:
00000000000010
00000000000101

import java.util.*;
import java.lang.*;
import java.io.*;

class binary {
    public static void main (String[] args) {
        //code
        Scanner kb=new Scanner(System.in);
        int times=kb.nextInt();
        int t=0;
        int arr[]=new int[14];
        for(int i=0;i<times;i++)
        {
            int num=kb.nextInt();

            for(int j=0;j<14;j++)
            {
                //System.out.println("j value "+ j);
                arr[j]=num%2;
                //System.out.println(arr[j]);
                num=num/2;
                //System.out.println(num);
            }



            //System.out.println("result");
            int j=13;
            while(j>=0)
            {
                System.out.print(arr[j]);
                j=j-1;
            }
            System.out.println();



        }//times
    }

}

Practice Coding Questions for Companies

Count ways to N'th Stair(Order does not matter)

There are N stairs, and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does not matter).
Note: Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same.

Input:
The first line contains an integer 'T' denoting the total number of test cases. In each test cases, an integer N will be given.

Output:
For each testcase, in a new line, print number of possible ways to reach Nth stair.

Constraints:
1 <= T <= 1000
1 <= N <= 106

Example:
Input:
2
4
5
Output:
3
3

Explanation:
Testcase 1: There are 3 ways to reach 4th stair.

Solution-

class DynamicProgramming{

    

    // function to find number of ways 

    Long countWays(int m){

        

        // your code here

        m=(m/2)+1;

        Long l=Long.valueOf(m);

        

        return l;

    }   

    

}

Question - Find the smallest positive number missing from an unsorted array

  Input: {2, 3, 7, 6, 8, -1, -10, 15}
 Output: 1

 Input: { 2, 3, -7, 6, 8, 1, -10, 15 }
 Output: 4

 Input: {1, 1, 0, -1, -2}
 Output: 2

Solution-

import java.util.*; 

  

class test

{    

       

    /* Utility function that puts all non-positive  

       (0 and negative) numbers on left side of  

       arr[] and return count of such numbers */

    static int segregate (int arr[], int size) 

    { 

        int j = 0, i; 

        for(i = 0; i < size; i++) 

        { 

           if (arr[i] <= 0)   

           { 

               int temp; 

               temp = arr[i]; 

               arr[i] = arr[j]; 

               arr[j] = temp; 

               // increment count of non-positive  

               // integers 

               j++;   

           } 

        } 

       

        return j; 

    } 

       

    /* Find the smallest positive missing  

       number in an array that contains 

       all positive integers */

    static int findMissingPositive(int arr[], int size) 

    { 

      int i; 

       

      // Mark arr[i] as visited by making  

      // arr[arr[i] - 1] negative. Note that  

      // 1 is subtracted because index start  

      // from 0 and positive numbers start from 1 

      for(i = 0; i < size; i++) 

      { 

        int x = Math.abs(arr[i]); 

        if(x - 1 < size && arr[x - 1] > 0) 

          arr[x - 1] = -arr[x - 1]; 

      } 

       

      // Return the first index value at which  

      // is positive 

      for(i = 0; i < size; i++) 

        if (arr[i] > 0) 

          return i+1;  // 1 is added becuase indexes  

                       // start from 0 

       

      return size+1; 

    } 

       

    /* Find the smallest positive missing  

       number in an array that contains 

       both positive and negative integers */

    static int findMissing(int arr[], int size) 

    { 

       // First separate positive and  

       // negative numbers 

       int shift = segregate (arr, size); 

       int arr2[] = new int[size-shift]; 

       int j=0; 

       for(int i=shift;i<size;i++) 

           { 

               arr2[j] = arr[i]; 

               j++; 

           }     

       // Shift the array and call  

       // findMissingPositive for 

       // positive part 

       return findMissingPositive(arr2, j); 

    } 

    // main function 

    public static void main (String[] args)  

    { 

        int arr[] = {0, 10,1,2, 2, -10, -20}; 

        int arr_size = arr.length; 

        int missing = findMissing(arr, arr_size); 

        System.out.println("The smallest positive missing number is "+  

                            missing); 

    } 

} 

Source-Geeksforgeeks

Question - Longest Common Substring in an Array of Strings

Input: grace graceful disgraceful gracefully
Output: grace

Input: sadness sad sadly
Output: sad

Solution - 

// Java program to find the stem of given list of 

// words 

import java.io.*; 

import java.util.*; 

class stem { 

// function to find the stem (longest common substring) from the string array 

public static String findstem(String arr[]) 

{ 

// Determine size of the array 

int n = arr.length; 

// Take first word from array as reference 

String s = arr[0]; 

int len = s.length(); 

String res = ""; 

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

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

// generating all possible substrings 

// of our reference string arr[0] i.e s 

String stem = s.substring(i, j); 

int k = 1; 

for (k = 1; k < n; k++) 

// Check if the generated stem is 

// common to to all words 

if (!arr[k].contains(stem)) 

break; 

// If current substring is present in 

// all strings and its length is greater 

// than current result 

if (k == n && res.length() < stem.length()) 

res = stem; 

} 

} 

return res; 

} 

// Driver Code 

public static void main(String args[]) 

{ 

String arr[] = { "grace", "graceful", "disgraceful", "gracefully" }; 

String stems = findstem(arr); 

System.out.println(stems); 

} 

} 

Question - Given an amount convert the amount into different currencies - example- amount to us,indian,france,china and display.

Solution-

import java.util.Scanner;

import java.text.NumberFormat;

import java.util.Locale;

public class Solution {

    

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        double payment = scanner.nextDouble();

        scanner.close();

        /* Create custom Locale for India. 

          I used the "IANA Language Subtag Registry" to find India's country code */

        Locale indiaLocale = new Locale("en", "IN");

        NumberFormat us     = NumberFormat.getCurrencyInstance(Locale.US);

        NumberFormat india  = NumberFormat.getCurrencyInstance(indiaLocale);

        NumberFormat china  = NumberFormat.getCurrencyInstance(Locale.CHINA);

        NumberFormat france = NumberFormat.getCurrencyInstance(Locale.FRANCE);

    

        System.out.println("US: "     + us.format(payment));

        System.out.println("India: "  + india.format(payment));

        System.out.println("China: "  + china.format(payment));

        System.out.println("France: " + france.format(payment));

    }

}

Question - Java Program to Print Diamond Pattern

Solution -

import java.util.*;

class dia

{

public static void main(String []args)

{

Scanner kb=new Scanner(System.in);

int n=kb.nextInt();

int i=0,j=0;

int space=n-1;

for (j = 1; j <= n; j++) 

        {

            for (i = 1; i <= space; i++) 

            {

                System.out.print(" ");

            }

            space--;

            for (i = 1; i <= 2 * j - 1; i++) 

            {

                System.out.print("*");                

            }

            System.out.println("");

        }

        space = 1;

        

        for (j = 1; j <= n - 1; j++) 

        {

            for (i = 1; i <= space; i++) 

            {

                System.out.print(" ");

            }

            space++;

            for (i = 1; i <= 2 * (n - j) - 1; i++) 

            {

                System.out.print("*");

            }

            System.out.println("");

        }

}

}

Question  - Write a program to evaluate the postfix expression

input = a mathematical expression 

example = 231*+9-

output = -4

Solution

import java.util.Stack; 

  

class main 

{ 

    static int evaluatePostfix(String exp) 

    {  

        Stack<Integer> stack=new Stack<>(); 

           

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

        { 

            char c=exp.charAt(i); 

              

            if(Character.isDigit(c)) 

                stack.push(c - '0'); 

              

            else

            { 

                int val1 = stack.pop(); 

                int val2 = stack.pop(); 

                  

                switch(c) 

                { 

                    case '+': 

                    stack.push(val2+val1); 

                    break; 

                      

                    case '-': 

                    stack.push(val2- val1); 

                    break; 

                      

                    case '/': 

                    stack.push(val2/val1); 

                    break; 

                      

                    case '*': 

                    stack.push(val2*val1); 

                    break; 

              } 

            } 

        } 

        return stack.pop();     

     }

           

    public static void main(String[] args)  

    { 

        String exp="231*+9-"; 

        System.out.println("postfix evaluation: "+ evaluatePostfix(exp)); 

    } 

}

Question - Given a collection of intervals, merge all the overlapping intervals, for example-

given - [1,3] [2,6] [8,10] [15,18]

output- [1,6] [8,10] [15,18]

Solution-

import java.util.*;

class main

{

public static void main(String []args)

{

Scanner kb=new Scanner(System.in);

int n=kb.nextInt();

int arr1[]=new int[n];

int arr2[]=new int[n];

int arr3[]=new int[n];

int arr4[]=new int[n];

int i,j,k=0;

int temp1=0,temp2=0;

for(i=0;i<n;i++)

{

arr1[i]=kb.nextInt();

arr2[i]=kb.nextInt();

}

for(j=0;j<n-1;j++)

{

if(arr2[j]>arr1[j+1])

{

System.out.println("Found at "+ arr1[j+1] +" and "+ arr2[j]);

temp1=j;

temp2=j+1;

}

}

       }

}

Question - Given an array of N elements, determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

input format- Input to contain a number of elements N, next line contain the N elements

5

3 1 5 9 12

Output format- Can be divided into two subsets of an equal sum

Solution-

import java.io.*; 

  

class main

{ 

    static boolean isSubsetSum (int arr[], int n, int sum) 

    { 

        if (sum == 0) 

            return true; 

        if (n == 0 && sum != 0) 

            return false; 

  

        if (arr[n-1] > sum) 

            return isSubsetSum (arr, n-1, sum); 

  

        return isSubsetSum (arr, n-1, sum) || 

               isSubsetSum (arr, n-1, sum-arr[n-1]); 

    } 

  

    static boolean findPartition (int arr[], int n) 

    { 

        int sum = 0; 

        for (int i = 0; i < n; i++) 

            sum += arr[i]; 

  

        if (sum%2 != 0) 

            return false; 

  

        return isSubsetSum (arr, n, sum/2); 

    } 

  

    public static void main (String[] args) 

    { 

  

        int arr[] = {3, 1, 5, 9, 12}; 

        int n = arr.length; 

        if (findPartition(arr, n) == true) 

            System.out.println("Can be divided into two "+ 

                                "subsets of equal sum"); 

        else

            System.out.println("Can not be divided into " + 

                                "two subsets of equal sum"); 

    } 

} 

__________________________________________________

source- geeksforgeeks.com

Question - You Are given an alphanumeric String. Write a program to find the sum of numbers in the given string.

input format-51b6de19

output format -21

Solution

import java.util.Scanner;

class main

{

public static void main(String [] args)

{

Scanner kb=new Scanner(System.in);

String word=kb.nextLine();

int length=word.length();

int sum=0;

for(int i=0;i<length;i++)

{

if(Character.isDigit(word.charAt(i)))

{

int temp=Character.getNumericValue(word.charAt(i));

sum=sum+temp;

}

}

System.out.println("The sum is" +sum);

}

}