Here’s the “Ransom Note” problem asked during the interview for Microsoft’s SDET. Reader’s if you are looking at this code you can see in actual program that I wrote all the way down, look at the comments that can be said as Tester’s way of thinking for breaking the code.

// The “Ransom Note” problem. I want to determine if I can create a particular ransom note by from a given magazine.

// This function returns true if it is possible to construct the Note from the Magazine without reusing any characters
// and false otherwise

// In other words: Is every character in the note present in the magazine at least as many times as it is in the note?
// Here is the C function prototype. How would you implement this, optimizing for speed.

bool CanMakeString( char *pMagazine, // A potentially long string of characters
unsigned countMag, // The number of characters in it
char *pNote, // The string we’d like to construct from the above
unsigned countNote); // The number of characters in it

Examples:
// This one would return “true”. All characters from the note are present in the magazine.
CanMakeString(“This is the beginning of a magazine”,32, “he is home”, 10);

// This one returns “false”. The magazine lacks the r, the k, the o’s, etc.
CanMakeString(“This is the beginning of a magazine”, 32, “bring cookies”, 14);

bool canMakeString(char *pMagazine, unsigned countMag, char *pNote, unsigned countNote){

// Check for countMag < countNote return false;
// Check for Null for both; return false;
// Check for unsigned character; return false;

int a[256];
for(int i=0; i<countNote; i++){
a[Ascii(pNote[i])]++;
}

for(int i=0;i0){
a[Ascii( pMagazine[i] )]–;
countNote–;
}
}

return false;
}

Advertisements