找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4849|回复: 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 编辑 0 ?5 E2 @# W* C$ _0 P2 R" [

8 A) Y5 _. _/ A8 l$ C3 bGiven 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 | 显示全部楼层

/*
3 y. Q$ _8 T0 X3 Q* f7 F8 ]Solution:0 L* V7 E. E2 a& z1 ~. Q
- the powerset is the set of all subsets
  S+ G/ ~4 O8 N+ ~) s: _/ L- all or no element can be part of and all combination- D0 V( O# B  J' ]0 w3 j
- per element two possibilities: be part of or not, 2 elements1 Q! A+ {0 J/ ]: R# `1 ]; q
  so 2^n possibilities' H  r7 N: U; J! g/ f  r1 `
- P, X7 ?: ?: M% P# |
How to compute:
2 ?7 N$ U" [3 C4 X$ rlets assume the set is given as a string:: u% y5 ^: s* C5 o
*/
, I8 a/ _' F# o0 q- x; H' h2 e- R6 P% A+ u0 c6 k3 t
#include <iostream>
( `" }) i9 n+ B#include <string>( O: I6 ?. u  v, E2 ?

- j7 z  c, h, x1 W( H  Y* p5 zusing namespace std;; x( K: |  H3 e& H4 P) N

, v# \  w7 `% R& o$ Pvoid printPowersetRec(const string& prefix, : F* K( Y! J$ e$ O' O+ k7 V2 M
					  const string& remaining)
0 w$ Q$ }7 I& R{7 X* p0 \/ i* |3 ?: n5 T# a
	* F" ]% C" c% Z- `. S! s& {
	if(remaining.length() == 0) 
! W4 l* {+ r6 `3 ?' f	{ . b2 L; w  o! C& b7 A' n
		cout << "{" << prefix << "} ";
: [% y, \5 n; ^1 R% l; u	}
% Q8 u. B1 N) Q8 X$ ~# Q3 c6 F	else 
3 ~; w3 v; q' A! ]- t	{
! C; ^' U% i2 z$ S: F		string newRemaining = remaining.substr(1);
' g. }8 I$ I& F( q' x) p1 f. c* \		string newPrefix = prefix;( m- F2 i/ V2 u  {( w  ]2 Y, e" Q/ U
		newPrefix.append(1, remaining[0]);
" Y+ A' E4 ?% a/ C* ^1 U$ l1 R9 K		printPowersetRec(prefix, newRemaining); // included% b4 X& I' u# O
		printPowersetRec(newPrefix, newRemaining); // excluded
8 N% D: m, b; m& F" v- N, w	}	 
; _2 s  M- i  r0 D  l}
2 a. l& x3 F/ h! T$ G* W0 D, l* N- l. o; B2 y
void printPowerset(const string& input)# E$ |! o7 D5 r0 `! u
{
" I, o7 u' m, X8 F: {+ {	printPowersetRec("", input);! a+ O0 f7 L0 b7 E
}8 `4 a" m* a2 G$ h4 g

- s) r! D2 r6 q) X  bint main()
; M4 ?3 w: n# A7 S( |- D$ \  u* s{5 j( x  }& G, b8 K
	printPowerset("ABCD");: t5 T! |- I& y" l3 E! [5 `8 h! J! m; _
}

回复 支持 反对

使用道具 举报

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

/* 
+ z4 L9 B7 H$ W/ U  ZoomBA powerset is simply done by 
4 k; {: F+ B8 ~  the following # ^9 o# m# ~8 a$ A8 W9 Z* S1 v6 a
*/
/ ~1 y' n7 E* }" K. l, qmy_vals = [ 0, 1, 2, 3 ]
: U; i; g* e+ D1 v( Q// sequences() function generates all possible sub sequences
  \6 ?6 Q: T- P, l7 W// which is the power set :) % s$ L$ w+ e1 Z% w
fold ( sequences(my_vals) ) -> { println($.o) }  h; ^* N& l; U0 t3 i! p$ Q1 U5 `: ?
4 W1 |2 ~- Y: x8 R7 X. Y
// in a sensible way, this is how you can do the same
8 z5 G# n1 w- M/ G5 y// also explains why it is Theta( 2^n )$ l3 l( C0 S5 H/ W' S4 I
def power_set( arr ){
! T1 S# {" v4 j  X- c  len = size( arr ) 
( {7 W- X6 K% n9 Q) M' k. }  n = 2 ** len
/ m- e8 M2 ]4 O+ K  for ( bn : [0:n] ){ // this is why it is 2^n & h$ B: p, x+ e2 M3 u$ g! G
    bs = str( bn, 2 ) // binary string format 
2 ]7 q% V# @$ C* l5 X    // to make it sized n binary digits ! |) K6 t3 F* ^
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
6 N1 n7 Z8 ^/ _' Y* W    // select the index i's item when bs contains 1 at index i / x0 r8 i& M, R7 z
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }1 I' R, b) s9 Q8 L# q
    println ( subseq )( x% u. {* d4 x% S& e% t: [
  } ' y) `' b2 F. B/ c
}* b  Y3 Z+ {5 ~3 R  J. z
power_set( my_vals )

回复 支持 反对

使用道具 举报

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

本版积分规则

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