Sort a stack using temporary stack

Stack is a data structure which is based on first-in ,last-out algorithm.It basically means the element which is added first will be removed at last.There are various ways available to sort the stack of which one of them is using temporary stack.

Sample Program:-

 import java.util.Stack;  
 /**  
  * @author Dixit  
  *  
  */  
 public class StackSorting {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           Stack<Integer> stack = new Stack<Integer>();  
           stack.add(1);  
           stack.add(5);  
           stack.add(10);  
           stack.add(9);  
           stack.add(2);  
           Stack<Integer> tempStack = new Stack<Integer>();  
           while (!stack.isEmpty()) {  
                int value = stack.pop();  
                while (!tempStack.isEmpty() && tempStack.peek() > value) {  
                     stack.push(tempStack.pop());  
                }  
                tempStack.push(value);  
           }  
           for (int i = 0; i < tempStack.size(); i++) {  
                System.out.println(tempStack.get(i));  
           }  
      }  
 }  

Output:  
 1  
 2  
 5  
 9  
 10  

Enjoy Programming:)

Find sum of each digit in a number using recursion

Recursion is a technique which allows to define something in terms of itself which means recursion allows a method to call itself repeatedly.Finding sum of digit using for loop is easy but using recursion it is bit tricky.

Sample Program:-

 /**  
  * @author Dixit  
  *  
  */  
 public class SumOfDigitUsingRecursion {  
      private static int sum = 0;  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           String number = "7214";  
           if (number != null && !number.trim().isEmpty())  
                System.out  
                          .println("Sum of Digit of given number " + number  
                                    + " is :-"  
                                    + getSumOfDigit(Integer.parseInt(number.trim())));  
           else  
                System.out.println("Either String is empty or null");  
      }  
      private static int getSumOfDigit(int num) {  
           if (num == 0)  
                return sum;  
           else {  
                sum = sum + (num % 10);  
                getSumOfDigit(num / 10);  
           }  
           return sum;  
      }  
 }  

Limitations:

• If your number is larger, then it will occupy more memory space as well as time.

Enjoy Programming:)

Find the middle node of linked list in one pass

Linked List is data structure which consist of nodes.Each node consist of data,previous node pointer and next node pointer.Previous node pointer points to previous node and next node pointer points to next node.Finding a middle node of linked list is one of important question asked in interview for experienced professionals.

Sample Program:-

 public class FindMiddleNodeInLinkedList {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           LinkedList linkedList = new LinkedList();  
           LinkedList.Node head = linkedList.head();  
           linkedList.add(new LinkedList.Node("10"));  
           linkedList.add(new LinkedList.Node("9"));  
           linkedList.add(new LinkedList.Node("8"));  
           linkedList.add(new LinkedList.Node("7"));  
           linkedList.add(new LinkedList.Node("6"));  
           LinkedList.Node current = head;  
           int length = 0;  
           LinkedList.Node middle = head;  
           while (current.next() != null) {  
                length++;  
                if (length % 2 == 0) {  
                     middle = middle.next();  
                }  
                current = current.next();  
           }  
           if (length % 2 == 1) {  
                middle = middle.next();  
           }  
           System.out.println(" Middle element of LinkedList is : " + middle);  
      }  
 }  
 class LinkedList {  
      private Node head;  
      private Node tail;  
      public LinkedList() {  
           this.head = new Node("head");  
           tail = head;  
      }  
      public Node head() {  
           return head;  
      }  
      public void add(Node node) {  
           tail.next = node;  
           tail = node;  
      }  
      public static class Node {  
           private Node next;  
           private String value;  
           public Node(String value) {  
                this.value = value;  
           }  
           public String value() {  
                return value;  
           }  
           public void setValue(String value) {  
                this.value = value;  
           }  
           public Node next() {  
                return next;  
           }  
           public void setNext(Node next) {  
                this.next = next;  
           }  
           public String toString() {  
                return this.value;  
           }  
      }  
 }  

Corner Cases:-

• If only one node is present, then it will return the node.
• If even number of nodes are present, then it will return middle element as the node which is exactly divisible by 2.

Enjoy Programming:)

Find first non repeated character in a string

String is most important topic in Java.There are many programming question on String which are important from interview perspective.This is one of the problem where we need to find the first non repeated character in the String.There can be multiple solutions for this problem.One of the solution is as follows:-

Sample Program:-

