CareerCup

You can do it in one pass, just use the auxiliary array as an array of linked lists, and append each ball to its respective linked list as you iterate through the 10,000 balls.

Pseudocode (assuming the aux array is already created as an array of linked lists):

for ball in balls:
  aux_array[ball.color].append(ball)

Gus, you are assuming that 'ball.color' is an integer. What if it is a string?

You probably don't need to store the balls again. Just maintain a count of each type of ball.
Take a convention where each array index represents a color, like 0=red, 1=blue, etc. If you can use a map then key would be ball color and value would be a count.

You pass over it once. Do a get, if present increment value, if not present insert and set value to 1.

package main

import "fmt"

type Ball struct {
	color string
}

func ColorCount(balls []Ball) map[Ball]int {
	ballMap := make(map[Ball]int)
	for _, ball := range balls {
		if ballMap[ball] == 0 {
			ballMap[ball] = 1
		} else {
			i := ballMap[ball] + 1
			ballMap[ball] = i
		}
	}
	return ballMap
}

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

import org.junit.Test;

/**
 * There are 10,000 balls and may be 500 different colors of ball
 * 
 * Example: There are:
 * 
 * 4 - red ball
 * 
 * 5900 - Blue ball
 * 
 * 3700 - Green ball
 * 
 * 396 - mintcream ball
 * 
 * Or there may be 10,000 red balls.
 * 
 * Or all balls are has same range, i.e. 500 red, 500 blue, etc.
 * 
 * We don’t know the range of any ball and number of color balls, but the
 * minimum is 1 color and maximum is 500 colors, and we have auxiliary array of
 * size 500. how to arrange all same color ball together in minimum passes over
 * balls? is it possible to do in less than two passes ??
 * 
 * 
 * Solution 1: sorting balls using count sort
 * 
 * Time complexity: O(n)
 * 
 * Space complexity: O(n)
 * 
 * 
 * Solution 2: sorting balls using count sort
 * (without extra space - using current and previous references/objects)
 * 
 * Time complexity: O(n)
 * 
 * Space complexity: O(1)
 * 
 */

public class SortingColoredBall {
	public enum Color {
		BLUE, GREEN, RED, MINDCREAM;
	}

	public class Ball {
		Color color;
		int size;
		int id;

		public Ball(Color color, int id, int size) {
			this.color = color;
			this.id = id;
			this.size = size;
		}

		@Override
		public String toString() {
			return "[" + id + ", " + color + ", " + size + "]";
		}
	}

	public void sort(Ball[] arr, int[] color) {
		for (int i = 0; i < arr.length; i++) {
			color[arr[i].color.ordinal()]++;
		}
		System.out.println(Arrays.toString(color));
		for (int i = 1; i < color.length; i++) {
			color[i] += color[i - 1];
		}

		System.out.println(Arrays.toString(color));

		Ball[] output = new Ball[arr.length];
		for (int i = 0; i < arr.length; i++) {
			int c = arr[i].color.ordinal();
			System.out.format("%d %d", c, color[c]);
			output[color[c] - 1] = arr[i];
			color[c]--;
		}

		for (int i = 0; i < arr.length; i++) {
			arr[i] = output[i];
		}
	}

	@Test
	public void testSort() {
		Ball[] arr = new Ball[10000];
		for (int i = 0; i < arr.length; i++) {

			Ball ball = new Ball(Color.values()[ThreadLocalRandom.current()
					.nextInt(3)], i, ThreadLocalRandom.current().nextInt(10));
			arr[i] = ball;
		}
		int[] color = new int[500];
		sort(arr, color);

		System.out.println(Arrays.toString(arr));
	}
	
	
	public void sortWithoutExtraSpace(Ball[] arr, int[] color) {
		for (int i = 0; i < arr.length; i++) {
			color[arr[i].color.ordinal()]++;
		}
		System.out.println(Arrays.toString(color));
		for (int i = 1; i < color.length; i++) {
			color[i] += color[i - 1];
		}

		System.out.println(Arrays.toString(color));

		Ball current = arr[0], previous = null;
		for (int i = 1; i < arr.length; i++) {
			int c = current.color.ordinal();
			System.out.format("%d %d", c, color[c]);
			previous = arr[color[c] - 1];
			arr[color[c] - 1] = current;
			color[c]--;
			current = previous;
		}
	}
	
	@Test
	public void testSortWithoutExtraSpace() {
		Ball[] arr = new Ball[10000];
		for (int i = 0; i < arr.length; i++) {

			Ball ball = new Ball(Color.values()[ThreadLocalRandom.current()
					.nextInt(3)], i, ThreadLocalRandom.current().nextInt(10));
			arr[i] = ball;
		}
		int[] color = new int[500];
		sortWithoutExtraSpace(arr, color);

		System.out.println(Arrays.toString(arr));
	}
}

O(n)? Two passes?

Maybe I am missing something...but here goes my idea.
1. Allocate one location in the auxiliary array for each color.
2. Pick a ball from the set of 10000 and place it in the auxiliary array.
3. If you get another ball of the same color, replace the one in the auxiliary array with the new one and push the old one back into the 10000 set, but remember not to pick this up.
4. As more balls are moved from the 10000 set to the 500 set, you can insert more from the 500 set into the 10000 set PROCESSED area using insertion sort say.

Is this acceptable?

Here's my solution (one sweep):

1) Initialize a dictionary of lists that holds up to 500 objects
2) Traverse the list of balls while adding them to the dictionary

for each ball in balls
	If ballDictionary[ball.color] exists then
		ballDictionary[ball.color].add(ball)
	else
		ballDictionary[ball.color] = new BallList
		ballDictionary[ball.color].add(ball)

Now we can index any ball color and get a list of the balls of that color.

Assuming the balls are also in an array, I would consider sorting them by color, where colors order is determined through their bit representation. This should cost O(n*log(n)) due to the sorting. But maybe I missed something...

I can think of an algorithm to do it in 2 passes but not less than that.

1) Take 1 pass through the entire set of balls and use the array to capture frequency of each color (histogram). Thus we can decide what range positions to allot to each color i.e. positions are from 1 to 10000.
2) In the array capture the first available position for each color.
3) Pick the ball at position 1 and place it at the correct position according to the color. Simultaneously update the array to capture the next position available for that color.
4) Repeat the above step for the ball that was displaced because of it.