Question

Media.net | SDE | Interview Experiences | Set - 1

Answer 1

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<pair<int, int> >,                    greater<pair<int, int> >) 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 }