Myntra Interview Question SDE-2s
Country: United States
The above answer with whitespaces preserved(hopefully ;)):
1. Sort {{R1,C1}, {R2, C2}, ..., {Rn, Cn}} on their radius value // notice how each Ci is satellite data for Ri
--> Let's call this sorted array A
2. Initialize T[i] for i from 1 to n
3. For each i from 1 to n
R(k) = D - R(i)
If (R(k) < 0) R(k) = 0 // if R(i) is larger than D itself, min radius of second gear needed is 0
minCostIdx = i
j = ModifiedBinarySearch(A, R(k))
For each m from j to n
FindMinPairCost(minCostIdx, A, m)
T[i] = minCostIdx;
Why do we do binary search internal to the outer "for loop" you ask? The reason is, in the average case, you expect to eliminate 1/2 of the array A based on it (thus bringing down your checks to only n/2). Basically, you can think of it as trading off n/2 checks for log(n) checks.
Additionally, you should add step 2A as follows
2A. If D > Rn return;
This basically avoids doing any computations if D > A[n].getRadius(). We need this step because otherwise, the algorithm will assign each T[i] = i, which is not as per the problem requirements.
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 1000000
struct node {
int r,c,idx;
};
struct node A[MAX_SIZE];
bool compare(struct node A1,struct node A2){
if(A1.r < A2.r) return true;
return false;
}
int n,T[MAX_SIZE]={0};
int modify_BS(int tr){
int start=0,end=n;
int mid = (start+end)/2;
while(start <= end){
if(A[mid].r >= tr && A[mid-1].r < tr ) return mid;
else if(tr > A[mid].r) start = mid+1;
else end = mid-1;
mid = (start+end)/2;
}
return -1;
}
int find_min_cost_idx(int idx){
int ans = idx;
for(int j=idx+1;j<n;j++){
if(A[j].c == A[ans].c){
if(A[j].r == A[ans].r) {
if(A[ans].idx > A[j].idx) ans = j;
}
if(A[j].r > A[ans].r) ans=j;
}
else if(A[j].c < A[ans].c) {
ans = j;
}
}
return ans;
}
int main() {
int D,r,c;
scanf("%d %d",&n,&D);
for(int i=0;i<n;i++){
scanf("%d",&A[i].r);
A[i].idx = i+1;
}
for(int i=0;i<n;i++){
scanf("%d",&A[i].c);
}
sort(A,A+n,compare);
for(int i=0;i<n;i++){
printf("%d %d %d\n",A[i].r,A[i].c,A[i].idx);
}
for(int i=0;i<n;i++){
int tr = D-A[i].r;
if(tr < 0) {T[A[i].idx] = 0; continue; }
printf("tr = %d\n",tr);
int ridx = modify_BS(tr);
printf("ridx = %d\n",ridx);
if(ridx != -1){
int mincostidx = find_min_cost_idx(ridx);
printf("mincostidx = %d\n",mincostidx);
T[A[i].idx] = A[mincostidx].idx;
}
}
for(int i=1;i<=n;i++){
printf("%d ",T[i]);
}
printf("\n");
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 1000000
struct node {
int r,c,idx;
};
struct node A[MAX_SIZE];
bool compare(struct node A1,struct node A2){
if(A1.r < A2.r) return true;
return false;
}
int n,T[MAX_SIZE]={0};
int modify_BS(int tr){
int start=0,end=n;
int mid = (start+end)/2;
while(start <= end){
if(A[mid].r >= tr && A[mid-1].r < tr ) return mid;
else if(tr > A[mid].r) start = mid+1;
else end = mid-1;
mid = (start+end)/2;
}
return -1;
}
int find_min_cost_idx(int idx){
int ans = idx;
for(int j=idx+1;j<n;j++){
if(A[j].c == A[ans].c){
if(A[j].r == A[ans].r) {
if(A[ans].idx > A[j].idx) ans = j;
}
if(A[j].r > A[ans].r) ans=j;
}
else if(A[j].c < A[ans].c) {
ans = j;
}
}
return ans;
}
int main() {
int D,r,c;
scanf("%d %d",&n,&D);
for(int i=0;i<n;i++){
scanf("%d",&A[i].r);
A[i].idx = i+1;
}
for(int i=0;i<n;i++){
scanf("%d",&A[i].c);
}
sort(A,A+n,compare);
for(int i=0;i<n;i++){
printf("%d %d %d\n",A[i].r,A[i].c,A[i].idx);
}
for(int i=0;i<n;i++){
int tr = D-A[i].r;
if(tr < 0) {T[A[i].idx] = 0; continue; }
printf("tr = %d\n",tr);
int ridx = modify_BS(tr);
printf("ridx = %d\n",ridx);
if(ridx != -1){
int mincostidx = find_min_cost_idx(ridx);
printf("mincostidx = %d\n",mincostidx);
T[A[i].idx] = A[mincostidx].idx;
}
}
for(int i=1;i<=n;i++){
printf("%d ",T[i]);
}
printf("\n");
return 0;
}
I had this gear problem in one of my tests.
I have written the working code for this.
Input
5 8
1 3 6 2 5
5 6 8 3 4
Output
0 5 4 3 5
Program:
import java.util.*;
public class GearSelection {
public static void main(String[] args) {
int distance = 8;
int[] radius = { 1, 3, 6, 2, 5 };
int[] cost = { 5, 6, 8, 3, 4 };
int[] ans = Circles(distance, radius, cost);
for (int i = 0; i < ans.length; i++)
System.out.println(ans[i] + " ");
}
static int[] Circles(int distance, int[] radius, int[] cost) {
int[] result = new int[radius.length];
for (int i = 0; i < radius.length; i++) {
List<Integer> tmp = new ArrayList<Integer>();
for (int j = 0; j < radius.length; j++)
if (radius[j] >= distance - radius[i])
tmp.add(j);
result[i] = getSmallest(radius, cost, tmp, i);
}
return result;
}
static int getSmallest(int[] radius, int[] cost, List<Integer> tmp, int i) {
if (tmp.size() == 0)
return 0;
int result = tmp.get(0);
int mincost = cost[i] + cost[tmp.get(0)];
for (int j = 1; j < tmp.size(); j++)
if (cost[i] + cost[tmp.get(j)] < mincost) {
mincost = cost[i] + cost[tmp.get(j)];
result = tmp.get(j);
}
return result + 1;
}
}
It’s a modified form of the interval scheduling problem.
Define class Gear(int radius, int cost, int position)
Sort Gears by radius in decreasing order
Iterate this sorted array
Keep track of Gear with minimal cost thus far
If entry is last entry with specific radius, add to an unordered map with current radius for key, and minimal cost Gear object for value
Iterate through original array of gear radii
Return the position from the Gear matching key == (distance - current gear radius)
O(n log n) time complexity (for sort) and O(n) space complexity.
It’s a modified form of the interval scheduling problem.
Define class Gear(int radius, int cost, int position)
Sort Gears by radius in decreasing order
Iterate this sorted array
Keep track of Gear with minimal cost thus far
If entry is last entry with specific radius, add to unordered map with current radius for key, and minimal cost Gear object for value
Iterate through original array of gear radii
Return the position from the Gear matching key == (distance - current gear radius)
O(n log n) time complexity (for sort) and O(n) space complexity.
This is one of those questions wherein you need to prompt the interviewer for more details. Specifically,
- Killedsteel April 05, 20151. Are {R1, R2, ..., Rn} in increasing order of magnitude?
2. Do both arrays fit into memory? Or do you only have a buffer of size k <= n?
My solution assumes the answers to the above questions as
1. No
2. Yes
In this case, you can basically implement the following algorithm:
1. Sort {{R1,C1}, {R2, C2}, ..., {Rn, Cn}} on their radius value // notice how each Ci is satellite data for Ri
--> Let's call this sorted array A
2. Initialize T[i] for i from 1 to n
3. For each i from 1 to n
R(k) = D - R(i)
If (R(k) < 0) R(k) = 0 // if R(i) is larger than D itself, min radius of second gear needed is 0
minCostIdx = i
j = ModifiedBinarySearch(A, R(k))
For each m from j to n
FindMinPairCost(minCostIdx, A, m)
T[i] = minCostIdx;
Notes:
1. ModifiedBinarySearch(A, R(k)) is basically binary search, but tweaked a little to find the smallest index j in array A that has R(j) >= R(k)
2. FindMinPairCost(minCostIdx, A, m) basically checks whether C(m) < C(minCostIdx). If C(m) = C(minCostIdx), it further compares R(m) to R(minCostIdx). It then keeps the index of the cost with the larger radius (as per problem requirements).
3. ABS is the absolute function in mathematics.
Complexity analysis:
1. Call 1 in the algorithm above takes O(nlog(n)) time.
2. Call 3 is O(n) on the outer "for loop". Within it, each time we do a binary search (i.e. O(log(n)). But in the worst case, we could end up with j going from 1 to n always (e.g. A = {{2, 2}, {3, 2}, {5, 1}} and D = 1). Hence, in the worst case, this is O(n). So, call 3 of the algorithm is O(n^2).
Hence,
Time complexity: O(n^2)
Space complexity: O(1) (assuming we're given space to store array T initially)