Coding Interview

coding interview questions part 2

Pinterest LinkedIn Tumblr

Subsets With Duplicate

Detect duplicate in a subset from a set of elements.
If we give the number of elements as 2, we will get 2^2= 2 * 2 = 4 output subsets.
If we give the number of elements as 3, we will get 2^3= 2 * 2 * 2 = 8 output subsets.
Example:-
Input array :[1, 2]
Output subsets:[[2], [1, 2], [1], []].

Source Code

package com.dsacode.Probelms;


public class FactTrailingZero {
	
	public static int TrailingZeros(int num){
		int count=0;
		if(num<0)
			return 0;
		for(int i=5;num/i>0; i=i*5){
			count+=num/i;
		}
		return count;
	}
	public static void main(String[] args){
		System.out.println("The Trailing Zeros of 23!:"+TrailingZeros(23));
		System.out.println("The Trailing Zeros of 101!:"+TrailingZeros(101));
		
	}
}
#include "stdafx.h"

#include < iostream >
#include < vector >
#include < algorithm >
using namespace std;

vector < vector < int > > subsetsWithDup(vector < int > &S) {
	vector < int > set = S;
	sort(set.begin(), set.end());  
	vector < int > counts(set.size(), 1);
	vector < vector < int > > superset = { {} };
	for (int i = 0; i < set.size(); i++) {
		if (i > 0 && set[i - 1] == set[i]) {
			counts[i] = counts[i - 1] + 1;  
		}
		int size = superset.size();
		for (int j = 0; j < size; j++) {
			if (!superset[j].empty() && superset[j].back() == set[i]) {
				continue;  
			}
			vector < int > subset = superset[j];

			for (int k = 0; k < counts[i]; k++) {
				subset.push_back(set[i]);
			}
			superset.push_back(subset);
		}
	}
	return superset;
}

int _tmain(int argc, _TCHAR* argv[])
{
	vector < int > test = { 1, 2, 3 };

	cout << "Input array   :";
	for (std::vector < int >::const_iterator i = test.begin(); i != test.end(); ++i)
		std::cout << *i << ' ';

	cout << endl<< "Output subsets:[";
	vector< vector < int > > result = subsetsWithDup(test);
	for (int i = 0; i < result.size(); ++i)
	{
		cout << "[";
		for (int j = 0; j < result[i].size(); ++j)
			if (j == result[i].size()-1)
				cout << result[i][j];
			else
				cout << result[i][j] << ",";
		cout << "], " ;
	}
	cout << "]" << endl;
	return 0;
}

Output

Input array   :[1, 2, 3]
Output subsets:[[3], [2, 3], [2], [1, 3], [1, 2, 3], [1, 2], [1], []]

Algorithm Explanation

Get existing sets from the array and add to the previous array list.
Add the current number to each element of the set.
Add each single number as a set, only if the current element is different with previous.
Add all set created in this iteration and Return the set.

1 2 3 4 5

Write A Comment