So a few weeks ago I did an online technical interview with Google (I was contacted by one of their recruiter). The main question centred around “Find the occurrence of an element in a sorted array”. Now the interviewer wanted the most optimal solution, which is O(log n). This means there shall be no linear counting of any sort, whether after a binary search or before it.
I created a CountSorted() extension method in my C# utility library that uses just this method. Its alittle more complex because I implemented it with IComparable<T>. I’m sure I will find use for this type of count sometime in the future as the built in one for .NET is O(N). All that is currently needed is for me to implement the extension on IEnumerable<T> instead of IList<T> and accept predicates as parameters.
The main code file could be found here.
The most optimal solution I could come up with is using a binary search to find an index of the value we are counting, then find the left edge and right edge by using modified binary searches, then minus them to get the count.
So I basically had 3 methods, the main method:
Find left edge method:
Find right edge method:
This code could be done better, so if you can optimize it, please do a pull request on github. A few test cases are here for this algorithm.