La entrevista se programó después de que superé el desafío de codificación.
El desafío de la codificación fue bastante simple, era una cuadrícula, con cada celda conectada a sus vecinas con algún costo, se le permite moverse hacia la derecha y hacia abajo, y debe calcular el costo total mínimo para algunos empleados (definido en la cuadrícula ) para llegar a la esquina inferior.
El tamaño de la cuadrícula era un máximo de 1000*1000, por lo que un simple Dijkstra podría resolverlo.
La entrevista comenzó unos 20 minutos tarde debido a problemas técnicos con la conexión de Skype, por lo que el entrevistador se sumergió rápidamente en la pregunta técnica.
Así que la pregunta técnica era la siguiente:
Queremos crear LRU Cache, una estructura de datos que almacena pares
Un elemento se considera usado cuando se inserta por primera vez en la memoria caché y si se recuperó su valor.
El entrevistador escribió el cuerpo de la clase y mi tarea fue implementarlo.
La primera idea que tuve fue usar una lista doblemente enlazada, donde cualquier proceso de inserción en el caché significa que insertamos un nuevo elemento como el encabezado de la lista enlazada y, por supuesto, el elemento usado menos recientemente está al final de la lista. .
El tiempo de ejecución del peor caso de inserción fue O(1), pero el método de recuperación se ejecutó en O(n).
Luego me pidieron que encontrara una mejor manera de mejorar el tiempo de ejecución del método get, y sugerí que usáramos una tabla hash para almacenar los pares.
Sugerí que podemos usar un montón para recuperar fácilmente el elemento usado menos recientemente, pero el entrevistador me pidió que combinara la idea de la tabla hash con la idea de la lista enlazada para lograr una mejor implementación.
Entonces, la idea que tuve fue crear una tabla hash para usar en el método get y una lista vinculada para almacenar la precedencia de cada clave.
Entonces, para cada clave, tenemos 2 entradas, 1 entrada en la tabla hash y otra en la lista enlazada, así que creé otra tabla hash, que dada la clave, devuelve el Node de esa clave en la lista enlazada.
Empecé a escribir el código y seguí actualizándolo cada vez que encontramos un error.
Mi código final fue el siguiente:
// This is the text editor interface.
// Anything you type or change here will be seen by the other
// person in real time.
/*
* Cache of at most maxCapacity objects, referenced by identifiers of
* type <K>. When the cache needs to free up space, it drops the
* least-recently-used object.
*/
class LruCache<K, T> {
class ListNode
{
public K key;
public ListNode next, prev;
public ListNode()
{
next = prev = null;
}
public ListNode (K key)
{
this.key = key;
}
public ListNode (ListNode next, ListNode prev)
{
this.next = next;
this.prev = prev;
}
public setNext (ListNode next)
public getNext
public setPrev (ListNode prev)
public getPrev
}
public class LinkedList
{
public ListNode head, tail;
public int size;
public LinkedList ()
{
head = tail = null;
size = 0;
}
public LinkedList (ListNode node)
{
this.head = this.tail = node;
}
public void removeNode (ListNode node)
{
if (node != list.getHead())
{
ListNode prev = node.prev;
ListNode next = node.next;
if (prev != null)
prev.setNext(next);
if (next != null)
next.setPrev(prev);
else
list.setTail (prev);
}
else
{
if (head == tail)
head = tail = null;
else
head = head.next;
}
}
public void setHead (ListNode node)
{
if (head != null)
head.setPrev = node;
node.next = head;
node.prev = null;
head = node;
}
public ListNode getHead
public void setTail (ListNode node)
{
if (tail != null)
{
node.prev = tail;
tail.next = node;
}
tail = node;
node.next = null;
}
public ListNode getTail
}
/*
--------------------- (K1, T1) <- 1 (1, K1) (LRU)
--------------------- (K2, T2) <- 2 (2, K2)
(K3, T3) <- 3 (3, K3) (MRU)
*/
private final int maxCapacity;
private HashTable <K, T> valueTable;
private HashTable <K, ListNode> nodeTable;
private LinkedList list;
/*
* Returns object with identifier <key>, stored in the cache.
* This object then becomes most-recently-used.
*/
public T get(K key) {
// fill in
if (!valueTable.contains(key))
return null;
ListNode node = nodeTable.get(key);
list.removeNode(node);
list.setHead(node);
return valueTable.get(key);
}
/*
* Puts <object> in the cache. At the time it's put in
* it is the most-recently-used.
*/
public void put(K key, T object) {
// fill in
ListNode newNode = new ListNode (key);
list.setHead = newNode;
list.size++;
valueTable.add(key, object);
nodeTable.add(key, newNode);
if (list.size > maxCapacity)
{
ListNode tail = list.getTail();
valueTable.remove (tail.getKey());
nodeTable.remove (tail.getKey());
list.removeNode (tail);
list.size--;
}
}
}
Después de que terminamos la pregunta técnica, el entrevistador pasó a discutir los proyectos en mi currículum y preguntó qué proyecto fue el más agradable y por qué.
Mi respuesta fue para el proyecto Ocean Simulation, porque entre todos los proyectos que hice en la universidad, ese fue el que más usé algoritmos y traté de hacer que el software fuera lo más inteligente posible.
1 cosa es que le pregunté al entrevistador sobre la vida de los pasantes en Palantir, su respuesta fue «¿Está solicitando una pasantía?»
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.
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