Swapping two numbers without using temporary variable

Very basic interview question : Swap two variables without using third or temporary variables.  This serves the purpose of getting started with the interview. There are 3 ways to do this and we will discus all of them now

1. Addition
2. XOR operation(bitwise operator)
3. Multiplication

By Addition

/**

 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/12/13
 * Time: 8:20 PM
 */
public class VariableSwapper {
    public static void main(String args[]){
        int a = 4;
        int b = 5;
        System.out.println("***** Swapping using Addition *****");
        System.out.println("Before Swapping a : " + a);
        System.out.println("Before Swapping b : " + b);
        a = a + b;
        b = a - b;
        a = a - b;
        System.out.println("After Swapping a : " + a);
        System.out.println("After Swapping b : " + b);
    }

}

By XOR operation

 /**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/12/13
 * Time: 8:20 PM
 */
public class VariableSwapper {

    public static void main(String args[]){

        int a = 4;
        int b = 5;
        System.out.println("***** Swapping using XOR *****");
        System.out.println("Before Swapping a : " + a);
        System.out.println("Before Swapping b : " + b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("After Swapping a : " + a);
        System.out.println("After Swapping b : " + b);

    }

}

By Multiplication

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/12/13
 * Time: 8:20 PM
 */
public class VariableSwapper {

    public static void main(String args[]){

        int a = 4;
        int b = 5;

        System.out.println("***** Swapping using Multiplication *****");

        System.out.println("Before Swapping a : " + a);
        System.out.println("Before Swapping b : " + b);

        a = a * b;
        b = a / b;
        a = a / b;

        System.out.println("After Swapping a : " + a);
        System.out.println("After Swapping b : " + b);

    }

}

Output remains the same except printing the method part.

***** Swapping using Multiplication *****
Before Swapping a : 4
Before Swapping b : 5
After Swapping a : 5
After Swapping b : 4 

XOR logic can be better understood with following diagram

Binary Tree Traversal

Background

You must have heard of binary trees. Nothing special about it. Each node has two nodes(right and left). One of the most common interview questions is traversing the tree. There are three common types of traversals -

1. Pre Order (Root - Left - Right)
2. In Order (Left - Root - Right)
3. Post Order (Left - Right - Root)

 We are going to first write code for the data structure that forms the Node which is used further to build the tree. Node class code goes something like below

package in.blogspot.osg.Demo;

public class Node {

    private String data;
    private Node left;
    private Node right;

    public String getData() {
        return data;
    }
    public void setData(String data) {
        this.data = data;
    }
    public Node(String data){
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }

}

Very simple. In this node structure we have String data and two nodes right and left. We have corresponding getters and setters. Note that data,right and left are instance variables and are assigned default values(null is our case).

Not Lets us build one tree and print various traversals.

package in.blogspot.osg.Demo;

public class MainRun {

    public static void main(String args[]){

        Node root = new Node("Aniket");

        root.setLeft(new Node("Amit"));
        root.setRight(new Node("Anubhav"));

        root.getLeft().setLeft(new Node("Sam"));
        root.getLeft().setRight(new Node("Ram"));

        root.getRight().setLeft(new Node("John"));
        root.getRight().setRight(new Node("Mark"));

        System.out.println("Printing Pre Order Traversal");
        PreOrder.printPreOrder(root);
        System.out.println("**********");
        
        System.out.println("Printing Post Order Traversal");
        PostOrder.printPostOrder(root);
        System.out.println("**********");
        
        System.out.println("Printing In Order Traversal");
        InOrder.printInOrder(root);
        System.out.println("**********");

    }

}

Above tree could be visualize as follows -

Now lets see our actual traversal logic. They are divided into 3 separate classes and each have it's own static method with corresponding logic.

Pre Order

package in.blogspot.osg.Demo;

public class PreOrder {

    /**
     * PreOrder : root-left-right
     * @param root
     */
    public static void printPreOrder(Node root){
        System.out.println("Value : " + root.getData());
        if(root.getLeft() != null){
            printPreOrder(root.getLeft());
        }
        if(root.getRight() != null){
            printPreOrder(root.getRight());
        }
    }
}

Post Order

package in.blogspot.osg.Demo;

public class PostOrder {
    
    /**
     * PostOrder : left-right-root
     * @param node
     */
    public static void printPostOrder(Node root){
       
        if(root.getLeft() != null){
            printPostOrder(root.getLeft());
        }
        if(root.getRight() != null){
            printPostOrder(root.getRight());
        }
        System.out.println("Value : " + root.getData());
    }
}

In Order

package in.blogspot.osg.Demo;

public class InOrder {
    
