0 like 0 dislike
1,492 views
| 1,492 views

## 1 Answer

0 like 0 dislike

Media.net campus drive took place in December 2020.

Round 1(90 min Coding Test): 3 questions were there.

1. Generate a tree given postorder and inorder traversals.
2. Array manipulation
3. DP + bitmasking

4 students were shortlisted for interviews.

Round 2 (Interview Round 1):

Question: Given two strings A and B of equal length with characters from the set {1,2}. A string S is a good string if you move exactly S[i] steps forward or backward at i’th position and ended at the last position such that you covered all positions exactly once. Given two good strings A and B, you have to tell the number of possible swapping between the corresponding positions in the strings such that the strings remain good.

Explanation and Answer

```A, B = length
{1, 2}

good strings:
1. covered all positions EXACTLY ONCE
2. ended at the last position

Example:
A = 2211
B = 1111

swap: {1, 2, 3}
A[1] B[1]
A[2] B[2]
A[3] B[3]

A' = 1111
B' = 2211

correct swapping.

How manny correct swappings
8
{}, {1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}, {3}, {4}, {3, 4}

Answer:

bool validate(int num, char value, int& newNum) {
if(value == '1') {
newNum = 0;
return (num != 1);
}
if(value == '2'){
if(num == 1){
newNum = 2;
return true;
}
else if(num == 0){
newNum = 1;
return true;
}
else{
return false;
}
}
}

string A,B;
int n = A.size();
int dp[n][3][3];//initialised to 0
int solve(int s, int j, int k){

char a = A[s];
char b = B[s];

int nextj,nextk;

if(validate(j,a,nextj) && validate(k,b,nextk)){
dp[s][nextj][nextk] += dp[s-1][j][k];
}

if(validate(j,b,nextj) && validate(k,a,nextk)){
dp[s][nextj][nextk] += dp[s-1][j][k];
}

}

int main(){
//inputs

for(int i=0;i<n;i++){
for(int j=0;j<=2;j++){
for(int k=0;k<=2;k++){
solve(i,j,k);
}
}
}

cout<<dp[n-2][0][0]*2;
}```

Only 1 was selected for 2nd interview.

Round 3 (Interview Round 2):

Question: You have a 100 GB file (numbers) on your disk. You need to sort the file, but your system has only 4 GB RAM.

Available Parameters

• File Size – 100 GB,
• RAM Size – 4 GB,
• Page Size – 4 MB
• Read, Write – read and write from the disk (with page size at a time). Sort – available for sorting numbers in RAM

Answer:

• C

 `// FileSize = 100(in GB), ramSize = 4(in GB), pageSize =` `// 4(in MB)` `Void merge(``int` `fileSize, ``int` `ramSize, ``int` `pageSize)` `{` `    ``Int chunks = fileSize / ramSize;` `    ``Int chunksize = fileSize / chunks;` `    ``for` `(``int` `i = 0; i < chunks; i++) {` `        ``Int curr = i * ramSize * 1024;` `        ``while` `(curr <= 4 * 1024) {` `            ``Read(curr);` `            ``Curr += pageSize;` `        ``}` `        ``Sort();` `        ``curr = i * ramSize * 1024;` `        ``Int pos = 0;` `        ``while` `(pos < ramSize * 1024) {` `            ``Write(pos, curr);` `            ``Curr += pageSize;` `        ``}` `    ``}` ` `  `    ``// now merge sorted chunks` `    ``Int cur = 0;` `    ``int``* ptr = ``new` `int``[chunks];` `    ``for` `(``int` `i = 0; i < chunks; i++)` `        ``Ptr[i] = 0;` ` `  `    ``priority_queue(pair<``int``, ``int``>, vector >,` `                   ``greater >) pq;` ` `  `    ``for` `(``int` `i = 0; i < chunks; i++) {` `        ``Read(ptr[i]);` `        ``Ptr[i] += pageSize;` `        ``For(every element k in page)` `        ``{` `            ``pq.push_back(make_pair(k, i));` `        ``}` `    ``}` ` `  `    ``int``* curr = ``new` `int``[chunks];` `    ``for` `(``int` `i = 0; i < chunks; i++)` `        ``curr[i] = 0;` ` `  `    ``Int k = 0;` `    ``// Output buffer` `    ``while` `(!pq.isEmpty()) {` `        ``pair<``int``, ``int``> p = pq.top();` `        ``pq.pop();` `        ``Int idx = p.second Output[k++]` `            ``= p.first curr[idx]++;` `        ``Int limit = pageSize / ``sizeof``(``int``);` `        ``if` `(curr[idx] == limit) {` `            ``Curr[idx] = 0;` `            ``if` `(ptr[i] != chunkSize) {` `                ``Read(ptr[i]);` `                ``Ptr[i] += pageSize;` `                ``For(every element k in page)` `                ``{` `                    ``pq.push_back(make_pair(k, idx));` `                ``}` `                ``Write(output to disk)` `            ``}` `        ``}` `    ``}` `    ``// Pop top element and store in output space` `    ``// If a page is emptied then bring next page` `    ``// from that chunk` `    ``// If ram is about to be filled then store the` `    ``// sorted file back to disk` `}`
by Expert (113,040 points)