Directi Interview Question for Software Engineer / Developers

• 0

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.

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

+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.

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

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

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

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.

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)

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?

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?

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

Did you read the dynamic programming solution above?

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

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

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

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

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

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;
}
}
}}

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;
}
}
}}}

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.

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.

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.