CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top-tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

import java.util.List;
import java.util.ArrayList;

public class IntegerCollection {
    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;
        }
    }
}

The best approach is to keep track of the operations and apply the reverse operation when you insert the number. In this way the insertion keeps track of the previous operations.

class IntegerCollection
{
	List<double> N = new List<double>();
	double mult = 1, sum = 0;
        int zeroIndex = -1;

	public void insert(int x) 
	{
		N.Add(x/mult - sum);
	}

	public void sum_to_all(int x)
	{
		sum+= x;
	}

	public void multiply_to_all(int x)
	{
                if(x ==0) {
                    zeroIndex = N.Length -1;
                    mult = 1;
                    sum = 0;
                }
                else {
		    sum *= x;
		    mult *= x;
                }
	}

	public int get(int x)
	{
                if (x <= zeroIndex) return sum;

		return (int) (N[x]*mult + sum);
	}
}

@aonecoding Very nice. But don't you mean "index <= set0" rather than "divisors.get(index) <= set0" in line 18?

It doesn't seem the solutions here work for the case in which addition comes before multiplication like in the input sample, do they? Also, I couldn't figure out how to implement "get()" in O(1) if we keep switching the order of add_to_all and multiply_to_all, like in the input sample below:

insert(1)
insert(2)
add_to_all(5)
insert(3)
get(0) -> returns 6
get(2) -> return 3
multiply_to_all(10)
insert(4)
get(1) -> returns 70
get(2) -> returns 30
get(3) -> returns 4

Adding the following lines:
====
multiply_to_all(20)
add_to_all(4)
get(0) →364

multiply_to_all(5)
get(0) -> 1820