找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4690|回复: 10
收起左侧

[Bloomberg] Bloomberg面经

[复制链接]

1154

主题

173

精华

3578

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3578
发表于 2-4-2017 05:12 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-4-2017 05:19 PM 编辑 5 E8 _- {% n9 N1 N
3 ]% i. [' a! Q) H
Given a set find its power set. (This question is from CTCI) Interviewer then discussed the complexity of my solution. He asked me to explain him how the complexity is 2^n? As per my solution, I was iterating over an arraylist which contained the set elements so the size of list was getting doubled in every iteration. Hence the complexity (2^0 + 2^1 + 2^2 +.....+2^n-1 = 2^n)

1183

主题

187

精华

3729

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/*  ]- e8 q" `6 Z: G; O" t
Solution:
& R4 |# m4 A7 {4 a- the powerset is the set of all subsets
, W9 M1 R0 D: c0 J- all or no element can be part of and all combination" f: \: \& @# F( E6 E( P7 i7 K
- per element two possibilities: be part of or not, 2 elements
' Z3 w+ `# q, m1 Y4 O  so 2^n possibilities$ o$ k% c1 y+ A) N) F0 A% G
( c% H! D( }2 x# R/ U
How to compute:, r4 g' Z4 ^/ ]1 n
lets assume the set is given as a string:/ C. \/ j# f) C: o7 u
*/
1 q6 f0 s1 _5 w
9 X2 p" S- J6 _' A4 s! b#include <iostream>
( X& l3 k9 ~% Y#include <string>9 x$ J1 w5 e4 e: F/ X

) G/ W: D+ U  l: f0 U( ]" t& Kusing namespace std;
' w- V; W" K  F% u/ Z& f& ]5 C
; J$ w' p& X. o9 Uvoid printPowersetRec(const string& prefix, 5 {: P4 H8 ]! Z+ z+ V
					  const string& remaining)
' l% c  a) N$ `1 R- \0 S1 {{3 n, ]) \5 I- G. Y5 M# c! M
	6 h' g7 h3 F! o5 f
	if(remaining.length() == 0) 2 j2 G; z- ?$ l4 p+ O. F
	{ 
2 C1 V4 Q; {8 ^( t0 o" W2 H, d" L		cout << "{" << prefix << "} ";
4 ?& J/ V6 a  p2 U3 D* X	}
% r& G2 U8 o8 p7 p5 a3 U	else 
* y1 v/ W8 Y2 P' T	{1 x: G: {+ f; ]7 j
		string newRemaining = remaining.substr(1);( D9 Z3 L. U% w/ Y* Y- e
		string newPrefix = prefix;, P" o- g& t+ i, v* `
		newPrefix.append(1, remaining[0]);
/ @' q# J$ J) S( }1 {( f		printPowersetRec(prefix, newRemaining); // included
. o( l$ L) V/ H+ |+ C		printPowersetRec(newPrefix, newRemaining); // excluded4 ~% n7 @. K3 U) I- W# s' S0 `& I
	}	 
: s; {8 H  {2 L! k& L}( R9 N3 C6 \  P+ d/ k

# O% n! m; s* w, x4 _' G% ]6 o( Nvoid printPowerset(const string& input)
8 r: i1 j4 e; F% \{
5 E- q& t. n) t	printPowersetRec("", input);
0 @7 \6 c$ O3 F. X. B  d3 t}
3 S( X. `8 P2 N0 N  _% Q* i* m! s/ R( T+ i
int main()
) c* {( b+ F8 p$ `" Y' ^# A{
# v4 z+ A4 g& ]	printPowerset("ABCD");
1 j8 j  t3 T6 S: D# R0 M3 D}

回复 支持 反对

使用道具 举报

1172

主题

170

精华

3583

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/*   a2 N% X5 J$ c# ^/ M+ v0 p
  ZoomBA powerset is simply done by ( `2 j/ N! X9 {. X) q
  the following 
7 N- X( @" Q1 o*/
3 `' X- _8 \& |. G3 ~my_vals = [ 0, 1, 2, 3 ]
0 y& F1 F4 X7 I2 f2 U3 @( X0 \0 H! @// sequences() function generates all possible sub sequences( t, t1 c' c: ]1 a
// which is the power set :) 
. K2 F9 u3 e# W7 Z3 Z: Afold ( sequences(my_vals) ) -> { println($.o) }( T( e& Y8 K1 D9 ]" b
% k1 O1 P6 q1 l3 p+ e1 J
// in a sensible way, this is how you can do the same
, e8 K, i0 g3 f, P0 |/ q" h* n/ F: @// also explains why it is Theta( 2^n )4 Y) O. |2 G) z  k+ S4 L  v& i" |
def power_set( arr ){3 ~) x9 E% d8 b- J" Y* b- ?
  len = size( arr ) 0 m# ?* A& `) B5 e" ?
  n = 2 ** len3 n6 x* V8 a; }( f* |
  for ( bn : [0:n] ){ // this is why it is 2^n 6 ~& \% I- ^' s9 }
    bs = str( bn, 2 ) // binary string format " N& k0 s' x8 L" m, i' ^
    // to make it sized n binary digits 
8 {- g* F/ T$ U! z* B2 s    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
- [1 |* x. q2 }( p8 \- s  L    // select the index i's item when bs contains 1 at index i ' q) V( ~8 |# z
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }* [, D/ w- P5 O6 G( Z' ]
    println ( subseq )8 E: u8 ]) J' g* Y' R+ i9 L
  } 
$ I2 c( e) F. G4 I3 J; d( c}
& u! p! u0 T; W4 a! Epower_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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