Had a Facebook Phone screen round yesterday, this was the second question asked.

First question was relatively easy string to integer conversion something like - https://leetcode.com/problems/string-to-integer-atoi/

In this problem, you have to design a data structure which can store key, value pairs. It should be able to support following operations - get(), put(), last(), delete().
'''
// interface ADTwithLast<K, V> {
// put(K k, V v);
// V get(K k);
// delete(K k);
// K last();
// }
'''

example -
// put("a", 1);
// put("b", 2);
// get("a"); ===> 1
// last(); ===> "a"
// delete("a");
// last(); ===> "b"

I though about 2 solutions

• 1 with stack, but then last() function was getting really expensive.
• 2nd i thought was using hashmap and keeping keys sorted in additional space based on their last access time. Here, get put will become expensive.

Not sure what is the best solution for this, would love to hear ideas on this.