Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
No need to code. We know the nearest star is the sun.
We also know the next nearest star system is : en.wikipedia.org/wiki/Alpha_Centauri.
However, given an arbitrary point in space, and arbitrary other points, min should do the trick :
// ZoomBA
#(min,max) = minmax(stars) :: {
$.o.0.distance_from_earth < $.o.1.distance_from_earth
}
println( min )
We can use heap to find closest star since sorting will take O(nlogn) time while using heap we can find it with complexity O(nlogk) where k <<n.
1 Use a max heap
2 add an element
3 compare next element with the top if bigger do nothing else replace top of heap
creating a heap from any array is O(n).
using brute force to find a min/max element in array is also O(n).
Could you clarify if interviewer agree with you to calculate Euclidean distances? Did he (she) provide you some hints?
lets do comparison analysis of a brute force method and Parallax Distance measurement method.
- zr.roman January 06, 2016In case of brute force method running time will be actually infinity. Why? Let's see.
To measure a distance from earth to a star we must send a signal to a star and wait for a response (reflected signal) and divide the overall time by 2. This will be the number of light years (ly) to that star. But what if the distance to some star is 1.000 ly? This means that we have to wait 2.000 years to receive a reflected signal! Nobody lives that long. In reality most stars are millions and billions lys far from us. That is why I say that actual running time of brute force is infinity.
Now Parallax Distance measurement method: actual running time is 1 year.
The algorithm is simple: we measure the start positions of all 10.000 stars in the beginning of the year. Then during 1 year we systematically measure parallaxes of all the stars. In the end of the year we compare all the parallaxes. The star with the greatest parallax is the nearest.