Bloomberg LP Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

/*
Solution:
- the powerset is the set of all subsets
- all or no element can be part of and all combination
- per element two possibilities: be part of or not, 2 elements
  so 2^n possibilities

How to compute:
lets assume the set is given as a string:
*/

#include <iostream>
#include <string>

using namespace std;

void printPowersetRec(const string& prefix, 
					  const string& remaining)
{
	
	if(remaining.length() == 0) 
	{ 
		cout << "{" << prefix << "} ";
	}
	else 
	{
		string newRemaining = remaining.substr(1);
		string newPrefix = prefix;
		newPrefix.append(1, remaining[0]);
		printPowersetRec(prefix, newRemaining); // included
		printPowersetRec(newPrefix, newRemaining); // excluded
	}	 
}

void printPowerset(const string& input)
{
	printPowersetRec("", input);
}

int main()
{
	printPowerset("ABCD");
}

- ChrisK December 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 
  ZoomBA powerset is simply done by 
  the following 
*/
my_vals = [ 0, 1, 2, 3 ]
// sequences() function generates all possible sub sequences
// which is the power set :) 
fold ( sequences(my_vals) ) -> { println($.o) }

// in a sensible way, this is how you can do the same
// also explains why it is Theta( 2^n )
def power_set( arr ){
  len = size( arr ) 
  n = 2 ** len
  for ( bn : [0:n] ){ // this is why it is 2^n 
    bs = str( bn, 2 ) // binary string format 
    // to make it sized n binary digits 
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
    // select the index i's item when bs contains 1 at index i 
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }
    println ( subseq )
  } 
}
power_set( my_vals )

- NoOne December 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A much cleaner way in ZoomBA :

my_vals = [ 0, 1, 2, 3 ]
// minimizing use of English and more math 
def power_set( arr ){
  len = size( arr ) 
  // this is why it is 2^n 
  list ( [0 : 2 ** len ] ) -> { 
    bs = str( $.o , 2 ) // binary string format 
    // to make it sized n binary digits 
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
    // select the index i's item when bs contains 1 at index i 
    select( bs.value ) :: { $.o == _'0' } -> { arr[$.i] }
  } 
}
println ( power_set( my_vals ) )

- NoOne December 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In your solution it is actually O(2^n+1), the one below is O(2^n) with better space complexity as well

vector<string> subsets = {""};
	cout << "{ } ";
	for (auto ch : input) {
		auto len = subsets.size();
		for (auto i = 0u; i < len; i++) {
			auto s = subsets[i] + ch;
			subsets.push_back(s);
			cout << "{" << s << "} ";
		}
	}

- Mikhail December 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this will now post twice or if my first post did not make it. The recursive C++ solution, shown here, actually has complexity of O(2^n+1). The iterative solution below is O(2^n) with lesser space complexity.

void printPowerset2(string input) {	
	vector<string> subsets = {""};
	cout << "{ } ";
	for (auto ch : input) {
		auto len = subsets.size();
		for (auto i = 0u; i < len; i++) {
			auto s = subsets[i] + ch;
			subsets.push_back(s);
			cout << "{" << s << "} ";
		}
	}
}

- Mikhail December 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Anonymous December 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The normal iterative approach:

def power_set(inp_set):
	result = [[]]

	for ele in inp_set:
		newSubSets = [subset + [ele] for subset in result] # this step is responsible for combining each element to every other element in the already existing power set
		result.extend(newSubSets)

	return result

The most famous bit manipulation technique

def power_set3(inp_set):
	pwr_set_size = 2 ** len(inp_set)
	pwr_set = [[]]

	for i in range(pwr_set_size):
		new_set = []
		for j in range(len(inp_set)):
			if i & 1 << j : # this is to check if the jth bit is set or not
				new_set.extend([inp_set[j]])

		pwr_set.append(new_set)
	
	return pwr_set

There could be a recursive definition which is a little tricky:

def power_set2(inp_set, new_set):
	if inp_set == []:
		return [new_set]
	else:
		result = []
		for ele in power_set2(inp_set[1:],new_set + [inp_set[0]]): # generate all subsets which has the first element
			result.append(ele)

		for ele in power_set2(inp_set[1:], new_set): #generate all the subsets which does not contain the first element
			result.append(ele)

		return result

- Sreejith January 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static List<List<Integer>> subset(int n) {
        
        List<List<Integer>> A = new ArrayList<>();
        
        if( n == 0 ) return A;
        
        List<Integer> S = new ArrayList<>();
        
        for(int i = 1;i <= n; i++) {
            S.add(i);
            dfsSubset(i, S, A, n);
            Integer tmp = S.remove(S.size()-1);
        }
        
        
        return A;
    }
    
    static void dfsSubset(int x, List<Integer> S, List<List<Integer>> A, int n){
        
        //process what we have
        List<Integer> tmpA = new ArrayList<>();
        for(Integer v : S){
            tmpA.add(v);
            System.out.print(v+" ");
            
        }
        System.out.println();
        
        A.add(tmpA);
        
        
        for(int i = x+1;i<=n;i++) {
            S.add(i);
            dfsSubset(i, S, A, n);
            Integer tmp = S.remove(S.size()-1);
        }
    }

- Anextro March 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To prove the complexity, use geometric series sum
Here is the logic

public class Set
{
	public List<string>() setStrings;
	// Constructors and all will come here.
	
	public void PrintPowerSet()
	{
		// Error conditions such as setStrings is null or does not any data will come here
		LinkedList<Set> powerSet = new LinkedList<Set>();
		powerSet.AddFirst(new Set(this.setStrings); // adding the first element
		foreach(var element in this.setStrings)
		{
			var enumerator = powerSet.GetEnumerator();
			while(enumerator.MoveNext())
			{
				powerSet.AddFirst(new Set(enumerator.Current.setStrings.Remove(element)); // adding the first element
			}
		}
		var enumerator = powerSet.GetEnumerator();
		while(enumerator.MoveNext())
		{
			Print(enumerator.Current);
		}
	}
}

public void Print(Set set)
{
	Console.WriteLine("{" + set.setStrings + "}");
}

Now complexity of this is 2^0 + 2^1 + 2^2.....2^n-1 = 2^n as per Geometric Series. so the time complexity is O(2^n), space complexity is O(2^n) because, we are storing all the data here PROVIDED that removing an entry from the list take only constant time, which i doubt :).

- sonesh April 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Many people posted their answers. But, I'm surprised that no one asked the question, do we have duplicates in the original array.

- guang April 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_subsets(input, i):
    # Use i as a binary mask to select which elements to include in the set.
    bitfield = list(bin(i))[2:]

    idx = len(input) -1

    res = []

    while(i > 0):
        if i%2 == 1:
            res.append(input[idx])
        i = i //2
        idx -= 1

    return res


input = [1, 2, 3, 4, 5, 6]

n = len(input)
subsets = []
for i in range(2**n):
    subsets.append(find_subsets(input, i))

print(subsets)

- NoName October 23, 2017 | 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