Este fue un reclutamiento del campus, por lo que el nivel y la dificultad pueden variar según su universidad.
Ronda 1: Ronda de codificación en Hackerearth
Unas 20 preguntas MCQ sobre aptitud y salida de código C/Java y 2 preguntas de codificación. Pude aprobar todos los casos de prueba para la primera pregunta, mientras que solo 2/3 casos de prueba para la segunda pregunta. Fui 1 de las 3 personas seleccionadas de esta ronda. No recuerdo la pregunta a partir de ahora.
Ronda 2: Ronda técnica 1
Comenzamos discutiendo mis proyectos en el currículum y me pidió que elaborara uno de mis proyectos Node.js, que era un sitio de blogs compatible con Node.js + mongoose en el backend. Me preguntaron por qué usé mangosta y no alguna base de datos relacional, porque estaba aprendiendo en ese momento y el instructor estaba usando mangosta, así que hice lo mismo. Luego me hizo una pregunta basada en SQL
Pregunta: Dada una tabla, extraiga sus columnas impares .
Lo intenté, pero como no respondí, acepté que no sé la respuesta
. Luego continuamos con una pregunta de programación
. Pregunta 1: Dadas dos listas vinculadas, ¿cómo puede fusionarlas en una lista ordenada ordenada?
Mi solución:
primero fusioné las dos listas enlazadas uniendo el último Node de la primera lista enlazada con el
primer Node de la segunda lista enlazada y clasificándolos usando la ordenación de burbujas
Me pidió que mejorara la complejidad de la solución.
Le pregunté si hay algún límite en la memoria, dijo que no. Así que nuevamente me uní a ellos y
usé la ordenación por conteo en la lista fusionada
Ahora dijo asumir que hay un límite en la memoria.
Le dije que sé que la ordenación por combinación será útil para ordenarlas primero y luego combinarlas, pero
realmente no sé cómo se aplica la ordenación por combinación en las listas vinculadas, lo sé solo para arrays y listas.
Preguntó la complejidad del tiempo de la ordenación por fusión y asumir que es una lista ordenada ahora fusionarlos.
Utilicé dos punteros que apuntaban al inicio de las listas y fusioné sus elementos uno por uno
moviendo el puntero uno por uno en el Node inferior hasta que no se agregaron todos los Nodes a la nueva lista.
Aquí está el código
def merge(list1, list2): """ list1, list2 are the two sorted lists Function returns the merged list """" ptr1 = 0 ptr2 = 0 finalList = [] # While any pointer reaches the end of the list while ptr1 < len(list1) and ptr2 < len(list2): # If list2 has the smaller element add it and increase the pointer to the next position if list1[ptr1]>list2[ptr2]: finalList.appennd(list2[ptr2]) ptr2 += 1 # Otherwise add element form list1 and increase the pointer to the next position else: finalList.append(list1[ptr1]) ptr1 += 1 # Adding the elements left in list1 or list2 if ptr1 == len(list1): while ptr2 <l en(list2): finalList.append(list2[ptr2]) ptr2 += 1 else: while ptr1 < len(list1): finalList.append(list1[ptr1]) ptr1 += 1 # finalList contains the merged list return finalList
I was asked the time complexity of the program, I replied
(Donde n y m son las longitudes de las listas). Me corrigió y me dijo que es
Ronda 3: Ronda técnica 2
Comenzó con una introducción básica y una pregunta sobre la estructura de datos.
Question: You have
logs y puedes unir dos de ellos a la vez con un costo
igual a la suma de sus longitudes. Tienes que unir todos los registros a un solo registro con un costo mínimo
Mi solución:
Me tomé un tiempo para pensar en la solución, pensé que si sigo uniendo los dos más pequeños
debería dar el costo mínimo, así que pedí un ejemplo para entender mejor el problema.
Example: 5 logs of size 2 3 4 5 7. Answer: 47 Solution: 2+3 = 5, logs = 4, 5, 5, 7 cost = 5 4+5 = 8, logs = 5, 7, 9 cost = 5+9 5+7 = 9, logs = 9, 12 cost = 5+9+12 9+12 = 21, logs = 21 cost = 5+9+12+21 = 47 I could have sorted the list but after each join, I will have to insert a new log into the list that can take
para cada registro, por lo tanto, hacer la solución
.
Así que usé minheap para calcular los registros mínimos cada vez. El Node superior ya es el mínimo
y después de eliminarlo, el mínimo 2ed llega a la raíz.
El tiempo de inserción en un montón es
que es mucho mejor que
.
Aquí está el código:
import heapq def cost(n, logs): """ n is the number of logs logs is the list containing length of logs Returns the minimum cost of joining all the logs """ # Createing a min-heap using length of logs heap = [] for i in range(n): heap.heappush(logs[i]) cost = 0 # Loop until one log is left while len(heap)>1: # Log with minimum value log1 = heap[0] # Removing the minimum / root value heap.heappop() # Similarly second minimum log will be the minimum after the previous removal log2 = heap[0] heap.heappop() # Length of new log which is equal to the cost of operation newlog = log1 + log2 cost += newlog # Inserting the new log back in the heap heap.heapush(newlog) # Cost stores the total cost for this operation return cost
I was asked the total time complexity of this operation which is
Ronda 4: Ronda Técnica 3
El entrevistado comenzó preguntándome sobre mis proyectos y luego preguntó por qué
. Entrevistado: ¿Por qué quieres hacer una pasantía en SDE
? Yo: Me encanta resolver problemas desde que comencé a programar competitivamente y me encanta hacer desarrollo, por lo tanto, creo que el desarrollo de software es lo correcto. posición para mí.
Entrevistado: ¿Cuál es su estructura de datos favorita y
yo?: Tree y luego mencioné mi proyecto sobre la generación de finalización de pruebas usando Trie Data Structure y discutimos cómo podemos manejar grandes datos cuando hay muchos datos con Trie. Sugerí recortar el árbol ya que la mayoría de los Nodes en el lado de la hoja serán punteros NULL, lo que ayudará a ahorrar mucho espacio en la memoria.
Esta fue una entrevista bastante corta que duró entre 30 y 40 minutos.
Al final, fui una de las 2 personas seleccionadas como pasante de SDE en Fourkites
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