找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Bloomberg] Bloomberg面经

[复制链接]

1132

主题

171

精华

3488

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-4-2017 05:19 PM 编辑
5 ~4 M; C) b% T* l2 T3 k7 u* m2 R7 B$ p8 x
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)

1170

主题

187

精华

3699

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/** B  Z6 C3 h& U' c% ?8 |) e0 r% o
Solution:) E' R* m0 y8 q
- the powerset is the set of all subsets
6 b% g' l& l& F" L% K. S- all or no element can be part of and all combination
4 p2 n# w+ l% C/ \( |6 x1 d; a- per element two possibilities: be part of or not, 2 elements3 C( i1 f  H& l0 D4 k
  so 2^n possibilities
; ^% K+ R' j: P; Z; o; r
5 T7 k, X. h( B. ^0 u5 L& IHow to compute:
; P& b# z# T6 V! i& ]/ c/ G3 l. ]! L, flets assume the set is given as a string:/ D* U8 d& [  u% n; t) ^
*/& f* y8 D9 Y! ]0 s( }% Y# U: ^2 m

/ t) R" |4 A/ T#include <iostream>- T* O6 f2 y4 i1 m
#include <string>
% J- o/ R2 b4 M$ Q+ L! x) f7 v3 Z& Q" S% s0 Y, c. I  X
using namespace std;* n5 Q; y9 \% ^* ?. a" ^/ c5 F

& v9 c$ e" F' c9 ?7 yvoid printPowersetRec(const string& prefix, 3 l, E3 H! a: a" I# f( z
					  const string& remaining)
7 j+ d/ H2 p% u7 w{" Z' A# w) b: o% c5 s" J
	' S9 c8 v6 p) d1 t" N2 @
	if(remaining.length() == 0) 
" V% r; L! f) t2 z9 V( b	{ 
' U& m  G+ M5 e. H! \		cout << "{" << prefix << "} ";0 v$ U* h: X* ?# F! P- E
	}
) z( f3 H0 j/ ^: }	else 
+ {5 K; |7 V5 B, }1 a; i6 C	{
8 ?: N3 T4 A6 h		string newRemaining = remaining.substr(1);/ j7 d3 Q! L" l$ x0 g, ^% s- {  D
		string newPrefix = prefix;
+ j1 L7 Q4 m# i- ^& C! A  w+ j; f		newPrefix.append(1, remaining[0]);
  n( d5 h* P3 @. Q		printPowersetRec(prefix, newRemaining); // included
6 m7 l4 d  {! s: j+ P		printPowersetRec(newPrefix, newRemaining); // excluded) Z0 q# L& Z5 a1 z$ T! z
	}	 
* U, j( e& B, V6 L9 g}0 G. |. b# O+ [8 T4 P  K& E
6 c: F. y* u0 k+ Y8 ]
void printPowerset(const string& input)
" K) t: W+ G; J7 \7 U% O{
6 \$ z  ]) x* S) X1 |# M! ^& b0 a3 g	printPowersetRec("", input);$ d4 R2 P' i* h: P/ }6 y
}0 s( J6 |; [1 U, I% u6 g
* B7 ]) s' h$ t3 a3 E. r5 ~
int main(). o4 v$ ^/ d7 s" X$ E
{- a# l1 K3 `6 c! q8 T+ i0 G. V
	printPowerset("ABCD");
  M+ _! I2 \" M- O4 u# ?}

回复 支持 反对

使用道具 举报

1159

主题

170

精华

3549

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* 7 l7 X, b6 i/ `
  ZoomBA powerset is simply done by 
+ I) S, @9 L+ |+ t  f9 p/ H. j  the following 
/ ?" l8 d, O9 q*/
5 F- v+ i/ ?! l3 {8 ]my_vals = [ 0, 1, 2, 3 ]' I3 N2 ~1 C+ G- P
// sequences() function generates all possible sub sequences
, R% Z4 b' z+ v( ?# B// which is the power set :) 
1 P& U$ j4 P/ }; ffold ( sequences(my_vals) ) -> { println($.o) }
  j' u: o+ J  X7 h: r: M: y( Y5 b; n/ a; L) H* y3 C9 A
// in a sensible way, this is how you can do the same
' [+ m" c8 V* b+ B. R# s/ V// also explains why it is Theta( 2^n )
6 x3 _5 ~% q. I# O5 xdef power_set( arr ){
3 l* }7 X# u, [! T0 K8 ~) ^" |  `  len = size( arr ) 
' F! F7 |( H4 u1 u+ N+ C. x3 l% P  n = 2 ** len  R2 |5 B) B* v: p' p; Z5 p2 a
  for ( bn : [0:n] ){ // this is why it is 2^n . y4 R2 B- y6 c! _: I1 B
    bs = str( bn, 2 ) // binary string format 8 X- E/ m0 o! l# P+ v  ?/ I
    // to make it sized n binary digits 
6 W! I- j4 C1 S/ l6 G- o5 q    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left ! y2 d$ J0 w1 C  U1 b
    // select the index i's item when bs contains 1 at index i 5 ^; b6 Y6 S3 ?8 @  k9 |9 ^
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }, P/ B2 Y$ t6 W  e6 L. n
    println ( subseq )
1 R6 v) _- d& o. a" h  } # t4 F' J: |* i0 Q9 ^" ~9 C# n
}
. J9 ^! q% M/ ?. {" F) _' dpower_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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