Challenge: Constant-Time Min-Element Stack

Here’s another problem from the Algorithm Design Manual (Skiena), Interview Problem 4-44:

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?
Hint 1
Constant time? Well then it’s stacks all the way down.
Hint 2
Two stacks, to be exact.
Answer
Data structure contains two stacks, all and mins. mins.top() is the minimum element. After calling all.push(), push to mins if all.top() <= mins.top(). Before calling all.pop(), pop from mins if all.top() == mins.top().

Challenge: Most Frequent Element

Here’s a nice problem from Notes on Streaming Algorithms:

Suppose we have sequence delim{lbrace}{x_1, x_2, ..., x_n}{rbrace} from a set epsilon, and that we know that one value from epsilon occurs more than n/2 times in the sequence; find the most frequent value using only two variables having total memory of only lg(n) + lg(max value) bits and in only a single sweep.

Spoiler 1
lg(n) can store any value up to n.
Spoiler 2
lg(max value) can store any value from epsilon.
Answer
Variables are count and major. Scan the list once, each element votes for major using count.

for each element
    element == major? count++ : count--
    if (count == 0)
        major = element
        count = 1

My implementation is in git and below.
Continue reading