## Myntra Interview Question for SDE-2s

Country: United States

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

This is one of those questions wherein you need to prompt the interviewer for more details. Specifically,
1. 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)

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

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.

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

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

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

The above implementation has bug that you have to print index of the input array...but above implementation will provide index from the sorted array... refer my solution given below.

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

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

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

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

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

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

for (int i = 0; i < radius.length; i++) {
List<Integer> tmp = new ArrayList<Integer>();

for (int j = 0; j < radius.length; 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;
}``````

}

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

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.

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

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.

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.