Google Interview Question for Software Developers


Country: United States




Comment hidden because of low score. Click to expand.
7
of 15 vote

Sort the numbers and traverse from starting keeping a cumulative sum of numbers found so far(including numbers added). At any point the cumulative sum value denotes the largest number that we can get by adding numbers in the array.

static int NumbersToAdd(int[] elements, int last)
{
	int size = elements.length;
	int addedNums = 0;
	int cum_sum = 0;
	int i = 0;
	while(i<size || cum_sum < last)
	{
		if(i>=size || elements[i] > cum_sum + 1)
		{
			addedNums++;
			int number_added = cum_sum + 1;
			cum_sum += number_added ;
		}
		else
		{
			cum_sum += elements[i];
			i++;
		}
	}
	
	return addedNums;
}

- Brandy August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

And this answers the question how?

- Anonymous August 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is a correct answer!!! I've figured it out by myself these days!

- xiaoc10 August 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Your code is flawed. If you wanted 10 and vect = {1,2,4,6,9} simply adding wouldn't do the trick.

- Paul August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Your code is flawed. If you wanted 10 and vect = {1,2,4,6,9} simply adding wouldn't do the trick.

- Paul August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is wrong. Does not return LEAST number of additions (it returns the MOST). and N = 10 arr = {1,2,4,6,7,9} will break it.

- Paul August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is wrong. Does not return LEAST number of additions (it returns the MOST). and N = 10 arr = {1,2,4,6,7,9} will break it.

- Paul August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a codeforcesTM problem!

- Agoston September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a codeforces problem

- Agoston September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Minimum floor(Log(N))+1 elements will be needed to make all 1 to N numbers using ADD operation.

2^0 = 1 (if N<=1 then required number of elements is 0+1 = 1)
2^1 = 2 (if N>=2 & N<=3 then required number of elements is 1+1 = 2)
2^2 = 4 (if N>=4 & N<=7 then required number of elements is 2+1 = 3)
2^3 = 8 (if N>=8 & N<=15 then required number of elements is 3+1 = 4)
2^4 = 16 (if N>=16 & N<=31 then required number of elements is 3+1 = 4)

- Naveen August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction for the range 16-31,

required number of elements is 4+1 = 5

- Naveen August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

I forgot to mention what exact number we need to add to get all numbers from 1 to N.

Solution is, no matter what set of numbers are given, we will need to add missing numbers from (1,2,4,8,16,32,64....so on) which is nothing but power of 2.

- Naveen August 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about given {3,6} and N=9. According to your solution the final list will contain {1,2,3,4,6,8} while the optimal solution is {1,2,3,6}

The representation of a number as the sum of powers of two is optimal but is not the only one. If the initial list is empty or has only powers of two your approach will work otherwise is not guarantied.

- sergio August 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, his solution doesn't tell you what the list will contain afterwards. His solution says that you can make any number, n in [8,15], using 3+1=4 elements in the array. This is the same size as your given optimal solution. The program would then return 2 because the difference between 4 and size({3,6}) is 2.

- jbaum517 August 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

But that's not right either. Let's say the starting set is {1, 3, 3, 3} and N=11. The optimal set size is 4, but that doesn't mean 0 numbers need to be added. In fact 1 number (2) needs to be added.

- Anonymous August 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

1. Initialize a bitmap array of size N to 0. Initialize a count variable to 0.
2. Run through the power set of input array, and for every element in power set - sum all elements and set corresponding location in bitmap array.
3. Check if all indices are set in bitmap array. If yes, return count
4. Add first index set to 0 in bitmap to input array. Set this bitmap index. Increment count. Run all combinations of input array with this element - size of 2, 3.. etc and set the bitmap. Go to step 3.

Complexity: O(min(N, 2^array_size)*logN)
Memory: O(N)

Eg: N = 4, input array {}
After iteration 1: add 1. Covers 1
After iteration 2: add 2. Covers 2, 3
After iteration 3: add 4. Covers 4
O(NlogN) in this case.

