Short Problem Definition:

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1. Push the element x into the stack.
2. Delete the element present at the top of the stack.
3. Print the maximum element in the stack.

Link

Maximum Element

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

I really enjoyed this problem. I did not see the solution at first, but after it popped up, it was really simple.

Keep two stacks. One for the actual values and one (non-strictly) increasing stack for keeping the maxima.

Solution:

class CustomStack:
    def __init__(self):
        self.stack = []
        self.maxima = []
    
    def push(self, value):
        self.stack.append(value)
        if not self.maxima or value >= self.maxima[-1]:
            self.maxima.append(value)
        
    def printMax(self):
        print self.maxima[-1]
    
    def pop(self):
        value = self.stack.pop()
        if value == self.maxima[-1]:
            self.maxima.pop()

def main():
    cs = CustomStack()
    
    N = int(raw_input())
    
    for _ in xrange(N):
        unknown = raw_input()
        
        command = unknown[0]
        
        if command == '1':
            cmd, value = map(int, unknown.split())
            cs.push(value)
        elif command == '2':
            cs.pop()
        else:
            cs.printMax()
    


if __name__ == '__main__':
    main()

Short Problem Definition:

In this problem, your task is to implement a simple text editor. Initially, a file contains an empty string S. Your task is to perform Q operations consisting of the following 4 types:

1. append(W) – Appends the string W at the end of S.
2. erase(k) – Erase the last k character of S.
3. get(k) – Returns the kth character of S.
4. undo() – Undo the last not previously undone operation of type 1 or 2, so it reverts S to the state before that operation.

Link

Simple Text Editor

Complexity:

time complexity is

space complexity is

Execution:

I maintain two separate stacks. Self.stack represents the current state of the text. I can read data from this stack by indexing it. Self.cmds keeps the history of commands. Each command type knows how to execute itself and how to revert itself.

Solution:

class AppendCmd():
    def execute(self, stack, value):
        self.length = len(value)
        stack.extend(value)
        
    def revert(self, stack):
        for _ in xrange(self.length):
            stack.pop()

class EraseCmd():
    def execute(self, stack, value):
        self.text = stack[-value:]
        for _ in xrange(value):
            stack.pop()
        
    def revert(self, stack):
        stack.extend(self.text)         
            
class CustomStack:
    def __init__(self):
        self.stack = []
        self.cmds = []
        
    def push(self, value):
        cmd = AppendCmd()
        cmd.execute(self.stack, value)
        self.cmds.append(cmd)
    
    def pop(self, value):
        cmd = EraseCmd()
        cmd.execute(self.stack, value)
        self.cmds.append(cmd)
        
    def get(self, value):
        print self.stack[value]
    
    def revert(self):
        cmd = self.cmds.pop()
        cmd.revert(self.stack)

def main():    
    
    cs = CustomStack()
    
    N = int(raw_input())
    
    for _ in xrange(N):
        unknown = raw_input()
        
        command = unknown[0]
        
        if command == '1':
            cmd, value = unknown.split()
            cs.push(list(value))
        elif command == '2':
            cmd, value = map(int, unknown.split())
            cs.pop(value)
        elif command == '3':
            cmd, value = map(int, unknown.split())
            cs.get(value - 1)
        else:
            cs.revert()
    

if __name__ == '__main__':
    main()

Short Problem Definition:

Given a sequence consisting of parentheses, determine whether the expression is balanced.

Link

Balanced Parentheses

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Equivalent to Codility Brackets.

Solution:

def isValidPair(left, right):
    if left == '(' and right == ')':
        return True
    if left == '[' and right == ']':
        return True 
    if left == '{' and right == '}':
        return True   
    return False
 
def isProperlyNested(S):
    stack = []
     
    for symbol in S:
        if symbol == '[' or symbol == '{' or symbol == '(':
            stack.append(symbol)
        else:
            if len(stack) == 0:
                return False
            last = stack.pop()
            if not isValidPair(last, symbol):
                return False
     
    if len(stack) != 0:
        return False
             
    return True

def main():
    N = int(raw_input())

    for _ in xrange(N):
        s = raw_input()
        if isProperlyNested(s):
            print "YES"
        else:
            print "NO"


if __name__ == '__main__':
    main()

Short Problem Definition:

You are given a 2D matrix, a, of dimension MxN and a positive integer R. You have to rotate the matrix R times and print the resultant matrix. Rotation should be in anti-clockwise direction.

Link

[Algo] Matrix Rotation

Complexity:

time complexity is O(N×M)

space complexity is O(NxM)

Execution:

There is just lots of code, but the actual solution is pretty simple. I first extract layers, to simplify the logic. Then, I rotate the layers similarly to the Codility Rotation challenge.

Solution:

def reverse(arr, i, j):
    for idx in xrange((j - i + 1) / 2):
        arr[i + idx], arr[j - idx] = arr[j - idx], arr[i + idx]


def rotateList(A, K):
    # performs a right rotation
    # K needs to be adjusted to len(A) - K for left rotation
    l = len(A)
    K %= len(A)

    reverse(A, l - K, l - 1)
    reverse(A, 0, l - K - 1)
    reverse(A, 0, l - 1)

    return A


def rotateLayers(N, M, R, layers):
    for layer in layers:
        rotateList(layer, len(layer) - R)


def rotateMatrix(M, N, R, mat):
    # generate a list of layers
    l = int(min(N, M) // 2)
    layers = [[] for _ in range(l)]
    for level in xrange(l):
        top = (N - 1) - 2 * level
        side = (M - 1) - 2 * level
        for i in range(top):  # right
            layers[level].append(mat[level][level + i])
        for j in range(side):  # down
            layers[level].append(mat[level + j][level + top])
        for i in range(top):  # left
            layers[level].append(mat[level + side][level + top - i])
        for j in range(side):  # up
            layers[level].append(mat[level + side - j][level])

    # rotate each layer
    rotateLayers(N, M, R, layers)

    # fill the layers back in
    for level in range(l):
        top = (N - 1) - 2 * level
        side = (M - 1) - 2 * level
        for i in xrange(top):
            mat[level][level + i] = layers[level].pop(0)  # right
        for j in range(side):
            mat[level + j][level + top] = layers[level].pop(0)  # down
        for i in range(top):
            mat[level + side][level + top - i] = layers[level].pop(0)  # left
        for j in range(side):
            mat[level + side - j][level] = layers[level].pop(0)  # up


def main():
    M, N, R = map(int, raw_input().split())
    mat = []
    for i in range(M):
        mat.append(list(map(int, raw_input().split())))

    rotateMatrix(M, N, R, mat)

    # print the rotated matrix
    for row in range(M):
        for col in range(N):
            print mat[row][col],
        print


if __name__ == '__main__':
    main()