Palantir Technologies访谈|第一组-yiteyi-C++库

面试是在我通过编码挑战后安排的。

null

编码的挑战有点简单，它是一个网格，每个单元以一定的成本连接到它的邻居，你可以左右移动，你需要计算一些员工（定义在网格上）到达底部的最低总成本。网格大小最大为1000*1000，因此一个简单的Dijkstra就可以解决这个问题。

由于Skype连接存在技术问题，面试推迟了大约20分钟，因此面试官迅速切入技术问题。

因此，技术问题如下：

我们想要创建LRU缓存，一种存储数据对的数据结构，并具有最大容量，在此之后，任何插入过程都应删除最近使用最少的元素。当元素第一次插入缓存时，以及如果检索到其值，则认为该元素已被使用。

面试官写下了课程的主体，我的任务是实施它。我的第一个想法是使用双链表，在这个链表中，任何对缓存的插入过程都意味着我们插入一个新元素作为链表的开头，当然最近使用最少的元素位于链表的末尾。

插入最坏情况下的运行时间是O（1），但检索方法是在O（n）中运行。

然后，我被要求找到一种更好的方法来提高get方法的运行时间，我建议我们使用一个哈希表来存储这些对，但我们仍然需要另一种方法来存储每个元素的使用顺序。

我建议我们可以使用堆，轻松检索最近使用最少的元素，但面试官让我将哈希表的想法与链表的想法结合起来，以获得更好的实现。所以，我的想法是创建一个用于get方法的哈希表和一个链表来存储每个键的优先级。对于每个键，我们有两个条目，一个在哈希表中，另一个在链表中，所以我创建了另一个哈希表，给定键，它返回链表中该键的节点。

我开始编写代码，并在发现bug时不断更新。

我的最终代码如下：

                             // 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--;                           
                                                         }                           
                                                         }                           
                             }                           

在我们完成了技术问题后，面试官接着讨论了我简历上的项目，并问哪个项目最令人愉快，为什么。我的答案是海洋模拟项目，因为在我大学里做过的所有项目中，这是我使用算法最多的一个，并试图使软件尽可能智能化。

第一件事是，我问面试官关于实习生在帕兰蒂尔的生活，他的回答是“你正在申请实习吗？”

如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章