Showing posts with label Linked List. Show all posts
Showing posts with label Linked List. Show all posts

Sunday, December 22, 2013

Find a number from sorted list where start and end of list is not known

Prob: find a number from a sorted list where start and end of list is not known. The moving pointer will rotate over from max to min and vice versa.

public class FindANumber {

    public int bTreeRotated(int A[], int start, int finish, int data) {
        int mid = start + (finish - start) / 2;
        if (start > finish) {
            return -1;
        }
        if (A[mid] == data) {
            return mid;
        } else if (A[start] <= A[mid]) {
            if (data >= A[start] && data <= A[mid]) {
                return bTreeRotated(A, start, mid - 1, data);
            } else {
                return bTreeRotated(A, mid + 1, finish, data);
            }
        } else //if(A[mid] <= A[finish]){
        if (data >= A[mid] && data <= A[finish]) {
            return bTreeRotated(A, mid + 1, finish, data);
        } else {
            return bTreeRotated(A, start, mid - 1, data);
        }
    }
 
    public static void main(String args[]){
        FindANumber fan = new FindANumber();
        int A[] = new int[]{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
        int res = fan.bTreeRotated(A, 0, 11, 5);
        if(res < 0)
            System.out.println("Not Found!!");
        else
            System.out.println("Fund at " + res);
     
    }
}

Saturday, December 21, 2013

Node & TNode Class declaration for Linked List & Tree

public class Node{
    int data;
    Node next;
    Node prev;
 
    Node(){
        data = 0;
        next = null;
        prev = null;
    }
 
    Node(int p){
        data = p;
        next = null;
        prev = null;
    }
}

public class TNode {

    int data;
    TNode left;
    TNode right;
    TNode parent;

    TNode() {
        data = -999999;
        left = null;
        right = null;
        parent = null;
    }

    TNode(int p) {
        data = p;
        left = null;
        right = null;
        parent = null;
    }
}