Look for a string in a very long string - a needle in a haystack. Write the program in pseudo-code.

Question

Xin Li · Accepted Answer

The Boyer–Moore string search algorithm can run, in < O(n) time, on average, particularly if the string being looked for is long.

Utilisateur anonyme · Answer

function isSubstring (needle, haystack) {
    for(int i=0; i

ojiisan · Answer

For production code, I would look up Boyer-Moore and do that. But if I had to answer off the top of my head, based on my memoires of Boyer-Moore, the pseudo-code would look like:

Construct table(char-diff, offset) {offset by which to move test string b4 next text}
begin:
Compare (needle, haystack): if comparison false, lookup in above table to compute next offset.
Compare (needle, haystack[next-offset] if comparison still false AND we have not passed end of haystack, repeat.
Test which case: did we pass end, or find needle
return 0 if passed end, offset to needle in haystack otherwise.

vic · Answer

Small optimization : can store length(haystack) and length(needle) to make it faster :)

Jeff · Answer

Note: the question specifically asks for a solution in *pseudo-code* ...

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois