找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Bloomberg] Bloomberg面经

[复制链接]

1142

主题

171

精华

3524

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-4-2017 05:19 PM 编辑
: |& {$ Q7 z+ r+ Q- M' _' R1 `2 F, r' d
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)

1175

主题

187

精华

3709

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/*
8 o8 `2 L; E& L+ D! O; d9 U. D6 @$ TSolution:
9 F0 W1 G' g9 w- the powerset is the set of all subsets& u' ?) q2 X' n+ S
- all or no element can be part of and all combination$ P. I% K. g2 j8 l. e
- per element two possibilities: be part of or not, 2 elements2 }9 s4 K# }! `- \5 U
  so 2^n possibilities' L2 V9 u+ q# k. @# @; n( {+ t
# v" j, H7 L% w
How to compute:
& w4 O6 Z1 L& Llets assume the set is given as a string:; [9 W5 S8 z' R6 s9 j
*/
5 Y; O7 f: g" _5 a+ V  j" B8 V( p; N1 j
#include <iostream>1 o, b9 o. ^2 K0 Q& n
#include <string>) F# n) D7 ?6 e: S5 R
7 l, e7 L6 f8 n
using namespace std;
- {+ ^, P7 J6 h+ ^2 b4 y
1 M2 a, w; y2 b" e* Yvoid printPowersetRec(const string& prefix, 
( b- M" K* H2 \3 T* b2 F					  const string& remaining)
, W) f9 n7 s8 E0 g{4 O" |( R2 Q! g% @
	
) y* A% d( @1 }. Y. c$ O	if(remaining.length() == 0) 
# F- M) a; W0 W. G	{ 
8 m) Q* W5 U; y2 `1 }3 A		cout << "{" << prefix << "} ";+ U; Z! i3 P2 e0 S& f
	}
2 s8 J2 S8 C5 ]  N	else 
6 H' ]$ i$ k1 n	{
! n: @* v9 O" R6 X# @		string newRemaining = remaining.substr(1);  [; S, h) Y& X3 U% n! c7 }
		string newPrefix = prefix;
2 Z: F; @2 K$ U1 o6 W1 z: n# O		newPrefix.append(1, remaining[0]);8 R* X$ A; U# i' w7 ?& z
		printPowersetRec(prefix, newRemaining); // included
4 z8 c) S( c$ ~) n		printPowersetRec(newPrefix, newRemaining); // excluded
) v9 n4 u3 z" C4 }	}	 
: N2 m9 i+ q" B  z% r1 s- i}
$ m$ x9 a. F' B' M% M" Z2 v' v
4 ^9 L/ S5 v  A: z8 Zvoid printPowerset(const string& input)
, c1 U* f: R+ b{) I  E* f0 I. V
	printPowersetRec("", input);
' O; I! Q  M; \! h' }8 [}( s& ?9 L  ^6 _" E* d4 z
, _. Y" m1 ^/ X
int main()
# K) `: @( V/ \{
7 f5 B' W- V- w0 g4 x4 t, X" e	printPowerset("ABCD");
! T+ m% |& P! u9 W+ T% M  `+ J}

回复 支持 反对

使用道具 举报

1162

主题

170

精华

3559

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* 3 g) C$ k# G5 l" y0 C& e; R
  ZoomBA powerset is simply done by 
) P, q3 r: K: T9 ~1 }9 ^) x1 u  the following 
. }5 a8 W9 T8 }" }: O& E*/
" s; O" Q1 W3 `9 T$ ?( H2 q3 Gmy_vals = [ 0, 1, 2, 3 ]8 F9 c7 \0 A; \3 Q" |% g
// sequences() function generates all possible sub sequences. M" T( M! f" R+ s% ]
// which is the power set :) ' P1 A9 d9 V* C) y2 {2 g' |% l
fold ( sequences(my_vals) ) -> { println($.o) }
* {! g* ~5 ^' T3 ?. o" r
, ~2 O& t% c* A. D7 i% x+ `// in a sensible way, this is how you can do the same
$ `" |, `9 a2 C) L  W// also explains why it is Theta( 2^n )
# ?$ ~/ A. N" G& B, k$ Z$ Wdef power_set( arr ){2 N! q6 M7 o* K
  len = size( arr ) 8 L7 _- s9 i8 \/ ]+ E/ D; o" P( k
  n = 2 ** len
3 w$ p! K  K/ M4 N1 L) J) d; `& e  for ( bn : [0:n] ){ // this is why it is 2^n 
" T! S5 ~( C9 W" \+ m% w1 T* Y    bs = str( bn, 2 ) // binary string format % i: o# Q- e' x! M' }8 m
    // to make it sized n binary digits 
/ {/ F% E! t. H+ Z0 H    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 3 l1 S, g5 \9 s! a
    // select the index i's item when bs contains 1 at index i / y. @! ?+ v: i8 B9 @; |! Z  F
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }% \( n) Z3 Z  b7 d
    println ( subseq )' P8 Z" n( v1 X( m! S
  } 7 T. }: x& s# f& k4 L
}
% i5 T; J3 w0 v  |. b' N5 l, p) Qpower_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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