CareerCup

We will implement writer class having a static property : int writerCount, and a private property writerId
and will implement reader class having a static property : int readerCount and a private property readerId

Each time a writer/readerId Object is created, the object will be assigned writerId = ++writerCount, and readerId = ++readerCount


Now writeToBuffer() method in writer class checks
if(getBuffer().isEmpty() && !getBuffer().writeLocked && getBuffer().writeCount()%Writer::writerCount == writerId) {
getBuffer().acquireWriteLock();
getBuffer().write(data);
getBuffer.incrementWriteCount();
getBuffer().setFull();
getBuffer.releaseWriteLock();
}
else wait();


For reader, we will do the following:
if(getBuffer().isFull() && getBuffer().readCount()%Reader::readerCount == readerId) {
data = getBuffer().read();
getBuffer.incrementReadCount();
getBuffer().setEmpty();
}
else wait();

I am mentioning 3 possible ways for having max() and secondMax() to be fetched in O(1) time. First 2 are non scalable to kth Max, but push and pop are better than the 3rd but scalable solution.

1) Save max and secondMax in each node. So create the node as follows:
struct Node {
int data;
int max,
int secondMax;
}
Struct Stack {
Node *top;
void push(int data);
int pop();
bool isEmpty() const {return top == NULL;}
int max(); // this is peek operation
int secondMax(); // this is peek operation
in peek(); // peek the top most data
}

a). Initially, the stack is empty. No max, no secondMax
b). When first element is inserted, the max element is the data itself. There is no secondMax element.
c). When an element is pushed, write following code:
int maxItem = max(), secondMaxItem = secondMax();
if(currItem > maxItem) { secondMaxItem = maxItem; maxItem = currItem; }
else if(currItem > secondMaxItem) secondMaxItem = currItem;
Node *newNode = new Node(currItem, maxItem, secondMaxItem);
newNode->next = top;
top = newNode;
}

The disadvantage is that the space requirement is 3 times. And it is not scalable to kth Max.

2) Another non scalable solution is to have an auxiliary stack:

So push will be as follows:
void push(int currItem) {
node *newNode = node(currITem);
if(stack.empty()) {
top = newNode;
auxStack.push(currItem);
}
else {
if(currItem > auxStack.peek())
auxStack.push(currItem);
newNode->next = top;
top = newNode;
}
else {
std::pair<int, int> top2Items = auxStack.peek2Items();
int secondMax = top2Items.second;
if(currItem > secondMax)
{ int max = auxStack.pop();
auxStack.push(currItem);
auxStack.push(max);
}
}

In this second case, the space requirement is just 2N where N is the size of stack at any given point of time.

3) A scalable solution is to have a dynamic array (i.e. vector) in the stack, which will save items in order. Push will take at the most O(n) for insertion sort. Pop will also take O(n) in worst case to remove the nth element in the dynamic array.

We can also think of a max heap, but push and pop could take O(log n) time to heapify. This solution is applicable to getting max and second max. As the max will be root and secondMax will be one of its children. Also kthMax() is slightly more than O(1) (will have to check k-1 levels)