Experiencia de la ronda de codificación de Expedia – Pasante 2021

Problemas de codificación para Expedia Inten 2021: Hubo 2 preguntas de codificación y 6 MCQ para la ronda de codificación de la Ronda Interna de Expedia 2021.

Pregunta 1: ¿Hay varias formas de dividir objetos en grupos, de modo que ningún grupo tenga menos objetos que los grupos formados previamente?

Ejemplo: 

objects=8, groups=4 Answer: 5
[1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2]
Input:
8 4 
Output:
5

Solución: 

Enfoque sencillo:Este problema se puede resolver utilizando la recursividad.

// C++ program to count the
// number of ways to divide objetcs in
// groups.
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to count the number
// of ways to divide the number objects
// in groups.
int count(int pos, int prev, int objects, int groups)
{
 
    if (pos == groups) {
        if (objects == 0)
            return 1;
        else
            return 0;
    }
 
    // if objects is divides completely
    // into less than groups
    if (objects == 0)
        return 0;
 
    int solution = 0;
 
    // put all possible values
    // greater equal to prev
    for (int i = prev; i <= objects; i++) {
        solution += count(pos + 1, i, objects - i, groups);
    }
    return solution;
}
 
// Function to count the number of
// ways to divide into objects
int WaysToGo(int objects, int groups)
{
    return count(0, 1, objects, groups);
}
 
// Main Code
int main()
{
    int objects, groups;
    objects = 8;
    groups = 4;
    cout << WaysToGo(objects, groups);
    return 0;
}

Complejidad del tiempo: O ( ^{Grupos de} objetos )

Enfoque dinámico: el enfoque anterior fallará ya que la complejidad del tiempo excederá, por lo que aplicaremos la programación dinámica.

// C++ implementation to count the
// number of ways to divide objects in
// groups.
 
#include <bits/stdc++.h>
 
using namespace std;
// DP 3DArray
int dp[500][500][500];
 
// Function to count the number
// of ways to divide the objects
// in groups.
int count(int pos, int prev, int objects, int groups)
{
    // Base Case
    if (pos == groups) {
        if (left == 0)
            return 1;
        else
            return 0;
    }
    // if objects is divides completely
    // into groups
    if (objects == 0)
        return 0;
 
    // If the subproblem has been
    // solved, use the value
    if (dp[pos][prev][objects] != -1)
        return dp[pos][prev][objects];
 
    int solution = 0;
    // put all possible values
    // greater equal to prev
    for (int i = prev; i <= objects; i++) {
        solution += count(pos + 1, i, objects - i, groups);
    }
 
    return dp[pos][prev][objects] = solution;
}
 
// Function to count the number of
// ways to divide into groups
int WaystoDivide(int objects, int groups)
{
    // Initialize DP Table as -1
    memset(dp, -1, sizeof(dp));
 
    return count(0, 1, objects, groups);
}
 
// Main Code
int main()
{
    int objects, groups;
    objects = 8;
    groups = 4;
    cout << WaystoDivide(objects, groups);
    return 0;
}

Pregunta 2: Número mínimo de elementos distintos después de eliminar m elementos

Dada una array de elementos, y el i-ésimo elemento de índice denota la identificación del elemento y dado un número m, la tarea es eliminar m elementos de modo que quede un mínimo de identificación distinta. Imprime el número de identificaciones distintas.

Ejemplos:

Input : arr[] = { 2, 2, 1, 3, 3, 3}
           m = 3
Output : 1

Remove 1 and both 2's.So, only 3 will be
left that's why distinct id is 1.
Input : arr[] = { 2, 4, 1, 5, 3, 5, 1, 3}
           m = 2
Output : 3
Remove 2 and 4 completely. So, remaining ids
are 1, 3 and 5 i.e. 3

#include <bits/stdc++.h>
using namespace std;
 
// Function to find distintc id's
int distIds(int a[], int n, int m)
{
    unordered_map<int, int> mi;
    vector<pair<int, int> > v;
    int count = 0;
 
    // Store the occurrence of ids
    for (int i = 0; i < n; i++)
        mi[a[i]]++;
 
    // Store into the vector second as first and vice-versa
    for (auto it = mi.begin(); it != mi.end(); it++)
        v.push_back(make_pair(it->second, it->first));
 
    // Sort the vector
    sort(v.begin(), v.end());
 
    int size = v.size();
 
    // Start removing elements from the beginning
    for (int i = 0; i < size; i++) {
 
        // Remove if current value is less than
        // or equal to m
        if (v[i].first <= m) {
            m -= v[i].first;
            count++;
        }
 
        // Return the remaining size
        else
            return size - count;
    }
    return size - count;
}
 
// Main code
int main()
{
    int arr[] = { 2, 3, 1, 2, 3, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int m = 3;
 
    cout << distIds(arr, n, m);
    return 0;
}

Complejidad de tiempo: O(n log n)