Adobe Interview Question for Computer Scientists


Country: India
Interview Type: In-Person




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

this is the perfect solution in c++. My previous solution was not giving all outputs...

#include <iostream>
#include <stdio.h>
#include<map>
#include<list>

using namespace std;

static int cnt=0;
int sum(int data[], int r)
{
	int sum=0; 
	for(int i=0; i<r; i++)
	{
		sum+=data[i];
	}
	return sum;
}

int check_list(const std::list<int> l, const std::list<int> m) 
{
	int set=1;
  	for (list<int>::const_iterator it1 = l.begin(), it2=m.begin(); it1 != l.end(); it1++, it2++ ) 
 	{
        	if(*it1!=*it2)
        	{
        		set=0;
        		break;
        	}
  	}
  	return set;
}

void combinationUtil(map<int, list<int>> &m, int arr[],  int data[], int start, int end, int index, int r, int k)
{
    if (index == r)
    {
    	if(sum(data, r)==k)
    	{
	    	list<int> l;
	    	for(int i=0; i<r ;i++)
	    	{
	    		l.push_back(data[i]);
	    	}
	    	l.sort();

	        int present=0;
	        for (map<int,std::list<int>>::const_iterator it = m.begin(); it != m.end(); it++) 
  			{
				 if(check_list(it->second, l)!=0)
				 {
				 	present=1;
				 }
			}
			if(present==0)
	       	{
	       		m.insert (pair<int,list<int>>(cnt++,l) );
	       	}
    	}
        return;
    }
 
    for (int i=start; i<=end && end-i+1 >= r-index; i++)
    {
        data[index] = arr[i];
        combinationUtil(m, arr, data, i+1, end, index+1, r, k);
    }
}

void printCombination(map<int, list<int>> &m, int arr[], int n, int r, int k)
{
    int data[r];
 
    combinationUtil(m, arr, data, 0, n-1, 0, r, k);
}

void dump_list(const std::list<int> l) 
{
  	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++ ) 
 	{
        	cout << *it << " ";
  	}
  	cout<<endl;
}

int main()
{
    int arr[] = {2,3,4,1,3,2,6,-1};
    int k = 5;
    int n = sizeof(arr)/sizeof(arr[0]);
    map<int, list<int>> m;
    for(int i=1; i<=n; i++)
    {
    	printCombination(m, arr, n, i, k);
    }

    for (map<int,std::list<int>>::const_iterator it = m.begin(); it != m.end(); it++) 
  	{
	    dump_list(it->second);
	}
}

- sudeep91soni January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int compareInts (const void * a, const void * b)
{
  if ( *(int*)a <  *(int*)b ) return -1;
  if ( *(int*)a == *(int*)b ) return 0;
  if ( *(int*)a >  *(int*)b ) return 1;
}

void print (int* elem, int n)
{
	for (int i=0;i<n;++i)
		cout << elem[i] << " ";
	cout << endl;
}

void findallsubsets (int sum, vector<int> prefix, int* a, int k, int n)
{
	if (k > n || sum < 0)
		return;

	if (sum == 0)
	{
		print (&prefix[0], prefix.size());
		return;
	}

	prefix.push_back (a[k]);
	findallsubsets (sum-a[k], prefix, a, k+1,n);
	prefix.pop_back ();

	findallsubsets (sum, prefix, a, k+1,n);
}

void findallsubsets (int sum, int* elem, int n)
{
	qsort (elem, n, sizeof (int), compareInts);
	int* l = std::unique (elem, elem+n);
	cout << "Sorted:" << endl;
	print (elem,l-elem);

	cout << "Subsets:" << endl;
	vector<int> v;
	findallsubsets (sum, v, elem, 0, l-elem);
}

- Anonymous June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not produce subsets that have a repeating element for eg 2, 2, 1 etc.

- _rahulg June 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Okay anyone with a better solution than the brute force approach ??

- Sorrowfull Blinger September 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we need to remove sum < 0 check here. Partial sum can become negative but total sum can become 0 eventually ex: with prefix as 2, partial sum as 3 - 4 = -1 should be explored as it can lead to 0 with 1.

why pass unique elements, can't just pass all ?

