## Google Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

So following Subbu's solution:

``````uint max_equal(int *a, uint n) {
int s = 0;
for (uint i = 0; i < n; i++) {
s = (s + a[i])%n; // avoid overflow issues at slight cost of performance.
// assumes % returns 0 to n-1.
}
return s==0 ? n : n-1;
}``````

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

Why is the answer only one of n or n-1?

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

Exactly, what should be the output for {1 1 2 2 3 3 3 4}?

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

It is n or n-1, because, as we said in the comments below. You can always pick a pivot element which you can increment or decrement to make all elements equal apart from that pivot element. Suppose that you want to make all 0 apart from the pivot element, then what you get in fact is a sum of all elements gathered in that pivot element. Now, if that sum can be spread evenly across all the n elements, then you have n elements that can be all equal, otherwise you have n-1. However, I believe the problem is not complete, but that's what the poster says.

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

@Vulkum: Yes, I agree. The problem is either an incomplete Google interview question, or homework/programming contest problem.

This is an aha! question, which makes me think it is the latter, as Google discourages use of such questions.

If it is an incomplete Google question, my guess is the number of steps to make them equal will be involved somehow.

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

We can always to n-1 (pick a dummy which absorbs +1 and -1 to make the others equal).

The key question is whether we can do n.

Comment hidden because of low score. Click to expand.
2

And that is answered by just checking if the sum of numbers is divisible by n.

If total sum = k*n, then we try to make the n-1 of them equal to k. The dummy will automatically become k, as the sum of numbers is constant.

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

I was just going to ask if the question is complete. Because from the looks of it, it's as you say: pick a pivot element and use that to make all other equals, and then check whether the difference can be distributed across all n elements.

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

@Vulkum: It is simpler than that. All you need to do is check if the sum is divisible by n.

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

Yeah, I agree...that's how I did it in the first place, but there must be a catch...something that we're not being told here.

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

O(nk) where k is the number of possible candidates

``````private static int getBestAlign(int[] array) {
// count number of elments that are equal - time: O(n)
Integer value, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, maxCount = Integer.MIN_VALUE;
for(int elem : array) {
if(elem > max)
max = elem;
if(elem < min)
min = elem;
}

// check each candidate - time O(nk) where k is the number of possible candidates
for(int candidate = min + 1; candidate < max; candidate++) {
int sum = 0;
for(int elem : array)
sum += candidate - elem;
if(sum == 0) {
System.out.println("Candidate: " + candidate);
return array.length;
}
}
return array.length - 1;
}``````

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

First sort the numbers. If there are 2 numbers then the minimal move is A - A by settling down the final number to any value between A and A. If there are 3 numbers, then the minimal move is A - A. by settling down the final number to A. For N numbers the minimal moves is

(A[N-1]-A) + (A[N-2]-A) ...

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

Can you please explain with an example. Thanks!

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

temp = (a1+a2+a3+.......+an)%n;

ans will be max(temp,n-temp)

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

Wrong.

4,4,4,2

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

Why don't you change 4 4 4 to 2 2 2?

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

I think it is always able to make them equal except one case: # of elements are 2 and they are different.
We know that we can make at least (n-1) elements equal.
(a b c d .... -> a a (c-b) d .... -> a a a (d-(c-b)) ... something like this.)
As a result, 1st~(n-1)-th elements are same, but the n-th element is different.
Then, we can just increase/decrease 1st~(n-1)th elements until they are the value of the n-th element.

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

You have got it completely wrong.

The order of elements does not matter, for instance.

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

Hey guys, I did not get the question at all, can you explain it more?

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

``````public static void main(String[] args) throws Exception{
Integer[] nArray = { 2, 5, 6, 3, 5, 5, 7, 2 };
Collections.sort(Arrays.asList(nArray));
Integer prevElement= nArray;
Integer elementWithMostOccurrences = 0;
Integer counter = 0;
Integer maxCount =0;
for(int i=0; j < nArray.length; j++) {
if(nArray[i] == prevElement) {
counter += 1;
} else {
if(counter > maxCount) {
maxCount = counter;
elementWithMostOccurrences = nArray[i-1];
}
prevElement = nArray[i];
counter = 1;
}

}

System.out.println("Element which has most occurrences = "+elementWithMostOccurrences);
System.out.println("Maximum number of elements that have same number = "+maxCount);

}``````

Comment hidden because of low score. Click to expand.

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.