Опыт раунда кодирования Expedia - стажер 2021 г.

Опубликовано: 21 Августа, 2021

Проблемы кодирования для Expedia Inten 2021: было 2 вопроса кодирования и 6 MCQ для раунда кодирования Intern Round Expedia 2021.

Вопрос 1. Несколько способов разделить объекты на группы, чтобы ни в одной группе не было меньше объектов, чем в ранее сформированных группах?

Пример:

 объектов = 8, групп = 4 Ответ: 5
[1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2]
Вход:
8 4 
Выход:
5

Решение:

Простой подход: Эту проблему можно решить с помощью рекурсии.

C ++

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

Временная сложность: O ( ^группы объектов)

Динамический подход: вышеупомянутый подход потерпит неудачу по мере превышения временной сложности, поэтому мы применим динамическое программирование.

C ++

 // 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)
 {
    // Intialize 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;
 }

Вопрос 2: Минимальное количество различных элементов после удаления m элементов

Учитывая массив элементов, а i-й элемент индекса обозначает идентификаторы элемента и задано число m, задача состоит в том, чтобы удалить m элементов таким образом, чтобы оставалось минимальное количество различных идентификаторов. Выведите количество различных идентификаторов.

Примеры:

 Ввод: arr [] = {2, 2, 1, 3, 3, 3}
           м = 3
Выход: 1

 Удалите 1 и обе двойки, так что только 3 будут
left, поэтому отдельный идентификатор равен 1.
Ввод: arr [] = {2, 4, 1, 5, 3, 5, 1, 3}
           м = 2
Выход: 3
Полностью удалите 2 и 4. Итак, оставшиеся идентификаторы
равны 1, 3 и 5, т.е. 3

C ++

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

Сложность времени: O (n log n)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию . Если вы готовы, проверьте свои навыки с помощью серий тестов TCS, Wipro, Amazon и Microsoft.

Собеседования

Опыт раунда кодирования Expedia - стажер 2021 г.

C ++

C ++

C ++

РЕКОМЕНДУЕМЫЕ СТАТЬИ