Entrevista de IDC de Microsoft | Conjunto 35 (en el campus para prácticas)

Prueba en línea: esta prueba fue organizada por cocubes.com y tenía que completarse en una hora.

Había dos preguntas de codificación:

1. Existe una lista enlazada cuyo Node se define de la siguiente manera

    struct node
    {
        int x,y;
        node* next;
    };

Tuvimos que implementar una función que tomara el encabezado de la lista enlazada, y si tres puntos consecutivos se encontraban en la misma línea horizontal o vertical, teníamos que eliminar el Node central. La lista enlazada estará vacía o contendrá al menos dos Nodes. El prototipo de la función fue:

    void remove(node* head)
    {

    }

Ejemplo:

Input: (1,2)->(2,3)->(2,4),(2,5)->(3,4)
Output: (1->2)->(2,3)->(2,5)->(3,4)

2. Dada una array ordenada, conviértala en un árbol de búsqueda binario equilibrado en altura. Un árbol de altura equilibrada es aquel en el que para cada Node, la diferencia de altura del subárbol izquierdo y derecho es como máximo 1. El Node del árbol binario era:

    struct node
    {
        int data;
        node* left;
        node* right;
    };

La función a implementar era:

    node* binary_tree(int* ar, int len)
    {

    }

Entrevista:
hubo 3 rondas de entrevistas y tuvimos que escribir el código en papel.

Ronda 1:
Había dos preguntas:
1. Dada una string, elimine todas las ocurrencias continuas de ‘a’ y cualquier ocurrencia de ‘b’.
Ejemplo: Entrada: “aacbccdbsssaba”, luego salida: “acccdsssa”

2. ¿Qué estructura de datos se debe utilizar si tenemos que implementar funciones de inserción y eliminación en un editor de texto? Las funciones deben ser lo más rápidas posible.

Ronda 2:
Pregunta 1: dada una string y dos posiciones en esa string, baraje la string, es decir, mueva la substring dada al frente. Ejemplo:
Entrada: abcdefgh, 4,6
Salida: defabcgh
Esto debe hacerse en el lugar con una complejidad de tiempo O(n).

Pregunta 2: ¿Cómo implementar la estructura de datos del diccionario en C++? ¿Qué tipo de funciones hash usaremos? ¿Cómo gestionar las colisiones?

Pregunta 3: ¿Cómo implementaría la estructura de datos vectoriales en C++ por su cuenta? ¿Cuál sería la complejidad del tiempo de acceso? ¿Cómo puedes hacer que sea O(1)? ¿Cómo cambiar el tamaño de la estructura?

Ronda 3:
Pregunta 1: dado un árbol k-ario, ¿cómo imprimir los elementos por capas?

Pregunta 2: Dada una lista enlazada individualmente y un número ‘n’, escriba código para invertir todos los elementos ‘n’ de la lista enlazada. Ejemplo:
Entrada: 1->2->3->4->5->6, n=3
Salida: 3->2->1->6->5->4

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.