找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4749|回复: 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 编辑 ' W0 |* `1 D" W
+ D. Y" w, T; I
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 | 显示全部楼层

/*
$ }4 w& ]" H- J8 b+ l; u% ISolution:
) g3 E4 f# V2 v9 ^$ N1 W( H* J3 G- the powerset is the set of all subsets7 J" I3 b( c5 q9 }$ l7 Y( C
- all or no element can be part of and all combination( G% v- [; U  v/ J* P+ p* [9 a
- per element two possibilities: be part of or not, 2 elements* X0 {4 g% O! I& A: P8 S
  so 2^n possibilities
3 r. r$ T+ J: U0 g% E! u8 V0 F! |7 H: ^, q
How to compute:& s  c6 Y9 H9 D2 O
lets assume the set is given as a string:: I% Z9 r, `1 G
*/0 R  h- p$ N5 W, }3 i* ^- B
! \4 j% {3 q/ |2 W' V3 V' A2 Z
#include <iostream>
# f- {# q. n! U3 l: e9 p#include <string>
% ~4 s& \9 R$ @7 N3 o% [5 z' H: [5 p# R5 K& T1 P4 I8 ?6 T
using namespace std;
4 K0 [9 Z2 w$ _- H+ X9 b) x- O# k+ ~  P" J4 e- o3 `1 x
void printPowersetRec(const string& prefix, ( H9 f! w5 P( J) A
					  const string& remaining)& w3 M; F# i+ z/ }- _' g0 H. u# f
{
3 N  A/ |9 I; u' i: @. T: Q2 F	# \$ E3 D2 \5 X- A
	if(remaining.length() == 0) - r% d: [8 x7 j- C
	{ 4 ?( _: x, s3 c# `- t, i. ]
		cout << "{" << prefix << "} ";
" m7 r+ b/ r7 E0 L% D. v	}+ B  r4 l& z: O# Y* \4 O+ h
	else 
: p4 |( Q- h; T# q! u  @	{
0 w* u0 V% n7 [0 c		string newRemaining = remaining.substr(1);7 H- B) j- }$ z& f
		string newPrefix = prefix;
8 q* u; P+ s2 E  f/ d		newPrefix.append(1, remaining[0]);4 v& S9 s7 ~7 ]7 G6 D2 ]8 p
		printPowersetRec(prefix, newRemaining); // included
1 ]8 A+ P  K1 C! a) T6 _$ c		printPowersetRec(newPrefix, newRemaining); // excluded/ L+ Z" ?4 ^3 _: i
	}	 
3 u3 n: |. B  Z' d, o- j  u! |! l}
' c% Z, O/ K. N6 m) s: @% `5 m  I' M6 l* s5 _- i& [3 E7 V6 r. ~
void printPowerset(const string& input)+ f. {$ G5 {8 e) _( n9 m; M+ R
{
7 H  E6 a6 V5 r% u	printPowersetRec("", input);. p& F# H. T, x6 m  @% r8 e6 d
}
0 O5 g& z) X6 o$ i; M) l: P( R! `& o* L! F6 @3 e) e
int main()* _2 A5 [( {5 I( S% e
{" C& V' T, d( D  U& f! m! y% f& ]
	printPowerset("ABCD");2 K6 E2 ]7 _' n
}

回复 支持 反对

使用道具 举报

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* ' Y$ O: m* `2 k. D4 L! J4 j1 ]
  ZoomBA powerset is simply done by 
# q# {! {* Y4 W8 I: E! I1 T  the following 
3 W/ ?. [# x  f" p. v) _*/
5 v# D6 d3 R) c9 O, b  p$ omy_vals = [ 0, 1, 2, 3 ]! D1 U* @% E6 @/ S# i, r
// sequences() function generates all possible sub sequences0 D3 y$ G) U: r
// which is the power set :) 
2 }5 r; n4 q9 n" ^- @$ U% ffold ( sequences(my_vals) ) -> { println($.o) }
! a* f2 Y' C5 n0 x4 r* U* J6 g# X# R# ]# b  e  s
// in a sensible way, this is how you can do the same
! c$ g" _0 S. F$ \" w. l- n. t) ]8 x// also explains why it is Theta( 2^n )
; f0 E0 G0 }5 b7 |6 ldef power_set( arr ){2 I, a  b! y1 I6 v) M# L
  len = size( arr ) 0 g% s. _( ~! R
  n = 2 ** len9 m+ @- l; K0 g
  for ( bn : [0:n] ){ // this is why it is 2^n 
2 A0 }4 a2 x( Y9 [; |" B( y; `    bs = str( bn, 2 ) // binary string format 4 U8 k! O: S- @& M& C8 F
    // to make it sized n binary digits : a. G  P* F, j' h
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
; F3 [5 T& L' G1 ^/ u/ i2 T    // select the index i's item when bs contains 1 at index i : Q6 Q) H8 y+ I/ Q3 O
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }2 V9 P- y2 ~# C
    println ( subseq )
& r+ S" _1 I  A4 n2 E  } , g4 |3 p, d) s$ f; m2 T3 k
}
, |5 O5 L- }* O, Opower_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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