How to print singly linked list in reverse order

How to print singly linked list in reverse order

Reverse Linked List  

If we talk about Singly Linked List then it will be a 1 way traversal from head node to tail node. But if we need to print the linked list values from tail node to head node (in reverse order) with O(N) time complexity. ???

• Its simple just we need to apply recursive algorithm where we need to start from head node and reach tail which is last node.
• Next print each node values in recursive call. By this way we can achieve printing linked list in recursive order without traversing more than once which is by time complexity O(N) only. 

Lets see simple code to create Singly Linked List and printing same Linked List in reverse order with O(N) complexity.

class NODE {

 int data;
 NODE next;

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

public class PrintLinkedList {

 public static void main(String[] args) {

  PrintLinkedList obj = new PrintLinkedList();
  int val[] = new int[] { 1, 5, 7, 10, 89 };

  NODE head = obj.createLinkedList(val);
  obj.printLLInReverse(head);
 }

 /*
  * Recursive method to print LL in reverse order
  */
 public void printLLInReverse(NODE tmp) {
  if (tmp != null) {
   printLLInReverse(tmp.next);
   System.out.println(tmp.data);
  }
 }

 /*
  * 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;
 }
}

OUTPUT:

89
10
7
5
1

Finding Minimum Distinct Ids

Finding Minimum Distinct Ids

Morgan Stanley Interview questions  

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

Save Ironman

Save Ironman

Java Interview Questions  

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