Given a range find how many numbers occur within it.

You are receiving a continuous stream of numbers, at any point i'll provide a range eg: 5- 15 and the output should be the number of numbers between 5-15.

P.S. - Since the input is a stream the output can change for the same range if the function is called again.

Design and optimal LRU Cache

Please look at here for problem description and solution/architecture details.


Files Present
----------------

1.  Top Level Directory
2.  Doubly Linked List Implementation Using Generics
3. LRU Cache Implementation Using Generics of JAVA 5
4. CleanupThread Implementation from SOFTCache

an array contain +ve and -ve element, find subarray whose sum =0;

an array contain +ve and -ve element, find subarray whose sum =0;

Lets take input array as a[]={-3,2,4,-6,-8,10,11}

Puzzle/Aglo available is posted here 

Working JAVA Code
---------------------------

import java.util.Comparator;


public class Index implements Comparable{
Integer start;
Integer end;
public Integer getStart() {
    return start;
}
public void setStart(Integer start) {
    this.start = start;
}
public Integer getEnd() {
    return end;
}
public void setEnd(Integer end) {
    this.end = end;
}


public int compareTo(Object index1) {
 
    index1 = (Index) index1;
    Index index2 = (Index) this;
    Integer  index1Distance = ((Index) index1).getEnd().intValue() -  ((Index) index1).getStart().intValue();
    Integer index2Distance = ((Index) index2).getEnd().intValue() -  ((Index) index2).getStart().intValue();
    if (index1Distance > index2Distance)
        return 1;
    else if (index1Distance == index2Distance)
        return 0;
    else
        return -1;
}
}

import java.util.HashMap;
import java.util.Map;


public class SubarraywithSumZero {

    public Index findLongestSubArraywithSumZero(long[] inputArray) {
        // 1. Generate a cummulative array
        for (int i=1; i < inputArray.length; i++) {
            inputArray[i] += inputArray[ (i-1)];
        }
        //2. Read the array, store it in map
        // For a subraary with 0 there should + and - numbers
        // we need to figure the longest distance indexes which have same numbers
        // since our array is cummulative postives and negatives which sum to 0 will bring the
        // intermittent array back to same number where it started
        // eg intermittent array = -6, -8, -10, -6, -4, 1, 2, 3, 4, 1
        // now from -6 we again reach -6
        // and later from 1 back to 1 which implies these two arrays are summing to 0
        // we just need the longest one
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        Index maxIndex = null;
        for (int i=0; i < inputArray.length; i++) {
            Integer index = new Integer(i);
            Integer val = new Integer((int) inputArray[i]);
            if (indexMap.get(val) == null) {
                indexMap.put(val, index);
            }
            else {
                if (maxIndex == null) {
                    maxIndex = new Index();
                    //collosion found the subarray
                    maxIndex.setStart(indexMap.get(val));
                    maxIndex.setEnd(new Integer(i));
                }
                else  {
                    Index index1 = new Index();
                    index1.setStart(indexMap.get(val));
                    index1.setEnd(new Integer(i));
                    if (maxIndex.compareTo(index1) <= 0) {
                        maxIndex = index1;
                    }
                }
            }
        }
            return maxIndex;       
    }
   
    public static void main(String[] args) {
        long inputArray[] = {3,2,4,-6,-8,10,11};
       
        SubarraywithSumZero subarraywithSumZero = new SubarraywithSumZero();
        Index maxIndex = subarraywithSumZero.findLongestSubArraywithSumZero(inputArray);
        System.out.println("Longgest Subarray with sum starts at [" + maxIndex.getStart() + " ] and ends at [" + maxIndex.getEnd() + "]");
    }
}

Find duplicates in a array of elements

You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Actual Algorithm is documented at - http://inder-gnu.blogspot.com/2010/11/find-duplicates-in-array-of-elements.html


Working Java Code -


//You are given an array of elements. Some/all of them are duplicates.
//Find them in 0(n) time and 0(1) space. Property of inputs -
//Number are in the range of 1..n where n is the limit of the array.
public class FindDupsInLinearTime {

    /* Algorithm in English
     * 1. Read input from startPos
     * 2. If input is within the maxRange or it's not in correct place then it's a candidate to be replaced else incrementStartPos
     * 3. finalPosition for input is input[i]
     * 4. if finalPosition < maxRange then swap input with finalPosition and increment finalPosition with MaxRange
     * 5. else no need to swap as previous instances of this element are recorded at finalPos so just increment finalPosition with MaxRange to record another instance
     * 6. if input at startPos is in correct place or reached zero then increment startPos++ till you go through end of Array
     * 7. Iterate through the array and divide each element with maxRange. The divisor indicates how many times a element was repeated and 0 indicates a missing element
     */
    public static void main(String[] args) {
        int[] inputArr = {0, 4, 3, 4, 1};
        findDuplicates(inputArr, 4);
        printDuplicatesAndMissingElements(inputArr);
        int[] inputArr1 = {0, 2, 3, 4, 3, 2};
        findDuplicates(inputArr1, 5);
        printDuplicatesAndMissingElements(inputArr1);
    }

    private static void findDuplicates(int[] inputArr, int maxRange) {
        // for simplicity reasons we will assume nothing is there in 0 index of array
        // and start from 1
        int i = 1;
        int maxArrLength = inputArr.length;
       
        while(true) {
            if ( i > maxArrLength - 1)
                break;
           
            int finalPos = inputArr[i];
            System.out.println(" Read :: " + inputArr[i]);
           
            if (finalPos > maxRange) {
                //this element is already in final position skip and move further looking for elements within maxRange
                i++;
                continue;
            }
            int finalPosElement = inputArr[inputArr[i]];
            int startPos = i;
            int startPosElement = inputArr[i];
           
            // if startPos element isn't in place and it's within the maxRange..
            // then candidate for swap or reaching final pos...
            if (inputArr[startPos] != i ||
                    inputArr[startPos] <= maxRange) {

                if (finalPosElement > maxRange) {
                    // if finalposElement > maxRange then no swapping required
                    // just add maxRange to denote multiple entry
                    inputArr[finalPos] += maxRange;   
                    //make startPosElement as 0
                    inputArr[startPos] = 0;
                    System.out.println("No swapping required incemented " + inputArr[finalPos] );
                }
                else {
                    //swap
                    int temp = startPosElement;
                    inputArr[startPos] = finalPosElement;
                    inputArr[finalPos] = temp + maxRange;
                    System.out.println("Swapped : " + startPosElement + " with " +finalPosElement);
                }
            }
            printArray(inputArr);
            // if the element in current evaluated position isn't still correct repeat the above again
            if (inputArr[startPos] == i ||
                     
                    inputArr[startPos] > maxRange) {
                System.out.println(" Read :: "+ inputArr[startPos] + " it's already in place");
                inputArr[startPos] += maxRange;
                i++;
            }
            else if (inputArr[startPos] == 0){
                i++;
                continue;
            }
            else {
                continue;
            }
               
        }
       
    }
   
    private static void printArray(int[] inputArr) {
        for (int i=1; i < inputArr.length; i++) {
            System.out.print(inputArr[i] +",");
        }
        System.out.println("");
    }
    private static void printDuplicatesAndMissingElements(int[] inputArr) {
        int maxRange = inputArr.length;
        for (int i=1; i < inputArr.length; i++) {
            if (inputArr[i] == 0) {
                System.out.println(" Element [" + i + "] is missing");
            }
            int input = inputArr[i];
            int mod = input / maxRange;
            if ( mod > 1) {
                System.out.println (" Element [" + i + "] is repeated + [" + mod + "] times");
               
            }
        }
    }

   
}