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 ?

Anonymous · 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

Microsoft interview question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches