Interview Question

Data Scientist Interview

-Dublin, Dublin

Microsoft

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 ?

AnswerAdd Tags

Interview Answer

1 Answer

0

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.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.