CareerCup

Ah, I see where you're going, I misinterpreted the number ranges. Clever solution, you got my vote.

The following is a solution in Java. Assumes that sorted integers are unique. We start by looking at position k since we're guaranteed that the value won't be in a position greater than k. Once we've checked k, we can then do a binary search on the range 0..k-1. This solution is O(log k).

public static int findPosition(String[] input, int k) {
	if (input == null || input.length == 0 || input[0] == "$")
		return -1;
	if (input[k] == Integer.toString(k))
		return k;
	return binarySearch(input, k, 0, k-1);
}

public static int binarySearch(String[] input, int k, int start, int end) {
	if (end < start)
		return -1;
	int mid = (start + end) / 2;
	// Convert string array value to int, if possible
	int midValue = -1;
	if (input[mid] != "$")
		midValue = Integer.parseInt(input[mid]);
	// Check mid point
	if (midValue == k)
		return mid;
	// Search low if mid value is greater than k
	// or if it is "$"
	if (midValue > k || input[mid] == "$")
		return binarySearch(input, k, start, mid - 1);
	// If mid point isn't "$", then search the upper range
	else if (input[mid] != "$")
		return binarySearch(input, k, mid + 1, end);
	return -1;
}

I'm not sure that your solution is O(log n) in the worst case, and it is not guaranteed to return the right index. The example case would be {1, 99, $, $, $, $, $, $, .....}, where n = 2 and the first n cells contains integers in sorted order.

Here's a brute force implementation in Java. The basic algorithm involves placing the first student in matrix[0][0]. For each successive student, evaluate the shortest distance to the next closest student for each cell position and place the student in the cell with the max shortest distance. I'm convinced a Dynamic Programming solution is probably the best option for this kind of a problem.

public static int[][] placeStudents(int width, int height, int numOfStudents) {
	int[][] result = new int[width][height];
	
	Cell c = new Cell();
	c.x = 0; c.y = 0;
	for (int k = 0; k < numOfStudents; ++k) {
		// When k = 0, position will 0,0 in the matrix
		result[c.x][c.y] = k + 1;
		if ((k + 1) < numOfStudents)
			c = evaluateCells(result);
	}
	
	return result;
}

public static Cell evaluateCells(int[][] positions) {
	double maxCost = -1.0; Cell result = new Cell();
	// For each matrix cell
	for (int i = 0; i < positions.length; ++i) {
		for (int j = 0; j < positions[i].length; ++j) {
			if (positions[i][j] > 0) continue;
			// Get the distance to the next closest cell
			double cost = getCost(i, j, positions);
			// If its the max distance, then remember the cell position
			if (cost >= maxCost) {
				maxCost = cost;
				result.x = i;
				result.y = j;
			}
		}
	}
	return result;
}

public static double getCost(int a, int b, int[][] positions) {
	double minDistance = Integer.MAX_VALUE;
	for (int i = 0; i < positions.length; ++i) {
		for (int j = 0; j < positions[i].length; ++j) {
			if (positions[i][j] > 0) {
				// Using the Pythagorean theorem to calculate distance between 
				// coordinates in matrix
				double cost = Math.sqrt(Math.pow(Math.abs(a - i), 2) + Math.pow(Math.abs(b - j), 2));
				if (cost < minDistance)
					minDistance = cost;
			}
		}
	}
	return minDistance;
}

@vgeek
Thanks for your reply! I thought I posted a comment in response so I apologize if it appears twice. The short of it is that I'm having trouble following your logic. Your solution assumes that the input will be unique that that you only need evaluate unique couples. My understanding of the problem assumes that the input can contain all of the same elements such that the number of couples I should report is n(n-1)/2 with a difference of 0.

Sticking to your example where arr = {1,2,3,4,5,6,7,8,9}, there are two couples with difference 7, three couples with difference 6, so forth and so on. A correct algorithm should produce the values 2,3,4,5,6,7, and 8.

I pasted your code into codepad.org (paste bTSskmXA) and changed the input to match your example . The output was not what I was expecting. Please let me know if I'm not using your code correctly.

I think you're on to something, but the implementation needs a little work. Thanks!

Here's a C# example. I've tested this against a single element array, an array containing all of the same elements, and against the sample posted above.

public int[] GetMaxInterval(int[] input) {
	// Jagged array will store a pair of values for the difference between the two values
	int[][] differences = null;
	Array.Sort(input);
	int maxDiff = input[input.Length-1] - input[0];
	differences = new int[maxDiff+1][];
	for (int i = 0; i < input.Length - 1; ++i) {
		int j;
		for (j = i + 1; j < input.Length; ++j) {
			if((j - i) == (input[j] - input[i])) {
				continue;
			} else {
				differences[j - i - 1] = new int[] {input[i], input[j - 1]};
				i = j - 1;
				break;
			}
		}
		// Check the edge case where the last element of the array is included in the max range.
		if(j == input.Length) {
			differences[j - i - 1] = new int[] {input[i], input[j - 1]};
		}
	}
	// Iterated through the jagged array backwards to find the max difference.
	for (int i = differences.Length - 1; i >= 0; --i) {
		if (differences[i] != null)
			return differences[i];
	}
	return null;
}

It's not clear to me how you can achieve O(n lg n) performance for arr = {1, 2, 4, 8, 16, 32, 64}. Doesn't every element have to be compared against another in order to calculate a difference? I do think we can do better than O(n(n-1)/2) in the average case by leveraging the fact that the array is sorted. For instance, if arr[arr.length] - arr[0] = 0, then the result is automatically arr.length * (array.length - 1) / 2. Of course, I'm only talking about arrays of length greater than 2.