Google Interview Question Software Developers
Country: India
Interview Type: In-Person
this is O(n!) right ? it might work for smaller values of N but something above 100 will take a long time...
I like the implementation but the 4 should not be part of the result because is all sub sets.
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).
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()) {
output.add(s);
}
return output;
}
public List sumOfNumberHelper(int n, Hashtable h, String prev) {
if (n < 0) {
return;
}
if (n == 0) {
h.add(prev.hashCode(), prev);
}
for (int i = 1; i < n; i++) {
sumOfNumberHelper(n - i, h, prev.append(i))
}
}
Maybe I am not understanding the problem.
Why is 22 not an output?
Why is 112 output twice?
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();
}
}
}
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();
}
}
}
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[0] = [[]]
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]
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[0] = [[]]
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]
Python solution:
def number_subset(n):
q = []
q.append([1]*n)
results = set([])
results.add("".join([str(item) for item in q[0]]))
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)
results.add(str_y)
return results
#main
n = 4
print number_subset(n)
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[0]--;
l[1]++;
if (l[0] == 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++)
{
numbers.Add(1);
}
return numbers;
}
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[0]--;
l[1]++;
if (l[0] == 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++)
{
numbers.Add(1);
}
return numbers;
}
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[0]--;
l[1]++;
if (l[0] == 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++)
{
numbers.Add(1);
}
return numbers;
}
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{
list.addLast(i);
printSubsets(j);
}
}
}
List<List<Integer>> getElems(int sum, int prev){
List<List<Integer>> curElems = new ArrayList<List<Integer>>();
if(sum == 0){
curElems.add(new ArrayList<Integer>());
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){
elems.add(0,i);
curElems.add(elems);
}
}
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.
List<List<Integer>> getElems(int sum, int prev){
List<List<Integer>> curElems = new ArrayList<List<Integer>>();
if(sum == 0){
curElems.add(new ArrayList<Integer>());
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){
elems.add(0,i);
curElems.add(elems);
}
}
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.
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);
newList.add(Integer.toString(number));
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;
newList.add(newCombination);
}
}
}
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
- NL March 21, 20151 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4