Cracking The Coding Interview/Q 3.2

From Software Engineers Wiki
Jump to: navigation, search

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

Answer

To meet the O(1) requirement, we can maintain two stacks, one with data, and the other with minimum value so far.

#include <iostream>
#include <mutex>
#include <stack>
#include <climits>

class CStackWithMin {
private:
        std::mutex m_mutex;
        std::stack<int> m_stackData;
        std::stack<int> m_stackMin;
        int m_min;
public:
        CStackWithMin() : m_min {INT_MAX} {}
        void push(int data);
        bool pop(int &data);
        bool min(int &min);
};

void CStackWithMin::push(int data)
{
        std::lock_guard<std::mutex> lock(m_mutex);
        m_stackData.push(data);
        if (data < m_min)
                m_min = data;
        m_stackMin.push(m_min);
}

bool CStackWithMin::pop(int &data)
{
        std::lock_guard<std::mutex> lock(m_mutex);
        if (m_stackData.empty())
                return false;
        data = m_stackData.top();
        m_stackData.pop();
        m_stackMin.pop();
        if (m_stackMin.empty())
                m_min = INT_MAX;
        else
                m_min = m_stackData.top();
        return true;
}

bool CStackWithMin::min(int &data)
{
        std::lock_guard<std::mutex> lock(m_mutex);
        if (m_stackMin.empty()) {
                data = m_min;
                return false;
        }
        data = m_stackMin.top();
        return true;
}

And a test program

int main(void)
{
        CStackWithMin swm;
        int i, data;

        for (i = 0; i < 20; ++i) {
                data = random() & 0xffff;
                swm.push(data);
                std::cout << "Pushed: " << data;
                swm.min(data);
                std::cout << ", min: " << data << "\n";
        }

        while (swm.pop(data)) {
                std::cout << "Popped: " << data;
                swm.min(data);
                std::cout << ", min: " << data << "\n";
        }

        return 0;
}

And the test result.

Pushed: 17767, min: 17767
Pushed: 9158, min: 9158
Pushed: 39017, min: 9158
Pushed: 18547, min: 9158
Pushed: 56401, min: 9158
Pushed: 23807, min: 9158
Pushed: 37962, min: 9158
Pushed: 22764, min: 9158
Pushed: 7977, min: 7977
Pushed: 31949, min: 7977
Pushed: 22714, min: 7977
Pushed: 55211, min: 7977
Pushed: 16882, min: 7977
Pushed: 7931, min: 7931
Pushed: 43491, min: 7931
Pushed: 57670, min: 7931
Pushed: 124, min: 124
Pushed: 25282, min: 124
Pushed: 2132, min: 124
Pushed: 10232, min: 124
Popped: 10232, min: 124
Popped: 2132, min: 124
Popped: 25282, min: 124
Popped: 124, min: 7931
Popped: 57670, min: 7931
Popped: 43491, min: 7931
Popped: 7931, min: 7977
Popped: 16882, min: 7977
Popped: 55211, min: 7977
Popped: 22714, min: 7977
Popped: 31949, min: 7977
Popped: 7977, min: 9158
Popped: 22764, min: 9158
Popped: 37962, min: 9158
Popped: 23807, min: 9158
Popped: 56401, min: 9158
Popped: 18547, min: 9158
Popped: 39017, min: 9158
Popped: 9158, min: 17767
Popped: 17767, min: 2147483647
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox