[Amazon interview question] Implement data structure overflow queue.

Implement data structure overflow queue. Overflow queue is a normal queue with one extra property. It never throw Stack overflow exception. So whenever queue becomes full, it replaces the oldest element present in the queue and front pointer simply shifted one step ahead. Constraint:- it should have public void enQueue(int n) and public int deQueue() methods of time complexity O(1) The implementation should be optimum and clean.

public class OverflowQueue {
    private int[] queue;
    private int front = -1, rear = -1;

    public OverflowQueue(int size) {
        queue = new int[size];
    }

    public void enQueue(int n){
        rear = getNextIndex(rear);
        queue[rear] = n;
         if (rear == front || front == -1){
          front = getNextIndex(front);
        }

    }

    private int getNextIndex(int index){
        if (index == queue.length - 1 ){
            index = 0;
        } else {
            index ++ ;
        }
        return index;
    }

    public int deQueue(){
        if (front == -1 ){
           throw new NullPointerException("deQueue operation is called on empty queue.");
        }
        int elem = queue[front];
        if (front == rear ){
            front = -1;
            rear = -1;
        } else {
            front = getNextIndex(front);
        }
        return elem;
    }

    public static void main(String[] args) {
        OverflowQueue q = new OverflowQueue(5);
        q.enQueue(1);q.enQueue(2);q.enQueue(3);
        q.enQueue(4);q.enQueue(5);q.enQueue(6);
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
    }
}

Please leave comments.

[Amazon interview question] A character array of arbitary length with 'R', 'B', 'W' is needed to be sorted in that order.

