Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- guilhebl January 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not just update self.last = key whenever set(key, value) or get(key) is called?

- sxiong January 18, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Self-Balancing Binary Tree: Red-Black Tree I think is the best choice because it gives you the best worst case (log).
Other options might be: AVL tree and Hash Tables... but, depends on what you want to do with this structure.

- Anonymous January 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Definitely the linked list solution is better

- Anonymous January 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Saurabh January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very similar to LRU Cache

- Anonymous January 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, the logic can be similar to LRU without the part to remove the element from the cache.

I have given my implementation idea with following time complexity
set --> O(LogN) --> since TreeMap put is used.
get --> O(1)
delete --> O(1)
last --> O(1)

- Saurabh January 21, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

- baites January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

small bug in your code, you are not checking whether key exists already in the dictionary. In that case only pointer will change for node linkedlist.

- Anonymous April 18, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

- baites January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vova January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Elena January 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Prateek Goel February 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nitinguptaiit March 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- srikanth546 July 25, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More