4 ms·
Pretty funny actually. The tactical error the interviewee made was not addressing the misconception on a different play field and then misplaying the politics
by joshuaellinger 13y ago
Pretty funny actually.
The tactical error the interviewee made was not addressing the misconception on a different play field and then misplaying the politics (assuming he wanted the job). He should have brought the question up in each subsequent interview and seen the reaction of the organization.
The way to address the misconception is to pose a slightly different question of the interviewer, namely, is this O(N) or O(N^2):
for (i=0; i<N; i++)
{
for (j=0; j<N; j++)
{
if (i==j) maxtrix[i,j] = 1;
}
}
and this
for (i=0; i<N; i++)
{
for (j=i; j<=i; j++)
{
matrix[i,j] = 1;
}
}
- gizmo686 13y agoAren't both of those O(N^2)? The first case is your standard example of nested for loops, where you run "i==j" N^2 times. In the second case, for every iteration of the outer loop, you run the inner command i times, leading to the sequence 1+2+3+4+5+...+N=N(N+1)/2=O(N^2) What is going on in the story is more a case of for(i=0; i<N; i++){for (j=0; j<K(i); j++) {matrix[i,j]=1}}, where K(i) does not grow with the size of the problem; and (for the sake of Big-O analysis) can be replaced with a constant.
- deleted 13y ago[deleted]
- joshuaellinger 13y agoI think you saw the 2nd case before I correct it to make my point clearer. In the first example, it is O(N^2) with clock cycles but O(N) with memory access. If memory access is 100 times slower than CPU or your compiler is smart enough, then the O(N) term dominates. My corrected 2nd example is clearly O(N). The reason for presenting these example to the interviewer is to reframe the problem into something simpler to make the point that having two nested loops does not make something O(N^2).
- gizmo686 13y agoEither that, or I just missed it. For anyone wondering (I think) the change is that the inner loop read "(j=i; j<=i; j++)". Note the first statement "j=i" is not "j=1". It would probably be clearer with a variable other than i.