There is char array of n length. Array can have elements only from of any order R, B, W. You need to sort array so that order should R,B,W i.e. all R will come first followed by B and then W.
Constraints: Time complexity is O(n) and space complexity should be O(1)
Assumption: You can assume one swap method is given with signature swap(int index1, int index2) that swaps number in unit time.
method given to implement: public sort(char[]array);

    public static void sort(char[] arr){
        int rIndex = 0, wIndex = arr.length -1;
        for (int i = 0 ; i <= wIndex; ){
            if ( arr[i] == 'R' ){
                swap(arr, i , rIndex ++ );
                i ++ ;
            } else if (arr[i] == 'W' ){
                swap(arr, i , wIndex -- );
            }else{
             i ++;
            }
        }
    }
    //a dummy implementation just for testing sake
    private static void swap(char[] arr, int index1, int index2){
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

Please leave your comments and suggestions that improves the logic above.

[Amazon interview Question] Calculate the weight of of binary tree path from root to leaf node in such a way that it would be equal to N

You have a binary tree (no BST etc, a simple binary tree). A number N will be given to you, you have to find out, whether path from root node to leaf node exists in such a way so that sum of all node's data in that path is equal to N. For example for given binary tree

           1

     2              3

 4       5      6           7

      3                           8
                             9

If value of N is 11 then path - 1 2 5 3 which is root node to left node 3 sums up to 11 hence for this tree method should return true.
Constraints: Time complexity is O(n) and space complexity should be O(1)
Method to implement : public boolean isSumTree(Node root, int N);

static class Node{
        int data;
        Node left;
        Node right;
    }
    public static boolean isSumTree(Node root, int N){
        if (root.left == null && root.right == null ){
            return root.data == N;
        }
        boolean leftResult = root.left != null && isSumTree(root.left, N - root.data );
        boolean rightResult = root.right != null && isSumTree(root.right, N - root.data );
        return leftResult || rightResult;
    }

Please leave your valuable comments to improve my answer.

Shortest Path between 2 points

Write a java program to find the shortest path from point A to point B in a maze.

Maze:

- The maze is represented by a 2-dimensional array of 1's and 0's

- 0 represent that user can traverse a path

- 1 represents that user cannot traverse path

- User can move only horizontal and vertical

Input: PointA, PointB, Maze Details

Output: Shortest Path

Sample Input:

PointA = 0,1

PointB = 2,3

Number of Rows in Maze = 5

Number of Columns in Maze = 5

Maze Co-ordinates = 1 0 1 1 1

1 0 1 0 0

1 0 0 0 1

1 0 1 1 1

0 1 1 1 1

1	0	1	1	1
1	0	1	0	0
1	0	0	0	1
1	0	1	1	1
0	1	1	1	1

Sample Output (Shortest Path):

1,0; 1,1; 1,2; 2,2; 2,3

Here is the program for the above. I took approach of breadth first search. Here is the algorithm for this. 
1. create a queue and push source point 
2. pop up element from queue and find out all of it's unvisited neighbors. 
3. if destination point found then back track them to the source and exit else mark the popped element visited and go to step 3. 
4. exit the queue if queue doesn't have any element. In this case destination can not be found given source. 

Here is the code. Point class that will represent each point within maze.

package com.adnan.shortestPath;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/21/13
 * Time  : 4:49 PM
 */
public class Point {

    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Point){
            Point point = (Point) o;
            if ( point.getY() == this.getY()
                    && point.getX() == this.getX()) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

Shortest path calculator service, this has main business logic to find out shortest path.

package com.adnan.shortestPath;

import java.util.*;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/21/13
 * Time  : 4:36 PM
 */
public class ShortestPathCalculator {

    private static final ShortestPathCalculator calculator
 = new ShortestPathCalculator();
    private ShortestPathCalculator(){}
    private static final int PATH = 0;

    public static ShortestPathCalculator getInstance(){
        return calculator;
    }

    private class WeightedPoint {
        private Point point;
        private WeightedPoint parentPoint;
        private WeightedPoint(Point point, 
WeightedPoint parentPoint) {
            this.point = point;
            this.parentPoint = parentPoint;
        }
    }

    public Stack getShortestPath(int[][] maze, Point pointA, 
Point pointB){
        Queue queue = new LinkedList<>();
        queue.add(new WeightedPoint(pointA, null));

        WeightedPoint pointBWeightPoint = null;
        Set pointTransversed = new HashSet<>();
        pointTransversed.add(pointA);
        while ( ! queue.isEmpty() )  {
            WeightedPoint curr = queue.poll();
            Set neighbors = 
getAllNeighborsNotAlreadyTraversed(maze, curr, pointTransversed);
            pointTransversed.addAll(neighbors);
            if (neighbors.contains(pointB)){
                pointBWeightPoint = 
new WeightedPoint(pointB, curr);
                break;
            }
          queue.addAll(covertToWeightedPoint(neighbors, curr));
        }
        throwExceptionIfPathNotFound(pointBWeightPoint);
        return prepareResultStack(pointBWeightPoint);
    }

  private Collection covertToWeightedPoint
(Collection neighbors,WeightedPoint current) {
        Collection collection = new HashSet<>();
        for (Point point : neighbors ){
            collection.add(new WeightedPoint(point, current));
        }
        return collection;
    }

    private void throwExceptionIfPathNotFound
(WeightedPoint pointBWeightPoint) {
        if ( pointBWeightPoint == null ){
            throw new NoPathFoundException();
        }
    }

    private Stack prepareResultStack
(WeightedPoint pointBWeightPoint) {
        Stack stack =  new Stack<>();
        while (pointBWeightPoint != null ){
            stack.push(pointBWeightPoint.point);
            pointBWeightPoint = pointBWeightPoint.parentPoint;
        }
        return stack;
    }

   private Set getAllNeighborsNotAlreadyTraversed(int[][] maze, 
WeightedPoint currWeightedPoint, Set pointTraversed) {
        Set neighbors = new HashSet<>();
        Point currPoint = currWeightedPoint.point;
        Point upperPoint = getUpperPoint(maze, currPoint);
        updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
 upperPoint, pointTraversed);
        Point lowerPoint = getLowerPoint(maze, currPoint);
        updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
 lowerPoint, pointTraversed);
        Point rightPoint = getRightPoint(maze, currPoint);
        updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
 rightPoint, pointTraversed);
        Point leftPoint = getLeftPoint(maze, currPoint);
        updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
 leftPoint, pointTraversed);
        return neighbors;
    }

    private void updateNeighborIfPointNotNullAndNotPresentInSet(
Set neighbors,Point point, Set pointTraversed) {
        if (point != null && ! pointTraversed.contains(point) ){
            neighbors.add(point);
        }
    }

    private Point getLeftPoint(int[][] maze, Point currPoint) {
        int yMinus1 = currPoint.getY() - 1;
        if (yMinus1 >= 0 
&& maze[currPoint.getX()][yMinus1] == PATH  ){
            return new Point(currPoint.getX(), yMinus1);
        }
        return null;
    }

    private Point getRightPoint(int[][] maze, Point currPoint) {
        int totalColumns = maze[0].length;
        int yPlus1 = currPoint.getY() + 1;
        if (yPlus1 < totalColumns 
&& maze[currPoint.getX()][yPlus1] == PATH  ){
            return new Point(currPoint.getX(), yPlus1);
        }
        return null;
    }

    private Point getLowerPoint(int[][] maze, Point currPoint) {
        int xMinus1 = currPoint.getX() - 1;
        if (xMinus1 >= 0  
&& maze[xMinus1][currPoint.getY()] == PATH ){
            return new Point(xMinus1, currPoint.getY());
        }
        return null;
    }

    private Point getUpperPoint(int[][] maze, Point currPoint) {
        int totalRows = maze.length;
        int xPlus1 = currPoint.getX() + 1;
        if (xPlus1 < totalRows 
&& maze[xPlus1][currPoint.getY()] == PATH ){
            return new Point(xPlus1, currPoint.getY());
        }
        return null;
    }

}

