Create a "ransom note verifier" uses a string "note" and make sure that from a string "magazine" that you can create the note using the letters from the magazine.

Question

Sigiloso · Accepted Answer

Use a set to store characters in the note, and while iterating through the magazine, remove the character from the set if found. If the set is empty at any point we can make the random note. O(n) where n is the number of characters in the note + the number of characters in the magazine.

Sigiloso · Answer

Not sure set is the right answer to this, as you also need to store how many times the character appears. i.e there are 15 Fs in the note, but only 14 in the magazine. This is bad!

You'd likely want a hash table of some kind. Maybe ask about what characters are in here - you can create one for ASCII letters only, to put a tight bound on the space complexity.

The runtime would be O(len(note) + len(magazine)), plus the final call to figure out if the hash table is all zeroes - constant time, if you made one for ASCII characters.

X

Pergunta de entrevista da empresa X

Respostas da entrevista

Empresas seguidas

Buscas de vagas