    /**
     * InOrder : left-root-right
     * @param root
     */
    public static void printInOrder(Node root){
        if(root.getLeft() != null){
            printInOrder(root.getLeft());
        }
        System.out.println("Value : " + root.getData());
        if(root.getRight() != null){
            printInOrder(root.getRight());
        }   
    }
}

Output for the same is

Output : 

Printing Pre Order Traversal
Value : Aniket
Value : Amit
Value : Sam
Value : Ram
Value : Anubhav
Value : John
Value : Mark
**********
Printing Post Order Traversal
Value : Sam
Value : Ram
Value : Amit
Value : John
Value : Mark
Value : Anubhav
Value : Aniket
**********
Printing In Order Traversal
Value : Sam
Value : Amit
Value : Ram
Value : Aniket
Value : John
Value : Anubhav
Value : Mark
**********

Level Order

Leaving the above three types of traversal there is one more type of traversal called level traversal in which we visit all nodes on the same level from left to right before moving on to the next level.

Code for Level traversal goes something like below - 

We need to use queue data structure for this

public class LevelTraversal {

    static Queue<Node> levelQueue = new LinkedList<Node>();

    public static void printLeveltraversal(Node root){

        System.out.println("Value : " + root.getData());

        if(root.getLeft() != null){
            levelQueue.offer(root.getLeft());
        }
        if(root.getRight() != null){
            levelQueue.offer(root.getRight());
        }

        if(levelQueue.size() != 0){
            printLeveltraversal(levelQueue.poll());
        }
    }

}

You can call this function from the same main we defined above output would be as follows

Output : 

Level order Traversal
Value : Aniket
Value : Amit
Value : Anubhav
Value : Sam
Value : Ram
Value : John
Value : Mark

You can uniquely derive the original binary tree give it's

1. Pre order and in order traversal
2. Post order and in order traversal

But you cannot determine a unique binary tree with just it's Pre ordee and  Post order traversals. However if you have the constraint that each internal node has both two children then you can very well find the original tree with above data.

Related Links

• Iterative binary tree traversal (OSFG)
• DataStructure git repository 
• Print binary tree in Spiral order (OSFG) 

FIFO based Queue implementation in Java

We know we have java.util.Stack as a data structure in Java. It has standard functions like pop(), push(), peek(). But  ever wondered what is analog for Queue in Java?

If you search for Queue class in java then you will wind such an interface java.util package.

public interface Queue<E> extends Collection<E>

And if you check classes implementing this interface you will find LinkedList in it. Yes LinkedList in java can be used for FIFO operations.  Actually LinkedList implements Deque which inturn implements Queue. If you see functions in Queue interface they are as follows -

1. element(): This method retrieves the head of the queue.
2. offer(E o): This inserts the specified element into the queue.
3. peek(): This method retrieves the head of this queue, returning null if this queue is empty.
4. poll(): This method retrieves and removes the head of this queue, or return null if this queue is empty.
5. remove(): This method retrieves and removes the head of this queue.

 Lets understand this better with a code -

Code -

import java.util.LinkedList;
import java.util.Queue;

public class FIFOTest {
    
    public static void main(String args[]){
        
        Queue<String> myQueue = new LinkedList<String>();
        myQueue.add("US");
        myQueue.add("Russia");
        myQueue.add("India");
        myQueue.offer("Canada");
        
        for(String element : myQueue){
            System.out.println("Element : " + element);
        }
        
        System.out.println("Queue : " + myQueue);
        System.out.println(myQueue.peek());
        System.out.println("After peek : " + myQueue);
        System.out.println(myQueue.poll());
        System.out.println("After poll : " + myQueue);
        System.out.println(myQueue.remove());
        System.out.println("After remove : " + myQueue);
            
    }
}

Output - 

Element : US
Element : Russia
Element : India
Element : Canada
Queue : [US, Russia, India, Canada]
US
After peek : [US, Russia, India, Canada]
US
After poll : [Russia, India, Canada]
Russia
After remove : [India, Canada]

Note : From usability point of view add() and offer() do the same thing. Same goes for poll() and remove().

Basic operations with Bitwise operators

Not a Java question as such but a more generic information that would be useful. Most of the interview questions consist of manipulations of bitwise operators. Some basic operations are listed below -

• OR can be used to set a bit to one: 11101010 OR 00000100 = 11101110
• AND can be used to set a bit to zero: 11101010 AND 11111101 = 11101000
• AND together with zero-testing can be used to determine if a bit is set:

11101010 AND 00000001 = 00000000 = 0

11101010 AND 00000010 = 00000010 ≠ 0

• XOR can be used to invert or toggle a bit:

11101010 XOR 00000100 = 11101110

11101110 XOR 00000100 = 11101010

• NOT can be used to invert all bits.

NOT 10110010 = 01001101

Find GCD of two numbers in Java?

Code :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 6/12/13
 * Time: 4:46 PM
 * To change this template use File | Settings | File Templates.
 */
public class GCDFinder {

    public static int gcd(int a,int b){
        int temp = a % b;
        if(temp == 0)
            return b;
        else
            return gcd(b,temp);
        }

    public static void main(String args[]){
        System.out.println("GCD of 12 and 10 is : " + gcd(12,10));
    }
}

Output :

GCD of 12 and 10 is : 2

Note : You can calculate LCM as Number1*Number2/GCD