找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Bloomberg] Bloomberg面经

[复制链接]

1156

主题

173

精华

3582

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-4-2017 05:19 PM 编辑 ) {& K+ N3 |+ S: E8 u0 X
( c) v) C' z: F! N3 p& {
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 | 显示全部楼层

/*
+ P! V4 Y$ g5 ]( g. o' RSolution:# @& Q( i! ^% R% J5 {$ c; h
- the powerset is the set of all subsets
$ |: x3 S) R9 Q0 e- g6 `$ Q- all or no element can be part of and all combination$ Y% @& V; s0 U% |; r
- per element two possibilities: be part of or not, 2 elements
( _1 K2 B; |- Y' \* V  so 2^n possibilities; W$ A  [5 o$ }, S6 y* q

: `/ y% R8 ~% E. S  jHow to compute:, R1 D8 m, _# p. P/ X
lets assume the set is given as a string:
/ u! ]: V& L. F5 T) M*/
" ?% _6 N1 m# y
+ }1 p7 l: ]5 V  I4 d: D& h, j#include <iostream>( ]' ?% W! N* H, T& q! F
#include <string>$ {) v, N* T+ _

8 w' A- k0 ?$ B  P* Husing namespace std;7 U) N$ s' i8 h& ]1 `  _/ \
: `: C8 g8 n; f3 s( g
void printPowersetRec(const string& prefix, * C0 S" s8 U1 g, ?. A, q; q- u
					  const string& remaining)
" w0 _9 ?0 V" o8 h$ U{# _* W4 j7 _/ A: S6 h0 O, X$ {
	6 z+ i5 v" B% C+ }5 q' ^8 ]" K+ \* V
	if(remaining.length() == 0) 
- u  A! }6 K& T: e  Z5 i	{ 
1 Y1 V& W% r1 q" ~		cout << "{" << prefix << "} ";
0 K/ C4 V9 A' y  R# s	}3 Q$ y0 k* I; U. b: N1 e$ q+ ^
	else 1 D+ r" Z# m+ O% b* {+ a* w+ L5 L" w
	{3 T2 N! {- \1 f# r
		string newRemaining = remaining.substr(1);
7 b- v9 k+ g3 H% {$ h' s" R		string newPrefix = prefix;: O8 g" U5 ]0 o- [
		newPrefix.append(1, remaining[0]);5 ]5 ?$ d$ S9 `& C
		printPowersetRec(prefix, newRemaining); // included  m& u( [4 h8 Y1 N  ~$ E% S  M
		printPowersetRec(newPrefix, newRemaining); // excluded* f/ A% b: L7 h1 t7 `
	}	 , ?7 e" t! P7 {; I
}
3 B5 M5 Y9 u; v2 @
- k6 |: G9 t( k6 T7 B3 K! qvoid printPowerset(const string& input)
! V/ Y# B/ g" C{
: a' X' l, R6 z	printPowersetRec("", input);
! h& v/ ?1 _, `) u3 \  E/ T}' _! N( a2 d: S6 U1 w: z( z
8 r/ d$ v" W, k$ t
int main()
6 U; J; ?; L" i4 E5 `$ e% ^{
( Q% l2 c% d4 V) s* @# o	printPowerset("ABCD");" N7 f0 {) Z' ^6 V
}

回复 支持 反对

使用道具 举报

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* 
# Y1 ~5 Q$ P2 L8 _7 h0 x6 g" c6 C  ZoomBA powerset is simply done by % ~4 g0 W5 x/ Y" L
  the following 3 [* R2 i) j% R1 S
*/+ C1 s" Q, C4 }
my_vals = [ 0, 1, 2, 3 ]
7 j2 M2 L$ s2 e" b3 \; N# `9 H% Z& s// sequences() function generates all possible sub sequences% W, h4 P! M! k& \
// which is the power set :) # I0 ]6 Z. J0 ?+ L) ]
fold ( sequences(my_vals) ) -> { println($.o) }
' K( V, O& ]% I: w0 x& S5 ?) e0 d5 t7 G
// in a sensible way, this is how you can do the same6 K0 D, P) o, |# s4 c2 y# F8 E% ?
// also explains why it is Theta( 2^n )
: A* ~; k, j% g/ B/ M5 R) Odef power_set( arr ){8 z" p/ H; i1 ~8 \  A1 V7 B
  len = size( arr ) 0 ]& o( I- b: x/ w: y$ S3 g# d
  n = 2 ** len- q" v2 `0 Y) j# {9 A' z
  for ( bn : [0:n] ){ // this is why it is 2^n , {+ n% |9 Z) V& V! H
    bs = str( bn, 2 ) // binary string format 
+ ~; d& N5 m0 r0 C; t    // to make it sized n binary digits / u" z1 Z3 w" d+ `; w
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left / A7 u# e$ F/ z4 x4 V
    // select the index i's item when bs contains 1 at index i 
  Q- T  l) G8 O+ y* j, l' g    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }
6 a8 M+ w, g9 n    println ( subseq )" l: W, ]& M. N* y
  } 0 _/ p, i% Z9 W6 `/ _# n, N
}
- `; c2 d1 ]3 y( R) @6 }power_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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