¿Cuál es la mejor estructura de datos de C++ que podría usarse para almacenar y administrar una colección de enteros?

collections integer

Question

esta es mi primera pregunta de StackOverflow, así que avíseme si no seguí las pautas de la comunidad con esta pregunta y si debo eliminarla.

Obtuve mi primera pregunta de la entrevista y me rechazaron debido a mi implementación.

La pregunta es:

Diseñe e implemente una clase de C ++ que almacene una colección de enteros. En construcción, la colección debe estar vacía. El mismo número se puede almacenar más de una vez.

Implementar los siguientes métodos:

1. Insertar (int x). Inserte una entrada para el valor "x".

2. Borrar (int x). Elimine una entrada con el valor “x” (si existe) de la colección.

3. Borrar (int desde, int hasta). Elimine todas las entradas con un valor en el rango [desde, hasta).

4. Cuenta (int desde, int hasta). Cuente cuántas entradas tienen un valor en el rango [desde, hasta).

Pensé que una buena implementación sería utilizar listas vinculadas, ya que usa memoria no contigua y eliminar entradas no requeriría barajar muchos datos (como en vectores o matrices). Sin embargo, recibí comentarios de la compañía que decían que mi implementación tenía una complejidad de tiempo O (n ^ 2) y era muy ineficiente, por lo que me rechazaron. No quiero repetir el mismo error si aparece una pregunta similar en otra entrevista, así que me gustaría saber cuál es la mejor manera de abordar esta pregunta (un amigo sugirió usar mapas, pero tampoco está seguro).

Mi código es:

void IntegerCollector::insert(int x)
{
    entries.push_back(x);
}

void IntegerCollector::erase(int x)
{
    list<int>::iterator position = find(entries.begin(), entries.end(), x);
    if (position != entries.end())
        entries.erase(position);
}

void IntegerCollector::erase(int from, int to)
{
    list<int>::iterator position = entries.begin();

    while (position != entries.end())
    {
        if (*position >= from && *position <= to)
            position = entries.erase(position);
        else
            position++;
    }
}

int IntegerCollector::count(int from, int to)
{
    list<int>::iterator position = entries.begin();
    int count = 0;

    while (position != entries.end())
    {
        if (*position >= from && *position <= to)
            count++;

        position++;
    }

    return count;
}

Los comentarios mencionaron que solo contratarían candidatos que puedan implementar soluciones con complejidad O (nlogn).

Answer 1

Debe usar map<int,size_t> el int es para el valor, el size_t es para el recuento.

Si necesita implementar el código, debe elegir un árbol binario equilibrado para llegar a la complejidad ''log N''.

para que tengas el siguiente nodo:

struct Node
{
  int key;
  size_t count;
  Node *left, *right; 
  size_t leftNodesCount, rightNodesCount;
};

leftNodesCount y rightNodesCount se indican para indicar qué tan bueno es el saldo, por lo que cualquier inserción y eliminación lo está cambiando hasta la raíz. un árbol equilibrado es cuando todo el árbol leftNodesCount y rightNodesCount son casi iguales (la diferencia de medias no es más de 1. pero puede establecer la tolerancia en un valor superior como 2 o 3)

Ahora debería implementar los métodos Insert , Delete y Balance .

Para equilibrar un árbol equilibrado, debe rotar los nodos desbalanceados. Girar a la izquierda significa reemplazar el nodo por el derecho del nodo, y agregar el nodo a la izquierda, Girar a la derecha es la misma operación en la otra dirección.

La complicidad del balance también es ''log N''. tenga en cuenta que después de las inserciones y las eliminaciones, debe llamar al equilibrio para mantener la complicidad del árbol algo sobre ''log N''

Answer 2

La consideración clave aquí es que los enteros del mismo valor son indistinguibles. Por lo tanto, todo lo que necesita hacer es almacenar un conteo de cada valor distinto en el contenedor .

Luego, solo puede usar std::map<int, size_t> como estructura de respaldo que asigna cada entero (clave) al número de veces que existe en su estructura de datos (value = count).

Insertar y borrar elementos individuales es solo incrementar y disminuir (posiblemente eliminando en este último caso) los valores de la clave dada (ambos O(log(distinct_values_in_container)) para encontrar la clave).

Como std::map está ordenado, puede usar lower_bound y upper_bound para realizar búsquedas binarias, por lo que encontrar las claves en [from, to) es muy eficiente (encontrar el rango también es O(log(distinct_values_in_container)) ). Borrarlos o sumar sus cuentas es fácil entonces (el tiempo de ejecución es más complicado aquí).

Si desea obtener crédito adicional, pagará para comprender las limitaciones de los tiempos de ejecución asintóticos. Considere estos puntos:

Lo que significan estos tiempos de ejecución asintóticos en la práctica depende mucho del patrón de uso. Si nunca se insertan duplicados, estamos en O(n) , pero también puede obtener buenos tiempos arbitrarios (en términos de n = número de inserciones) si hay muchos elementos idénticos (por ejemplo, si cada tecla tiene O(exp(n)) valores de O(exp(n)) entonces O(distinct_values_in_container) = O(log(n)) ). En el caso extremo de que todos los enteros involucrados sean iguales, todas las operaciones son O(1) .

Como entrevistado, también hablaría sobre si estos tiempos de ejecución asintóticos son significativos en la práctica. Puede ser que la estructura de árbol del mapa (que es tóxica para el caché y el predictor de rama) se pierda en un simple std::vector<std::pair<int, size_t>> (si el borrado está siempre en forma) o incluso un std::vector<size_t> (si las claves son "densas") para la aplicación dada.

Creo que su error principal (y por qué fue rechazado) no es darse cuenta de que no es necesario almacenar cada entero insertado por separado. Desafortunadamente, también parece haber perdido la posibilidad de mantener la lista ordenada, pero no veo de dónde proviene la O(n^2) .

Answer 3

Si te contrataran para un puesto que no requería experiencia previa en programación, no te habría rechazado solo en ese ejemplo de código.

Usar una std::list fue una opción interesante y demostró que había pensado en esto. El hecho de que haya utilizado un contenedor de biblioteca estándar de C ++ en lugar de intentar construirlo desde un nivel inferior es un indicador de contratación sí para mí. Con su aproximación (1) es rápido, pero (2), (3) y (4) serán lentos. En ausencia de cualquier otra información, debe organizar las cosas para que la lectura (incluida la consulta) de los datos sea más rápida que la escritura. Su enfoque tiene esto al revés. A veces, aunque eso es lo que desea, por ejemplo, al tomar mediciones en tiempo real, desearía que la etapa de volcado de datos fuera lo más rápida posible a expensas de cualquier otra cosa. ¡Para esa aplicación su solución sería difícil de superar!

Reservas, pero de ninguna manera líneas rojas:

Un entero no significa un int . En ausencia de ser capaz de aclarar, construya su clase en

template<typename Y> std::map<Y, std::size_t>

donde Y es un tipo integral. Tenga en cuenta el uso de std::size_t para el contador. Cuenta el número de veces que una Y particular está presente.

Incluir algunos comentarios del programa la próxima vez.

No utilice el using namespace std; . Aunque los tutoriales lo hacen por claridad, los programadores profesionales no lo hacen.