## Directi Interview Question Software Engineer / Developers

- 0of 0 votes
You are given 100 stations and distance between each adjacent stations. Now you have to select 10 stations(means 10 hops) among those 100 stations in such a way that maximum of distance between any 2 hops will be minimised. By default 1 and 100 stations are selected , so you need to choose only 8 more stations.

The solution to this problem seems like Dynamic programming.

**Country:**India

**Interview Type:**In-Person

Hey guys, it we have 100 nodes and I want to reach from node 1 to node 100 in exactly 10 hops (with min expense), how do we do that? Dijkstra's algo might give me a path in < 10 hops. Any ideas?

My approach is this:

Consider this question for 10 stations and 4 flags Let the distance between them be as

1-----2--3---4----5-----6------7-------8-9---10

Where – represents the distance in units It means distance between 1st and 2nd station is 5, And hence the distance between the first and tenth station will be (5+2+3+4+5+6+7+1+3) = 36

We apply binary search between 1st and 10th station hence we get 36/2 = 18

Hence this distance is 1 unit far from 6 and 3 units from 5, hence we will select the 6th station as the pivot and apply binary search between (i) 1st station and 6th station (ii) 6th station and 10th station

Average of distance between 1st station and 6th station is 19/2 = 9.5units from 1st station Hence 9.5 is more closer to station 4 and we place flag on station 4.

Average of distance between 6th station and 10th station is 17/2 = 8.5units from 6th station Hence it is more closer to station number 7 and we place flag on station 7.

Hence answer will be 1,4,7,10.Hence maximum distance is optimized as b/w any two stations is 15 in this case Similarly we can solve for 100 stations.

Correct me if i am wrong

Please check whether this approach is correct or there can be any more efficient. Correct me if i am wrong Thanks in advance

I have updated my solution as

Consider this question for 10 stations and 4 flags Let the distance between them be as 1-----2--3---4----5-----6------7-------8-9---10

Where – represents the distance in units It means distance between 1st and 2nd station is 5, And hence the distance between the first and tenth station will be (5+2+3+4+5+6+7+1+3) = 36

We apply binary search between 1st and 10th station hence we get 36/2 = 18

Hence we will choose the pivot as 18 unit of distance and apply binary search from

(i) 1st and 18th unit of distance for 1st flag

(ii) 19th and 36th unit of distance for 2nd flag

Average of distance is 9 for 1st flag which is more closer to 4th station we place flag on station 4.

Average of distance is 9 and hence distance from starting is 27 which is more closer to 7th station Hence we place 2nd flag on station 7.

Hence answer will 1,4,7,10.Hence maximum distance is optimized as b/w any two stations is 15 in this case Similarly we can solve for 100 stations

Please check whether this approach is correct or there can be any more efficient. Correct me if i am wrong Thanks in advance

This problem is very simple .... Greedy approach will work. step 1: Find the minimum distance, step 2: Add this minimum distance with the minimum adjacent distance (Either left one or

right one). step 3: Join this two to one single distance. step 4: Repeat step 1-3 until total number of distinct distance become equal to the number of flags+1

Assuming a general graph with edge weights and you are allowed to repeat intermediate nodes, then the following recursion seems to give a dynamic programming algorithm:

Let the source and destination vertices be s and t.

We need to compute Best[s,t,10]. Best[x,y,t] is best path between x to y of t hops.

The recurrence is

Best[u,v,1] is easy to calculate.

- Anonymous on September 20, 2011 Edit | Flag ReplyAssuming the number of hops is constant, a naive implementation of this will give an O(n^2) time and O(n^2) space algorithm.