Directi Interview Question Software Engineer / Developers

  • directi-interview-questions
    0
    of 0 votes
    16
    Answers

    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.

    - nitatbit on September 19, 2011 in India Report Duplicate | Flag
    Directi Software Engineer / Developer Algorithm

Country: India
Interview Type: In-Person


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

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,m] =  min_{over all u'} [ max {Distance(u,u'), Best[u',v, m-1]} ]

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

Assuming the number of hops is constant, a naive implementation of this will give an O(n^2) time and O(n^2) space algorithm.

- Anonymous on September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 This solution must work.
However, though space is O(n^2) , time is O(n^3). As there are O(n^2) entries (value of m = 10, hence assumed to be constant), and it takes O(n) to compute min for each entry.

- anon on September 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- luv on May 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think ur solution will work only for odd number of stations

- decoder on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if you select 1 and 100...that itself will make the max distance b/w two hops as 99...
am i missing something here.

- Anonymous on September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

looks like a shortest path problem --> see Dijkstra's algorithm (you were on the right track with a dynamic programming approach)

- Anonymous on September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is not very clear to me.

Are we given the list of possible adjacent stations? OR any two stations are adjacent and we are given the distance?

Can we repeat stations in the hops? (assuming we can repeat makes the problem easier, I think).

Can you please clarify?

- Anonymous on September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Anonymous on September 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did you read the dynamic programming solution above?

- Anonymous on September 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about finding hop near the 1/8th distance, 2/8 th distance and so on ? So we can find the cumulative distance O(n) and search for the 8 hops O(1).

- Anonymous on September 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about all pairs shortest path execution on a general graph?
Post the execution short them and return minimum k (10) results

- Amit Priyadarshi on March 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

floyld warshall with a modification for number of steps will work. Correct me if i am wrong

- Nitish on May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- luv on May 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Amar on December 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach. I 'll start doing depth first search from the root and will maintain a level variable which will be counting the number of levels.
{{

int graph[100][100];
bool flag[100];
int n;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void dfs(int node,int level)
{
if(level==10&& node==dest)
print(stack);
else
{
flag[node]=false;
qsort(graph[node],n,sizeof(int),compare);
for(int i=0;i<n;i++)
{
if(!flag[i])
{
dfs(i,level+1);
stack.push(i);
}
}
stack.pop(node);
flag[node]=false;
}
}
}}

- Aditya on October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{My approach. I 'll start doing depth first search from the root and will maintain a level variable which will be counting the number of levels.
{{

int graph[100][100];
bool flag[100];
int n;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void dfs(int node,int level)
{
if(level==10&& node==dest)
print(stack);
else
{
flag[node]=false;
qsort(graph[node],n,sizeof(int),compare);
for(int i=0;i<n;i++)
{
if(!flag[i])
{
dfs(i,level+1);
stack.push(i);
}
}
stack.pop(node);
flag[node]=false;
}
}
}}}

- Aditya on October 25, 2014 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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