- palemgangireddy August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That works and it results in a relatively nice piece of code in Java 8 (and Guava).

public class Solver {

    public static void main(String[] args) {
        int input[] = {1, 3, 8};
        int n = 70;
        new Solver().solve(input, n);
    }

    private void solve(int[] input, int n) {
        BitSet bitSet = new BitSet(n + 1);
        Set<Integer> solution = IntStream.of(input).boxed()
                .collect(Collectors.toSet());

        for (int addedCount = 0; ; addedCount++) {
            for (Set<Integer> combination : Sets.powerSet(solution)) {
                int sum = combination.stream().mapToInt(i -> i).sum();
                if (sum <= n) {
                    bitSet.set(sum);
                }
            }

            if (bitSet.cardinality() > n) {
                System.out.println("Added numbers: " + addedCount);
                System.out.println("Final set: "
                        + Ordering.natural().sortedCopy(solution));
                return;
            }

            solution.add(bitSet.nextClearBit(1));
        }
    }
}

- heikki.salokanto August 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the right idea. Below is working C++ implementation. Basically, we're adding elements and solving subset sum problem repeatedly until all the elements are covered. Complexity is O(N*(n+k)) where n + k is the overall length of the array including additions.

void updateSubsetSumBitmap(vector<bool> &D, int val)
{
	for (int i = D.size() - 1; i >= val; i--)
	{
		if (!D[i] && D[i-val])
		{
			D[i] = true;
		}
	}
}

int getSmallestNumberOfAddedElements(vector<int> &A, int N)
{
	vector<bool> D(N+1);
	D[0] = true;
	for (int v : A)
		updateSubsetSumBitmap(D, v);

	int added = 0;
	
	vector<bool>::iterator pNull = D.begin();

	while ((pNull = find(pNull, D.end(), false)) != D.end())
	{
		int ind = pNull - D.begin();
		updateSubsetSumBitmap(D, ind);
		added++;
	}

	return added;
}

void testSmallestNumberOfAddedElements()
{
	vector<int> A = { 1,3,5 };
	int N = 8;
	int res = getSmallestNumberOfAddedElements(A, N);
}

- AP September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the right idea. Below is the working C++ implementation. Basically, we're adding elements and solving subset sum problem repeatedly. Complexity is O(N*(n+k)) where n is the original number of array elements and k is added

void updateSubsetSumBitmap(vector<bool> &D, int val)
{
	for (int i = D.size() - 1; i >= val; i--)
	{
		if (!D[i] && D[i-val])
		{
			D[i] = true;
		}
	}
}

int getSmallestNumberOfAddedElements(vector<int> &A, int N)
{
	vector<bool> D(N+1);
	D[0] = true;
	for (int v : A)
		updateSubsetSumBitmap(D, v);

	int added = 0;
	
	vector<bool>::iterator pNull = D.begin();

	while ((pNull = find(pNull, D.end(), false)) != D.end())
	{
		int ind = pNull - D.begin();
		updateSubsetSumBitmap(D, ind);
		added++;
	}

	return added;
}

void testSmallestNumberOfAddedElements()
{
	vector<int> A = { 1,3,5 };
	int N = 8;
	int res = getSmallestNumberOfAddedElements(A, N);
}

- AP September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This should work:

class Solution {
  
  
  public static void main(String[] args) {
    int[] arr = {1, 3, 5};
    System.out.println(findN(arr, 6));
  }
  
  public static int findN(int[] arr, int n) {
    int res = 0;
    ArrayList<Integer> al = new ArrayList<Integer>();
    for (int elem : arr)
      al.add(elem);
    for (int i = 1; i <= n; i++) {
      if (false == findX(al, i)) {
        res++;
        al.add(i);
      }
    }
    return res;
  }
  
