Return Maximum Number Of Different Sweets

From the above title you may be wondering what this one is all about. Well, let me explain a little.

I recently did an interview where part of it was peer programming. Well, that is not entirely true. There was a programming exercise where the interviewers watched while I attempted the question.

Now. little caveat is that my Java skills are very rusty. It has been a few years since I've had to knock out any Java code. Currently, I'm working in C# and ASP.NET.

That out of the way... here is the question I was asked.

The question

The question went something along the lines of:

Mary had some sweets which are represented as numbers in an array. She is going to share these sweets with her friend (let's call him George as I can't remember the name used).

The number of sweets, for this case, are always even.

Mary wants her sweets to be the maximum number of different sweets from what she has. She wants to know how many different types of sweets she will get.

So, image this array of numbers (sweets) {1, 2, 2, 3, 5, 5, 6, 6}. The size of the array is 8. The maximum number of different sweets Mary could expect is 4. It's 4 because she can have only half the number - and there are at least 4 different numbers she would have {1, 2, 5, 6) or {2, 3, 5, 6} and so on.

Now image if the array (sweets) looked like this {1, 80, 80 ,20957383,5 ,30,80, 80, 80, 80, 5,1,94,1090075, 80, 80}.

From this, you would work out that, although the array is 16 values in size, the number of different values is just 7. So we would return 7 for this array.

So, who did I work it out?

When I was doing the code in the 20-30 minutes I had, with my Java rusty I did not come up with the best solution. Too many loops and statements.

So, out of interest, I decided to rewrite this code (with the aid of Google to get the syntax of a few commands).

My idea was simple. Loop through the array and add any different values into a list. Then get the size of the list and if it was smaller than the array divided by 2 - that was your return value.

Otherwise, just return the size of the array divided by 2.

So, what does my code look like - what is the answer to this question. Let's take a look:

import java.util.*;  class DifferentValues {  public int CalculateDifferentValues(int[] T) {   int arrSize = T.length;   List<Integer> foundValues = new ArrayList<Integer>();    // Loop through the array   for (int count = 0; count < arrSize; count++)   {    // Check if the current value has already been found    if (!foundValues.contains(T[count]))    {     // If not in the ArrayList then add it     foundValues.add(T[count]);    }   }    // How many different found values where there (take size of ArrayList)   int foundSize = foundValues.size();    // If number different is smaller than half of array size - then    // return the different found size   if (foundSize < (arrSize/2))    return foundSize;    // If foundSize is greater than half array size, then return    // the array size divided by 2   return (arrSize/2);  }   public static void main(String[] args)  {   // Initialise my array with lots of numbers   int theArray[] = {1, 80, 80 ,20957383,5 ,30,80, 80, 80, 80, 5,1,94,1090075, 80, 80};      // Create my object and call the calculate different method   DifferentValues differentValues = new DifferentValues();   int totalDifferent = differentValues.CalculateDifferentValues(theArray);    System.out.println("Total number of different items is: " + totalDifferent);  } }

Hope this helps

So, if you ever get asked a question similar to this one, I hope this example helps. It's basically can take an array of T[N] (so any size array) and return you the maximum different values that one person can expect.