找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Bloomberg] Bloomberg面经

[复制链接]

1148

主题

173

精华

3566

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-4-2017 05:19 PM 编辑 $ b$ t5 O( S7 B8 G. Z/ I
+ K( p! E: P5 M
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)

1182

主题

187

精华

3727

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/*
5 \& G3 F5 a  j8 U. v( k( G( CSolution:% E% \  F5 ]! u. o# j
- the powerset is the set of all subsets
) t+ Y! C7 F& j# C- all or no element can be part of and all combination  \) O  v8 m9 F& B  ^3 q* L4 D
- per element two possibilities: be part of or not, 2 elements* u' ]3 j" \, H
  so 2^n possibilities8 ?' u. ~6 ^- w3 ~

9 K: D  ]4 t! h6 rHow to compute:
2 |( m6 A$ @8 N! @lets assume the set is given as a string:
# K1 P% E$ t: D6 L*/
: Y3 d' W5 s$ ?  a3 D: E% |7 d8 w) G0 ^/ w( ]
#include <iostream>
) W! E8 a: V% N# k#include <string>4 h( j/ d4 F0 `) c1 C. e& s9 Y* F
) O' ?0 N: I$ z- h7 @$ k- a
using namespace std;! E4 P7 v7 ~* c- |9 f" b6 R
* S3 y4 z% v2 Z1 e- @) i# |7 |
void printPowersetRec(const string& prefix, 
. B7 s) {- B( K4 N$ L					  const string& remaining)
  k& T& T7 ?/ z! A4 M{
: Q( h8 v7 s' n' J) N* O	# k/ ]  ]3 E4 p. O+ u$ r
	if(remaining.length() == 0) 
7 c- I$ i8 G; Z4 r7 l% O2 X6 X	{ " K$ r8 I$ a. F7 R5 M
		cout << "{" << prefix << "} ";5 }! C4 k, z! m( p/ E
	}3 G' b. J2 ~3 R4 n- F  K& A) l$ _6 N
	else $ U+ ~# T1 E/ p' C& N& a8 n
	{
. ~) Y1 Q* y  ^0 l! f& Z$ w		string newRemaining = remaining.substr(1);
/ [0 u4 i. Y; z$ e) X" L# X$ f		string newPrefix = prefix;
0 F* s4 D2 v6 M+ X		newPrefix.append(1, remaining[0]);* _9 O( d! u/ W
		printPowersetRec(prefix, newRemaining); // included; D* r# Y/ C9 }: o
		printPowersetRec(newPrefix, newRemaining); // excluded( P# \% m1 x8 ]% ^, V! |
	}	 ; a% n& G$ Q- {
}2 O7 k5 u: r# n' F
$ l% K; {3 S4 T2 v/ E5 o4 `
void printPowerset(const string& input)1 I7 \2 z$ J0 a; [: s* @* h9 z
{: w# }( p) ~. H8 P1 J5 ^
	printPowersetRec("", input);/ B5 C, C3 Y% X
}
8 [; w% m* R+ ?  }, o0 E& p
* r1 i( w$ v* Pint main()4 a! T* @6 i& C8 j% f: E
{! J1 D8 m0 b1 @# C% r1 T6 u) I/ u
	printPowerset("ABCD");5 K6 p, q0 O6 w% r% r& f3 |% N
}

回复 支持 反对

使用道具 举报

1167

主题

170

精华

3573

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* ) b: l. |6 ]7 I0 X2 ^
  ZoomBA powerset is simply done by 2 M1 L3 A# O, ^$ \' `! a3 G
  the following . C9 t- j$ y0 A* B, e
*/
3 `) J: N) C9 O! n# j* m( Bmy_vals = [ 0, 1, 2, 3 ]
: F' w4 \) I1 D/ e4 T// sequences() function generates all possible sub sequences2 F/ Z# B% \  ~: i, L) W' @
// which is the power set :) 3 }- C' W2 ]- X5 b! i$ c+ `
fold ( sequences(my_vals) ) -> { println($.o) }
8 M) S9 u8 M2 G* \
/ {2 _$ s, {% V# w0 T// in a sensible way, this is how you can do the same* e9 Z4 J. i* H! o
// also explains why it is Theta( 2^n )- C. f8 @# S9 C* d" _  r
def power_set( arr ){
) u' M7 ~9 y3 X* o0 J: P5 c  len = size( arr ) 
3 E# G; K* G1 I  n = 2 ** len$ a& x. @3 b! R( ^* u! A3 [/ q  w+ N) {
  for ( bn : [0:n] ){ // this is why it is 2^n 8 B, }* u. x5 e. f1 m  R! F0 O
    bs = str( bn, 2 ) // binary string format 
& @$ x( r9 G, s    // to make it sized n binary digits 
" w$ v- D- ^. q2 y8 \    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left - A3 M7 v( Y/ Y6 @* A7 S; x
    // select the index i's item when bs contains 1 at index i 
  ^- }- u6 |: @    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }( ?. ]3 z  A2 K6 `) C+ C
    println ( subseq )7 o6 x. j- Y' [' Y( O5 P2 e: u) ^: e
  } 
0 R: m! u; r  y$ M2 q: J6 P}
1 y/ A. Y2 Z' R& G( spower_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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