找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: woaini
收起左侧

[Bloomberg] Bloomberg面经

[复制链接]

208

主题

158

精华

1812

积分

顶级会员

Rank: 6Rank: 6

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

1174

主题

171

精华

3558

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

The normal iterative approach:

def power_set(inp_set):
. B  E8 K1 c9 d2 l/ L& I	result = [[]]! o6 n* _! H( x3 g% Z' c5 }

  l/ ?9 u" }$ q! p	for ele in inp_set:
, C0 x; K0 q0 O( n/ P8 C		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
# a1 T4 a! @; u		result.extend(newSubSets)0 B, K. j1 q9 f; G, _

% J% t; g9 X5 W	return result

The most famous bit manipulation technique

def power_set3(inp_set):: @6 W( h) a- e  M
	pwr_set_size = 2 ** len(inp_set)
% J5 N! s3 h; q+ U	pwr_set = [[]]" B! {( @! D" {
/ k/ }4 I3 }$ {
	for i in range(pwr_set_size):, D: @" [6 h. Q, l; \/ d: W
		new_set = []
# |$ X' W: D# D; Q4 Q; A		for j in range(len(inp_set)):
& `; o: b# C( U- i1 q8 Y. R			if i & 1 << j : # this is to check if the jth bit is set or not8 [3 D; a" z7 L; I6 A4 i' E7 T
				new_set.extend([inp_set[j]])* {/ @: ~8 {: u% o9 [. Q% A

4 r% V4 l8 j5 }* y0 V; Q		pwr_set.append(new_set)+ s( Q( W( a: L6 Z/ Y4 j
	4 z! B7 v# n( o2 S9 u0 U( u0 [) K6 ?
	return pwr_set

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

def power_set2(inp_set, new_set):
3 i/ v5 t6 s7 L7 \" d/ D: X: a	if inp_set == []:
0 ]- Z6 P) L3 \/ t		return [new_set]
7 P) l1 g% k! j* o; Z( S. u	else:
3 G0 l1 B0 r; A		result = []) P" b% w/ s' n( n
		for ele in power_set2(inp_set[1:],new_set + [inp_set[0]]): # generate all subsets which has the first element$ u' O" }* a' H% N. E
			result.append(ele)
9 z6 X! o7 L8 {- S0 M  w( F9 h$ H+ E. j8 n- Y$ K5 K- Q6 X  a
		for ele in power_set2(inp_set[1:], new_set): #generate all the subsets which does not contain the first element2 U1 E! I" y" P1 d% `2 O
			result.append(ele)2 f- T; f7 e3 V4 P* E
7 L% f" [+ o/ E3 L- H+ l4 P
		return result

1178

主题

174

精华

3584

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3584
发表于 2-6-2017 03:38 PM 来自美国米群网手机版 | 显示全部楼层
给您点个赞~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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