CareerCup

Ignoring the LRU/MRU and cache eviction concerns for a moment, you can use a balanced binary search tree like a red-black tree as your cache. Using a balanced BST helps in 2 important ways (i) you can do a range query or comparisons (ii) you still get a good performance as searching would be O(log N).

So to solve this problem,
1) Use a red-black tree (TreeMap in Java provides this out of the box)
2) Node data: Each node in the tree will hold an integer key and a small list of ordered primes (say 50 primes bigger than this key)
3) Search: Look up the biggest key in the tree which is smaller than your search key. This can be done in O(log N). Scan the list of primes stored in the node until you find one which is bigger than your search key. Return this prime.
4) Insertion: If your search failed to return a prime, you need to insert a new node in the tree. This is easy and again takes O(log N).

So, this way you can avoid too many trips to the server for nearby values, as the interviewer wanted.

For LRU/MRU stuff you could maintain an additional hashtable with pointers to tree nodes as keys and timestamps as values.

Use cache with augmented splay trees such that the element if goes beyond x height will be removed from the tree

Here x can be the number of elements the client want to access fastly
Advantage
1. it has better average run time for insertion removal and search amortized 0(log n)
2. Benefits with less memory usage

Why complicate? Binary search tree is sufficient. Each node would contain two numbers.
- key: the least integer for which <value> is the smallest bigger prime
- value: the prime itself

When you check for a given number, you search the biggest number smaller than the given one. When you find it in O(logN) on average, you check the prime. Two scenarios occur:
- prime is bigger than your number: cache hit
- prime is smaller: cache miss

In case of cache miss you send a request to the server and get the prime. You then search the smallest bigger number than your number, and get it's prime value. Check if that prime is the same as your prime. Again two scenarios occur:
- prime is the same: you replace the key with your key as it does not corrupt the tree and it's smaller than the given key.
- prime is not the same: add another note with your number and it's prime

Whoops, it seems that it's a bit more complicated :D But IMO it gives the best time and space complexity. Please correct me if I made a mistake.

How about this?

For each number N queried, compute 2 prime numbers L and R, so that
L <= N < R, and there's no prime in range (L, R). We save the ranges
in the cache. The ranges are sorted by their bounds.

When a new number is asked, find a range (L, R) with the smallest L
in the cache so that L <= N. If N <=R, return R. Otherwise, need to
compute a covering range for N, and add the new range in the cache.

Using Sieve of Eratosthenes and bitset to save results

/*
  Sieve of Aristhoteles
  Prime numbers
*/

#include <iostream>
#include <bitset>

template <size_t N>
class prime_util {
public:
	prime_util();
	int get_smaller_bigger_prime(int x);

private:
	std::bitset<N> bset;
};

template <size_t N>
prime_util<N>::prime_util() {

	bset.set(0);
	bset.set(1);

	// Initialize the bitset with sieve of Aristoteles
	for(int i = 2; i < N; ++i) {
		if(bset.test(i))
			continue;

		for(int c = i + i; c < N; c += i) {
			bset.set(c);
		}
	}

}

template <size_t N>
int prime_util<N>::get_smaller_bigger_prime(int x) {
	if(x > N)
		return -1;

	for(int check = x; check < N; ++check)
		if(!bset.test(check))
			return check;

	return -1;
}

int main() {
        const int max = 20;
	prime_util<max> primeutil;
	std::cout << primeutil.get_smaller_bigger_prime(6) << std::endl;
	std::cout << primeutil.get_smaller_bigger_prime(7) << std::endl;
	return 0;
}