Pages

Reverse words in a given string

 
Given a String of length N reverse the words in it. Words are separated by dots.
Input:
The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string containing spaces and characters.
Output:
For each test case, output a single line containing the reversed String.
Constraints:
1<=T<=20
1<=Lenght of String<=2000

Example:
Input:
2
i.like.this.program.very.much
pqr.mno
Output:
much.very.program.this.like.i
mno.pqr


public class ReverseWords {
    
 private static final Scanner scanner = new Scanner(System.in);

 public static void main(String[] args) {
  
  ArrayList<String> list = new ArrayList<String>();
  int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        
  for (int k=0;k<n;k++) {
   String str = scanner.nextLine();

   String[] strArr = str.split("\\.");
   str = "";
   for(int i=strArr.length-1;i>=0;i--) {
    if(i == 0)
     str = str + strArr[i];
    else
     str = str + strArr[i] +".";
   }
   list.add(str);
  }
  
  for (String string : list) {
   System.out.println(string);
  }
 }
}

INPUT:

2
i.like.this.program.very.much
pqr.mno

OUTPUT:

much.very.program.this.like.i
mno.pqr

Count set bits in an integer

 
Set bits is nothing but number of 1's in the binary representation of the given integer. Lets see simple example and program to count the no. of set bits in the given integer.
Count set bits

 
import java.util.Scanner;

public class CountSetBits {

 public static void main(String[] args) {
  
  Scanner s = new Scanner(System. in);
  String str = "";
  int n = s.nextInt();
  s.close();
  int count = 0;
        while(n > 0)
        {
            int a = n % 2;
            str = (a == 0) ? 0 + str : 1 + str;
            count += a;
            n = n / 2;
        }

        System.out.println("BINARY VALUE : "+str);
        System.out.println("SET BITS     : "+count);
 }
}


INPUT:
13

 OUTPUT:

 
BINARY VALUE : 1101
SET BITS     : 3


Merge 2 Sorted Linked Lists

 
Function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. The new list should be made by splicing
together the nodes of the first two lists.
For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.


There are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.

{ 3, 6, 7, 8, 9 }
{ 1, 5, 7, 10, 89 }
OUTPUT: 1, 3, 5, 6, 7, 7, 8, 9, 10, 89

{}
{3, 4, 7, 8}
OUTPUT: 3, 4, 7, 8
Lets see simple Java code to get merge 2 sorted linked list without creating new (3rd) linked list and only by splicing both list nodes.

class NODE {
 
 int data;
 NODE next;

 public NODE(int data) {
  this.data = data;
  this.next = null;
 }
}

public class MergeLinkedList {

 public static void main(String[] args) {

  MergeLinkedList obj = new MergeLinkedList();

  int val1[] = new int[] { 3, 6, 7, 8, 9 };
  int val2[] = new int[] { 1, 5, 7, 10, 89 };

  /* Create 1st linked list */
  NODE firstListStart = obj.createLinkedList(val1);
  
  /* Create 2nd linked list */
  NODE secondListStart = obj.createLinkedList(val2);

  /* Merge both linked list without 3rd linked list */
  NODE start = obj.mergeLinkedList(firstListStart, secondListStart);

  NODE print = start;
  while (print != null) {
   System.out.println("----> " + print.data);
   print = print.next;
  }
 }

 /*
  * Create linked list based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }

 /*
  * Merge both the linked list without creating new Linked List.
  */
 public NODE mergeLinkedList(NODE first, NODE second) {

  if (first == null)
   return second;
  if (second == null)
   return first;

  NODE start = null;
  NODE mover = null;

  while (first != null && second != null) {
   if (start == null) {
    if (first.data <= second.data) {
     start = mover = first;
     first = first.next;
    } else if (second.data <= first.data) {
     start = mover = second;
     second = second.next;
    }
   } else {
    if (first.data <= second.data) {
     mover.next = first;
     first = first.next;
    } else if (second.data <= first.data) {
     mover.next = second;
     second = second.next;
    }
    mover = mover.next;
   }
  }
  if (first == null) {
   while (second != null) {
    mover.next = second;
    second = second.next;
    mover = mover.next;
   }
  }
  if (second == null) {
   while (first != null) {
    mover.next = first;
    first = first.next;
    mover = mover.next;
   }
  }
  return start;
 }
}
OUTPUT:

