interview questions

merge.py

"""
Merge N sorted iterables into a sorted list
"""


def merge_n_lists(list_of_lists):
    if len(list_of_lists) == 0:
        return []

    if len(list_of_lists) == 1:
        return list_of_lists[0]

    mid = len(list_of_lists) // 2
    return merge_2(merge_n_lists(list_of_lists[:mid]), merge_n_lists(list_of_lists[mid:]))



def merge_2(iter1, iter2):
    """merge 2 sorted lists"""
    p1, p2 = 0, 0
    res = []
    while len(res) < len(iter1) + len(iter2):
        if p1 == len(iter1):
            res.extend(iter2[p2:])
            break
        if p2 == len(iter2):
            res.extend(iter1[p1:])
            break
        if iter1[p1] < iter2[p2]:
            res.append(iter1[p1])
            p1 += 1
        else:
            res.append(iter2[p2])
            p2 += 1
    return res    

stack.py

"""
implement a standard lifo stack with the added functionality of getting the max value
all operations should be O(1)
"""


class MaxStack:

    def __init__(self, iterable=()):
        self._q = []
        self._max = []
        for v in iterable:
            self.push(v)

    def push(self, v):
        if self.empty():
            self._max.append(v)
        else:
            self._max.append(max(v, self.peek()))
        self._q.append(v)

    def max(self):
        return self._max[-1]

    def empty(self):
        return len(self._q) == 0

    def peek(self):
        return self._q[-1]

    def pop(self):
        self._max.pop()
        return self._q.pop()