dxmio.com

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
 
public class Program
{
	public static void main(String[] args)
	{
		doMatrixSearch();
		doMissingNumberSearch();
		doFirstUnrepeated();
	}
 
	public static void doFirstUnrepeated()
	{
		String testString = "nnnnnnnnxxnnpnn";
		char[] testStringChars = testString.toCharArray();
 
		class EntryInfo
		{
			int count;
			int firstPos;
		}
 
		HashMap<Character, EntryInfo> stuff = new HashMap<Character, EntryInfo>();
 
		for(int i = 0; i < testStringChars.length; i++)
		{
			EntryInfo thisInfo;
 
			if(stuff.containsKey(testStringChars[i]))
			{
				thisInfo = stuff.get(testStringChars[i]);
				thisInfo.count++;
			}
			else
			{
				thisInfo = new EntryInfo();
				thisInfo.count = 1;
				thisInfo.firstPos = i;
			}
 
			stuff.put(testStringChars[i], thisInfo);
		}
 
		int minPosition = testStringChars.length - 1; 
 
		Collection<Character> coll = stuff.keySet();
		Iterator<Character> iter = coll.iterator();
		while(iter.hasNext())
		{
			Character thisChar = iter.next();
			EntryInfo thisInfo = stuff.get(thisChar);
			if(thisInfo.count == 1 && thisInfo.firstPos < minPosition)
				minPosition = thisInfo.firstPos;
		}
 
		System.out.println("doFirstUnrepeated():\t First non-repeater: " + testStringChars[minPosition]);
 
	}
 
	public static void doMissingNumberSearch()
	{
		int minInclusive = 1;
 
		int[] arr = {1,2,5,6,7,8,9};
 
		int[] missingNums = new int[2];
		int missingNumsPtr = 0;
 
		int shouldExist = minInclusive;
 
		for(int i = 0; i < arr.length && missingNumsPtr < 2; i++)
		{
			if(arr[i] != shouldExist)
			{
				missingNums[missingNumsPtr] = shouldExist;
				missingNumsPtr++;
			}
			shouldExist++;
		}
 
		System.out.println("doMissingNumberSearch():\t Missing nums: " + missingNums[0] + " and " + missingNums[1]);
 
	}
 
	public static void doMatrixSearch()
	{
		int numRuns = 1000;
		int numSteps = 0;
 
		for(int z = 0; z < numRuns; z++)
		{
			Random rnd = new Random();
 
			int[][] arr = new int[5][5];
			int last = 0;
 
			for(int y = 0; y < 5; y++)
			{
				for(int x = 0; x < 5; x++)
				{
					int newval = rnd.nextInt(5) + last;
					arr[x][y] = newval + 10;				
					last = newval;
				}
			}
 
			int toFind = 30;
 
			numSteps += matrixSearch(arr, toFind);
		}
 
		double averageSteps = (double)numSteps / (double)numRuns;
 
		System.out.println("doMatrixSearch():\t Average steps: " + averageSteps);
	}
 
	public static int matrixSearch(int[][] arr, int toFind)
	{
		int numSteps = 0;
 
		int x = arr[0].length - 1;
		int y = 0;
 
		while(x >= 0 && y < arr.length)
		{
			numSteps++;
 
			if(toFind < arr[y][x])
				x--;
			else if(toFind > arr[y][x])
				y++;
			else if(toFind == arr[y][x])
				break;
		}
 
		return numSteps;
 
	}
}