Ronda 1:
Preguntas sobre trabajos anteriores, patrones de diseño utilizados en el trabajo anterior.
Dados dos enteros representados en formato de lista enlazada y ahora agregue estas dos listas y colóquelas en la tercera lista, en cualquier momento, un Node puede tener solo un dígito.
Con las discusiones, surgió al considerar los arrastres y todo similar a algunos de los dos números enteros representados en forma de lista enlazada. Se le pidió a la entrevista que dijera primero el enfoque y luego la codificación.
// Approach 1 // 1 2 3 // 12 8 9 // 14 1 2
Versión 1:
Java
private static void Add(Node head1, Node head2)
{
int res = 0;
if (head1 != null)
{
count++;
Add(head1.Next, head2.Next);
count--;
res = head1.Data + head2.Data + carryFwd;
carryFwd = res / 10;
Node newNumNode =null;
newNumNode = new Node() { Data = res % 10 };
if (head3 == null)
{
head3 = newNumNode;
}
else
{
newNumNode.Next = head3;
head3 = newNumNode;
}
// happy with this logic where the list will go in
// reverse direction something like Insert at the head
// position every time a new node occurs to be created
}
Versión 2: me pidió que tomara un ejemplo y probara que la solución es correcta
Uno de mis casos de prueba falló si los últimos dígitos también dan el traspaso
Java
static int[] aa = new int[3];
static int carryFwd = 0;
static Node head3 = null;
static int count;
private static void Add(Node head1, Node head2)
{
int res = 0;
if (head1 != null)
{
count++;
Add(head1.Next, head2.Next);
count--;
res = head1.Data + head2.Data + carryFwd;
carryFwd = res / 10;
Node newNumNode =null;
if (count == 0)
{
newNumNode = new Node() { Data = res };
}
else
{
newNumNode = new Node() { Data = res % 10 };
}
if (head3 == null)
{
head3 = newNumNode;
}
else
{
newNumNode.Next = head3;
head3 = newNumNode;
}
}
}
}
Versión 3:
Esto guardará la suma de los últimos dígitos en un solo Node. Esto no es lo que esperaba cuando la suma es de dos dígitos, así que corrija el código.
Java
private static void Add(Node head1, Node head2)
{
int res = 0;
if (head1 != null)
{
count++;
Add(head1.Next, head2.Next);
count--;
res = head1.Data + head2.Data + carryFwd;
carryFwd = res / 10;
Node newNumNode =null;
newNumNode = new Node() { Data = res % 10 };
if (head3 == null)
{
head3 = newNumNode;
}
else
{
newNumNode.Next = head3;
head3 = newNumNode;
}
if(carryFwd ==1)
{
newNumNode = new Node() { Data = carrFwd};
newNumNode.Next = head3;
head3 = newNumNode;
}
}
Versión 4:
¿Puedes optimizar más aquí…? ¿Cuál es el máximo cuando sumas dos dígitos…? ¿Cuáles son los valores posibles para el arrastre…? Preguntas consecutivas
Entonces, en la versión final mía, se eliminó la variable de conteo y se movió la última condición de arrastre fuera de la función. Creó más diversión aquí que por qué está cavando tan profundo.
Java
public class Node
{
public int Data { get; set; }
public Node Next { get; set; }
}
}
Ahora escriba los casos de prueba para este problema.
Alrededor de 15 casos de prueba significa entradas de prueba. Había escrito mirando mi solución.
La pregunta aquí es si escribe los casos de prueba para su solución o para el problema, considere que este no es su código, se le ha dado un problema y escribe los casos de prueba.
Luego agregué algunos de los casos de prueba ignorando mi suposición de la misma longitud de la lista.
Cuando se me pidió que escribiera algo más, estaba feliz cuando escribí una prueba con un tamaño de lista vinculada de 10000000, ya que mi solución es recursiva, es posible que obtenga la excepción de desbordamiento de pila.
Con esta respuesta me golpeó con muchas preguntas.
Entrevistador: Entonces, ¿por qué elige la recursividad? Necesito un enfoque alternativo. No estoy contento con una alternativa.
// Approach 2
/*
* Reverse list 1:
* Reverse list 2:
* Add the lists with remainder and dividends
* Reverse list 3:
*/
// Approach 3
/*
* make the linked list to array and use the indices to
traverse and do the addition
* No program is asked for it
*/
// Approach 4
/*
* mConvert the entire linked list to an integer and then
add both the integers and then prepare a linked list
with the result
* but the issue if the result is out of integer boundary
*/
Cuando le dije al enfoque 4, me preguntó al
entrevistador: «¿Estás pensando por qué este tipo está guardando números enteros en una lista vinculada y luego me pide que agregue esas listas…?»
Yo: Sí
Entrevistador: entonces respóndete a ti mismo qué es lo que hace que haga esto, intercambiemos los roles
Yo: dije algunos escenarios como
1. Quiero tener números enteros basados en índices y crecer dinámicamente (para que las arrays no sean amigables)
2. Si Quiero tener un contador cuyo valor sea mayor que el rango de enteros, entonces puedo ir con esta u otra estructura de datos.
Entrevistador: Ahora volvamos a la pregunta y luego arreglemos el código ignorando la suposición de la misma longitud de las listas.
Yo:los enfoques anteriores 3 y 4 pueden resolver
Entrevistador: ¿pero estos son enfoques alternativos para resolver cualquier forma de arreglar la misma solución en lugar de ir con la alternativa?
Yo: Puede ser que rellene la lista más pequeña con los ceros y luego use mi algoritmo adicional inicialmente, pero funciona.
Entrevistador: Ok, de vuelta a su solución Recursión, ¿por qué saltó y comenzó con la recursión cuando tiene tantas alternativas…?
Yo: Por lo general, pienso en la recursividad cuando alguien hace una pregunta en una lista enlazada que a veces se resuelve fácilmente ya que es unidireccional.
Entrevistador: ¿Puede explicar más cómo la recursividad facilitará la lógica del desarrollador
? Yo:Utiliza un árbol interno a través del cual puedo realizar operaciones en dirección inversa en una lista enlazada.
Vijj: ¿Qué árbol mantiene?
Yo: El nombre es RecursionTree, pero en realidad no es un árbol .
Entrevistador: Entonces, ¿qué es eso?
Yo: alguna estructura de datos.
Entrevistador
: por supuesto, ¿cuál es esa estructura de datos? fácilmente. Es por eso que uno de mis casos de prueba verifica la excepción de desbordamiento de pila, ya que usé la recursividad cuando tengo una gran cantidad de datos.
Entrevistador: ¿Qué es LIFO?
Yo: explicado sobre el LIFO y comparado con el FIFO.
Entrevistador: ¿Alguna pregunta para mí…?
Yo: Si no es confidencial y obvio, dígame cuál es la lógica central o los algoritmos utilizados en Bing, ya que mi gerente dijo que esto es para el equipo de Bing.
Entrevistador: está bien, si desea escribir un algoritmo para una búsqueda, ¿cuál es su enfoque
? Yo : Yo Iré con algunas búsquedas basadas en heurística, como la búsqueda Best-First tipo de algoritmo A * o solución de problema TSP (vendedor itinerante).
Entrevistador: si ese es el caso, cualquiera puede escribir un motor de búsqueda 🙂 también usamos algunas heurísticas, pero nunca seremos como A * algo directo
. una vez que hablamos con otro tipo.
Ronda 2: dura 1:30 min
Entrevistador:Comenzará directamente con la pregunta sin perder tiempo.
Dado un arreglo de +ves y -ves, encuentre un subarreglo cuyo máximo sea máximo entre todos los subarreglos de cualquier longitud en el arreglo dado.
Dile el enfoque primero y luego escribe el código.
Yo: después de un tiempo, le dije al enfoque con una complejidad O (n), luego me pidió que escribiera el código.
C
int len = sizeof(arr)/sizeof(arr[0]);
int currMax = a[0], finalMax = arr[0];
for (int i=1;i<=len;i++) {
currMax += a[i]; i
if(currMax > finalMax)
finalMax = currMax;
if(currMax<0)
currMax =0;
}
Entrevistador: Tome algunos números y demuestre que su solución es correcta.
Yo: Se muestra con el ejemplo. Necesito recorrer toda la lista hasta obtener la respuesta.
Entrevistador: ¿Falla en algún escenario?
Yo: no nunca
Entrevistador: Fallará si todos los números en la array son -ves
Yo: pero inicialmente la pregunta era que la array es una mezcla de +ve y -ve
Entrevistador: Ok, entonces déjame cambiar la pregunta y considerar que tiene todos -ves, ¿su código falla si es así, dónde?
Yo: sí, lo hará con la condición de currMax
Entrevistador: entonces arréglalo
Yo: tomó mucho tiempo arreglarlo y luego me pidió que probara que era correcto
No pude probar mi solución porque perdí en algún lugar mientras rastreaba con la lista grande, pero la solución era correcta, entonces
Entrevistador: me pidió que cambiara la inicialización y arreglara esa es la pista
Yo: no pude arreglar como yo me apegué a mi solución, pero di un enfoque alternativo, como
multiplicaré todos los números -ve con -1 y haré que la lista esté llena de +ves y luego encontraré el mínimo de la array secundaria en lugar del máximo una vez que lo consiga. haga que sea un número -ve antes de regresar o imprimir
Entrevistador: muy interesado en cuál es el valor de retorno de la función que escribí; y te dijo que ibas a la solución alternativa en lugar de arreglar la solución existente
Entrevistador: ok, pasemos a otra pregunta dado un árbol para encontrar el antepasado
Yo:es decir padre, abuelo o bisabuelo
Entrevistador: ¿te importa? ¿Y cuál es su enfoque para, digamos, abuelo?
Yo: Dije que tal vez iré con la pila y, según su opción, miraré el Node de la pila.
Entrevistador: Ok, iremos a otra pregunta en lugar de esta.
Entrevistador: dibujaré un árbol en un papel y te lo daré, tómate tu tiempo y recuerda el árbol en una estructura de datos y una vez que digas que sí, borraré o recuperaré mi papel y consideraré que la estructura de datos está ingresada. a su algoritmo y ellos construyen mi árbol de vuelta
Yo:No pude entender el problema. Hizo demasiadas preguntas sobre lo que realmente quiere. Construiré el árbol usando su árbol y luego llamaré a la misma función para recrear.
Entrevistador: ¿cómo crea cuál es su entrada? ¿Cuál es la estructura de datos? eso
Yo: Dije Node, bla, bla … hice demasiadas preguntas, entonces entiendo lo que quiere.
Así que mi enfoque fue que representaré su árbol en dos arrays, una estará en orden y la otra será pre/post aquí iré con Pre y una vez que tengo estas dos arrays, puedo seguir con el algoritmo de construcción dando estas entradas.
Entrevistador: dime el enfoque, ¿cómo construyes si estas dos arrays
? Yo:Le dije que combinando estos dos cómo podemos ir y construir como para que podamos obtener el elemento raíz y encontrar esa raíz en la segunda array y luego dividir la array que es igual a la izquierda y derecha del árbol para la raíz y continuar; esto necesito hacerlo manualmente para que el árbol dado pruebe mi solución; e hizo un par de preguntas después de dividir dónde irán los subconjuntos y cómo recordar lo que queda a la derecha; Manualmente, expliqué todo esto con el ejemplo y dije que no sé qué condición debo verificar cuando escribo esto como un programa.
Entrevistador: contento con el enfoque y pregunté qué órdenes In/Pre/Post por qué elegiste solo a estos dos
Yo. : Necesito Inorder y puedes decirme cuál quieres que tome ya sea antes o después
Entrevistador: depende de usted, su algoritmo, su estructura de datos y escribir el programa
Yo: No pude poner mi lógica en el código ya que no pude probar las condiciones adecuadas de manera normal y recursiva, pero no pude hacer un código concreto en absoluto.
Entrevistador: se nos está acabando el tiempo, así que me detendré aquí.
Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA