找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: woaini
收起左侧

[Bloomberg] Bloomberg面经

[复制链接]

1161

主题

184

精华

3664

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3664
发表于 2-4-2017 05:12 PM | 显示全部楼层

A much cleaner way in ZoomBA :

my_vals = [ 0, 1, 2, 3 ]$ K; b4 b; F# ?) D: c7 Z( A0 K* P  y
// minimizing use of English and more math 
7 d% J" G+ Y7 Mdef power_set( arr ){# ?, R" ^; d# N9 I( Y, R9 ]6 d
  len = size( arr ) 5 v; K8 b3 {7 K6 ?" o  y3 c
  // this is why it is 2^n 
1 L5 a& w' }9 T" O$ ]! e' ^, n0 |  list ( [0 : 2 ** len ] ) -> { % v6 L. A0 z/ \3 w
    bs = str( $.o , 2 ) // binary string format 
- @6 `' e" s: J5 v    // to make it sized n binary digits 8 q/ v, F% o4 M  |" p* n
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
) R1 H3 }+ h) M+ x) `    // select the index i's item when bs contains 1 at index i 
9 E3 O) o; i5 I. m    select( bs.value ) :: { $.o == _'0' } -> { arr[$.i] }$ a1 [9 X4 R7 P8 t+ v
  } 
" M: D5 \4 I" L$ u- G! e}
8 `, }" l- ]0 B* ?; K( z; j  v: cprintln ( power_set( my_vals ) )

1195

主题

170

精华

3596

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3596
发表于 2-4-2017 05:12 PM | 显示全部楼层

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 = {""};
5 L1 x6 I0 g1 O; P* y- s9 o	cout << "{ } ";
$ g2 ~8 G/ L( j2 h5 n) E- t* b# P	for (auto ch : input) {
. r1 J9 J; {: h9 S) N" F) {		auto len = subsets.size();. w; ~0 R- i! Z
		for (auto i = 0u; i < len; i++) {
9 y9 Y9 E1 x* A( r8 \" e' C			auto s = subsets[i] + ch;
# ?: W' F' W' y			subsets.push_back(s);' @6 N* W" k0 `9 V) |
			cout << "{" << s << "} ";0 d7 h) \8 M. A4 K3 Q' X: F* T0 \
		}5 S& [) m7 f$ V' L
	}

1117

主题

178

精华

3488

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3488
发表于 2-4-2017 05:12 PM | 显示全部楼层

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) {	
+ T- W4 W! H! q5 r6 ^	vector<string> subsets = {""};
+ n6 Y; l: F) s' Z0 ~- \# N	cout << "{ } ";: G  p3 M, [- o* ?- |3 f1 J
	for (auto ch : input) {
9 H# k) ~1 ~' k  o		auto len = subsets.size();2 a0 U: G* ~$ f
		for (auto i = 0u; i < len; i++) {
2 z0 y# T: _( P3 i6 t			auto s = subsets[i] + ch;
- P& d3 f( t; h, ?) m) U			subsets.push_back(s);! M4 V/ x2 I' b% V+ P# E
			cout << "{" << s << "} ";4 M# [* Q" f, a
		}9 p4 X" |- r- O# P! `( |5 i/ D
	}
, c( ~4 p9 S1 q! n4 Y}

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表