Palantir Technologies Interview Questions and Answers

Interview preparation tips for other job seekers - Utilize the best optimal solution when coding with Palantir technical interviews.

Round: Technical Interview
Experience: The interview was scheduled after I passed the coding challenge.The interview started about 20 minutes late due to technical problems with Skype connection, so the interviewer dived in quickly to the technical question.We want to create LRU Cache, a data structure that stores pairs , and has maximum capacity, after which, any insertion process should remove the least recently used element.An element is considered used when it’s first inserted to the cache, and if its value was retrieved.The interviewer wrote the body of the class, and my task was to implement it.
The first idea I got was to use a doubly-linked list, where any insertion process to the cache means we insert a new element as the head of the linked list, and of course the least recently used element is at the tail of the list.The insertion worst case run-time was O(1), but the retrieval method was to run in O(n).I was then asked to find a better way to improve the running time of the get method, and I suggested we use a hashtable to store the pairs , but then we would still need another way to store the order of usage of every element.I suggested we can use a heap, to easily retrieve the least recently used element, but the interviewer asked me to combine the idea of the hash table with the idea of the linked list to get a better implementation.
So, the idea I got was to create both a hash table to be used in the get method, and a linked list to store the precedence of each key.
So, for each key, we have 2 entries, 1 entry in the hash table, and another one in the linked list, so I created another hash table, that given the key, it returns the node of that key in the linked list.I started writing the code and kept updating it whenever we find a bug.My final code was as follows:// 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 .  When the cache needs to free up space, it drops the  *  least-recently-used object. */class LruCache {         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 valueTable;    private HashTable nodeTable;    private LinkedList list;    /*     * Returns object with identifier , 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