Google Interview Question for Software Developers

Country: India
Interview Type: In-Person

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

Java approach:

public static void main(String[] args) {
allSubsets(4, "");
}

private static void allSubsets(int num, String out) {
if(num == 0){
System.out.println(out);
} else if (num > 0){
for(int i = 1; i <= num; i++)
allSubsets(num - i, out + " " + Integer.toString(i));
}
}

1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4

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

this is O(n!) right ? it might work for smaller values of N but something above 100 will take a long time...

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

This is a n! algorithm can you optimize the code ??

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

I like the implementation but the 4 should not be part of the result because is all sub sets.

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

Guys, first of all, it's O(2^n) because there're 2^N-1 ways to sum up N and we don't make any spare runs without forming a combination or recurring.
Second, there's no way to optimize it to something lower because of the very problem statement. Even if you already had all combinations precalculated and stored, you need some time to simply enumerate them (even skipping the need to output).

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

Recursively check all unique combinations

public List sumOfNumber(int n) {

Hashtable h = new Hashtable();

sumOfNumberHelper(n, h, "");

List output = newList<String>();

for (String s : h.values()) {

}

return output;
}

public List sumOfNumberHelper(int n, Hashtable h, String prev) {

if (n < 0) {

return;
}

if (n == 0) {

}

for (int i = 1; i < n; i++) {

sumOfNumberHelper(n - i, h, prev.append(i))
}
}

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

Maybe I am not understanding the problem.
Why is 22 not an output?
Why is 112 output twice?

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

I think you are understanding it correctly as those were my thoughts as well. Probably just a typo.

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

void PrintSubsets(int n, int currSum, vector<int>& combinations)
{
if (n == currSum)
{
for (auto item : combinations)
cout << item << " ";
cout << endl;
return;
}

for (int i = 1; i <= (n - currSum); i++)
{
if ((currSum + i) <= n)
{
combinations.push_back(i);
PrintSubsets(n, currSum + i, combinations);
combinations.pop_back();
}
}
}

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

void PrintSubsets(int n, int currSum, vector<int>& combinations)
{
if (n == currSum)
{
for (auto item : combinations)
cout << item << " ";
cout << endl;
return;
}

for (int i = 1; i <= (n - currSum); i++)
{
if ((currSum + i) <= n)
{
combinations.push_back(i);
PrintSubsets(n, currSum + i, combinations);
combinations.pop_back();
}
}
}

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

This doesn't make sense as phrased. Based on the example input/output, I assume the intention was this: given an integer N, determine all ordered subsets of the unordered set {1,2,3,...,N} whose sum is N.

In that case, this is just a classic dynamic programming problem. Define S[i] to be the set of subsets of {1,2,3,...,N} whose sums equal i, for 1 <= i <= N. Then we observe the following recurrence relation:

S[i] = {{1} U X for X in S[i-1]} U {{2} U X for X in S[i-2]} U ... U {i}.

Here's this bottom-up memoized implementation of this recurrence in Python, which works well for this sort of thing thanks to its list comprehensions:

def subsets(N):
S = [[] for i in range(0,N+1)]
S = [[]]
for i in range(1, N+1):
for j in range(1, i+1):
S[i] += [[j] + X for X in S[i-j]]
return S[N]

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