  private static boolean findX(ArrayList<Integer> arr, int x) {
    return internalFindX(arr, x, new boolean[arr.size()], 0);
  }
  
  private static boolean internalFindX(ArrayList<Integer> arr, int x, boolean[] arrBool, int currSum) {
    boolean b_res = false;
    
    if (currSum == x)
      return true;
    
    if (currSum > x)
      return false;
    
    // currSum < x
    for (int i = 0; i < arr.size(); i++) {
      if (arrBool[i])
        continue;
      currSum += arr.get(i);
      arrBool[i] = true;
      b_res |= internalFindX(arr, x, arrBool, currSum);
      if (b_res)
        return b_res;
      currSum -= arr.get(i);
      arrBool[i] = false;
    } 
    return b_res;
  }
}

- upak August 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This seems to give the right answer, but the code isn't exactly very self-explanatory.

- heikki.salokanto August 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's a backtracking approach, exponential in complexity.

- Vishal August 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we need to have all powers of 2 that are less than N in the array, so you need to add int(log(N))+1 minus the amount of powers of 2 already in the array

- javier.sardinas August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Imagine [1,3,5] and N=6. We only need to add the integer 2 to the array, even though the array has no powers of 2.

- eric decker August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It becomes an O(n) time loop through the array seeing how many of the powers of 2 we have and then returning how many we need minus that count.

- jbaum517 August 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int solve(int n, vector<int> &v) {
    sort(v.begin(), v.end());
    int cnt = 0;
    int up = 0;
    int i = 0;
    while (up < n) {
        if (i < v.size() && v[i] <= up)
            up += v[i++];
        else
            up += up + 1, cnt++;
    }
    return cnt;
}

- zhaotianzju August 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My previous below solution gives only number of elements needed without even traversing the array.

Minimum floor(Log(N))+1 elements will be needed to make all 1 to N numbers using ADD operation.

2^0 = 1 (if N<=1 then required number of elements is 0+1 = 1)
2^1 = 2 (if N>=2 & N<=3 then required number of elements is 1+1 = 2)
2^2 = 4 (if N>=4 & N<=7 then required number of elements is 2+1 = 3)
2^3 = 8 (if N>=8 & N<=15 then required number of elements is 3+1 = 4)
2^4 = 16 (if N>=16 & N<=31 then required number of elements is 3+1 = 4)

Here is solution what numbers need to be added to the array.

1. add 1 at index 0 in solutionArray
2. if 1 is already there in inputArray then just increment the index of inputArray.
3. loop while solutionArray[solutionIndex]*2 < N
4. check if next element in inputArray is less than current solutionIndex value * 2.
if(true) then copy the element from inputArray
else add solutionIndex value * 2 in the solution array.

//below is the code snippet, I am considering input array is in sorted format and taking extra array to avoid shifting the elements in existing array

int solutionIndex = 0;
int inputIndex = 0;

if (N < 1)
	return;
	
solutionArray[solutionIndex++] = 1;
if(inputArray[inputIndex] == 1)
			inputIndex++;		

while( solutionArray[solutionIndex]*2 < N) {
	if((solutionArray[solutionIndex]*2) > inputArray[inputIndex]) {
			//No new element is need to be added, just copy the element from inputArray[].
			solutionArray[++solutionIndex] = inputArray[inputIndex++];
		}
	else {
		// add Array[index]*2 in the array as next element at index+1 position
		solutionArray[solutionIndex+1] = solutionArray[solutionIndex] * 2
		solutionIndex++;
	}
}

returnt solutionArray;

- Naveen August 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did you test this code? If I understood your solution correctly, you are not increasing solutionIndex correctly. Lets consider a simple case when arr[] = {1, 3, 5} and N = 7,
You enter loop with solutionIndex and inputIndex both equal to 0. In first iteration, since the solutionIndex is 0, it will enter into the if condition, you are adding 1 to solution array. But since you are not incrementing solutionIndex, you will always come in the if condition and run into an infinite loop.