----> 1
----> 3
----> 5
----> 6
----> 7
----> 7
----> 8
----> 9
----> 10
----> 89

Finding Minimum Distinct Ids

 
Given an array of items, an i-th index element denotes the item id’s and given a number m, the task is to remove m elements such that there should be minimum distinct id’s left.Print the number of distinct id’s.
Input:
The first line of the input contains a single integer T, denoting the number of test cases. Then Ttest case follows, the three lines of the input, the first line contains N, denoting number of elements in an array,second line contains N elements/ids, and third line contains the number M.
Output:
For each test case, print the minimum number of distinct ids.
Constraints:
1<=T<=100
1<=N<=100
1<=arr[i]<=10^6
1<=M<=100
Example:
Input:
2
6
2 2 1 3 3 3
3
8
2 4 1 5 3 5 1 3
2
Output:
1
3


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.Map.Entry;

public class MinimumDistinct {

 private static final Scanner scanner = new Scanner(System.in);
 private static ArrayList<Integer> output = new ArrayList<Integer>();
 
 public static void main(String[] args) {
  
  int t = scanner.nextInt();
  scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  
  for (int i = 0; i < t; i++) {
   int n = scanner.nextInt();
   scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

   String array = scanner.nextLine();
   scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

   int arr[] = Arrays.stream(array.split(" ")).mapToInt(Integer::parseInt).toArray();
   int m = scanner.nextInt();
   scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

   getMinimumDistinct(n, arr, m);
  }
  
  for (int ids : output) {
   System.out.println(ids);
  }
 }
 
 /*
  * Convert array to map and get the distinct count
  */
 private static void getMinimumDistinct(int n, int arr[], int m) {
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  for (int i : arr) {
   if(map.containsKey(i)) {
    map.put(i, (map.get(i)+1));
   }else {
    map.put(i, 1);
   }
  }
  sortMapAndGetDistinct(map , m);
  
 }
 
 /*
  * Sort the map based on value and remove the least numbers of ids for m times
  */
 private static void sortMapAndGetDistinct(HashMap<Integer, Integer> map, int m) {
  Set<Entry<Integer, Integer>> set = map.entrySet();
        List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(set);
        Collections.sort( list, new Comparator<Map.Entry<Integer, Integer>>() {
            public int compare( Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2 ) {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } ); 
        for(Map.Entry<Integer, Integer> entry:list){
           if(m > 0 && entry.getValue() <= m) {
            map.remove(entry.getKey());
            m = m-entry.getValue();
           }
         }
        output.add(map.size());
 }
}

INPUT:
2
6
2 2 1 3 3 3
3
8
2 4 1 5 3 5 1 3
2

OUTPUT:
1
3

Invert bits of a number

 
Given a non-negative integer n. The problem is to invert the bits of n and print the number obtained after inverting the bits. Note that the actual binary representation of the number is being considered for inverting the bits, no leading 0’s are being considered.

 
Input : 11
Output : 4
(11)10 = (1011)[2]
After inverting the bits, we get:
(0100)2 = (4)10.

Input : 10
Output : 5
(10)10 = (1010)2.
After reversing the bits we get:
(0101)2 = (101)2
        = (5)10.



INPUT:

 

import java.util.Scanner;

public class InvertNumberBit {

