Amazon Interview Question SDE-2s
Country: India
just a thing ...the mode is the no with the max frequency. So you should be returning the set of no.s stored at mBestCount's location. Everything else seems right.
I don't know if you are allowed to use complementary data structures, but I guess this works - we use a queue for insert and FIFO removal. We use a hashtable to keep track of modes of nodes, and finally we keep chronological track of modes with a stack (if we remove a mode, it will take us O(n) to search for the next one in the hash table, but we want this to be O(1)).
class DS {
HashTable<Node, Integer> ht;
Queue q;
Stack modeStack;
Node currentMode;
int modeNum;
insert(int element) {
Node curr = Node(element);
q.enqueue(curr);
int checkMode = ht.getValue(curr) + 1;
ht.put(Node, ht.getValue(Node) + 1);
if (checkMode > modeNum) {
curr = currentMode;
modeNum = checkMode;
modeStack.push(curr);
}
}
remove() {
Node curr = q.dequeue;
ht.put(curr, curr.getValue() - 1);
Node modeTop = modeStack.pop();
Node modeSecond = modeStack.peek();
if (ht.getValue(modeTop) < ht.getValue(modeSecond)) {
currentMode = modeSecond;
modeNum = ht.getValue(modeSecond);
return;
}
modeStack.push(modeTop);
}
findMode() {
Node mode = modeStack.pop();
currentMode = modeStack.peek();
modeNum = ht.getValue(currentMode);
return mode;
}
}
it is not correct, consider list (A, A, A, B, B), B has no chance to get into your modeStack, when pop two As from the front, your answer is wrong.
@soup:
yes, you make a valid point.
In this case, I am not sure that there is really a way to do Mode in O(1) - I can only think of changing the stack to a priority queue, in which case it would work, but wouldn't be O(1)
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <hash_map>
#include <stack>
class DS
{
int curMode;
int lastValue;
std::unordered_map <int,int> ElementTable ;// count of inserted value
std::unordered_map<int, std::unordered_set<int> > countTable;//count of elements count
int elementcount;
public:
DS()
{
curMode = 0;
elementcount = 0;
lastValue = 0;
ElementTable.clear();
countTable.clear();
}
void insert(int element)
{
elementcount++;
int CurCount = ElementTable[element] +1 ;
int curModeCount = ElementTable[curMode];
if (curModeCount < CurCount)
{
curMode = CurCount+1;
}
countTable[CurCount].erase(element);
countTable[CurCount+1].insert(element);
ElementTable[element]++;
}
bool erase(int element)
{
if (elementcount > 0)
{
if (ElementTable.find(element) != ElementTable.end())
{
int CurCount = ElementTable[element];
countTable[CurCount].erase(element);
if (countTable[CurCount].empty())
{
countTable.erase(CurCount);
}
if (ElementTable[element] == 1)
{
ElementTable.erase(element);
}
else
{
countTable[CurCount - 1].insert(element);
ElementTable[element]--;
}
if (element == curMode)
{
if (countTable.find(CurCount) != countTable.end() )
{
curMode = *(countTable[CurCount].begin());
}
}
elementcount--;
}
return false;
}
return false;
}
bool mode(int& value)
{
if (elementcount > 0)
{
value = curMode;
return true;
}
else
return false;
}
};
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <hash_map>
#include <stack>
using namespace System;
//insert
//delete
//mode
class DS
{
int curMode;
int lastValue;
std::unordered_map <int,int> ElementTable ;// count of inserted value
std::unordered_map<int, std::unordered_set<int> > countTable;//count of elements count
int elementcount;
public:
DS()
{
curMode = 0;
elementcount = 0;
lastValue = 0;
ElementTable.clear();
countTable.clear();
}
void insert(int element)
{
elementcount++;
int CurCount = ElementTable[element] +1 ;
int curModeCount = ElementTable[curMode];
if (curModeCount < CurCount)
{
curMode = CurCount+1;
}
countTable[CurCount].erase(element);
countTable[CurCount+1].insert(element);
ElementTable[element]++;
}
bool erase(int element)
{
if (elementcount > 0)
{
if (ElementTable.find(element) != ElementTable.end())
{
int CurCount = ElementTable[element];
countTable[CurCount].erase(element);
if (countTable[CurCount].empty())
{
countTable.erase(CurCount);
}
if (ElementTable[element] == 1)
{
ElementTable.erase(element);
}
else
{
countTable[CurCount - 1].insert(element);
ElementTable[element]--;
}
if (element == curMode)
{
if (countTable.find(CurCount) != countTable.end() )
{
curMode = *(countTable[CurCount].begin());
}
}
elementcount--;
}
return false;
}
return false;
}
bool mode(int& value)
{
if (elementcount > 0)
{
value = curMode;
return true;
}
else
return false;
}
};
FIFO queue pointing to HashMap with index formed by elements of queue and Hashmap pointing further to a MaxHeap( based on frequency of elements). The insert and delete operations will always be changing the frequency of an element by one, hence the heapify function of MaxHeap will always be doing a single exchange between parent and child. It will be a constant operation.
- popescu.af January 21, 2015template<typename value_type> class DS { std::list<value_type> mData; std::unordered_map<value_type, size_t> mValueToCountMap; std::unordered_map<size_t, std::unordered_set<value_type>> mCountToValuesMap; size_t mBestCount; public: DS() : mData() , mValueToCountMap() , mCountToValuesMap() , mBestCount(0) { } void insert(const value_type &value) { mData.push_back(value); if (mValueToCountMap.find(value) == mValueToCountMap.end()) { mValueToCountMap[value] = 1; mCountToValuesMap[1].insert(value); if (mBestCount == 0) mBestCount = 1; } else { auto& count = mValueToCountMap[value]; mCountToValuesMap[count].erase(value); if (mCountToValuesMap[count].empty()) mCountToValuesMap.erase(count); ++count; mCountToValuesMap[count].insert(value); if (count > mBestCount) mBestCount = count; } } void erase() { if (mData.empty()) return; auto& value = mData.front(); auto& count = mValueToCountMap[value]; mCountToValuesMap[count].erase(value); if (count == mBestCount && mCountToValuesMap[count].empty()) { mCountToValuesMap.erase(count); --mBestCount; } if (--count != 0) mCountToValuesMap[count].insert(value); else mValueToCountMap.erase(value); mData.pop_front(); } const std::unordered_set<value_type> & mode() const { auto foundIt = mCountToValuesMap.find(mBestCount); return foundIt->second; } };