- Mukesh August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code will run into infinite loop. Your solutionIndex is always 0 and keeps falling into first if condition.

- Mukesh August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Observation if you already generate/process the values until M (where M < N) the next required value is sum(values in array) + 1. Eje:

Int[] a = {5, 9};
Int n = 20;

And you already processed until 5 (M = 5) so you array currently is { 1, 2, 4, 5, 9 } the sum of those values is 12 = 1 + 2 + 4 + 5 so the next required value is 13. But you need to take in consideration that can be values between 5 and 13 in this case 9; so adding 1, 2, 4 to the original array [5, 9] you can generate until 21.

public List<int> NeededValues(int[] a, int n)
{
    List<int> values = new List<int>();
    if (a == null || a.Length == 0)
        return values;

    int sum = 0;
    int index = 0;
    int i = 1;

    while (i <= n)
    {
        if (index < a.Length && i == a[index])
        {
            sum += a[index];
            index++;
        }
        else if (sum < i)
        {
            sum += i;
            values.Add(i);
        }

        i++;
    }

    return values;
}

- hnatsu August 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.util.stream.*;
public class HelloWorld{

     public static void main(String []args){
        int[] arr={1, 3, 3, 3} ;
        int N=11;
        System.out.println(getNum(arr, N));
     }
     
     public static int getNum(int[] arr, int num){
         int count=0;
         List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
         Collections.sort(list);
         LinkedList<Integer> llist = new LinkedList<>(list);
         for(int i=1; i<=num; i++){
             if(isNumCanBeFormed(i, llist, 0, 0)){
                 continue;
             } else{
                 System.out.println("current list: "+llist+"\n"+"cannot form:: "+i);
                 insertAtRightIndex(i, llist);
                 count++;
             }
         }
         return count;
     }
     
     private static void insertAtRightIndex(int num, List<Integer> llist){
         if(llist instanceof LinkedList){
            int i=0;
            for(; i<llist.size(); i++){
                if(num<llist.get(i)){
                 break;
                }
            }
            llist.add(num, i);
         } else{
             llist.add(num);
             Collections.sort(llist);
         }
         
     }
     
     private static boolean isNumCanBeFormed(int num, List<Integer> list, int index, int sum){
         if(index>=list.size() || list.get(index)>num){
             return false;
         }
 
        boolean flag =false;
        for(int i=index; i<list.size(); i++){
             sum +=list.get(i);
             if(num==sum){
                return true;
             }
            flag |= isNumCanBeFormed(num, list, i+1, sum-list.get(i));
         }
         return flag ;
     }
}

Time Complexity:- O(n*2^m), where n=N and m =arr.length

- infinity August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's really a good problem

- malinbupt September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here its my faster solution in dp... :D


int dp[10000][10],n;
int main(){
cin>>n;
dp[0][0]=0;
for(int i=1;i<10;i++) dp[1][i]=1;

for(int i=2;i<=n;i++){
for(int j=0;j<10;j++){
if(j<5){
for(int k=j+4;k<10;k++)
dp[i][j]+=dp[i-1][k];
if(j==4)
{
dp[i][j]+=dp[i-1][0];
}
}
else if(j>5){
for(int k=0;k<=j-4;k++)
dp[i][j]+=dp[i-1][k];
}
else{
dp[i][j]+=(dp[i-1][0]+dp[i-1][9]+dp[i-1][1]);
}
}
}
int ans=0;
for(int i=0;i<10;i++) ans+=dp[n][i];
cout<<ans;
return 0;
}

- !dmn February 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

addNumbers(int n, int[] arr) {
	Collections.sort(arr);
	int sum = 0;
	int ans = 0;
	int last = 0;

	for ( int i = 0; i < ar.size(); i ++ ) {
		while ( ar.get(i) > sum ) {
			sum += last;
			last ++;
			ans ++;
		}
	}

	return ans;
}

