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

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

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

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

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

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

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

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++) {
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){
System.out.print(v+" ");

}
System.out.println();

for(int i = x+1;i<=n;i++) {
dfsSubset(i, S, A, n);
Integer tmp = S.remove(S.size()-1);
}
}``````

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
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 :).

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.

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

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.

### 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.