- Vib December 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print(int *arr,int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int printAllSubsets(int *arr,int n,int last_selected,int pos,int *ele,int sum)
{
//arr is the main array
//n is the size of the array
//last_selected is the last selected element of the arr array
//pos is the current postion in ele array
//sum is the sum to be found
//cout<<"Current Sum :- "<<sum<<endl;
if(last_selected==n)
return 1;
if(sum<0)
{
return -1;
}
if(sum==0)
{
print(ele,pos);
return 0;
}
int check=1;
int flag=0;
for(int i=last_selected+1;i<n;i++)
{
ele[pos]=arr[i];
check=printAllSubsets(arr,n,i,pos+1,ele,sum-arr[i]);
if(check==0)
{
flag=1;
int j=i+1;
while(j<n && arr[j]==arr[i])
j++;
i=j-1;
}
}
if(flag==1)
return 0;
else return 1;
}
int partition(int *arr,int low,int high)
{
int left=low+1;
int right=high;
int pivot=arr[low];
while(left<=right)
{
if(arr[left]<=pivot)
left++;
if(arr[right]>=pivot)
right--;
if(left<right)
{
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
}
int temp=arr[low];
arr[low]=arr[right];
arr[right]=temp;
return right;
}
void quick_sort(int *arr,int low,int high)
{
if(low<high)
{
int pos=partition(arr,low,high);
quick_sort(arr,low,pos-1);
quick_sort(arr,pos+1,high);
}
}
int main()
{
/*int arr[]={1,2,3,4,5,6,7,8};
int size=sizeof(arr)/sizeof(arr[0]);
printArray(arr,size);
swapArray(arr,0,size-1);
printArray(arr,size);
getchar();*/
/*int arr[]={1,2,3,4,5,6,7,8,9,10};
Tree t;
for(int i=0;i<=9;i++)
t.insert(arr[i]);
cout<<t.findMax()<<endl;*/
//PrintOneToN<100> b;
int arr[]={2,3,4,1,3,2,6,-1};
int n=(sizeof(arr))/sizeof(arr[0]);
quick_sort(arr,0,n-1);
//int *l=unique(arr,arr+n);
//n=l-arr;
int *ele=new int[n];
printAllSubsets(arr,n,-1,0,ele,5);
getchar();

}

- Shankar Lal Agarwal June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package questions;

public class Sort {
      public static void main(String[] args){
            int[] sample={1,3,5,-4,-5,9};
            int sum=8;
            int tempSum=0;
            for(int i=0;i<sample.length;i++){
                        tempSum=sample[i];
          
                        for(int j=i+1;j<sample.length;j++){
                              tempSum=tempSum+sample[j];
          
                              if(tempSum==sum){
          
                                    for(int a=i;a<=j;a++){
                                          System.out.print(sample[a]+" ");                                       
                                    }
                                    System.out.println("\n");
                              }
                                         
                        }
          
                             
                       
                  }
                 
            }

}

- check this out... June 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int n;
std::vector<int> in;

void printSubset(std::vector<int> &partialSubset)
{
	for (int i = 0; i < partialSubset.size(); ++i)
	{
		cout<<partialSubset[i]<<",";
	}
	cout<<endl;
}

void findSubSet(int pos, int sum, std::vector<int> &partialSubset)
{
	if(sum == 0) 
	{
		printSubset(partialSubset);
		return;
	}
	if(pos >= n) return;
	if(in[pos] > sum) return;


	do {
		partialSubset.push_back(in[pos]);
		findSubSet(pos+1, sum - in[pos], partialSubset);
		partialSubset.pop_back();
		
		do{
			pos++;
		}while(pos<n && in[pos-1]==in[pos]);
	} while(pos < n);
}

int main(int argc, char const *argv[])
{
	int temp,sum;
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		cin>>temp;
		in.push_back(temp);
	}
	cin>>sum;
	sort(in.begin(), in.end());

	int i=0;
	while(i<n)
	{
		std::vector<int> partialSubset(1,in[i]);
		findSubSet(i+1,sum-in[i], partialSubset);
		do {
			i++;
		}while(i<n && in[i-1]==in[i]);
	}
	return 0;
}

- sc.shobhit June 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code prints subset of answer... but not all answers

package codeforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Setsofk {
	public static void main(String [] args)
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		List<Integer> li = new ArrayList<>();
		Map<Integer, List<Integer>> m = new HashMap<>();
		List<Integer> set=new ArrayList<>();
		try {
			int k=Integer.parseInt(br.readLine());
			String[] array=br.readLine().split(",");
			for(int i=0; i<array.length; i++)
			{
				li.add(Integer.parseInt(array[i]));
			}
			System.out.println(li);
			Collections.sort(li);
			System.out.println(li);
			int key=0;
			for(int i=0; i<li.size(); i++)
			{
				int sum=li.get(i);
				set.clear();
				set.add(li.get(i));
				for(int j=i+1; j<li.size(); j++)
				{
					sum=li.get(i);
					int l=j;
					while(l<li.size())
					{
						sum+=li.get(l);
						if(sum<k)
						{
							set.add(li.get(l));
						}
						else if(sum==k)
						{
							set.add(li.get(l));
							if(m.containsValue(set))
							{
								continue;
							}
							else
							{
								m.put(key, new ArrayList<Integer>(set));	
								key++;
								break;
							}
						}
						else if(sum>k)
						{
							break;
						}
						l++;
					}
					set.clear();
					set.add(li.get(i));
				}
			}
			System.out.println(m);
		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

- sudeep91soni January 14, 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