Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

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;
        }
    }
}

- aonecoding September 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
	}
}

- Nelson Perez October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Shahar October 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- fernandoVieiraDaSilva October 09, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More