Google Interview Question Software Engineers
Country: United States
I don't think this works as it does not keep track of the order of operations. Keeping track of the overall factor to multiply by and the overall number to add will lose the actual number.
E.g. append 2 -> add 3 -> mult 5 -> add 5 -> mult 2
This should result in the number being 2+3=5*5=25+5=30*2=60
Your method would do this 2*10=20+8=28
Is there a way to account for the order of operations and still runs in O(1)? I struggled to come up with a method.
I don't think any of these solutions work for the follow up, as it does not keep track of the order of operations. Keeping track of the overall factor to multiply by and the overall number to add will lose the actual number.
E.g. append 2 -> add 3 -> mult 5 -> add 5 -> mult 2
This should result in the number being 2+3=5*5=25+5=30*2=60
Your method would do this 2*10=20+8=28
Is there a way to account for the order of operations and still runs in O(1)? I struggled to come up with a method. Or am I missing something?
import java.util.ArrayList;
import java.util.HashMap;
public class CollectionIntegers {
HashMap<String, Object> collectionOfIntegers = new HashMap<String, Object>();
CollectionIntegers()
{
collectionOfIntegers.put("List", new ArrayList<Integer>());
collectionOfIntegers.put("Add", 0);
collectionOfIntegers.put("Multiply", 1);
}
void append(int x)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");
Integer addResult = (Integer) collectionOfIntegers.get("Add");
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");
list.add(x);
addResult += x;
multiplyResult *= x;
collectionOfIntegers.put("List", list);
collectionOfIntegers.put("Add", addResult);
collectionOfIntegers.put("Multiply", multiplyResult);
}
int get(int idx)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");
return list.get(idx);
}
void add_to_all(int x)
{
Integer addResult = (Integer) collectionOfIntegers.get("Add");
addResult += x;
collectionOfIntegers.put("Add", addResult);
}
void multiply_to_all(int x)
{
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");
multiplyResult *= x;
collectionOfIntegers.put("Add", multiplyResult);
}
}
import java.util.ArrayList;
import java.util.HashMap;
public class CollectionIntegers {
HashMap<String, Object> collectionOfIntegers = new HashMap<String, Object>();
CollectionIntegers()
{
collectionOfIntegers.put("List", new ArrayList<Integer>());
collectionOfIntegers.put("Add", 0);
collectionOfIntegers.put("Multiply", 1);
}
void append(int x)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");
Integer addResult = (Integer) collectionOfIntegers.get("Add");
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");
list.add(x);
addResult += x;
multiplyResult *= x;
collectionOfIntegers.put("List", list);
collectionOfIntegers.put("Add", addResult);
collectionOfIntegers.put("Multiply", multiplyResult);
}
int get(int idx)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");
return list.get(idx);
}
void add_to_all(int x)
{
Integer addResult = (Integer) collectionOfIntegers.get("Add");
addResult += x;
collectionOfIntegers.put("Add", addResult);
}
void multiply_to_all(int x)
{
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");
multiplyResult *= x;
collectionOfIntegers.put("Add", multiplyResult);
}
}
Think of this of the form ax +b... When we add a number, we simply are going to add to b (add in the code below). When we need to multiply, we multiply the whole expression so... c * (ax + b) = a*c*x + b*c. So, when we get a value, we simply use the multiply factor and the addition factor to know the value for any element in the list. Implementation below:
import java.util.List;
import java.util.ArrayList;
public class CollectionIntegers {
List<Integer> col; // our list of values
int add; // the addition factor (b from the explanation)
int factor; // our multiply factor (a from the explanation)
public CollectionIntegers() {
col = new ArrayList<Integer>();
add = 0; // addition starts with zero
factor = 1; // multiplication starts as a one
} // end constructor
public int get( int idx ) {
return col.get(idx) * factor + add; // implement ax+b
} // end get
public void append( int value ) {
col.add(value); // append adds a value to our element list
} // end append
public void add_to_all(int x) {
add += x; // addition only changes the b factor
} // end add_to_all
public void multiply_to_all(int x) { // multiply happens to both components
add *= x;
factor *= x;
} // end multiply_to_all
} // end CollectionIntegers
package code;
import java.util.ArrayList;
/**
*
* Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x)，//add x to all numbers in collection
These methods should run in O(1) time.
Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time
*
*/
public class ConstantTimeMathOperations
{
private ArrayList<Integer> arrayList;
private int adder;
private int multiplier;
public ConstantTimeMathOperations()
{
// a reasonably large initial capacity
this.arrayList = new ArrayList<Integer>(10000000);
this.adder = 0;
this.multiplier = 1;
}
public void append(int x)
{
this.arrayList.add(x);
}
public int get(int index)
{
int x = this.arrayList.get(index);
return ((multiplier * x) + adder);
}
public void add_to_all(int x)
{
System.out.println("Added " + x);
this.adder += x;
}
public void multiply_to_all(int x)
{
System.out.println("Multiplied " + x);
this.adder *= x;
this.multiplier *= x;
}
public void print()
{
for(int i = 0; i < this.arrayList.size(); i++)
{
System.out.print(this.get(i) + " ");
}
System.out.println();
}
}
class Ints {
public:
Ints()
{
addition_ = 0;
factor_ = 1;
}
void Append(int x)
{
vals_.push_back(x - addition_);
base_factor_.push_back(factor_);
}
void AddToAll(int x)
{
addition_ += x;
}
void MultiplyAll(int x)
{
factor_ *= x;
addition_ *= x;
}
int Get(int idx) const
{
return idx < vals_.size() && idx >= 0
? vals_[idx] * (factor_ / base_factor_[idx]) + addition_
: 0;
}
private:
vector<int> vals_;
vector<int> base_factor_;
int addition_, factor_;
};
Looking for interview experience sharing and coaching?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution:
append and get are naturally done in constant time with ArrayList. To achieve add_to_all in constant time, have an extra variable 'addition' to store the added number. For any incoming number x to append, append(x - addition) instead. The get() method returns get(index) + addition.
Followup:
We could do the same thing for the multiply to all. keep track of the current multiplication factor and append the new number x by append(x / factor). However this brings the data type into double which is lousy.
A way around that is have another array divisor to keep track of the current factor when a new number x is appended at index i. Append x as it is. But later when x is requested, return x * factor / divisor.get(i).
Don't forget that every time the factor changes - such as when it doubles, the addition will be doubled as well.
- aonecoding June 15, 2017import java.util.List; import java.util.ArrayList; public class Collection { List<Integer> collection = new ArrayList<>(); List<Integer> divisors = new ArrayList<>(); int factor = 1; int addition = 0; public void append(int x) { collection.add(x - addition); divisors.add(factor); } public int get(int index) { if(index >= collection.size()) throw new RuntimeException(); 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) { addition *= x; factor *= x; } }