A runtime exception to be thrown when path not found

package com.adnan.shortestPath;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/22/13
 * Time  : 12:13 AM
 */
public class NoPathFoundException extends RuntimeException {

}

And how can I forget to write test case since I follow test driven development. I could have pasted test code first ;-)

package com.adnan.shortestPath;

import org.junit.Test;

import java.util.Stack;

import static org.junit.Assert.assertTrue;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/21/13
 * Time  : 4:53 PM
 */
public class ShortestPathCalculatorTest {

    private ShortestPathCalculator calculator = 
ShortestPathCalculator.getInstance();

    @Test
    public void test_shortestPath() throws Exception {
        int[][] maze = {
                {1, 0, 1, 1, 1 },

                {1, 0, 1, 0, 0 },

                {1, 0, 0, 0, 1 },

                {1, 0, 1, 1, 1 },

                {0, 1, 1, 1, 1 }
        };
        Stack stack = 
calculator.getShortestPath(maze, new Point(0, 1) , new Point(2, 3));
        assertTrue(stack.size() == 5);
        Point point = stack.pop();
        assertTrue(point.getX() == 0 &&point.getY()==1);//0, 1
        point = stack.pop();
        assertTrue(point.getX() == 1 &&point.getY()==1);//1,1
        point = stack.pop();
        assertTrue(point.getX() == 2 &&point.getY()==1);//2,1
        point = stack.pop();
        assertTrue(point.getX() == 2 &&point.getY()==2);//2,2
        point = stack.pop();
        assertTrue(point.getX() == 2 &&point.getY()==3);//2,3
    }

    @Test(expected = NoPathFoundException.class)
    public void 
test_shortestPath_whenSourceDoesNotMatchWithDestination() 
throws Exception {
        int[][] maze = {
                {1, 0, 1, 1, 1 },

                {1, 0, 1, 0, 0 },

                {1, 0, 0, 0, 1 },

                {1, 0, 1, 1, 1 },

                {0, 1, 1, 1, 1 }
        };
      calculator.getShortestPath(maze, new Point(0, 1) , 
new Point(0, 4));

    }
}

Please give your precious comments and suggestions. I would be more than happy to have them.

Reverse linked list without using any extra space.

Linked list reversal I found very common question asked in many companies. One of the easy way to implement this is, using stack and traversing whole singly linked list and dumping into stack. One list linked list finishes, start poping up and preparing new linked list. Problem gets interesting when we are not suppose to use any extra space like stack or another linked list. Here is the implementation of such. I am using java to implement this and approach is test driven development hence test cases are also attached.
The Node class that represent single node -

package com.adnan.linkedlist;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/21/13
 * Time  : 12:02 PM
 */
public class Node {

    public Node(int value, Node node){
        this.value = value;
        this.node = node;
    }
    private int value;
    private Node node;

