Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
Use a HashMap and a Doubly Linked List, where Hashmap would have a pointer to the list Node such as Map<Key, ListNode> and List would have ListNode(Value, Left, Right)
and the head of the list would be the most recent element added or read.
HEAD -> * Most recently added or read
TAIL -> * Least recently read or added, "oldest" element
For set(Key, value) check if key exists in HashMap, if so get ListNode and set new value make it HEAD, set left and right pointers accordingly. If not create new ListNode, set it as new HEAD and make HEAD -> right point to old HEAD.
For get(Key) check if key exists in HashMap, if so get ListNode and make it HEAD, set left and right pointers accordingly. Return value. If it does not exits return null or throw exception.
For delete(Key) check if key exists in HashMap, if so get ListNode and set left and right pointers accordingly eliminate this node and remove it from hashmap . Return value. If it does not exits return null or throw exception.
For last() check if list is empty, if not return HEAD, If empty return null.
The trickiest part of this question is constant time operation for last() method. I would expect the interviewer to ask for constant-time time complexity to find the last accessed element.
The idea is similar to LFU (Least frequently used) cache, where we keep track of when the element was accessed, but here instead of keep track of how many times the element was accessed, we keep track of what was the last time the element was accessed.
We can implement this using the following data structure
1. values map - HashMap<Integer, Integer> --> this keeps track of actual keys and values
2. whenAccessed map - HashMap<Integer, Long> --> This keeps track of the element and when was it access in System.nanoTime()
3. lastAccessed map - TreeMap<Long, Integer> --> this keeps track of time against the element. This data structure is used for responding to last() method call.
Time Complexity:
put(key, value) --> O(logN) --> internally TreeMap put is used
get(key) --> O(1)
delete(key) --> O(1)
last() --> O(1)
Here is the code
public class DictionaryWithLast {
Map<Integer, Integer> values = new HashMap<>();
Map<Integer, Long> whenAccessed = new HashMap<>();
TreeMap<Long, Integer> lastAccessed = new TreeMap<>();
public static void main(String args[]) {
DictionaryWithLast cache = new DictionaryWithLast();
cache.set(1, 1);
System.out.println("cache.get(2) = " + cache.get(2));
System.out.println("cache.get(1) = " + cache.get(1));
cache.set(2, 2);
cache.set(3, 3);
System.out.println("cache.get(1) = " + cache.get(1));
System.out.println("cache.last() = " + cache.last());
cache.delete(2);
System.out.println("cache.last() = " + cache.last());
cache.delete(1);
System.out.println("cache.last() = " + cache.last());
}
public void set(int key, int value) {
values.put(key, value);
long currentTime = System.nanoTime();
Long lastValue = whenAccessed.put(key, currentTime);
if(lastValue != null) {
lastAccessed.remove(lastValue);
}
lastAccessed.put(currentTime, key);
}
public int get(int key){
if(! values.containsKey(key)) {
return -1;
} else {
long time = whenAccessed.get(key);
lastAccessed.remove(time);
long currentTime = System.nanoTime();
lastAccessed.put(currentTime, key);
whenAccessed.put(key, currentTime);
}
return values.get(key);
}
public void delete(int key) {
Integer previous = values.remove(key);
if(previous != null) {
Long time = whenAccessed.get(key);
whenAccessed.remove(key);
lastAccessed.remove(time);
}
}
public int last(){
Map.Entry<Long, Integer> entry = lastAccessed.lastEntry();
return entry.getValue();
}
}
Output:
=======
cache.get(2) = -1
cache.get(1) = 1
cache.get(1) = 1
cache.last() = 1
cache.last() = 1
cache.last() = 3
Here it is a python version that is O(1) for all operations.
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DictWithLast:
def __init__(self):
self._map = {}
self._tail = None
def set(self, key, value):
node = Node(value)
if self._tail is None:
self._tail = node
else:
node.prev = self._tail
self._tail.next = node
self._tail = node
self._map[key] = node
def get(self, key):
return self._map[key].value
def last(self):
assert self._tail is not None
return self._tail.value
def delete(self, key):
node = self._map[key]
if len(self._map) == 1:
self._tail = None
elif node.next is None:
node.prev.next = None
self._tail = node.prev
else:
node.prev.next = node.next
node.next.prev = node.prev
del self._map[key]
dlast = DictWithLast()
dlast.set(1, 'A')
dlast.set(2, 'B')
dlast.set(3, 'C')
print(dlast.get(3)) # print "C"
print(dlast.last()) # print "C"
dlast.delete(2)
print(dlast.last()) # print "C"
dlast.delete(3)
print(dlast.last()) # print "A"
dlast.delete(1)
print(dlast.last()) # Assert error!
Python solution in O(1) for all the operations.
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DictWithLast:
def __init__(self):
self._map = {}
self._tail = None
def set(self, key, value):
node = Node(value)
if self._tail is None:
self._tail = node
else:
node.prev = self._tail
self._tail.next = node
self._tail = node
self._map[key] = node
def get(self, key):
return self._map[key].value
def last(self):
assert self._tail is not None
return self._tail.value
def delete(self, key):
node = self._map[key]
if len(self._map) == 1:
self._tail = None
elif node.next is None:
node.prev.next = None
self._tail = node.prev
else:
node.prev.next = node.next
node.next.prev = node.prev
del self._map[key]
dlast = DictWithLast()
dlast.set(1, 'A')
dlast.set(2, 'B')
dlast.set(3, 'C')
print(dlast.get(3)) # print "C"
print(dlast.last()) # print "C"
dlast.delete(2)
print(dlast.last()) # print "C"
dlast.delete(3)
print(dlast.last()) # print "A"
dlast.delete(1)
print(dlast.last()) # Assert error!
public class DictionaryWithLast<K, V> {
private final List<KVP<K, V>> list = new LinkedList<>();
public void set(K key, V value) {
list.add(new KVP.create(key, value));
}
public V get(K key) {
KVP<K, V> result = null;
for (KVP<K, V> kvp : list) {
if (equals(kvp.key, key)) {
result = kvp.value;
break;
}
}
if (result != null) {
// make last after read
delete(result.key);
set(result.key, result.value);
}
return result;
}
public void delete(K key) {
int index = -1;
Iterator<KVP<K, V>> iterator = list.iterator();
while (iterator.hasNext()) {
KVP<K, V> kvp = iterator.next();
if (equals(kvp.key, key)) {
iterator.remove();
return;
}
}
}
public K last() {
return list.isEmpty() ? null : list.get(list.size() - 1).key;
}
private static boolean equals(Object one, Object other) {
// in case we are not allowed to use Objects.equals, we can write our own
return Objects.equals(one, other);
}
private static class KVP<K, V> {
final K key;
final V value;
KVP(K k, V v) {
key = k;
value = v;
}
<K, V> static KVP<K, V> create(K k, V v) {
return new KVP<>(k, v);
}
}
}
public class DictionaryWithLast
{
private class KeyValue
{
public string Key;
public string Value;
public KeyValue(string key, string value)
{
if (string.IsNullOrEmpty(key))
{
throw new ArgumentNullException(nameof(key));
}
if (string.IsNullOrEmpty(value))
{
throw new ArgumentNullException(nameof(value));
}
this.Key = key;
this.Value = value;
}
}
private List<KeyValue> dictionary;
private KeyValue keyLast;
public DictionaryWithLast()
{
dictionary = new List<KeyValue>();
}
public void Set(string key, string value)
{
var element = new KeyValue(key, value);
if (!dictionary.Contains(element))
{
dictionary.Add(element);
keyLast = element;
Console.WriteLine($"{key} has been added to the dictionary.");
}
else
{
Console.WriteLine($"The dictionary already has this key {key}.");
}
}
public string Get(string key)
{
var element = dictionary.FirstOrDefault(x => x.Key == key);
if (element != null)
{
keyLast = element;
return element.Value;
}
return null;
}
public void Delete(string key)
{
var element = dictionary.FirstOrDefault(x => x.Key == key);
if (element != null)
{
dictionary.Remove(element);
Console.WriteLine($"{key} has been deleted from the dictionary.");
if (keyLast == element)
{
var size = dictionary.Count;
keyLast = size > 0 ? dictionary[size - 1] : null;
}
}
}
public string Last()
{
return keyLast?.Value;
}
import java.util.*;
class Dictionary{
HashMap<Integer,Node> table = new HashMap<Integer,Node>();
Node head;
public void set(int key,int value){
if(head==null){
head = new Node(value);
table.put(key,head);
}
else{
head.left = new Node(value);
head.left.right = head;
head = head.left;
table.put(key, head);
}
}
public int get(int key){
if(table.containsKey(key)){
Node n = table.get(key);
//System.out.print(n.left.data);
n.left.right = n.right;
n.right.left = n.left;
n.right = head;
n.right.left = n;
n.left = null;
head = n;
return table.get(key).data;
}
return -1;
}
public int delete(int key){
if(table.containsKey(key)){
Node n = table.get(key);
if(n==head){
head = head.right;
head.left = null;
}
else{
n.left.right = n.right;
n.right.left = n.left;
}
return table.remove(key).data;
}
return -1;
}
public int last(){
if(head!=null){
return head.data;
}
return -1;
}
}
public class DictionaryWithLast {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Dictionary d = new Dictionary();
d.set(12, 1);
d.set(13, 2);
d.set(14, 3);
d.set(15, 4);
System.out.println(d.get(13));
d.set(16, 5);
d.set(15, 4);
System.out.println(d.last());
d.delete(15);
System.out.println(d.last());
}
}
class Node{
int data;
Node left;
Node right;
public Node(Node left,int data,Node right){
this.left = left;
this.data = data;
this.right = right;
}
public Node(int data){
this.data = data;
}
}
We can do all operation in constant time using Hashmap and doubly LL
Node {
T key
T value
}
Map<key,Node>
LinkesList
Keep two variable also
1. Tail this is the tail node of DLL
2. LastAaccess this will tell abt the last access node
1. Set
Insert it to tail of DLL update tail to point last node. If LastAaccess is same as tail then make both same(LastAaccess =tail)
O(1)
2. Get(key)
Go to hash map, get the node if exist and go to that node in DLL return value.
Also update the LastAaccess to this node.
O(1)
3. Delete (key), use map, get the node if exist and remove from both DLL and map
Here if
1. If LastAaccess = key node the update LastAaccess to tail otherwise don't update LastAaccess
A. In case if all LastAaccess, tail and key to delete are same then automatically tail gets update and with inner if condition the last Access gets update
B. If key and tail are same the it won't affect LastAaccess at all
Will construct a binary search tree whenever we do set(Key , Value) pairs. This will help in get(key) & delete(key). To get last, last but one , last but two nodes will traverse the in-order traversal. That is when a tree root,left,right nodes, the right node is the last node, left node is the last but one node & root is the last but two node.
Hope this creates the new data structure.
class DictEntry(object):
def __init__(self, val):
self.prev = None
self.next = None
self.val = val
class DictWithLast(object):
def __init__(self):
self.dict = {}
self.latest = None
def set(self, key, value):
if key in self.dict:
self.delete(key)
new_entry = DictEntry(value)
self.dict[key] = new_entry
if self.latest == None:
self.latest = new_entry
else:
self.latest.next = new_entry
new_entry.prev = self.latest
self.latest = new_entry
def get(self, key):
if key not in self.dict:
raise KeyError
return self.dict[key].val
def delete(self, key):
if key not in self.dict:
raise KeyError
entry = self.dict[key]
if entry.prev:
entry.prev.next = entry.next
if entry.next:
entry.next.prev = entry.prev
if entry == self.latest:
self.latest = entry.prev
del self.dict[key]
def last(self):
if self.latest == None:
raise Exception('Empty dictionary no element')
return self.latest.val
if __name__ == '__main__':
mydict = DictWithLast()
mydict.set(1, 'a')
print(mydict.last())
mydict.set(2, 'b')
print(mydict.last())
mydict.set(3, 'c')
print(mydict.last())
mydict.set(2, 'x')
print(mydict.last())
mydict.set(4, 'd')
print(mydict.last())
mydict.delete(3)
print(mydict.last())
mydict.delete(4)
print(mydict.last())
mydict.delete(1)
print(mydict.last())
mydict.delete(2)
print(mydict.last())
Self-Balancing Binary Tree: Red-Black Tree I think is the best choice because it gives you the best worst case (log).
- Anonymous January 15, 2019Other options might be: AVL tree and Hash Tables... but, depends on what you want to do with this structure.