## Bloomberg LP Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 2 vote

No one asks these types of questions in interviews. We are not in college.

Comment hidden because of low score. Click to expand.
1
of 1 vote

When in doubt, Wolfram Alpha is the one to help you out.
Go to : wolframalpha.com/input/?i=T(n)+%3D+n+*+(+T(n%2F2)+%5E++2+)
You are correct, it is exponential in nature :
picpaste.com/w38Ckgj7.png

Clearly now, it has tight asymptotic bound is it not?

Comment hidden because of low score. Click to expand.
0
of 0 vote

O( (N/2)^(N-1) )

Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually, one can use logarithmic series to solve this problem.
Check this out

``````T(n) = n(T(n/2)^2)
Log(T(n)) = Log(n(T(n/2)^2)) => Log(n) + 2Log(T(n/2))
Log(T(n)) = Log(n) + 2(Log(n/2) + 2Log(T(n/4)) and so on which you can write as
Log(T(n)) = Sum(i = 0 to k)(2^i * Log(n/2^i) where k is Log(n)``````

Now, If you see the values of this sequence varies from Log(n) to n.
Worst case would be that the sum is nLog(n) only, considering every value to n, and i varies from 0 to Log(n), so that sum.

``````Log(T(n)) = nLog(n)
T(n) = 2^(nLog(n)) = n2^n.``````

and so this does not have asymtotic bound.
Now we know that the sum would always be more than n, which itself make the

``T(n) = 2^n``

and so, this does not have any asymptotic lower bound, and so it does not have tight asympotatic bound.

Comment hidden because of low score. Click to expand.
0
of 0 vote

T(n) = 4^(n-1)/n
Brute-force exact solution:

``````T(n) = n*(T(n/2)^2)
ln(T(n)) = f(n) = 2*f(n/2) + ln(n)
f(2^x) = 2*f(2^(x-1)) + ln2*x
f(2^x) = g(x) = 2*g(x-1) + ln2*x
g(x) = h(x)*2^x  = 2*h(x-1)*2^(x-1) + ln2*x
h(x) = h(x-1) + ln2*x/2^x = ln2*(x/2^x + (x-1)/2^(x-1) +...) = ln2*(2 - (x+2)/2^x)
//
h(n) = 1/2+2/4 +3/8+...+n/2^n  = 2 - (n+2)/2^n
h1(x) = 1 + x/2 +...+ (x/2)^n = [1-(x/2)^(n+1)]/[1-(x/2)]
h(n) = h1'(x=1) = -2*[(n+1)*(1/2)^(n+1)] + 2*[1-(1/2)^(n+1)] = 2 - (n+2)/2^n
//
g(x) = ln2*(2 - (x+2)/2^x)*2^x = ln2*(2^(x+1) - (x+2))
--check: ln2*(2^(x+1) - (x+2)) = 2*ln2*(2^x - (x+1)) + ln2*x : OK!!
f(x) = f(2^lg2(x)) = g(lg2(x)) = ln2*(2*x - (lg2(x)+2))
T(n) = exp(ln2*(2*n - (lg2(n)+2))) = 2^(2*n - (lg2(n)+2)) = 4^(n-1)/n
--check: 4^(n-1)/n = n*(4^(n/2-1)/(n/2))^2 = 4*n*4^(n-2)/n^2 ...OK!``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.