Facebook Interview Question Interns
Country: India
Interview Type: Phone Interview
Clever solution. The strategy is to use a bitmask pattern to generate all the combinations. I believe it can be optimized somewhat by removing the duplicate test from the loops and instead performing a one time addAll to a Set<String> once the loops have completed.
"set of integers with repeated occurences of elements" this is mathematically incorrect. A set does not have repeated elements. A Multiset does.
Anyway, we can shrink the input in pairs: (number, n_occurrences) and generate the power set with a recursive function. Sample code in C++:
void PowerSet(int i, const vector<pair<int,int> >& vo, vector<int>& cur) {
if (i == vo.size()) {
if (cur.size() == 0)
cout << "NULL" << endl;
else {
for (size_t i = 0; i < cur.size(); i++)
cout << cur[i] << " ";
cout << endl;
}
} else {
size_t cur_size = cur.size();
PowerSet(i+1, vo, cur); // don't use any of these numbers
for (size_t k = 1; k <= vo[i].second; k++) {
cur.push_back(vo[i].first); // use this number k times
PowerSet(i+1, vo, cur);
}
cur.resize(cur_size); // get cur vector to previous size
}
}
void PowerSet(int v[], int n) {
sort(v, v+n);
vector<pair<int,int> > voccur;
for (int i = 0; i < n ; i++) {
int num = 1;
for (; i+1 < n && v[i] == v[i+1]; i++)
num++;
voccur.push_back(make_pair(v[i], num));
}
vector<int> cur_set;
PowerSet(0, voccur, cur_set);
}
It looks like powerset problem!
for each element of input :
If it is visited for the first time, just add it to all sets that has been added to powerset.
else check hashmap to find number of this element that has been visited, then add new element to set(s) that has exactly this number of duplication.
public static void powerSet(ArrayList<Integer> input) {
ArrayList<ArrayList<Integer>> powerSet = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> set = new ArrayList<Integer>();
powerSet.add(set);
HashMap<Integer, Integer> hm = new HashMap<>();
int focoused;
int counter=0,dupCounter;
if (input.isEmpty())
System.out.println("null");
else {
while (!input.isEmpty()) {
focoused = input.remove(0);
int psize = powerSet.size();
counter=0;
dupCounter=0;
{
if(hm.containsKey(focoused))
{
hm.put(focoused, hm.get(focoused)+1);
dupCounter = hm.get(focoused);
for (int i = 0; i < psize; i++) {
for(Integer ii : powerSet.get(i))
if(ii==focoused)
counter++;
if(counter==dupCounter-1)
{
powerSet.get(i).contains(focoused);
set = (ArrayList<Integer>) powerSet.get(i).clone();
set.add(focoused);
powerSet.add(set);
}
counter=0;
}
}
else{
hm.put(focoused, 1);
for (int i = 0; i < psize; i++) {
set = (ArrayList<Integer>) powerSet.get(i).clone();
set.add(focoused);
powerSet.add(set);
}
}
}
}
System.out.println(powerSet.toString());
}
}
My complete code is as follows.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
void printSet(vector<int>& iset){
if(iset.size() == 0){
printf("NULL");
return;
}
printf("{");
for(int j = 0; j < iset.size(); j++){
printf("%d%s", iset[j],
j < iset.size() - 1 ? ", " : "");
}
printf("}");
}
int genPowerSetIdx(vector<int> &pset, int newIdx, vector<vector<int>> &result)
{
int numRepeat = 1;
int value;
int size = result.size();
assert(newIdx < pset.size());
value = pset[newIdx];
for(int i = newIdx + 1; i < pset.size(); i++){
if(pset[i] != value)
break;
numRepeat++;
}
for(int i = 0; i < size; i++){
vector<int> newSet = result[i];
for(int j = 0; j < numRepeat; j++){
newSet.push_back(value);
result.push_back(newSet);
}
}
return newIdx + numRepeat;
}
void genPowerSet(vector<int> &pset, vector<vector<int>> &result)
{
sort(pset.begin(), pset.end());
result.push_back(vector<int>{});
for(int i = 0; i < pset.size(); ){
i = genPowerSetIdx(pset, i, result);
}
return;
}
int main()
{
vector<int> pset;
vector<vector<int>> result;
pset = {1, 2, 2};
genPowerSet(pset, result);
printf("{");
for(int i = 0; i < result.size(); i++){
vector<int> &iset = result[i];
printSet(iset);
if(i < result.size() - 1)
printf(", ");
}
printf("}");
}
result:
{NULL, {1}, {2}, {2, 2}, {1, 2}, {1, 2, 2}}
void power_set(vector<int>& v, vector< vector<vector<int> > >& res){
res.push_back(vector<vector<int> >(1, vector<int>()));
if(v.size() == 0){
return;
}
res.push_back(res[0]);
res.back().push_back(vector<int>(1,v[0]));
if(v.size() == 1)
return ;
for(int i = 1; i < v.size(); i++){
int start = 0;
res.push_back(res.back());
if(v[i] == v[i-1]) start = res[res.size()-3].size();
vector<vector<int> > tmp = res[res.size()-2];
for(int j = start;j < tmp.size(); j++){
tmp[j].push_back(v[i]);
res.back().push_back(tmp[j]);
}
}
}
js code
function toCountMap(array) {
var map = {};
array.forEach(function (item){
if(item in map) {
map[item]++ ;
} else {
map[item] = 1;
}
});
return map;
}
function fromCountMap(map){
var buff = [];
for(var key in map){
var count = map[key];
for(var i=0;i<count;i++) {
buff.push(key);
}
}
return buff;
}
function cloneMap(map){
var clone = {};
for(var key in map) {
clone[key] = map[key];
}
return clone;
}
function allSubSet(map) {
var buff = [];
var numbers = [];
for(var number in map) {
numbers.push(number);
}
function r(index, tempMap) {
var n = numbers[index];
var count = map[n];
if(index >= numbers.length - 1 ) {
for(var c=0;c <= count;c++) {
var cMap = cloneMap(tempMap);
cMap[n] = c;
buff.push(cMap);
}
} else {
for(var c=0;c <= count;c++) {
var cMap = cloneMap(tempMap);
cMap[n] = c;
r(index+1, cMap);
}
}
}
r(0, {});
return buff;
}
function listAllSubArray(array){
return allSubSet(toCountMap(array)).map(fromCountMap);
}
// test code
JSON.stringify(listAllSubArray(["a", "b", "b", "c"]))
complexity O(2^k) where k is count different values
Can we assume that the input set is sorted and can contain duplicates as in S={1,2,2} instead of S={2,1,2}?
If we can assume so, the solution becomes simpler:
To generate a power set of a given a set of length n
1) Generate sets of size 0 to n.
Use the permutation/ combination algorithm for each sizes to generate the sets.
2) When doing so, you just need to remember the previously generated set.
For example, when generating sets of size 2, I would get {1,2} and {1,2} twice right after each other since they are sorted. So, I just record the previously generated set, compare with the currently generated set. If the set is different, print it.
Running time - 2^n
Space - Constant
python solution
from collections import defaultdict
seen = defaultdict(int)
def powerset(arr):
if len(arr) == 0: return [[]]
val = arr[0]
sets = powerset(arr[1:])
new_sets = []
for s in sets:
count = len([x for x in s if x == val])
if count == seen[val]:
new = s[:]
new.append(val)
new_sets.append(new)
seen[val] += 1
sets.extend(new_sets)
return sets
import java.util.Scanner;
class ARR
{
public static void main(String a[])
{
int m,s;
int k=0;
int arr[]=new int[5];
int temp[]=new int[5];
System.out.println("enter values for array");
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
arr[i]=sc.nextInt();
}
for(int i=0;i<5;i++)
{
int f=0;
for(int j=i-1;j>=0;j--)
{
if(arr[i]==arr[j])
{
f=1;
break;
}
}
if(f==0)
{
temp[k]=arr[i];
k++;
}
}
for(s=1;s<=k;s++)
{
int i;
for( i=0;i<s;i++)
{System.out.print("{");
System.out.print(temp[i]);
for(int j=i+1;j<s;j++)
{
System.out.print(","+temp[j]);
}
System.out.println("}\n");
}
}
}
}
import java.util.Scanner;
class ARR
{
public static void main(String a[])
{
int m,s;
int k=0;
int arr[]=new int[5];
int temp[]=new int[5];
System.out.println("enter values for array");
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
arr[i]=sc.nextInt();
}
for(int i=0;i<5;i++)
{
int f=0;
for(int j=i-1;j>=0;j--)
{
if(arr[i]==arr[j])
{
f=1;
break;
}
}
if(f==0)
{
temp[k]=arr[i];
k++;
}
}
for(s=1;s<=k;s++)
{
int i;
for( i=0;i<s;i++)
{System.out.print("{");
System.out.print(temp[i]);
for(int j=i+1;j<s;j++)
{
System.out.print(","+temp[j]);
}
System.out.println("}\n");
}
}
}
}
import java.util.Scanner;
class ARR
{
public static void main(String a[])
{
int m,s;
int k=0;
int arr[]=new int[5];
int temp[]=new int[5];
System.out.println("enter values for array");
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
arr[i]=sc.nextInt();
}
for(int i=0;i<5;i++)
{
int f=0;
for(int j=i-1;j>=0;j--)
{
if(arr[i]==arr[j])
{
f=1;
break;
}
}
if(f==0)
{
temp[k]=arr[i];
k++;
}
}
for(s=1;s<=k;s++)
{
int i;
for( i=0;i<s;i++)
{System.out.print("{");
System.out.print(temp[i]);
for(int j=i+1;j<s;j++)
{
System.out.print(","+temp[j]);
}
System.out.println("}\n");
}
}
}
}
static List<int[]> AllSets(int[] a)
{
return AllSets(a, 0, new List<int>()).ToList();
}
static IEnumerable<int[]> AllSets(int[] a, int i, List<int> curr)
{
if (i == a.Length)
{
yield return curr.ToArray();
}
else
{
foreach(var s in AllSets(a, i + 1, curr))
{
yield return s;
}
curr.Add(a[i]);
foreach(var s in AllSets(a, i + 1, curr))
{
yield return s;
}
curr.RemoveAt(curr.Count - 1);
}
}
public class PowerSet {
static void go(int index, int [] inp,String out) {
if( index == inp.length) return;
int pre = -1;
for(int i=index;i<inp.length;i++) {
String _o = out;
if(pre != inp[i]) {
if(out.equals("")) _o += inp[i];
else _o +=","+inp[i];
System.out.println(_o);
go(i+1,inp,_o);
pre=inp[i];
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] ip = {1,2,2};
Arrays.sort(ip);
go(0, ip, "");
}
}
C solution:
#include <stdio.h>
#include <math.h>
void print_subset(int *org_set, unsigned int set_map)
{
unsigned int i = 0;
printf ("{");
for (i = 0; set_map; i ++)
{
if (set_map & 0x1)
{
printf ("%d,", org_set[i]);
}
set_map >>= 1;
}
printf ("\b}");
}
int main (int argc, char *argv[])
{
int org_set[] ={1,2,3, 9,300,56, 7, 90};
unsigned int set_map = pow(2,sizeof(org_set)/sizeof(int));
unsigned int i = 0;
printf ("The number of subset is : %d\n", set_map);
printf ("{NULL}\n");
for (i = 1; i < set_map; i ++)
{
print_subset (org_set, i);
printf ("\n", i);
}
return 0;
}
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
public class PowerSet {
public static void main(String[] args) {
int [] ns = {0, 2, 1, 2};
System.out.println(powerSet(ns).toString());
}
public static Set<ArrayList<Integer>> powerSet(int [] ns){
AListComparator comp = new AListComparator();
Set <ArrayList<Integer>> all = new TreeSet<ArrayList<Integer>>(comp);
ArrayList<Integer> al = new ArrayList<Integer>();
all.add(null);
perm(0, ns, all, al);
return all;
}
private static void perm(int size, int [] ns, Set<ArrayList<Integer>> all, ArrayList<Integer> al){
for(int i = size; i < ns.length; i++ ){
ArrayList<Integer> tal = new ArrayList<Integer>();
if( al != null )
tal.addAll(al);
tal.add(ns[i]);
all.add(tal);
ArrayList<Integer> tal2 = new ArrayList<Integer>();
tal2.addAll(tal);
//And further processing.
perm(i + 1, ns, all, tal2);
}
}
}
class AListComparator implements Comparator<ArrayList<Integer>>{
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
if(o1 == o2){
return 0;
}else if ( o1 == null && o2 != null){
return -1;
}else if ( o1 != null && o2 == null ){
return 1;
}else if ( o1.size() < o2.size() ){
return -1;
}else if ( o1.size() > o2.size() ){
return 1;
}
for( int i = 0 ; i < o1.size(); i++ ){
if( o1.get(i) > o2.get(i))
return 1;
else if ( o1.get(i) < o2.get(i))
return -1;
}
return 0;
}
}
the key thing is that if the inputs are sorted.
we should skip expending the powerset from current element, if it has the same value as previous.
vector<vector<int>> powersets(vector<int> &num)
{
vector<vector<int>> ret;
vector<vector<int>> vv;
vector<int> v;
vv.push_back(v);
ret.push_back(v);
vector<int> ends;
ends.push_back(-1);
for(int i=0; i<num.size(); i++)
{
vector<vector<int>> nvv;
vector<int> nends;
for(int j=0; j<vv.size(); j++)
{
vector<int> v = vv[j];
int pre = -1;
for(int k=ends[j]+1; k<num.size(); k++)
{
if (pre >= 0 && num[k] == num[pre]){
continue;
}
pre = k;
vector<int> nv(v);
nv.push_back(num[k]);
nvv.push_back(nv);
nends.push_back(k);
ret.push_back(nv);
}
}
vv = nvv;
ends = nends;
}
return ret;
}
This code will be ok.
{
void Trace(std::vector<std::vector<int> > &rs, std::vector<int> & v, std::vector<int> & cnt, std::vector<int> & path, int k) {
rs.push_back(path);
for (int i = k; i < v.size(); i++) {
if (cnt[i] > 0) {
cnt[i]--;
path.push_back(v[i]);
Trace(rs, v, cnt, path, i);
path.pop_back();
cnt[i]++;
}
}
}
std::vector<std::vector<int> > PSet(std::vector<int> & num) {
std::map<int, int> tmap;
for (int i = 0; i < num.size(); i++) {
if (!tmap.count(num[i])) tmap[num[i]] = 0;
tmap[num[i]]++;
}
std::vector<int> v;
std::vector<int> cnt;
for (std::map<int, int>::iterator i = tmap.begin(); i != tmap.end(); i++) {
v.push_back(i->first);
cnt.push_back(i->second);
}
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, v, cnt, path, 0);
return rs;
}
We map input into set of form <x : count(x)>. Since each x can be taken from 0 to count(x) times we have total
Prod(count(x) + 1) for every distinct x
different subsets.
We can enumerate this subsets using value system with variable base, using same mask approach as in regular subset enumeration. But in our case, i-th digit of mask indicating how many times we peek i-th element of our set (in fact, in regular subset enumeration we do the same thing).
Here is sample code in C#:
static IEnumerable<List<int>> AllSubsets(int[] arr)
{
// next 2 steps can be done in linear time using hash table. here i use LINQ for short
var items = arr.Distinct().ToArray(); // get distinct items
var count = items.Select(x => arr.Count(k => k == x) + 1).ToArray(); // get their counts
Array.Sort(items, count); // for estetic purposes
int resSize = count.Aggregate(1, (x, y) => x * y); // each number k can be taken from 0 to count(k) times, so it is |Prod(count(k)+1) for each k| subsets in total
for (int i = 0; i < resSize; i++)
{
var mask = i;
var res = new List<int>();
for (int p = 0; p < items.Length; p++)
{
for (int c = mask % count[p]; c > 0; c--) res.Add(items[p]); // here c is p-s digit in mask
mask /= count[p];
}
yield return res;
}
}
void print(vector<int> mySet) {
vector<int> solution(mySet.size());
vector<int> prevSolution;
sort(mySet.begin(), mySet.end());
int n;
function<void(int, int)> back = [&](int k, int prevI) {
if(k == n) {
if(prevSolution != solution) {
cout << "{";
for(int i = 0; i < k; i++) {
cout << solution[i];
if(i < k - 1) cout << ", ";
}
cout << "}"<< endl;
prevSolution = solution;
}
}
else {
for(int i = prevI + 1; i < mySet.size(); i++) {
solution[k] = mySet[i];
back(k + 1, i);
}
}
};
for(n = 0; n <= mySet.size(); n++) {
back(0, -1);
}
}
A simple c# solution
using System;
using System.Linq;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
int[] array = new int[] { 2, 3, 3, 4 };
PowerSet ps = new PowerSet(array);
ps.ComputePowerSet();
}
public class PowerSet
{
int[] array;
List<int> prevList = null;
List<List<int>> powerSet;
public PowerSet(int[] array)
{
this.array = array;
this.powerSet = new List<List<int>>();
}
public void ComputePowerSet()
{
// Computing PowerSet by finding all sets of size in each for loop
for (int i=0; i<= array.Length; i++)
{
Permute(new List<int>(), 0, i);
}
// Prinitng PowerSet
foreach (var set in this.powerSet)
{
PrintList(set);
}
}
public void Permute(List<int> list, int level, int length)
{
if (list.Count == length)
{
if (!powerSet.Any() || !list.SequenceEqual(powerSet[powerSet.Count - 1]))
{
powerSet.Add(list.ToList());
}
return;
}
for (int i = level; i < array.Length; i++)
{
list.Add(array[i]);
Permute(list, i + 1, length);
list.RemoveAt(list.Count - 1);
}
}
public static void PrintList(List<int> list)
{
Console.Write("{ ");
foreach(var elem in list)
{
Console.Write(elem + ", ");
}
Console.WriteLine("}");
}
}
}
Python
from collections import defaultdict
# a list of numbers
def foo(lst):
dic = defaultdict(int)
for num in lst:
dic[num] +=1
output = 1
for key in dic:
output *= dic[key] +1
return output
if __name__ == '__main__':
print foo([1,2])
print foo([1,2,2])
print foo([1,2,2,3])
print foo([1,3,5,2,2,4,4,4])
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
int[] arr = {1,2,3};
boolean[] bflag = new boolean[arr.length];
for(int i=1;i<=arr.length;i++)
sets(arr,bflag,0,i,0);
}
public static void sets(int[] arr, boolean[] bflag, int currS, int size, int index){
if(currS == size){
// print
for(int i=0;i<arr.length;i++){
if(bflag[i]){
System.out.print(arr[i] + "," + " ");
}
}
System.out.println(" ");
return;
}
if(index >= arr.length){
return;
}
bflag[index] = true;
sets(arr, bflag, currS+1, size, index+1);
bflag[index] = false;
sets(arr, bflag, currS, size, index+1);
}
}
Folks, why aren't we discussing our algorithms in psuedocode or in english (writing steps)? That is the most important part if we want to discuss our solutions.
For this problem, you can solve it by using "techniques" that you should already have in your mind (but then later you can find a custom technique if it's worth optimizing.. but in this case you won't be able to do better):
{First step, figure out if you can remove duplicates in O(n) }
{There is a standard technique for this: }
1) Hash the elements of your array (which removes duplicates)
-> Assume you picked the write hash table and you can do the operations in amortized average time of O(1)
2) Reverse the hash table into a simple array A[i], which will now have no duplicates {you can use the oringal array to store A}
[Steps 1 and 2 are a technique for removing duplicates of integers from an array in O(n) time]
[If you didn't know how to do above, you could do it less optimally
a) Sort your original list (nlgn or n if you are able to use bucket/count sort)
b) Linear scan and create a new array without duplicates
{ Or even less optimally:
Brute force O(n^2) to remove duplicates
POINT: Don't give up. Break your problem into steps and use brute force methods in some steps if you can't think of any better. }
3) Use a "n-bit generating" function to generate bits strings of length n
[You should have such a function memorized for use in these set generation problems... if not commit to memory how to make this function]
4) In the base case of 3), instead of printing the n-bit binary numbers, print sets from the array you created in 2) above in this way:
if your binary number is 0011010...
your output set will be { A[i] such that position i in bit string is 1 }
Algorithm runtime:
These type of problems always require a 2^n solution because you need to generate 2^n sets (and there is no way around this). And you can confirm this by noting:
1) Step 1: O(n) time, plus O(n)
2) Step 2): O(n) time, plus no extra space (as you can use your original array)
at this point you can also delete the hash table
3) Step 3: O(2^n) time, plus O(n) bits space
I want to make another point
1) In this case, if you thought of a solution in steps (where each step is something you know as a technique) then you will always win...
Because all the earlier steps before the 2^n step can be brute force and it will not change the optimality of the solution. So your interviewer shouldn't care if you used some n^k stuff before the 2^n step.
import java.lang.*;
- @@@@@@@ October 07, 2013import java.util.*;
import java.math.*;
public class powerset_without_repeating {
public static void main(String[] args)
{
int a[]={1,2,2};
int n=a.length;
int cf=(int)Math.pow(2,n);
List<String>l=new ArrayList<String>();
for(int c=0;c<cf;c++){
String s="";
for(int j=0;j<n;j++){
int x=c&(1<<j);
if(x!=0){
s+=a[j];
}
}
if(!l.contains(s)){
l.add(s);
}
}
for(String st:l){
System.out.println(st);
}
}
}