找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6070|回复: 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 编辑 6 A& m7 d! y) U& G( X+ f# u9 d# l
1 v- ~$ Z6 \9 X) o- e  H2 F" 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)

1183

主题

187

精华

3729

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/*( L2 v! i- v/ l2 f% t8 `
Solution:2 a2 y7 }$ |: Z. q+ F( t
- the powerset is the set of all subsets- ^- O2 l/ U/ I2 W/ m/ i/ @
- all or no element can be part of and all combination
1 X% [; H$ V9 A& b/ d+ H- per element two possibilities: be part of or not, 2 elements
0 p( W1 |' J+ x7 |: z$ f0 i3 ^  so 2^n possibilities
- S  x( F" _' ?: l$ T7 _" }' r
! Q9 E( u& x, iHow to compute:* }1 U# i; P+ |4 ^+ {* {7 O4 f
lets assume the set is given as a string:
, s0 @# K8 R3 j2 @$ ?! h*/1 t5 q. }1 z4 I% u6 o

6 ^1 i( e* o# k: e8 ]; i#include <iostream>
  Y" X- h  d( q- e& R5 B#include <string>; K" ?1 o" l, e7 T
& p/ E* ^* r4 X2 S' M# ~
using namespace std;
3 Y/ [* d9 Q1 D& _/ x2 D9 I( l
void printPowersetRec(const string& prefix, 8 L0 j; ]7 q6 x) s4 A+ T/ Z
					  const string& remaining)
) S5 K" @' a) t4 L{
4 {% k# S! U. ]5 s	+ [3 O7 A8 W0 l( e  d; O, Y  n/ }
	if(remaining.length() == 0) 0 Q+ Z! V9 i( ]
	{ 
9 G( B; y* `% u" s! x7 m/ S		cout << "{" << prefix << "} ";  k: U1 v# S  Y9 O" P
	}
( `, u* k+ o& _# G	else " @( M( X" Q8 Q4 V
	{
5 F& w$ T0 ]- ]' S		string newRemaining = remaining.substr(1);6 m, \" _! e7 g! K
		string newPrefix = prefix;2 }! o) r5 ~# E+ d4 ~$ M
		newPrefix.append(1, remaining[0]);
2 Z5 y: H! f6 \1 u# H1 n		printPowersetRec(prefix, newRemaining); // included& s* T/ y; v2 ~( L% A8 y8 ]# q
		printPowersetRec(newPrefix, newRemaining); // excluded
+ V8 v: a/ Z! h5 K	}	 
# d+ R$ ^% |0 T4 J; |}
% m- i# y' C' o9 Z
& i( g7 f/ g& [3 [/ `8 Evoid printPowerset(const string& input)0 L# F; A6 k$ k
{
% d. F8 I1 z7 ?; l% z	printPowersetRec("", input);/ o! F, H! |2 R) \: }
}
  {* Q/ Y: p( L* n& v
3 t2 r& q+ B' ~1 _int main()6 j( X8 H( ]5 \' A
{: W: M+ P  }7 J" Q1 W% d
	printPowerset("ABCD");& k  {, u( e& Z5 |: Z* [
}

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* * e7 A' s0 F. X% [
  ZoomBA powerset is simply done by 0 ~' ^; W/ a$ t8 M( l3 Y" g8 ]6 J
  the following 
) p! H7 }+ X8 F" R% g*/% b. N' U' u) }; H
my_vals = [ 0, 1, 2, 3 ]) n+ G) o4 O( }" X& v
// sequences() function generates all possible sub sequences
. {7 ]2 w. F8 P) }, T% p9 A// which is the power set :) 9 O; t" d) {, m' C5 b6 K( V
fold ( sequences(my_vals) ) -> { println($.o) }: ~) J7 w  s1 h5 y, x* }( `4 x

( Z) T6 D3 |1 m) Y// in a sensible way, this is how you can do the same5 G, U+ k* e5 T% D; \
// also explains why it is Theta( 2^n )( B* [0 r* Y3 t- V+ E. f; o
def power_set( arr ){
* Q! H2 B6 Q& G  len = size( arr ) 
8 P. ^5 f: W2 G8 M, g7 H  n = 2 ** len7 {! j; [# s, V# L
  for ( bn : [0:n] ){ // this is why it is 2^n ' T6 {# |' h# D  |) c6 J& R
    bs = str( bn, 2 ) // binary string format 
$ y! E5 h" K+ {    // to make it sized n binary digits # H' c4 }1 X+ q6 Z; t; {2 f
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 9 V- q/ ?1 T3 V0 `1 A2 ~
    // select the index i's item when bs contains 1 at index i , Z! i3 J: s% X/ O+ x
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }
) l8 \% L$ `2 @3 `. @7 i( i/ {    println ( subseq )' c8 }! ]; A2 O$ Q' X
  } ; t' h' u) x4 e6 p8 q( t3 ~
}, _' a3 q/ `! \2 h( s! Q
power_set( my_vals )

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

本版积分规则

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