Building a toy from Lego toys

Question

I recently attempted a coding problem, but my solution was not well received during the interview (modified slightly to reduce Google-ability).

Suppose a child has several Lego blocks, and wants to build a toy from them. Every piece has a size, and when two pieces are combined a new piece is created whose size is the sum of the attached blocks. The time it takes to combine two blocks is equal to the size of the individual blocks

Find the sequence of combinations that takes the least amount of time to combine all of the Legos

Here is an example:

Given the following blocks: 5, 2, 8 the child could combine them in the following methods:

5 + 8 = 13  --> Kid spent 13 units of time
13 + 2 = 15 --> Kid spent 15 units of time
Total time spent: 13 + 15 = 28

Another combination would be:

2 + 5 = 7
7 + 8 = 15
Total time spent: 22

I came up with the following algorithm to find the shortest time required to combine all of the blocks:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class AssemblyTime {

  int shortestAssemblyTime(List<Integer> lego) {
    Collections.sort(lego);

    int counter = lego.size() - 1;
    int sum = lego.get(0) * (lego.size() - 1);

    for (int i = 1; i < lego.size(); i++) {
      sum += lego.get(i) * counter;
      counter--;
    }

    return sum;
  }


  public static void main(String[] args) {
    int i = new AssemblyTime().shortestAssemblyTime(Arrays.asList(5, 2, 8, 4));
    assert i == 36;
  }
}

The test cases are not available to me, however my solution timed out on 6 of the 10 (it passed the other 4).

The idea of my algorithm is as follows. Given my test case in code, the process is something like this:

2 + 4
2 + 4 + 5
2 + 4 + 5 + 8

So the last element is added once, the last-1 is added twice until elements at index 0 and 1, which are both added list.length - 1 times.

How can I improve the performance for this algorithm? Is there any other data structure I can use?

Answer 1

You have a more fundamental problem here than performance: your solution isn't actually correct. Consider 4 lego pieces all of size 1. Your solution combines them as

1. \$1+1=2\$
2. \$2+1=3\$
3. \$3+1=4\$

for a total cost of \$2+3+4 = 9\$. However, we can combine more efficiently in the following way

1. \$1+1=2\$
2. \$1+1=2\$
3. \$2+2=4\$

for a total cost of \$8\$. In general this problem is asking you to rediscover the famous Huffman coding. If you consider your size \$w\$ blocks to be code words with frequency \$w\$, then the solution is asking you to find the cost of the optimal prefix code for those code words.

The optimal combination is obtained by at each step picking the two smallest size blocks and combining them. We need a data structure where we can efficiently find and remove the smallest element, and also insert new elements (we need to reinsert combined blocks at each step). This can be done efficiently with a min priority queue.

Strictly speaking, in an actual interview, you might be asked to justify why the above algorithm gives the most efficient combination. For this, see a resource on the Huffman code.

Answer 2

Your inner loop contains an addition, multiplication, subtraction and two assignments. The multiplication is unnecessary as you can do with two additions and two assignments:

int totalTimeSpent = 0;
int sumOfPair = lego.get(0);
for (int i = 1; i < lego.size(); i++) {
    sumOfPair += lego.get(i);
    totalTimeSpent += sumOfPair;
}

Regarding the data structures: were you forced to use a List? An int array with Arrays.sort(int[]) would have been more efficient.

Answer 3

You could use reverse order and multiply by array index +1 (except last element):

2 + 4
2 + 4 + 5
2 + 4 + 5 + 8

Could be transformed to:

element    index  result
    8   *   1      8
    5   *   2      10  
    4   *   3      12
    2   *   3      6  
                   36

It allows you to remove reverse counter. Also you can use Array it consume less memory.

Here is my implementation:

class AssemblyTime {

    int shortestAssemblyTime(Integer... lego) {
      Arrays.sort(lego, Collections.reverseOrder());
      int sumOfLastElement = lego[lego.length - 1] * (lego.length - 1);
      return IntStream.range(1, lego.length)
              .map(i -> lego[i] * (i + 1))
              .sum() + sumOfLastElement;
    }

    public static void main(String[] args) {
        int i = new AssemblyTime().shortestAssemblyTime(5, 2, 8, 4);
        assert i == 36;
    }
}

Answer 4

As TorbenPutkonen already said, the good way to improve the performance of your solution is relying on primitive types using Arrays.sort(int[] and rewriting of loop as he suggested. I add my thoughts and code, consider that for your interviewer can be edge cases like o or 1 toy blocks , in this case the shortest time is equal to 0. Now you can use a method having as parameter an int[] array to avoid use of Integer class and operations of boxing and unboxing:

public static int shortestAssemblyTime(int[] arr) {
    int n = arr.length;
    if (n < 2) { return 0; }  //<-- edge cases 0, 1
    int[] copy = Arrays.copyOf(arr, n);
    Arrays.sort(copy);
}

I created a copy of the original array, because for me the method is supposed to not modify the original array passed as parameter and I added the static modifier. Once you have the copy ordered inside the method, you can calculate the shortest time like the code below:

int shortestTime = 0;
int toylength = copy[0];
for (int i = 1; i < n; ++i) {
    toylength += copy[i];
    shortestTime += toylength;
}
return shortestTime;

Below the code of the class Assembly.java with main method including one test:

import java.util.Arrays;

public class AssemblyTime {

    public static int shortestAssemblyTime(int[] arr) {
        int n = arr.length;
        if (n < 2) { return 0; }
        int[] copy = Arrays.copyOf(arr, n);
        Arrays.sort(copy);
        int shortestTime = 0;
        int toylength = copy[0];
        for (int i = 1; i < n; ++i) {
            toylength += copy[i];
            shortestTime += toylength;
        }
        return shortestTime;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 2, 8, 4};
        System.out.println(AssemblyTime.shortestAssemblyTime(arr)); // print 36
    }
}