Experiencia de entrevista de Media.Net para SDE (en el campus)

La campaña del campus de Media.net tuvo lugar en diciembre de 2020.

Ronda 1 (prueba de codificación de 90 min): había 3 preguntas.

1. Genere un árbol dados los recorridos en orden y en orden.
2. manipulación de array
3. DP + máscara de bits

4 estudiantes fueron preseleccionados para entrevistas.

Ronda 2 (Entrevista Ronda 1):

Pregunta : dadas dos strings A y B de igual longitud con caracteres del conjunto {1,2}. Una string S es una buena string si mueve exactamente S[i] pasos hacia adelante o hacia atrás en la i-ésima posición y termina en la última posición de modo que cubrió todas las posiciones exactamente una vez. Dadas dos buenas strings A y B, debe indicar el número de intercambios posibles entre las posiciones correspondientes en las strings de modo que las strings sigan siendo buenas.

Explicación y respuesta : 

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

Sólo 1 fue seleccionado para la 2ª entrevista.

Ronda 3 (Entrevista Ronda 2):

Pregunta: Tiene un archivo de 100 GB (números) en su disco. Debe ordenar el archivo, pero su sistema solo tiene 4 GB de RAM.

Parámetros disponibles

• Tamaño del archivo: 100 GB,
• Tamaño de RAM: 4 GB,
• Tamaño de página: 4 MB
• Leer, escribir: leer y escribir desde el disco (con tamaño de página a la vez). Ordenar: disponible para ordenar números en RAM

Responder:

// 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
}

Finalmente, recibí la oferta de “Media.net” .

Gracias, Geeksforgeeks.