import java.util.Hashtable;  
 public class FirstUnRepeatedCharacter {  
      private static Character getFirstUnRepeatedCharacterUsingHashTable(  
                char[] charArray) {  
           Hashtable<Character, Integer> hashtable = new Hashtable<Character, Integer>();  
           for (Character character : charArray) {  
                if (!hashtable.containsKey(character))  
                     hashtable.put(character, 0);  
                else  
                     hashtable.put(character, hashtable.get(character) + 1);  
           }  
           for (Character character : charArray) {  
                if (hashtable.get(character) == 0)  
                     return character;  
           }  
           return 0;  
      }  
      private static char getFirstUnRepaedtedCharacterUsingLoops(String str) {  
           int count;  
           for (int i = 0; i < str.length(); i++) {  
                count = 0;  
                for (int j = 0; j < str.length(); j++) {  
                     if (i != j && str.charAt(i) == str.charAt(j)) {  
                          count = count + 1;  
                          break;  
                     }  
                }  
                if (count == 0) {  
                     return str.charAt(i);  
                }  
           }  
           return 0;  
      }  
      public static void main(String[] args) {  
           String str = "daabbcc";  
           System.out.println("First Un repeated Character Using For loops:-"  
                     + getFirstUnRepaedtedCharacterUsingLoops(str));  
           System.out.println("First Un repeated Character Using HashTable:-"  
                     + getFirstUnRepeatedCharacterUsingHashTable(str.toCharArray()));  
      }  
 }  

The Time Complexity in case of First approach i.e. using for loops is O(n2) because each character is compared with remaining characters and 2 for loops are used for that to iterate over all the characters.

And The time Complexity for other approach i.e. using HashTable is O(2n) because first loop is used to insert the character in HashTable along with the count of character and Second loop is used to get the first unrepeated character.
First approach is preferable if given string is small and in case of large String we can use Second approach.

Enjoy Programming :)

How to remove duplicates from ArrayList

In Java, List permits ordered access of their elements. They can have duplicates because their lookup key is the position not some hash code, every element can be modified while they remain in the list where as Set represents a collection of unique elements and while elements are in set, they must not be modified.While there is no restriction preventing you from modifying elements in a set, if an element is modified, then it could become forever lost in the set.

In this problem, to remove duplicates from an ArrayList, you can store the element of list in the Hashset . You can iterate over Hashset or you can convert the Hashset into new ArrayList.

Sample Program:-

 import java.util.ArrayList;  
 import java.util.HashSet;  
 import java.util.List;  
 import java.util.Set;  
 public class RemoveDuplicates {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> l = new ArrayList<String>();  
           l.add("A");  
           l.add("B");  
           l.add("C");  
           l.add("A");  
           System.out.println("Before removing duplicates: ");  
           for (String s : l) {  
                System.out.println(s);  
           }  
           Set<String> set = new HashSet<String>(l);  
           List<String> newlist = new ArrayList<String>(set);  
           System.out.println("after removing duplicates: ");  
           for (String s : newlist) {  
                System.out.println(s);  
           }  
      }  
 }  

Output:-

 Before removing duplicates:   
 A  
 B  
 C  
 A  
 after removing duplicates:   
 A  
 B  
 C  

Enjoy Programming.

Write a program to find average of consecutive N Odd numbers and Even numbers

Sample Program:-

 public class AvgEvenOddNumbers {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           int n = 100;  
           int evenCount = 0, oddCount = 0, evenSum = 0, oddSum = 0;  
           while (n > 0) {  
                if (n % 2 == 0) {  
                     evenCount++;  
                     evenSum = evenSum + n;  
                } else {  
                     oddCount++;  
                     oddSum = oddSum + n;  
                }  
                n--;  
           }  
           int avgEven, avgOdd;  
           avgEven = evenSum / evenCount;  
           avgOdd = oddSum / oddCount;  
           System.out.println("Average of Even no till 100 is :- " + avgEven);  
           System.out.println("Average of Odd no till 100 is :- " + avgOdd);  
      }  
 }  

Output:-

 Average of Even no till 100 is :- 51  
 Average of Odd no till 100 is :- 50  

Enjoy Programming.

How to obtain Array From an ArrayList ?

The Collection interface includes the toArray() method to convert a new collection into an array. There are two forms of this method. The no argument version will return the elements of the collection in an Object array: public Object[ ] toArray(). The returned array cannot cast to any other data type. This is the simplest version. The second version requires you to pass in the data type of the array you’d like to return: public Object [ ] toArray(Object type[ ]).

For example:- assume col represents a collection of Date objects,

Date d[ ] = (Date []) col.toArray(new Date[0]);

To convert ArrayList into an Array, first method is sufficient.

Sample Program:-

 import java.util.ArrayList;  
 import java.util.List;  
 public class ConvertArrayListIntoArray {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> l=new ArrayList<String>();  
           l.add("A");  
           l.add("B");  
           l.add("C");  
           Object arr[]=l.toArray();  
           for(Object a:arr)  
           {  
                String str=(String)a;  
                System.out.println(str);  
           }  
      }  
 }  

Output:-

 A  
 B  
 C  

Enjoy Reading