Building a toy from Lego toys 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  --&gt; Kid spent 13 units of time
13 + 2 = 15 --&gt; 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&lt;Integer&gt; lego) {
    Collections.sort(lego);

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

    for (int i = 1; i &lt; 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?
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 &lt; 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.