Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
/*
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 )
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 ) )
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 << "} ";
}
}
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 << "} ";
}
}
}
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
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);
}
}
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 :).
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)
- Chris December 14, 2016