Facebook Interview Question for Interns


Country: India
Interview Type: Phone Interview




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

import java.lang.*;
import 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);
}

}

}

- @@@@@@@ October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- MrPeteHeller November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nifty technique, but this won't work for an element count > than 32 (64 for 64bit integer architectures) right?

- Anonymous December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

"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);
}

- Miguel Oliveira September 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

can you write psuedocode instead, so that we can understand what the approach is.

- J September 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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());
		}
	}

- ehsan September 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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}}

- linuxchain July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
		}
	}

}

- Anonymous September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mj September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Abhisheak Iyer September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ssds

- Anonymous September 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sola September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}
}

- Anonymous October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}
}

- Anonymous October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}
}

- java soln October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- ZuZu October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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, "");
	}

}

- javaD November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- yuxiaohui78 November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what the logic> ? how does it prevent {2} coming twice in :

{1,2,3,2}

- yozaam September 20, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;  
	}
}

- Create a comparator class to sort the generated sets. December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Look similar to oj.leetcode.com/problems/subsets/

- kilaka December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- BIN December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- guoliqiang2006 December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

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

Sets make this easy in python

def powerset(s):
    if len(s)==0:
        return [[]]
    nxt=powerset(s[1:])
    return map(lambda l:[s[0]]+l ,nxt)+nxt

def uniqPset(s):
	return set(map(tuple,powerset([1,2,2])))

- bechira October 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sets make this easy in python

def powerset(s):
    if len(s)==0:
        return [[]]
    nxt=powerset(s[1:])
    return map(lambda l:[s[0]]+l ,nxt)+nxt

def uniqPset(s):
	return set(map(tuple,powerset([1,2,2])))

- bechira October 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- Outermeasure November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time Complexity O(n * 2 ^ n), space complexity: Additional O(n) space for remembering the current solution and the previous one.

- Outermeasure November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't get people on careercup. We don't want to read big pile of code - we can code too. We are just interested in the main idea of the solution in a couple of sentences.

- Safi November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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("}");
		}
	}
}

- shanmuk December 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- smillence1992 February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
     }
}

- sunny April 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- bigphatkdawg September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bigphatkdawg September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if you remove duplicate elements than
{1,2,2}
can never be the output.

- jv September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, I misunderstood the OP.
It is easy to modify for that situation too.

- bigphatkdawg September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

set < vector < int > > PowerSet(vector < int > a)
{
	 int n = a.size();
    set < vector < int > > ret;
    int num = (1 << n);
    for(int i = 0; i < num; ++i)
    {
        vector < int > v;
        for(int j = 0; j < n; ++j)
        {
            if(i & (1 << j)) v.push_back(a[j]);
        }
        ret.insert(v);
    }
    return ret;
}

- ameydhar January 11, 2014 | 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