01/29/16

# HackerRank ‘Maximum Element’ Solution

##### 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.

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

if command == '1':
cmd, value = map(int, unknown.split())
cs.push(value)
elif command == '2':
cs.pop()
else:
cs.printMax()

if __name__ == '__main__':
main()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/28/16

# HackerRank ‘Simple Text Editor’ Solution

##### 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.

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

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()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/25/16

# HackerRank ‘Balanced Parentheses’ Solution

##### Short Problem Definition:

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

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()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/22/16

# HackerRank ‘Matrix Rotation’ Solution

##### 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.

[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()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/19/16

# Codility ‘CyclicRotation’ Solution

##### Short Problem Definition:

Rotate an array to the right by a given number of steps.

Cyclic Rotation

##### Complexity:

expected worst-case time complexity is O(N)

##### Execution:

There are multiple solutions to this problem. I picked the one that does not create a copy of the array.

##### 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 solution(A, K):
l = len(A)
if l == 0:
return []

K = K%l

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

return A


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.