Entrevista en Twitter | Serie 1

Pantalla del teléfono – yo 

1. Serie de Fibonacci sin usar una array: esta es una pregunta típica favorita de Programación dinámica en la que solicitará no usar Memoización o cualquier almacenamiento adicional para almacenar los valores de las iteraciones anteriores. 
(Versión más complicada del mismo problema: generar la enésima fila del triángulo de pascal sin usar una array 2D de dimensiones N x N) 

2. Árbol N-ario: encuentre si existe un Node en el árbol con valor = x. En caso afirmativo, devuelva verdadero, de lo contrario, devuelva falso. 

Pantalla del teléfono – II  
1. Encuentra el ancestro común más bajo de Binary Tree 
Respuesta: Hecho 10 veces 🙂 ¡Explicado cómo hacerlo! 

2. Clonar un gráfico y analizar la complejidad del tiempo y el espacio (ya que los enfoques basados ​​en DFS aprovechan menos tiempo a costa de más memoria) 
 

public class Node {
   public int data;
   List neighbhors;

   public Node (int data) {…}
   setNeighbors(List neighbhors) {…}
}

// HashMap created = new HashMap();

public Node clone(Node oldGraph) {

  if (created.get(oldGraph))
    return created.get(oldGraph);

  Node newGr = new Node(oldGraph.data);
  List nbors = new ArrayList();

  created.put(oldGraph, newGr);

  List adj = oldGraph.getNeighbhors();
  for (Node n : adj) {
     nbors.add(clone(n));
  }

  newGr.setNeighbors(nbors);
  return newGr;
}

Pantalla del teléfono III 

¡Diseñe un filtro de floración para eliminar los duplicados de una array desordenada! 

En el sitio 

1. (Boggle, como una pregunta) En una array 2D (M x N, en el ejemplo dado 3 × 3) de números, encuentre la ruta estrictamente creciente desde la celda de origen especificada (1,0) hasta la celda de destino especificada (0, 2). La array puede contener duplicados y la solución debería funcionar con los duplicados. 

2.a. Diseñe una función hash única para cada tweet en Twitter que se utilizará como parte de un servicio. 
2.b. Encuentra si un gráfico dirigido tiene ciclos o no. Escriba una función con tipo de retorno booleano para el mismo. 

3. Entrevista de almuerzo informal. 

4. Coincidencia de patrones usando patrones que contienen caracteres (a a z) y ‘*’, ‘?’ y ‘.’ 

5.a. Describa cómo haría una ordenación externa -> llegue a una solución de tipo de reducción de mapa. Cada máquina tiene 10 millones de números (total 100 millones), 10 máquinas en total. Cada m/c tiene 20 MB de RAM y 50 GB de memoria. 
5.b. Problema de N-Queens: encuentre e imprima todas las posibles posiciones no conflictivas para la Reina. 

6.a. Dado un árbol binario de entrada y una referencia a un Node en el árbol, busque el siguiente sucesor en orden para el Node de entrada. Salida nula si no hay ninguna. 
6.b. ¿Cuál es la mejor manera de ordenar una array ordenada por k? Optimizar para la complejidad del tiempo. 
(Mi consejo: use una cola de prioridad de tamaño k) 

7.a. Responsable de contratación: Servicio de diseño para a. Durabilidad B. Consistencia 
7.b. Explique el problema de C++ con las herencias múltiples. 

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.