Stack implementation using Linked List

We have seen Stack implementation using array in our earlier tutorials. Now lets see same stack implementation using Linked List and how to push() and pop() values in Stack.
Below is the simple example to push() integers into Stack internally having Linked List nodes with total stack size of 10.
Stack implementation using Linked List

class NODE {
 
 NODE link;
 int data;
 
 public NODE() {
 }
 
 public NODE(int data) {
  this.data = data;
 } 
}



public class StackUsingLinkedList {

 NODE root;
 int stackSize = 0;
 int stackLimit = 10;
 
 public static void main(String[] args) {
  
  StackUsingLinkedList obj = new StackUsingLinkedList();
  
  for(int i =0;i<11;i++){
   obj.push(i+10);
  }
  
  for(int i =0;i<11;i++){
   System.out.println(obj.pop());
  }
 }
 
 private int pop(){
  if(stackSize == 0){
   System.out.println("Stack empty ....");
   return -1;   
  }
  NODE tmp = root;
  root = root.link;
  stackSize--;
  return tmp.data;
  
 }
 
 private void push(int val){
  if(stackLimit == stackSize) {
   System.out.println("Stack Full ....");
   return;
  }
  if(root == null){
   root = new NODE(val);
   root.link = null;   
  }else{
   NODE tmp = new NODE(val);
   tmp.link = root;
   root = tmp;
  }
  System.out.println("PUSH ::: "+stackSize + " :: "+val);
  stackSize++;
 }
}



OUTPUT:

PUSH ::: 0 :: 10
PUSH ::: 1 :: 11
PUSH ::: 2 :: 12
PUSH ::: 3 :: 13
PUSH ::: 4 :: 14
PUSH ::: 5 :: 15
PUSH ::: 6 :: 16
PUSH ::: 7 :: 17
PUSH ::: 8 :: 18
PUSH ::: 9 :: 19
Stack Full ....
19
18
17
16
15
14
13
12
11
10
Stack empty ....
-1

Create Binary Tree - Preorder, Inorder and Postorder Traversal

Lets see simple java code to create Binary Tree and all 3 traversals like Preorder, Inorder and Postorder.
Used 2 classes called BST (used for binary tree node) and BinaryTree to construct Binary Tree and for traversals.

Create Binary Tree - Preorder, Inorder and Postorder Traversal
class BST {

 BST left; // Left subtree
 BST right; // Right subtree
 int data; // Element

 public BST(int data) {
  this.data = data;
 }
}



public class BinaryTree {

