Experiencia de entrevista de Bharti SoftBank (caminata) | conjunto 2

Ronda 1 (prueba escrita)
Duración: 90 minutos

Sección 1 (preguntas de objetivos técnicos)
: 25 mcq se centran principalmente en c, c ++, os, estructuras de datos, algoritmos

Sección 2 (2 preguntas de codificación)
: se suponía que el código estaba escrito en papel

Pregunta 1: dada una string de palabras, devuelve todas las palabras que tienen su reverso presente en la string como ((palabra1, palabra inversa1), (palabra2, palabra inversa2))

eg .
Input -   
Sachin tendulkar is the best   tseb    eth  nihcaS  

Output  - 
{ ( best ,   tseb )  , ( the  ,  eth) , (Sachin  ,  nihcaS) }  

Pregunta 2: Encontrar el número más pequeño formado usando el mismo número de dígitos.
Imprima -1 si no es posible.

eg 
input  -  371 
output  -  317

input  -  456   
output  -  -1 

Ronda 2 (Entrevista)
La primera ronda de entrevistas se basó en estructuras de datos básicos

1. El entrevistador me pidió que escribiera código para el segundo elemento máximo de una array . Luego se discutió el tercer y k-ésimo elemento más grande de la array.

2. Conceptos relacionados con el árbol binario de búsqueda, usos y complejidad comparativa.

3. Preguntó sobre Hashing, Colisiones, Implementación para hashing.

Ronda 3 (Entrevista)
Pregunta 1: Se le pidió que escribiera el código para el recorrido de orden de nivel en el árbol binario. La pregunta se modificó aún más para hacer un recorrido de orden en espiral. Se suponía que ambos debían hacerse en una complejidad de tiempo O (n).

Luego me preguntó un rompecabezas

http://www.programmerinterview.com/index.php/puzzles/3-ants-on-a-triangle-riddle/

Entonces hubo una pequeña discusión sobre mis proyectos.

Luego comenzó a hacer preguntas sobre el sistema operativo
: exclusión mutua y semáforos.
– Escribir código para el problema del consumidor del productor usando semáforos.
Después de que escribí un pseudo código, el problema se hizo más complejo al agregar más restricciones.

El entrevistador quería probar mi comprensión acerca de los semáforos y me hizo algunas preguntas engañosas y confusas.

Ronda 4 (Entrevista)

Pregunta 1: escriba código para obtener el máximo y el segundo elemento máximo de una pila. La función dada debe tener una complejidad O(1).

Di una solución usando 2 pilas adicionales

Luego lo hizo más interesante al extender la pregunta a Encontrar el número k-ésimo más grande de la pila en cualquier instancia en el tiempo O(1). Stack admite las funciones push, pop, peek y kthmaximum.
Fue muy particular sobre la restricción O(1).
Le di muchas soluciones, pero él quería que llegara a una solución O(1).
Finalmente, le di una solución que usaba un montón adicional y un árbol de búsqueda binaria y podía obtener una complejidad de tiempo O(1).

Pregunta 2: dada una array biotónica (los primeros números aumentan y luego disminuyen), escriba el código para buscar un número dado . Complejidad de tiempo O(logn)

La pregunta se modificó aún más para escribir código para 4 casos para buscar:
1 array podría ordenarse de forma ascendente
2 array podría ordenarse de forma descendente
3 la array podría aumentar primero y luego disminuir
4 la array podría disminuir primero y luego aumentar

La idea era detectar primero de qué caso se trataba y luego buscar en consecuencia
Complejidad de tiempo O (logn)

La pregunta se modificó aún más para manejar duplicados. En caso de duplicados, mi algoritmo se convirtió en O(n)

Ronda 5 (Entrevista Telefónica)
Esta ronda fue una entrevista telefónica con el CTO de la empresa.

Primero me preguntó sobre la indexación de bases de datos. Qué ? ¿Por qué utilizar la indexación? ¿Cómo se implementa?
Le di una explicación completa
Esta es una muy buena explicación
http://www.programmerinterview.com/index.php/database-sql/what-is-an-index/

Comenzó con una pequeña discusión sobre mis proyectos y trabajos de investigación.

Luego pasó a las estructuras de datos y me preguntó cómo elegir una estructura de datos relevante para un problema dado.
– Le di las ventajas de cada estructura de datos y ciertos problemas donde estructuras de datos específicas podrían ser útiles.

Luego hizo una pregunta y me preguntó qué estructura de datos debería usarse teniendo en cuenta la complejidad del tiempo.

Pregunta: Dada una lista de estudiantes y sus calificaciones, escriba una función que imprima a todos los estudiantes con calificaciones en un rango dado l , r

eg  .     
           Akshay   30
           Atul     25  
           Angay    20
           Sahil    10
Then if  input is  l = 12 and r = 26  
Output  -  Angay, Atul 

Di una solución indexando marcas con una lista de enlaces de estudiantes creando una array de listas de enlaces

Luego modificó las preguntas agregando marcas en puntos flotantes que también se permitieron.

Le di una solución usando el mapa (c++) basado en un par de marcas de valor clave y una lista de estudiantes

Pero me pidió optimizar la complejidad del tiempo
. Entonces le di una modificación a mi primera solución y agregué el concepto de cubos y búsqueda binaria.

Me hizo algunas preguntas de hora al final.

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.