Interview Question for Software Trainees

Country: India
Interview Type: In-Person

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

We can treat this as a shortest path problem.
Going from chest to clue A, then to clue B and returning to chest, does not affect the result of picking all clues except A and B.
So we can use dynamic programming with bitmasks (handy that N <= 24). We can process the bitmasks in ascending order from 1 to 2^N - 1. A bitmask will have bit i set to 1 if we need to pick clue i. The minimum cost of selecting a set of clues is given by:
- the cost of picking one of the clues with bit set to 1 + the cost of picking all the other clues
- or the cost of picking 2 of the clues with bit set to 1 + the cost of picking all the other clues

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX = 24;
int dp[1<<MAX], N, sx, sy, x[MAX], y[MAX], dist[MAX][MAX], chest_dist[MAX];

int main() {
scanf("%d", &nt);
for (t = 1; t <= nt; t++) {
scanf("%d %d %d", &sx, &sy, &N);
for (i = 0 ; i < N ; i++) {
scanf("%d %d", &x[i], &y[i]);
chest_dist[i] = (x[i]-sx)*(x[i]-sx)+(y[i]-sy)*(y[i]-sy);
}
for (i = 0 ; i < N ; i++)
for (j = i+1; j < N ; j++)
dist[i][j] = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);

dp[0] = 0;
all_mask = (1 << N) - 1;
// mask with bit i set to 1 if we need to pick clue i
for (i = 0 ; i < N; i++)
if (mask & (1 << i)) {
// pick clue i and come back to chest
for (j = i+1; j < N; j++)
if (mask & (1 << j)) {
// pick clues i and j, come back to chest
cost = chest_dist[i]+chest_dist[j]+dist[i][j] +
}
}
}
}
return 0;
}

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

NP complete my son said

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

I Got the Solution...it can be done using bit masking DP

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

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

hehe no

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

My approach is as follows:
Step 1: Make the "Clue Box" to origin and make all points relative to that
Step 2: For all the pairs (all combination of two) of clues find the angle between them. If the angle between them is less than or equal to 90 degree then it is considered as acceptable. (If there are two nodes whose angle difference between them is greater than 90 then it is better to visit them separately)
Step 3: For all pairs of acceptable nodes sort them in the order of distance between them. Note: The distance metric is as per given in the problem statment
Step 4: Take each edge (sorted order) and compute the distance needed to get those two clues. (Remove both the nodes from a HashMap)
NOTE: We track all nodes using a HashMap (python Dict)
Step 5: Once all the edges are over, iterate through the HashMap and add the cost to visit those independent nodes.
Return the result

import math
import pdb
import itertools

#arr = [(1,1),(4,3),(3,4),(0,0)] #containing all points
#arr = [(-3,4), (2,2) ]
#arr = [(0,0), (1,1), (-1,1), (1,-1), (-1,-1)]
#arr = [(0,0), (0,1), (0,2)]
arr = [(0,0),(0,5),(1,5),(5,1),(5,0),(-5,-5)]

nodeDict = {} #dictionary containing all nodes
distanceArr = []
totalDistanceTravelled = 0

def myComparator(x, y):
if y[2] < x[2] and y[2] < x[2]:
return 1
if x[2] == y[2] and x[2] == y[2]:
return 0
return -1

def angleDiffAndDistance(index):
index1, index2 = index
degs1 = math.degrees(math.atan2(*arr[index1]))
degs2 = math.degrees(math.atan2(*arr[index2]))
diff =  abs(degs1-degs2)
if diff >= 270 or diff <= 90: #acceptable angle difference
distance  = (arr[index1][0] - arr[index2][0])**2 + (arr[index1][1] - arr[index2][1])**2
distanceArr.append((index1, index2, distance))

def getDistance(index1, index2):
distance = 0
distance  = (arr[index1][0] - arr[index2][0])**2 + (arr[index1][1] - arr[index2][1])**2
distance += (arr[index1][0])**2 + (arr[index1][1])**2
distance += (arr[index2][0])**2 + (arr[index2][1])**2
return distance

def getSingleDistance(index1):
distance = 0
distance += (arr[index1][0])**2 + (arr[index1][1])**2
return 2*distance

if __name__ == "__main__":
#Making relative to Origin
originX, originY = arr[0][0], arr[0][1]
for i in range(1, len(arr)):
arr[i] = (arr[i][0]-originX, arr[i][1]-originY)
arr = arr[1:]
indexes = [i for i in range(0, len(arr))]
for i in indexes:
nodeDict[i] = 0
combinations = itertools.combinations( indexes, 2)

for i in combinations:
angleDiffAndDistance(i)
distanceArr.sort(myComparator)
print arr
print distanceArr
for i in distanceArr:
if i[0] in nodeDict and i[1] in nodeDict:
del nodeDict[i[0]]
del nodeDict[i[1]]
totalDistanceTravelled += getDistance(i[0], i[1])
for node in nodeDict:
totalDistanceTravelled += getSingleDistance(node)
print totalDistanceTravelled

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

This is a shortest path problem. Your greedy approach is incorrect. Counter-examples:

2
-1 -2
3
3 2
-1 -1
-1 1
0 0
3
1 0
2 1
1 0

In case 1, the best is to take clue at -1, -1 and come back. Then clue at -1, 1 go to clue 3, 2 and come back. This costs 60. Your program returns 78.
The answer to test 2 is 10, but your program gives 12.

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

successboy123; Paring any two clues is better than visiting them separately.

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

@Kiarash, that sounds intuitive but it's not true because the time is equal to the square of the euclidean distance between the points. Being the square makes the difference (recall the a^2 + b^2 = c^2 equation and what happens with angles bigger than 90 degrees)

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.