interview - data structures and algorithms pdf

insertar, eliminar, max en O(1)

Question

¿Puede alguien decirme qué estructura de datos admite la operación de inserción / eliminación / máxima en O (1)?

Answer 1

Aunque la answer @Can Berk Güder es correcta. Pero si tenemos restricciones de espacio, podemos hacerlo mucho mejor, incluso si los elementos no son distintos. Para obtener más detalles, consulte mi respuesta Here con implementación en Java .

Answer 2

Como algunos ya han señalado, la pregunta carece de información. No especifica si insertar / eliminar, ni la naturaleza de los datos con los que estamos tratando.

Algunas ideas que podrían ser útiles: dices,

insertar / eliminar / operación máxima en O (1)

tenga en cuenta que si podemos insertar, eliminar y encontrar maximun en O (1), entonces podemos usar esta técnica hipotética para ordenar en O (n), porque podemos insertar los n elementos, y luego tomar max / delete y obtenemos todos ordenados Está demostrado que ningún algoritmo de clasificación basado en comparaciones puede ordenar menos que O (nlogn), por lo que sabemos que ningún enfoque basado en la comparación funcionará. De hecho, una de las maneras más rápidas de hacerlo es la cola Brodal, pero su tiempo de eliminación excede O (1).

Tal vez la solución es algo así como un árbol raíz, donde la complejidad de todas estas operaciones está relacionada con la longitud de la clave como opuesta a la cantidad de claves. Esto solo es válido si le permiten vincular la longitud de la clave con algún otro número, por lo que puede considerarlo constante.

Pero tal vez no era algo tan genérico. Otra interpretación, es que la inserción / eliminación son las de una pila clásica. En ese caso restringido, puede usar la answer doble pila que answer le dio.

Answer 3

Debajo del programa se hace un seguimiento de los elementos máximos en la pila de tal manera que cualquier punto del tiempo el puntero superior nos daría el máximo en la pila: Entonces, el máximo sería O (1), y podemos encontrar máximo por máximo [N]

ITEM   MAX

+---+  +---+
| 1 |  | 1 |
| 10|  | 10|
| 9 |  | 10|
| 19|  | 19| <--top
+---+  +---+

Programa Java:

public class StackWithMax {

private int[] item;
private int N = 0;
private int[] max;

public StackWithMax(int capacity){
    item = new int[capacity];//generic array creation not allowed
    max = new int[capacity];
}

public void push(int item){
    this.item[N++] = item;
    if(max[N-1] > item) {
        max[N] = max[N-1];
    } else {
        max[N] = item;
    }
}

public void pop() {
    this.item[N] = 0;
    this.max[N] = 0;
    N--;
}

public int findMax(){
    return this.max[N];
}
public static void main(String[] args) {
    StackWithMax max = new StackWithMax(10);
    max.push(1);
    max.push(10);
    max.push(9);
    max.push(19);
    System.out.println(max.findMax());
    max.pop();
    System.out.println(max.findMax());


}

}

Answer 4

El comentario de @KennyTM señala un detalle importante que falta: inserte dónde y elimine desde dónde. Así que voy a suponer que siempre quiere insertar y eliminar solo desde un extremo como una pila.

La inserción (push) y Delete (pop) son O (1).

Para obtener Max en O (1), use una pila adicional para registrar el máximo actual que corresponde a la pila principal.

Answer 5

Esta es una pregunta de entrevista clásica, y generalmente se presenta así:

Diseñe una estructura de datos similar a una pila que realice operaciones push, pop y min (o max) en O (1) tiempo. No hay restricciones de espacio

La respuesta es que utilizas dos pilas: la pila principal y una pila mínima (o máxima).

Entonces, por ejemplo, después de presionar 1,2,3,4,5 en la pila, tus stacks se verían así:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

Sin embargo, si presionara 5,4,3,2,1, las pilas se verían así:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

Para 5,2,4,3,1, tendrías:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

y así.

También puede ahorrar algo de espacio presionando a la pila mínima solo cuando cambie el elemento mínimo, si se sabe que los elementos son distintos.

Answer 6

La siguiente solución usa O (1) memoria extra y O (1) tiempo para operaciones max, push y pop. Mantenga un máximo variable que hará un seguimiento del elemento máximo actual en un momento determinado. Vamos a utilizar el hecho de que cuando max se actualiza, todos los elementos en la pila deben ser menores que el nuevo elemento max. Cuando se produce una operación de inserción y el nuevo elemento (newElement) es mayor que el máximo actual, empujamos el max + newElement en la pila y actualizamos max = newElement.

Cuando estamos haciendo una operación pop y encontramos que el elemento popup actual es mayor que el máximo actual, entonces sabemos que este es el lugar donde hemos actualizado nuestra pila para mantener max + elem. Entonces, el elemento real que debe devolverse es max y max = poppedElem - max.

Por ej. si estamos presionando 1, 2, 3, 4, 5, la pila y la variable máxima se verán a continuación:

MAIN       Value of MAX
+---+      +---+
| 9 |      max = | 5 |
| 7 |      max = | 4 |
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Ahora digamos que sacamos un elemento, básicamente haremos pop, elemento max (desde arriba> max) y actualizaremos el elemento max (top-max)

MAIN       Value of MAX
+---+      +---+
| 7 |      max = | 4 | = (9-5)
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Ahora digamos que estamos presionando los números 5, 4, 3, 2, 1, la pila se verá así:

MAIN       Value of MAX
+---+      +---+
| 1 |      max = | 5 |
| 2 |      max = | 5 |
| 3 |      max = | 5 |
| 4 |      max = | 5 |
| 5 |      max = | 5 |
+---+      +---+

Cuando hacemos pop, la parte superior de la pila aparece desde arriba <max, y max permanece sin cambios.

A continuación se muestra un pseudo código para cada una de las operaciones para una mejor comprensión.

Elem max;
void Push(Elem x){
    if x < max :
        push(x);
    else{
        push(x+max);
        max = x;
    }
}
Elem Pop(){
    Elem p = pop();
    if |p| < |max|:
        return p;
    else{
        max = p - max;
        return max;
    }
}
Elem Max(){
    return max;
}

push y pop son operaciones de pila normales. Espero que esto ayude.

Answer 7

Si está utilizando solo comparaciones, sería difícil encontrar una estructura de datos de este tipo.

Por ejemplo, podría insertar n elementos, obtener max, eliminar max, etc. y podría ordenar números en O (n) tiempo, mientras que el límite inferior teórico es Omega (nlogn).

Answer 8

Una tabla hash podría admitir inserción / eliminación en O (1), sin embargo, no hay ninguna pista sobre el máximo. Probablemente necesites seguirlo de alguna manera.