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.

- zr.roman January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- mehraz January 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes you are right :)

- Parag Thombare July 12, 2019 | Flag
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 )

- NoOne October 07, 2016 | Flag Reply
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
2 add an element
3 compare next element with the top if bigger do nothing else replace top of heap

- abhay0609 January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

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

- zr.roman January 05, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice explanation

- HimanshuP January 05, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- teli.vaibhav January 07, 2016 | Flag
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.

- pcbabu January 05, 2016 | Flag Reply
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?

- EPavlova January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- The Puzzler 2.0 January 06, 2016 | Flag
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.

- EPavlova January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

en.wikipedia.org/wiki/Parallax#Distance_measurement

- zr.roman January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ikoryf January 06, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

thank you zr.roman.

- EPavlova January 06, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More