## Interview Question

Country: United States

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

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.

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

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
1. it has better average run time for insertion removal and search amortized 0(log n)
2. Benefits with less memory usage

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

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.

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

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.

Comment hidden because of low score. Click to expand.
0

Excellent idea, and certainly the simplest one, but I think we can only call server (which computes the prime) to compute the smallest bigger one. So to get smaller we would have to sequentially call server N-L times to determine L...

Comment hidden because of low score. Click to expand.
0

When result is not in cache for number N, the client sends N to server and the server sends a prime number p1. Then the client send p1+1 to the server, and the server returns p2, store [p1, p2] in the cache.

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

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

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.

### 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.

### 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.

### 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.