    public int getValue() {
        return value;
    }

    public Node getNode() {
        return node;
    }

    public void setNode(Node node){
        this.node = node;
    }
}

Service class that takes start node as input and reserve it without using extra space.

package com.adnan.linkedlist;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/21/13
 * Time  : 11:54 AM
 */
public class SinglyLinkedListReversal {

    private static final SinglyLinkedListReversal service 
= new SinglyLinkedListReversal();
    public static SinglyLinkedListReversal getService(){
        return service;
    }



    public Node reverse(Node start){
        if (hasOnlyNodeInLinkedList(start)){
            return start;
        }
        Node firstNode, secondNode, thirdNode;
        firstNode = start;
        secondNode = firstNode.getNode();
        while (secondNode != null ){
            thirdNode = secondNode.getNode();
            secondNode.setNode(firstNode);
            firstNode = secondNode;
            secondNode = thirdNode;
        }
        start.setNode(null);
        return firstNode;
    }

    private boolean hasOnlyNodeInLinkedList(Node start) {
        return start.getNode() == null;
    }


}


  

Another logic of reversal could be a recursive approach. So replace reverse method of above class by below and it should return result in recursive manner.

 public Node reverseRecursively(Node start){
     if (start == null ){
         return null;
     }
     Node lastNode;
     if (start.getNode() == null ){
       lastNode = start;
     }else {
         lastNode = reverseRecursively(start.getNode());
         start.getNode().setNode(start);
         start.setNode(null);
     }
      return lastNode;
   }
  

And The test case that covers above scenario. Please note that you require junit jars. I am using testng.jar; you can use any whatever pleases you..

package com.adnan.linkedlist;

import org.testng.annotations.Test;

import static org.testng.AssertJUnit.assertTrue;

/**
 * User  : Adnan
 * Email : sendtoadnan@gmail.com
 * Date  : 9/21/13
 * Time  : 12:11 PM
 */
public class SinglyLinkedListReversalTest {

    private SinglyLinkedListReversal reversalService = 
SinglyLinkedListReversal.getService();

    @Test
    public void test_reverseSingleElement() throws Exception {
        Node node = new Node(1, null);
        reversalService.reverse(node);
        assertTrue(node.getNode() == null);
        assertTrue(node.getValue() == 1);
    }


    //original - Node1(1) -> Node2(2) -> Node3(3)
    //reverse - Node3(3) -> Node2(2) -> Node1(1)
    @Test
    public void test_reverseThreeElement() throws Exception {
        Node node3 = new Node(3, null);
        Node node2 = new Node(2, node3);
        Node start = new Node(1, node2);


        start = reversalService.reverse(start);
        Node test = start;
        for (int i = 3; i >=1 ; i -- ){
          assertTrue(test.getValue() == i);
            test = test.getNode();
        }


    }

    @Test
    public void test_reverseFourElement() throws Exception {
        Node node4 = new Node(4, null);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node start = new Node(1, node2);


        start = reversalService.reverse(start);
        Node test = start;
        for (int i = 4; i >=1 ; i -- ){
            assertTrue(test.getValue() == i);
            test = test.getNode();
        }
    }

        @Test
        public void test_reverse10Element() throws Exception {
            Node node10 = new Node(10, null);
            Node node9 = new Node(9, node10);
            Node node8 = new Node(8, node9);
            Node node7 = new Node(7, node8);
            Node node6 = new Node(6, node7);
            Node node5 = new Node(5, node6);
            Node node4 = new Node(4, node5);
            Node node3 = new Node(3, node4);
            Node node2 = new Node(2, node3);
            Node start = new Node(1, node2);


            start = reversalService.reverse(start);
            Node test = start;
            for (int i = 10; i >=1 ; i -- ){
                assertTrue(test.getValue() == i);
                test = test.getNode();
            }


    }

    @Test
    public void test_reverseTwoElement() throws Exception {
        Node node2 = new Node(2, null);
        Node start = new Node(1, node2);


        start = reversalService.reverse(start);
        Node test = start;
        for (int i = 2; i >=1 ; i -- ){
            assertTrue(test.getValue() == i);
            test = test.getNode();
        }


    }
}