## Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

lets do comparison analysis of a brute force method and Parallax Distance measurement method.
In 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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

No need to sort. Just find the min distance O(n).

Comment hidden because of low score. Click to expand.
0

yes you are right :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 )``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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
3 compare next element with the top if bigger do nothing else replace top of heap

Comment hidden because of low score. Click to expand.
3

creating a heap from any array is O(n).
using brute force to find a min/max element in array is also O(n).

Comment hidden because of low score. Click to expand.
0

Nice explanation

Comment hidden because of low score. Click to expand.
0

The heap solution would make sense if k closest stars to the earth are asked.

Comment hidden because of low score. Click to expand.
0
of 0 vote

stars are shorted by distance in sky. so the first element in the array will be closest.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you clarify if interviewer agree with you to calculate Euclidean distances? Did he (she) provide you some hints?

Comment hidden because of low score. Click to expand.
0

No, he didn't give any hints, he just said chose any method

Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe this is open for discussion problem, because linear solution with calculating all distances seems to me very misleading.

Comment hidden because of low score. Click to expand.
0
of 0 vote

en.wikipedia.org/wiki/Parallax#Distance_measurement

Comment hidden because of low score. Click to expand.
0

Cool idea! An alternative to euclidean distance.
The algorithm to search for the smallest displacement over a period of time would still require sorting/heap etc, but it's a nice approach :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

thank you zr.roman.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.