找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4907|回复: 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 编辑
  @. r1 r* j5 L; w% F1 @* r" E1 m% X; l# }: `
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 | 显示全部楼层

/*
! N8 }+ J0 [8 N1 J2 k. z7 pSolution:
5 T) Q- [- G: K6 b% F9 J: s7 @8 H- the powerset is the set of all subsets% M- X( Z* Y7 w6 l4 e
- all or no element can be part of and all combination, E8 S5 q& h) u" i' [& ^
- per element two possibilities: be part of or not, 2 elements
( G8 @. X/ |- A6 b" [  so 2^n possibilities+ u$ Q' e. \; R4 O
' y$ I' E& l8 D4 N' Y
How to compute:2 b+ l9 {& o  Y* Z6 {
lets assume the set is given as a string:
% K: l$ o5 h* ~: W/ H- o. w*/
2 }2 b4 m/ w" e6 K& |- S3 d& v+ X2 Y* J
#include <iostream>7 ]9 D( B4 H3 U4 Q2 i
#include <string>
& f) |4 P, Q4 m8 I" E" |/ ~& C6 X! d! z* `
using namespace std;
9 G7 u9 D9 X% J6 s. B
0 W, p1 H5 u+ ?0 U7 j+ s* O; ~void printPowersetRec(const string& prefix, 
5 p/ T4 w1 a3 z" B3 \					  const string& remaining)
4 I8 }; v* T) N; h$ M( `4 `{) X. N/ T+ f' Z9 G
	
) |8 N) y* I7 y. P- `	if(remaining.length() == 0) & }2 `2 j: F1 C' O% F
	{ . l  }7 O5 B$ }  B9 O! i
		cout << "{" << prefix << "} ";
; d1 n) v& S7 N+ P5 R	}9 Y) o/ R* L1 d$ p
	else 
/ u9 F4 r3 }$ I2 N	{
4 d4 G. {8 L1 l9 _* l		string newRemaining = remaining.substr(1);
% Z1 |9 f' ^7 q, |" O' \		string newPrefix = prefix;
& C& W" `, x( P( S		newPrefix.append(1, remaining[0]);$ n& |* u" b( _- [2 [
		printPowersetRec(prefix, newRemaining); // included; F8 }5 z: `2 O. _) r  p
		printPowersetRec(newPrefix, newRemaining); // excluded
- d. [# Z% r6 S" @7 b	}	 
5 m7 U# B+ s' T$ |1 a2 ]}
# M/ }3 N: {% r7 j- j8 _( ]
1 z. N: b3 ]- z5 t0 Gvoid printPowerset(const string& input). m) h) U. E* x4 {1 d/ o
{
* J9 ?' n6 s0 q+ B	printPowersetRec("", input);1 v; ^. ], j+ m5 t
}! W: B& ^% ~* |" |, {( ?
/ R' {# ~3 C! f# d  _( k; l$ [
int main()
6 M7 n& ]3 L: |  c{
, v6 ~/ _6 G# r	printPowerset("ABCD");
6 j  h% O$ G- B}

回复 支持 反对

使用道具 举报

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* 
9 @7 ]$ ?( ~3 c  ZoomBA powerset is simply done by 
. B/ L0 H5 q3 b- j2 J  ^  the following / R0 x, U* Y1 z" v$ P' P
*/+ ~9 g+ D- ]& M6 w
my_vals = [ 0, 1, 2, 3 ]! Z1 @( ?8 l& B0 E' z- {) t
// sequences() function generates all possible sub sequences
" _8 f! n/ D  C// which is the power set :) - A. M1 ?9 ~$ c
fold ( sequences(my_vals) ) -> { println($.o) }
7 e8 D2 h6 q- e; l3 F" U, ~0 v9 T, o0 O' U' H3 k3 [" M8 j+ H. I
// in a sensible way, this is how you can do the same
4 u2 V7 j" W0 w+ u0 K// also explains why it is Theta( 2^n )  }. V4 B. e/ ~/ A( _( O
def power_set( arr ){0 f+ V: T3 ~# A9 A
  len = size( arr ) " p' ?3 d* E  k9 F$ B4 W
  n = 2 ** len6 b# C* J* X% t8 I: t% ]: e5 m
  for ( bn : [0:n] ){ // this is why it is 2^n / O0 x$ {2 P$ }/ Q+ P$ z
    bs = str( bn, 2 ) // binary string format 
1 z7 L' \" m* C! V: T! ]4 ~* @5 g& T    // to make it sized n binary digits 
* u: Q+ P% I$ h* ?    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
! X9 E% Q# }+ j. f; S    // select the index i's item when bs contains 1 at index i 
  a, E: L; J0 U% I5 F5 @2 w    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }
3 L) u; F" I& ~4 P8 ~* S) l    println ( subseq )2 f4 G& X& K. A' H" T
  } . K  n  I. f( k) ?1 b' B0 M
}8 K+ @2 c8 i. w
power_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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