SoftDev : Python (I chose), you have an array of string sorted but with empty strings (e.g. ["abc","","","","cef","","","dej,""] and you want to know if an other string is in this array. How to do it with a complexity of O(log n) in general case ?
Then how to find how many times it appears in this array ?

Question

SoftDev : Python (I chose), you have an array of string sorted but with empty strings (e.g. ["abc","","","","cef","","","dej,""] and you want to know if an other string is in this array. How to do it with a complexity of O(log n) in general case ?
Then how to find how many times it appears in this array ?

Sigiloso · Accepted Answer

Variant of binary search algorithm. Just that if array[i] = "" you take array[i-1] until reaching a non empty string.
For the second, once you find the index you just look at his neighboors.

Microsoft

Pergunta de entrevista da empresa Microsoft

Resposta da entrevista

Empresas seguidas

Buscas de vagas