0 like 0 dislike
881 views
| 881 views

0 like 0 dislike
Pattern
Total Duration of Test – 120 mins
Total No. of Sections - 5
Section 1 – One Coding Question - Easy difficulty (20 mins)
Section 2 – One Coding Question - Medium difficulty (30 mins)
Section 3 – One Coding Question - Medium difficulty (30 mins)
Section 4 - Technical MCQs - 10 questions (20 mins)
Section 5 - Aptitude MCQs - 10 questions (20 mins)

Coding Q 1 - (20 min)

Given a list of number and queries contains k and m. where you have to find the kth smallest integer considering mth least significant bits

l = [1,129,9, 802]

k = [2,1]

m =[2, 1]
output - [802,1]
Explanation -

query 1 - k= 2 ,m=2

2 smallest considering 2least significant digits

[1,29,9,02] here 02 would 2nd smallest

query 2 k =1 m=2

1st smallest considrign 1 least significant digit

[1,9,9,2] here 1 would be 1st smallest

Coding Q2 - (Matrix Problem | dont remember exact q | DP Maximization )

Coding Q3 - Minimum number of train platforms

position of engine of a train (start) and position of last car of a train (end) are given find how many platform are needed to fit train with out overlap/ crash | start and end are start position and end of train

Sample 1

enginePos =[1,2]

lastCarPos=[2,3]
o/p 2

Reason trains are 1,2 , 2,3 (as given) | will crash(overlap) hence need 2 platform

Sample 2

enginePos =[1,2]

lastCarPos=[3,4]
o/p 1 Reason no crash 1,2 | 3,4 no overlap

Sample 3

enginePos =[1, 5 ,5, 8 ,8]

lastCarPos=[4, 5, 8, 9, 9]
o/p- 3 |Reason at pos 8 there are 3 trains at i a time so 3 platforms needed;

anyone know efficant answer to Q1
by Expert (111,350 points)
0 like 0 dislike

3rd sort both arrarys according to last coach position, the make a min priority queue and insert the first element of array(train with least position of last coach), if starting position of next train is less top of priority queue the we need new platform else update priority queue.

Very difficult to explain but still I will try to give you some points
1)
Only column matters therefore make an array which contains only systems and therefore res[i] will contain all system having column i.
2)
How efficiently can you calculate pairwise distance between all 2 columns.
Hint ->
suppose we have columns 1 and 2
Column 1 will contain these 2,3,4 (row no) this denote there is a system at v[2][1],v[3][1]......
Column 2 will contain 1,5,7,8
Now to calculate distance between column 1 and column 2
Pair wise b/w column 1 and 2 i.e 2-1,2-5,2-7,2-8,3-1,3-5,3-7,3-8,4-1,4-5,4-7,4-8
int temp= abs(col[j]*cnt[i]- col[i]cnt[j]) + abs(jcnt[j]cnt[i] - icnt[i]*cnt[j]); here the first term is for |c1-c2| and other is for |r1-r2|
elements In column 1 i.e distance between 2-3 ,2-4,3-4 sum[1][0] stores this distance
elements In column 2 i.e 2-5,2-7,2-8,5-7,5-8 sum[2][0] stores this distance
3)
Suppose we have columns 1,2,3,4 and k=2
then we have to calculate distance between
1-2,1-3,2-3 and between elements in the same column
or 2-3,2-4,3-4 and between elements in the same column

Sum[i][j] will store sum of distance of elements in column i from elements in (column i to column i+j)
2nd problem

```void solve(){
vector<string>v{".&.",".&.","&.&"};
int n=v.size();
int m=v[0].size();
int k=3;
vector<int>col(m+1,0);
vector<int>cnt(m+1,0);
vector<vector<int>>res(m+1);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(v[i][j]=='&'){
col[j+1]+=i+1; //it stores the sum of row value of all the system at column j
res[j+1].push_back(i+1);
cnt[j+1]++;   //count
}
}
}

int sum[m+1][m+1];  //sum[i][j] tells the pair wise sum when we are considering all elements in column[i] and all elements between column i and column i+j
memset(sum,0,sizeof(sum));

for(int i=1;i<=m;i++){
int x=cnt[i];
int t=0;
for(int j=0;j<res[i].size();j++){
t+=res[i][j];
sum[i][0]+=abs((col[i]-t)-(x-1)*res[i][j]);
x--;
}
}

for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
int d=j-i;
int temp= abs(col[j]*cnt[i]- col[i]*cnt[j]) + abs(j*cnt[j]*cnt[i] - i*cnt[i]*cnt[j]);
sum[i][d]=temp+sum[i][d-1];
}
}
```

//suppose we are calculating all columns at dist p1 from column i then for the next column we need to calculate at distance p1-1
int mx=0;
for(int i=1;i<=m;i++){
int ans=0;
int p1=k;

for(int j=i;j<=m;j++){
int u=m-j;     //if max distance from column i is less than p1
ans+= sum[j][min(u,p1)];
p1--;
if(p1<0)break;
}
mx=max(mx,ans);
}

cout<<mx;

}

1st, just sort v[d] , d = 1 to 15, and answer the query like v[d][k].
2nd can't solve. (Any idea how to solve in N^2 ? ).
3rd sort both engine and rear positions, the trick was if engine[i] > rear[i] , swap(engine[i] , rear[i]) . Now the problem reduces to meeting rooms 2. Sort both
initiliaze i = 0 , j = 0, if engine[i] <= rear[i] ++cnt , ++i, else --cnt , ++j. Ans = max(ans, cnt) , return ans.

by Expert (111,350 points)