Pages

Tuesday, January 12, 2010

Circular list

PROBLEM: You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.

SOLUTION:  This is the most naive solution:

package google;

import java.util.Collections;
import java.util.LinkedList;

public class CircularList {
    private LinkedList<Integer> list = new LinkedList<Integer>();

    public void insert(int[] n) {
        for (int i = 0; i < n.length; i++)
            insert(n[i]);
    }

    public void insert(int n) {
        Integer insert = new Integer(n);
        if (!list.contains(insert)) {
            list.add(insert);
            Collections.sort(list);
        }
    }

    public int findMinimumNumber() {
        return list.peekFirst();
    }

    public int findNumber(int n) {
        int index = list.indexOf(new Integer(n));
        return index == -1 ? index : list.get(index).intValue();
    }

    public LinkedList<Integer> getList() {
        return list;
    }
}


TEST:

package google.test;

import google.CircularList;

import java.util.Random;

public class CircularListTest {
    public static void main(String[] args) {
        int TEST_SIZE = new Double(Math.pow(2, 8)).intValue();
        Random r = new Random();
        CircularList list = new CircularList();
        int n[] = new int[TEST_SIZE];
        for (int i = 0; i < TEST_SIZE; i++) {
            n[i] = r.nextInt(TEST_SIZE);
        }
        list.insert(n);
        System.out.println("List size:" + list.getList().size());
        for (Integer i : list.getList()) {
            System.out.println(i);
        }
        System.out.println("Minimum #: " + list.findMinimumNumber());
        System.out.println("Find #3: " + list.findNumber(3));
    }
}



No comments :