## Google Interview Question for Software Engineers

• 5

Country: United States

Comment hidden because of low score. Click to expand.
3
of 9 vote

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.

``````import 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) {

}

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) {

}

public void multiply_to_all(int x) {

factor *= x;

}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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("Multiply", 1);
}

void append(int x)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");

multiplyResult *= x;

collectionOfIntegers.put("List", list);
collectionOfIntegers.put("Multiply", multiplyResult);
}

int get(int idx)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");

return list.get(idx);
}

{
}

void multiply_to_all(int x)
{
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");
multiplyResult *= x;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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("Multiply", 1);
}

void append(int x)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");

multiplyResult *= x;

collectionOfIntegers.put("List", list);
collectionOfIntegers.put("Multiply", multiplyResult);
}

int get(int idx)
{
ArrayList<Integer> list = (ArrayList<Integer>) collectionOfIntegers.get("List");

return list.get(idx);
}

{
}

void multiply_to_all(int x)
{
Integer multiplyResult = (Integer) collectionOfIntegers.get("Multiply");
multiplyResult *= x;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the idea is actually to multiply your add for example:
append 2 -> add 3 -> mult 5 -> add 5 -> mult 2
factor = 1 factor= 1 factor = 5 factor = 5 factor = 5*2
2*10+40 = 60

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
factor *= x;
} // end multiply_to_all
} // end CollectionIntegers``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
void multiply_to_all(int x)
The same required to run in O(1) time
*
*/

public class ConstantTimeMathOperations
{
private ArrayList<Integer> arrayList;
private int multiplier;

public ConstantTimeMathOperations()
{
// a reasonably large initial capacity
this.arrayList = new ArrayList<Integer>(10000000);
this.multiplier = 1;
}

public void append(int 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);
}

public void multiply_to_all(int x)
{
System.out.println("Multiplied " + 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();
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````class Ints {
public:
Ints()
{
factor_ = 1;
}
void Append(int x)
{
base_factor_.push_back(factor_);
}
{
}
void MultiplyAll(int x)
{
factor_ *= 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_;
};``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.