 public static void main(String[] args) {

  int val[] = new int[] { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };;
  
  BST root = new BST(val[0]); // Initialize root with 1ft element
  BST tmpRoot = root; // Temporary root node

  for (int i = 1; i < val.length; i++) {

   BST lastNode = getLastNode(tmpRoot, val[i]);

   if (val[i] > lastNode.data) {

    BST tmp = new BST(val[i]);
    lastNode.right = tmp;

   } else {

    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }

  System.out.print("\n\n PREORDER :::::: ");
  preOrderTraversal(root);

  System.out.print("\n\n INORDER ::::::: ");
  inOrderTraversal(root);

  System.out.print("\n\n POSTORDR :::::: ");
  postOrderTraversal(root);
 }

 public static BST getLastNode(BST root, int val) {

  if (val > root.data) {

   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {

   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }

 // BST Pre-order traversal
 public static void preOrderTraversal(BST root) {

  System.out.print(root.data + ", ");

  if (root.left != null) {
   preOrderTraversal(root.left);
  }
  if (root.right != null) {
   preOrderTraversal(root.right);
  }
 }

 // BST in-order traversal
 public static void inOrderTraversal(BST root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }

 // BST post-order traversal
 public static void postOrderTraversal(BST root) {

  if (root.left != null) {
   postOrderTraversal(root.left);
  }
  if (root.right != null) {
   postOrderTraversal(root.right);
  }
  System.out.print(root.data + ", ");
 }
}



OUTPUT:

 PREORDER :::::: 4, 3, 2, 1, 5, 8, 7, 6, 100, 9, 

 INORDER ::::::: 1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 

 POSTORDR :::::: 1, 2, 3, 6, 7, 9, 100, 8, 5, 4, 

Longest Substring without duplicate character

There can be N number of questions can be framed by using String, like longest substring without duplicate character, substring with repeated characters, most consecutive characters in substring etc., Now let's see simple java code to find the longest substring without duplicate characters with O(N) time complexity.
Longest Substring without duplicate character


public class LongestSubString {

 public static void main(String[] args) {

  String mainStr = "JavaDiscover";

  String longSubStr = longSubString(mainStr);

  System.out.println("ORIGINAL STRING    ::: " + mainStr);
  System.out.println("LONGEST SUB STRING ::: " + longSubStr);
 }

 public static String longSubString(String mainStr) {

  String longStr = "";
  String tmp = "";

  char[] charArray = mainStr.toCharArray();

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

   if (tmp.contains(charArray[i] + "")) {

    if (longStr.length() < tmp.length()) {
     longStr = tmp;
    }

    tmp = tmp.substring((tmp.indexOf(charArray[i]) + 1), tmp.length());
    tmp = tmp + charArray[i];

   } else {
    tmp = tmp + charArray[i];
   }
  }

  if (longStr.length() < tmp.length()) {
   longStr = tmp;
  }

  return longStr;
 }
}


OUTPUT:



ORIGINAL STRING    ::: JavaDiscover
LONGEST SUB STRING ::: aDiscover

Java Interview Questions - 10

Below are the few set of java interview questions to get more knowledge on core java basics. For most of the questioned we need to find the output and for few questions have to get any compile time error or run-time error??

QUESTION - 1 - Output ??

public class ArrayTest {

 public static void main(String[] args) {
  
  int[] arr = {1,2,3,4};
  myMethod(arr[1], arr);
  System.out.println(arr[1] +" : "+arr[2]);
 }
 
 static void myMethod(int val, int arr[]){
  arr[val] = 100;
  val = 500;
 }
}



QUESTION - 2 - Output ??

import java.util.ArrayList;
import java.util.Collection;

public class CollectionTest {

 public static void main(String[] args) {
  Collection<Object> coll = new ArrayList<Object>();
  myMethod(coll, "java");
  myMethod(coll, 123);
 }
 
 static void myMethod(Collection<Object> coll, Object val){
  coll.add(val);
  System.out.println(coll);
 }
}



QUESTION - 3 - Output ??

public class DoubleNumberTest<D extends Number> {

 private D d;
 
 public DoubleNumberTest(D d) {
  this.d = d;
 }
 
 public double getDouble(){
  return d.doubleValue();
 }
 
 public static void main(String[] args) {
  DoubleNumberTest<Integer> obj = new DoubleNumberTest<Integer>(new Integer(24));
  System.out.println(obj.getDouble());
 }
}



QUESTION - 4 - Will it compile without any error ?

public class EnumTest {

 public EnumTest() {
  System.out.println("Inside Constructor");
  enumList();
 }
 
 public void enumList(){
  public enum myEnum {HIGH, MEDIUM, LOW}
 }
 
 public static void main(String[] args) {
  new EnumTest();
 }
}



QUESTION - 5 - Will it compile without any error ?

public class ExceptionTest {

 public static void main(String[] args) {
  
  try{
   int val = 1000;
   val = val / 0;
  
  }catch(Exception e){
   e.printStackTrace();
  
  }catch (ArithmeticException e) {
   e.printStackTrace();
  }
 }
}



QUESTION - 6 - Output ??

class Parent{
 int val = 100;
 
 public void myMethod(){
  System.out.print("Im Parent");
 }
}

class Child extends Parent{
 int val = 200;
 
 public void myMethod(){
  System.out.print("Im Child");
 }
}

public class Inheritance1Test {
 
 public static void main(String[] args) {
  
  Parent obj = new Child();
  System.out.print(obj.val+", ");
  obj.myMethod();
 }
}



QUESTION - 7 - Output ??

class Class1{
 public Class1() {
  System.out.println("Inside Class1");
 }
}

class Class2{
 public Class2() {
  System.out.println("Inside Class2");
 }
}

class Class3{
 public Class3() {
  System.out.println("Inside Class3");
 }
}

public class InheritanceTest {

 public static void main(String[] args) {
  new Class3();
 }
}



QUESTION - 8 - Will it serialize ??

import java.io.Serializable;

class Car implements Serializable{
 
}

class Colors {
 private String color;
 public Colors(String color) {
  this.color = color;
 }
}

public class SerializableTest implements Serializable {

 private Car car;
 private Colors[] colors = new Colors[4];
 
 public SerializableTest() {
  car = new Car();
  colors[0] = new Colors("red");
  colors[1] = new Colors("blue");
  colors[2] = new Colors("white");
  colors[3] = new Colors("black");
 }
 
 public static void main(String[] args) {
  
  /*
   * If we serialize obj, will Colors class also get Serializable ??
   */
  SerializableTest obj = new SerializableTest();
  
 }
}



QUESTION - 9 - Output ??

import java.util.HashSet;
import java.util.Set;

public class SetTest {

 public static void main(String[] args) {
  
  Set mySet1 = new HashSet();
  Set mySet2 = new HashSet();
  
  int j = 0;
  short i = 0;
  
  for(;i<100;i++,j++){
  
   mySet1.add(i);
   mySet1.remove(i-1);
   
   mySet2.add(j);
   mySet2.remove(j-1);   
  }  
  System.out.println("Int Set Size   : "+mySet1.size());
  System.out.println("Short Set Size : "+mySet2.size());
 }
}



QUESTION - 10 - Output ??

public class StringCompare {

 public static void main(String[] args) {
  
  String s1 = "java";
  String s2 = s1.intern();
  
  if(s1.equals(s1) && s1 == s2){
   System.out.println("first");
  }
  if(s1.equals(s1) && s1 != s2){
   System.out.println("second");   
  }
  if(!s1.equals(s1) && s1 == s2){
   System.out.println("third");
  }
  if(!s1.equals(s1) && s1 != s2){
   System.out.println("fourth");
  }
 } 
}



QUESTION - 11 - Will it compile without any error ?

public class StringMethod {

 private void myMethod(String str){
  System.out.println("Inside String method");
 }
 
 private void myMethod(StringBuilder str){
  System.out.println("Inside StringBuilder method");
 }
 
 private void myMethod(StringBuffer str){
  System.out.println("Inside StringBuffer method");
 }
 
 public static void main(String[] args) {
  new StringMethod().myMethod(null);
 }
}



QUESTION - 12 - Output ??

public class Thread1Test extends Thread {

 @Override
 public void run() {
  System.out.println("Inside run");
 }
 
 public static void main(String[] args) {
  Thread thread = new Thread(new ThreadTest());
  thread.start();
  thread.start();
 }
}



QUESTION - 13 - Output ??

public class ThreadTest extends Thread {

 @Override
 public void run() {
  System.out.println("Inside run");
 }
 
 public static void main(String[] args) {
  Thread thread = new Thread(new ThreadTest());
  thread.start();
  try {
   thread.join();
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
 }
}



QUESTION - 14 - Output ??

public class TwoDArrayTest {

 public static void main(String[] args) {
  
  int[][] val = {{1,2,3}, {4,5,6}};
  int[][] valClone = val.clone();
  
  valClone[0][0] = 100;
  System.out.println(val[0][0]);
  System.out.println(valClone[0][0]);
  
  valClone[1] = new int[]{111, 222, 333};
  System.out.println(val[1][1]);
  System.out.println(valClone[1][1]);
 }
}



QUESTION - 15 - Output ??

import java.util.ArrayList;
import java.util.Collection;

public class ValueOfTest {

 public static void main(String[] args) {
  
  myMethod(new ArrayList<Object>());
  
 }
 
 public static void myMethod(Collection<Object> coll){
  
  Number n = null;
  coll.add(n);
  coll.add(Integer.valueOf(100));
  coll.add(Float.valueOf(200));
  
  System.out.println(new ArrayList<Object>().addAll(coll));
 }
}


ANSWERS:

1. 2 : 100

2.  [java]
     [java, 123]

3. 24.0

4. Compilation error - The member enum myEnum can only be defined inside a top-level class or interface or in a static context

5. Compilation error - Unreachable catch block for ArithmeticException. It is already handled by the catch block for Exception

6. 100, Im Child

7. Inside Class3

8. Won't serialize and we will get "java.io.NotSerializableException" when we access Color class

9. Int Set Size   : 100
    Short Set Size : 1

10. first

11. Compilation error - The method myMethod(String) is ambiguous for the type StringMethod

12. Prints "Inside run" and "IllegalThreadStateException" while starting thread again.

13. Inside run

14.  100
       100
       5
       222

15. true