 public static void main(String[] args) {
  
  Scanner s = new Scanner(System. in);
  String str = "";
  int n = s.nextInt();
  s.close();
        while(n > 0)
        {
            int a = n % 2;
            str = (a == 1) ? 0 + str : 1 + str;
            n = n / 2;
        }
        n = Integer.parseInt(str, 2);
        System.out.println(n);
 }
}

OUTPUT:


11
4

Save Ironman

 
Jarvis is weak in computing palindromes for Alphanumeric characters.
While Ironman is busy fighting Thanos, he needs to activate sonic punch but Jarvis is stuck in computing palindromes.
You are given a string containing the alphanumeric character. Find whether the string is palindrome or not.
If you are unable to solve it then it may result in the death of Iron Man.
Input:
The first line of the input contains t, the number of test cases. Each line of the test case contains string 'S'.
Output:
Each new line of the output contains "YES" if the string is palindrome and "NO" if the string is not a palindrome.
Constraints:
1<=t<=100
1<=|S|<=100000
Note: Consider alphabets and numbers only for palindrome check. Ignore symbols and whitespaces.
Example:
Input:
2
I am :IronnorI Ma, i
Ab?/Ba
Output:
YES
YES


import java.util.Scanner;

public class SaveIronman {

 private static final Scanner scanner = new Scanner(System.in);

 public static void main(String[] args) {

  int lengthsCount = scanner.nextInt();
  scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

  String values[] = new String[lengthsCount];
  for (int i = 0; i < lengthsCount; i++) {
   String str = scanner.nextLine();
   values[i] = str;
  }
  findPalindromes(values);
 }
 
 public static void findPalindromes(String[] values) {
  
  for (String string : values) {
   
   char[] strCh = string.toCharArray();
   StringBuilder strBuild = new StringBuilder();
   for (char c : strCh) {
    if(Character.isDigit(c)) strBuild.append(Character.toString(c));
    if(Character.isAlphabetic(c)) strBuild.append(Character.toString(c).toLowerCase());
   }
   boolean flag = true;
   for(int i=0,j=strBuild.length()-1;i<j;i++,j--) {
    if(strBuild.charAt(i) != strBuild.charAt(j)) {
     System.out.println("NO");
     flag = false;
     break;
    }
   }
   if(flag)
   System.out.println("YES");
  }
 }
}

INPUT:


2
I am :IronnorI Ma, i
Ab?/Ba
OUTOUT:


YES
YES

Smallest substring which contains all characters of other String

 
Find the smallest substring which contains all the characters of the other string. Here the characters order can be anything and only the conditions which need to be

  • All the characters of 2nd string should present the the substring
  • Substring should be with least window size.


Smallest Window
SAMPLE:


Input :  string = "this is a test string"
        pattern = "tist"

Output :  Minimum window is "t stri"
Explanation: "t stri" contains all the characters of pattern.

Input :  string = "geeksforgeeks"
        pattern = "ork" 

Output :  Minimum window is "ksfor"


Lets see simple program to get Smallest substring which contains all characters of other String


public class SmallestWindow {

 public static void main(String[] args) {
  
  String sen = "this is a test string";
  String sStr = "tist";
  int sStrLen = sStr.length();
  String smallSubString = null;
  
  for(int i=0;i<sen.length();i++) {
   for(int j=sStrLen-1;j<sen.length();j++) {
    String tmp = sen.substring(i, j+1);
    boolean isContains = isContains(tmp, sStr);
    if(isContains) {
     if(smallSubString == null) 
       smallSubString = tmp;
     else if(smallSubString.length() > tmp.length()) 
       smallSubString = tmp;
    }
   }
   sStrLen++;
  }
  if(smallSubString == null)
   System.out.println("No such window exists");
  else
   System.out.println("Smallest window ::: "+smallSubString);
 }
 
 public static boolean isContains(String tmp, String sStr) {
  
  int array[] = new int[256];
  
  for(int i=0;i<tmp.length();i++) {
   array[tmp.charAt(i)]++;
  }
  
  for(int i=0;i<sStr.length();i++) {
   if(array[sStr.charAt(i)] == 0) 
    return false;
   else 
    array[sStr.charAt(i)]--;
  }
  return true;
 }
}



OUTPUT:


Smallest window ::: t stri
Get updates in your email box

Complete the form below, and we'll send you our recent update.

Deliver via FeedBurner
© Copyright 2015 Java Discover. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates. Powered by Blogger.