Technical interviews - prep

[Pho]

MIT have excellent lecture series on you tube:
Introduction to algorithms
https://www.youtube.com/watch?v=JPyuH4qXLZ0

Analysis of algorithms
https://www.youtube.com/playlist?list=PLU2PyJOcZ7fg9wk_ZouOkgPb1PbCMja04

Had an email for this yesterday which may be of use . Free MOOC course run by Princeton University:

Algorithms, Part I

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers basic iterable data types, sorting, and searching algorithms.

https://www.coursera.org/course/algs4partI

 

[peterwalkley]

That's a good course. Well worth the time even if you think you know it all already.

 

[D.P.]

Yes but the result of 1<<4=16 doesn't it? So 8 & 16 = 01000 & 10000 = 00000

Yes, I'm not sure what you are trying to ask though.
1 << 4 is 16. If you know python this kind of stuff is really nice and easy to double check:

>>> x  = 1 << 4
>>> x
[B]16[/B]
>>> y = 8
>>> x & y
[B]0[/B]

In the number 8 the 4th bit is set to 1 and no other bits are set, but remember like array you need to start from 0, not 1.

e.g. if you have an array and you want to check the nth value you look in array position n-1:

int[] numbers = {10,20,30,40,50};
cout << "3rd number is " << numbers[2] << endl;

If you want to check the nth bit is set you check n-1.
In your post you have this:

num = 4
bit = 2
                    0100&
0001 << 2 = 0100
                    ----
                    0100

This is wrong, the 2nd bit is not set in 4, the 3rd bit is:

Bit:           8th  7th   6th    5th  4th  3rd  2nd  1st
Value:      128  64     32    16    8     4      2     1
Bit Index:  7     6       5      4     3     2      1     0

You want to check the 1st bit is set:

Number 3 = 0011
Bit = 1 
1 << 0    =  0001

  0011 &
  0001
=0001

And for 3rd bit:

1 << 2 = 0100

The question itself doesn't mention any assumptions, the answer does however

That is an issue, maybe the assumptions are at the start of the the chapter on string manipulation? The fact that the answer asks for a solution without a data structure indicates that the bit mask solution is what they intended.

It may be worth telling the publisher about the error, you might get a voucher for free books etc.

This does highlight an issue you sometimes get at interviews though, the people having asked the same question hundreds of times end up short cutting the pretext and excluding useful information.

In the flip side this is the thing that we would want interviewers to ask about. Is the sting preformatted, Unicode, lowercase, alpha-numeric, only letters, do they want fastest time, lowest memory usage, or most maintainable code? Asking the interviewer such questions shows you have avery good understanding of real world software development and such textbook answers dont always apply.

I said it earlier but such neat solutions as the bit mask are quite common, especially if you know the text is formatted. E.g the text might be a surname taken from a database entry where all the text are formatted before entry.

As a coincidence, next to chrome I have a window with this javascript (yuck!) code visible just above the function I was working on:

function hasCommonPhase(phase1,phase2)
{
   if ( phase1 > 0 && phase2 > 0 &&  (phase1 & phase2) > 0) return true;
   else return false;
}

function phaseToBits(phase)
{
   if (phase == 0) return 0;
   else return (1 << (phase-1));
}

Note the -1...

 

[D.P.]

Had an email for this yesterday which may be of use . Free MOOC course run by Princeton University:


https://www.coursera.org/course/algs4partI

Looks like a good course to me

 

[PaulStat]

Ah ok zero based that's where I was going wrong