Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
1. make the points angle based = angleArray
2. sort angleArray nlogn
3. for i in range(0,len(angleArray):
count how many enter in you window. = tempSum = max
4. move to next point where the is tempSum = tempSum-1 + count untill you exeed the window (you continue from the index you stopped you dont go back) so you just do here O(n)
5. if tempSum > max then max = tempSum
O(nlogn) Solution.
1. consider the given view point as center of axis and calculate the angle of each point.
2. sort the angles
3. find the maximum window in the sorted list with max difference of given viewing angle.
- Paras November 14, 2016