- gime July 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main ()
{
int n,sum=0;
cin>>n;
int m,i,t;
cin>>m;
int a[m];
for (i=0;i<m;i++)
{
cin>>a[i];
}
for (i=0;i<m;i++)
{
sum=sum+a[i];
}
t=n-sum;
cout<<t;
}

- maheshvangala1997 June 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Find X^2 + X = 2*N Where N is given. Solve this equation.
Number of Required Element is = ceil(X) - n , Where n is number of element in array.

- Anonymous August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Solve X(X+1) = 2*N , where N is given.

Number of Required Element is = ceil(X) - n , Where n is number of element in array.

- manidam07 August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the logic? How did you arrive at that equation?

- aka[1] August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

By using X(X+1) = 2*N i am trying to find sum of natural numbers.
For Ex if N is 6 then x will come as 3 so we need {1,2,3} as element. By using these 3 element you can make any number from 1 to 6...

same If N = 7 then ceil of X will comes as 4. here if is impossible to get 7 if we have only {1,2,3} as element so we add new element as 4. So now by using {1,2,3,4} we can make any element from 1 to 10.

Again if number is 11 then you need to add 5 in your set. so by using {1,2,3,4,5} you can make any number form 1 to 15....

So once we got X then total number of element in array - X will give the answer.

PS: i am considering array will have all the element lower then required N.
If array have element grater then N, then after finding X we need to check set {1 to X} present in array or NOT. if any element from this set {1 to X} not present then increase the count.

- manidam07 August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The question is to find out how many numbers are required to make a sum equal to a given integer N.
The array should contain at least first x natural numbers to make this sum.
The sum can be given by sum of first x natural numbers N = x*(x+1)/2.
So to know how many numbers are required in the array solve the equation to get X.

#include <iostream>
#include <math.h>
using namespace std;

//Get the element to be added by deducting
// the lenght of the given array from (-1+sqrt(1+8n))/2
int getMinNumElementsToAdd(int lengthOfArr, int n)
{
    double TotalElemReqd = ceil((-1+sqrt(8*n+1))/2) - lengthOfArr;
    return TotalElemReqd;
}

int main()
{
    int a[] = { 1,2,9};
    int num = 10;
    int lengthOfArr = sizeof(a)/sizeof(int);
    int n = getMinNumElementsToAdd(lengthOfArr, num);
    cout<<"Number of elements to add = "<<n<<endl;
    return 0;
}

- jeetscoder August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about n=1023 and arr[]={}. It seems that we only need to add 1, 2, 4, 8,...,512 to meet the requirement.

- Anonymous August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about N=1024 and array[]={}? It seems that we only need to add 1, 2, 4, 8, ..., 512 to meet the requirement.

- flexwang August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is my code for this one:
1. Sort the array: O(nlgn)
2. Search the array and check the maximum No. can be reached with 1~preVal.
(1). If the No. in array is equal to preVal, update maxreach, look at next.
(2). If the No. in array is bigger than preVal, update maxreach, put this No. into result.
Python code:

def leastNo(array, N):
if array is None:
array = []
array.sort()
maxreach, preVal, index, res = 0, 0, 0, []
while maxreach < N and index < len(array):
if array[index] <= 0:
continue
if array[index] > preVal + 1:
res.append(preVal + 1)
else:
index += 1
maxreach += preVal + 1
preVal += 1
while maxreach < N:
res.append(preVal + 1)
maxreach += preVal + 1
preVal += 1
return res

testcase:
leastNo(None, 10)
[1,2,3,4]
leastNo([], 6)
[1,2,3]
leastNo([3,2,1], 10)
[4]
leastNo([3,1,4], 7)
[2]
leastNo([3,1], 6)
[2]
leastNo([8,4,2,3,1,9], 10)
[]

I don't know how to maintain white space, sorry...
Looking for better ideas~ Thanks!

- impromptuRong August 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is this a NP-hard problem?

- FSM August 13, 2015 | 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