## Microsoft Interview Question

Country: United States

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

It is certainly O(N^3). If you doubt it replace the inner "// some code" with a c++ to count how many times that line get executed.

n = 1 -> c = 0
n = 2 -> c = 0
n = 4 -> c = 4
n = 8 -> c = 56
n = 16 -> c = 560
n = 32 -> c = 4960
n = 64 -> c = 41664

As you see when n doubles c increases around 8-9 times, so it is a N^3.
The only possibility is that the code in your interview was different.

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

Complexity of the code can be represented by the formula: [n(n-1)(n-2)]/6
which is O(n^3).

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

Why is [n(n-1)(n-2)] divided by 6?

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

Because inside the inner-most loop the code basically enumerates nC3 or all possible combinations (i,j,k) with three numbers in [1,n]. n(n-1)(n-2) gives you all possible permutations(where 1,2,3 and 3,2,1 counted differently). By dividing it by 3!=6 you count permunations with the same set of numbers only once.

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

and that's why you should consider again whether you REALLY want to work for microsoft

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

Seriously..!!!

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

Simple way to look at this is drop all the "off by one" non-sense. The +1 and -1's don't matter much at scale.

so for N iterations, we run N/2 iterations of N/4 iterations. But when you account for constants getting dropped and such we still get N^3

for (int i = 0; i < n; ++i)
{
//some code
for (int j = i; j < n; ++j)
{
//some code
for (int k = j; k < n; ++k)
{
//some code
}
}

Yes each loop isn't starting at 0 but it doesn't have to to count. This is very similar to the question of how many contiguous subarrays are there in an array.

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

There is 3 for loops each loop will take n times. So you think that O(n^3). but when ever considering time complexity we need to consider tightest upper bound which is O(n^2). You cannot go below this time to complete all the three loops.

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

Definitely this will be O(n^3)

Suppose,

if i=0,
j=1, then some code will execute= n-2
j=2, then some code will execute= n-3
.
.
j=n-1, then some code will execute= n-(n-1)=1
so for i=0, some code will execute = (n-2) + (n-3)+...1 = O(n^2)
so for i=1, like that code execution will be 0(n^2)..
so after executing it n times ... it will be 0(n^3)

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

it is O(n*n*n). may be interviewer want to distract the person.

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

I know the code that is put up here looks like an obvious n^3 , however, i dont think we can rule out n^2 completely. I mean there are many graph based dynamic programming algorithms where the efficiency when analysed from the node side is nm or even n^2.
Could you please include the code in the middle ? I mean if there are
continue; statements in the higher recurrence structures as well,
it might help clear it out.

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

It's not O(n^3) because the # of ops doesn't scale anywhere near n^3 as n increases,
consider `n = 16`, 16^2 = 256, 16^3 = 4096, at n= 16 this algorithm executes only 560 operations (this is more than 256, but is still an order of magnitude lower than O(n^3) so the lower order is O(n^2))

As to why this is the case: the reason is because as `i` iterates the number of `j` loops decreases and as `j` iterates the number of times `k` loops decreases.

If `i`, `j`, `k` were static loops of fixed iteration n then this would be O(n^3)

n = 16
sum = 0
for (i = 0; i < n - 2; i++)
for (j = i + 1; j < n - 1; j++)
for (k = j + 1; k < n; k++)
sum += 1
console.log(sum)
var sum
, i
, j
, k
, n

! node time-complexity.js
560
!

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

When an algorithm is O(n^3) it doesn't mean that for n=16 it runs exactly 16^3. Especially for small values of n (like n=16) the number is biased by the constants and what you get is not accurate enough to discriminate between O(n^3) or O(n^2) or even some cases O(n)!

You have to consider the growth rate. For example, what happens if n doubles or triples and then measure the increase. This code is O(n^3).

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

Yes, you are right. I graphed it and it does break back toward O(n^3).

Here was the #s
! node time-complexity
1 0 0
2 0 0
4 4 0.0625
8 56 0.109375
16 560 0.13671875
32 4960 0.1513671875
64 41664 0.158935546875
128 341376 0.16278076171875
256 2763520 0.1647186279296875
512 22238720 0.16569137573242188
1024 178433024 0.16617870330810547
2048 1429559296 0.16642260551452637

Comment hidden because of low score. Click to expand.

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.