Nice recurrence. One minor additional step is to compute or print all permutations of each set in S[N] you have defined above (unless I'm mistaken in that S[N] indeed stores all ordered sets).

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

This doesn't make sense as phrased. Based on the example input/output, I assume the intention was this: given an integer N, determine all subsets of {1,2,3,...,N} whose sum is N.

In that case, this is just a classic dynamic programming problem. Define S[i] to be the set of subsets of {1,2,3,...,N} whose sums are i, for 1 <= i <= N. Then we observe the following recurrence relation:

S[i] = {{1} U X for X in S[i-1]} U {{2} U X for X in S[i-2]} U ... U {i}.

def subsets(N):
S = [[] for i in range(0,N+1)]
S = [[]]
for i in range(1, N+1):
for j in range(1, i+1):
S[i] += [[j] + X for X in S[i-j]]
return S[N]

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

Python solution:

def number_subset(n):
q = []
q.append(*n)
results = set([])

while (len(q) != 0):
x = q.pop(0)
for i in range(1, len(x)):
y = x[0:(i-1)] + [ x[i-1] + x[i] ] + x[(i+1):]
str_y = "".join([str(item) for item in y])
if str_y not in results:
q.append(y)

return results

#main
n = 4
print number_subset(n)

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

This code prints for Sum(4) following result:
1, 1, 1, 1,
2, 1, 1,
1, 2, 1,
3, 1,
2, 2,
1, 3,
4,

private void Sum(int goal)
{
List<int> l = GetOnes(goal);
Print(l);

while (l.Count > 1)
{
l--;
l++;
if (l == 0)
{
l.RemoveAt(0);
}

Print(l);
}
}

private void Print(List<int>l)
{
foreach(int i in l)
{
Console.Write(i);
Console.Write(", ");

}
Console.WriteLine();
}

private List<int> GetOnes(int result)
{
List<int> numbers = new List<int>();
for (int i = 0; i < result; i++)
{
}

return numbers;
}

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

This code (c#) prints
1, 1, 1, 1,
2, 1, 1,
1, 2, 1,
3, 1,
2, 2,
1, 3,
4,

for Sum(4)

private void Sum(int goal)

{

List<int> l = GetOnes(goal);

Print(l);

while (l.Count > 1)

{

l--;

l++;

if (l == 0)

{

l.RemoveAt(0);

}

Print(l);

}

}

private void Print(List<int>l)

{

foreach(int i in l)

{

Console.Write(i);

Console.Write(", ");

}

Console.WriteLine();

}

private List<int> GetOnes(int result)

{

List<int> numbers = new List<int>();

for (int i = 0; i < result; i++)

{

}

return numbers;

}

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

This code (c#) prints
1, 1, 1, 1,
2, 1, 1,
1, 2, 1,
3, 1,
2, 2,
1, 3,
4,

for Sum(4)

private void Sum(int goal)
{
List<int> l = GetOnes(goal);
Print(l);
while (l.Count > 1)
{
l--;
l++;
if (l == 0)
{
l.RemoveAt(0);
}
Print(l);
}
}
private void Print(List<int>l)
{
foreach(int i in l)
{
Console.Write(i);
Console.Write(", ");
}
Console.WriteLine();
}
private List<int> GetOnes(int result)
{
List<int> numbers = new List<int>();
for (int i = 0; i < result; i++)
{
}
return numbers;
}

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

public void printSubset(int n, String s)
{
if(n == 0)
System.out.println(s);
for(int i=1; i<=n; i++)
{
printSubset( n-i, s + i);
}

}

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

public static void printSubsets(int number){
if(number < 0)
return;
if(number==0){
int result=0;
for (Iterator iterator = list.iterator(); iterator.hasNext();) {
Integer integer = (Integer) iterator.next();
result = result * 10 + integer;
}
System.out.println(result);
if(list.size() > 0)
list.removeLast();
return;
}

for (int i = 1; i < 10; i++) {
int j =  number - i;
if(j<0){
if(list.size() > 0)
list.removeLast();
return;
}else{
printSubsets(j);
}
}
}

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

List<List<Integer>> getElems(int sum, int prev){

List<List<Integer>> curElems = new ArrayList<List<Integer>>();
if(sum == 0){
return curElems;
}

int start = Math.min(sum, prev);
for(int i=start; i>=1; i--){
List<List<Integer>> restElems = getElems(sum-i,i);
for(List<Integer> elems : restElems){
}
}
return curElems;

}

Also can optimize by caching all mid result to avoid redoing sub problem in recursive way. Even if using iterative way, still need space to cache. By cache can save some time, but it goes tremendous cache when calculating big number. A trade-off should be considered obviously.

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

List<List<Integer>> getElems(int sum, int prev){

List<List<Integer>> curElems = new ArrayList<List<Integer>>();
if(sum == 0){
return curElems;
}

int start = Math.min(sum, prev);
for(int i=start; i>=1; i--){
List<List<Integer>> restElems = getElems(sum-i,i);
for(List<Integer> elems : restElems){
}
}
return curElems;

}

Also can optimize by caching all mid result to avoid redoing sub problem in recursive way. Even if using iterative way, still need space to cache. By cache can save some time, but it goes tremendous cache when calculating big number. A trade-off should be considered obviously.

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

this is another recursive solution that uses a map to cache the intermittent results to avoid recursive calls for same numbers

public List<String> getAllPossibleSubsets(int number) {
Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
getAllPossibleSubsets(number, map);
return map.get(number);
}

private void getAllPossibleSubsets(int number, Map<Integer, List<String>> map) {
List<String> newList = new ArrayList<String>();
map.put(number, newList);
for (int i = 1 ; i < number ; i++) {
int remaining = number - i;
if (!map.containsKey(remaining)) {
getAllPossibleSubsets(remaining, map);
}
List<String> list = map.get(remaining);
for (String combination : list) {
String newCombination = Integer.toString(i) + "," + combination;
}
}
}

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.