Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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);
}
}
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
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!
- aonecoding September 22, 2017