Add / Multiply To Collection

Google Interview Data Structure Design

Create a class of integer collection that supports ‘add to all’ that adds a given number to all the elements in the collection at this point
3 APIs:
append(int x),
get(int idx),
add_to_all(int x)，
in O(1) time.

Follow-up
Implement another API
multipy_to_all(int x)
in O(1) time.

Solution

A collection that supports append(x) and get(i) can be a vector or an array list.
To enable add to all in O(1), have an integer value ‘addition’ that records the values added to the collection.
For example, if the collection is currently A = [1, 2, 3], int addition = 0

call add_to all(1)
update addition = 1

call add_to_all(5)
update addition = 6

call get(idx = 2)
returns A[2] + addition = 9

call append(4)
update collection to [1, 2, 3, -2]
where -2 comes from (4 - addition) because the newly appended number was not involved with the previous add_to_all calls.

Solution to Follow-up

Can we apply the same approach as above to multiply_to_all() by having an integer to keep track of the current factor?
See an example,
A = [1, 2, 3], factor = 3

call append(4)
then we will append 4/3 = 1.3333.. into the collection, which is kind of lousy.

To avoid the hassle on dealing with decimal numbers, we create another vector to keep track of the current factor when a number is appended.

e.g.
A = [1], factor = 1
F = [1]

call append(5)
A = [1, 5], factor = 1
F = [1, 1]

call multiply_to_all(2)
A = [1, 5], factor = 2
F = [1, 1]

call append(10)
A = [1, 5, 10], factor = 2
F = [1, 1, 2]

call multiply(3) and then append(20)
A = [1, 5, 10, 20], factor = 2 * 3 = 6
F = [1, 1, 2, 6]

call get(idx)
return A[idx] * factor / F[idx]

To enable both add_to_all and multiply_to_all
When a new factor T comes in, not only update the factor variable by factor = factor * T, also update the addition variable by addition = addition * T;
When appending a number X, append (X - addition).
When getting a number at idx, get (A[idx] * factor/F[idx] + addition).

Implementation

public class AddToAllCollection {
    List<Integer> collection = new ArrayList<>();
    List<Integer> divisors = new ArrayList<>();
    int factor = 1;
    int addition = 0;
    int set0 = -1;

    public void append(int x) {
        collection.add(x - addition);
        divisors.add(factor);
    }

    public int get(int index) {
        if(index >= collection.size()) throw new RuntimeException();
        if(divisors.get(index) <= set0) return addition;
        return collection.get(index) * (factor / divisors.get(index)) + addition;
    }

    public void add_to_all(int x) {
        addition += x;
    }

    public void multiply_to_all(int x) {
        if(x == 0) {
            addition = 0;
            factor = 1;
            set0 = collection.size() - 1;
        } else {
            addition *= x;
            factor *= x;
        }
    }
}