## Amazon Interview Question for SDE-2s

• 0
of 0 votes

Country: India

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

Suppose that priority function is given F(c,t), then I would answer like this: We will need four things - an array of elements 'a', a symbol table 'st' (e.g. hash map or tree map) and priority queue 'pq' and a custom mutable class Node.

Now, how to put everything together: (i) Node contains an array index 'i' and priority of an element stored at a[i]. Node is comparable, hence can be comapred with other Node via priority. (ii) The priority queue 'pq' contains these nodes, notice that node with the highest priority is alway at the head. (iii) The map 'st' contains 'key, value' pairs which are an element hash and reference to the node (or a pointer if you will).

Given new element, first check if the element is present in the chache, hence check if the key is present in the map 'st':
a) Existing element
Get corresponding Node reference from 'st' and update its priority.

b) Non-existing element
(i) Dequeue the Node with the highest priority, get index 'i', get element at a[i]
(ii) Remove key (element a[i]) from the 'st'
(iii) Replace a[i] with the new element
(iv) Add new Node with F(c,t) and 'i' into the priority queue
(v) Add element, Node pair into the symbol table 'st'

This is just a general idea but it might work. I am not going to put some code here since it would be too long and not that interesting.

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

Since t is time elapsed, it is constantly changing, Hence, the F(t, c) will also be ever-changing. So, every time we need to remove an element from cache, we would need to evaluate F(t, c) and get the least and remove that. That makes it O(n).

Instead if t is the timestamp when the element was added, it can be done in O(1) using Priority Queues.

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

As the previous comment says, timestamps should be used instead of elapsed time.
The timestamp function is strictly increasing, thus a Min Priority Queue is enough to tell us
how to remove elements in O(1).
We also need a hashtable, for storing the data and retrieving it from the outside.

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

A possible solution (remove() is linear in worst case):

``````template <typename key_type, typename value_type, uint32_t size_value>
class CustomLruCache
{
public:
typedef std::function<uint32_t(const time_t &, const uint32_t &)> tKeyFunction;

public:
CustomLruCache(const tKeyFunction &f)
: mF(f)
, mData()
, mPriorities()
, mPriorityMap()
{ }

value_type & operator[] (const key_type &key)
{
return get(key);
}

const value_type & operator[] (const key_type &key) const
{
return get(key);
}

void insert(const key_type &key, const value_type &value, const uint32_t cost)
{
if (mData.size() == size_value)
remove();

uint32_t prio = mF(time(nullptr), cost);
mData[key] = Element(value, cost, prio);
mPriorities.push(prio);
mPriorityMap[prio].insert(key);
}

private:
struct Element
{
value_type value;
uint32_t cost;
uint32_t priority;

Element()
: value()
, cost(0)
, priority(0)
{ }

Element(const value_type &value, const uint32_t cost, const uint32_t priority)
: value(value)
, cost(cost)
, priority(priority)
{ }
};

private:
value_type & get(const key_type &key)
{
auto& el = mData[key];
mPriorityMap[el.priority].erase(key);
if (mPriorityMap[el.priority].empty())
mPriorityMap.erase(el.priority);

el.priority = mF(time(nullptr), el.cost);
mPriorityMap[el.priority].insert(key);
return el.value;
}

void remove()
{
while (!mPriorities.empty())
{
uint32_t lowestPrio = mPriorities.top();
auto& keysAtLowestPrio = mPriorityMap[lowestPrio];

if (keysAtLowestPrio.empty())
{
mPriorityMap.erase(lowestPrio);
mPriorities.pop();
continue;
}

auto keyIt = keysAtLowestPrio.begin();
mData.erase(*keyIt);

keysAtLowestPrio.erase(keyIt);
if (keysAtLowestPrio.empty())
{
mPriorityMap.erase(lowestPrio);
mPriorities.pop();
}

return;
}
}

private:
tKeyFunction mF;

std::unordered_map<key_type, Element> mData;
std::priority_queue<uint32_t, std::vector<uint32_t>, std::greater<uint32_t>> mPriorities;
std::unordered_map<uint32_t, std::unordered_set<key_type>> mPriorityMap;
};``````

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

Create a min heap using the function value for the different nodes. Create a hashmap in parallel which contains the page address as key and value as the node pointer of the heap. Whenever a page access is done, the node's function value is updated and we heapify with that node as start point. The nodes with highest value of 'f' will be at the end. During removal, remove the node at the top and insert the last node at the root location and call heapify.

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

Maintain a heap for each cost so you don't have to keep re-heapifying to figure out which F(t, c) to remove. You'll still have to scan through the heap tops to find the next one to remove. This obviously only works if you have cost categories. If every item has a unique cost then this becomes a list.

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