02/9/16

HackerRank ‘Largest Rectangle’ Solution

Short Problem Definition:

There are NN buildings in a certain two-dimensional landscape. Each building has a height given by hi,i∈[1,N]hi,i∈[1,N]. If you join KK adjacent buildings, they will form a solid rectangle of area K×min(hi,hi+1,…,hi+k−1)K×min(hi,hi+1,…,hi+k−1).

Given NN buildings, find the greatest such solid area formed by consecutive buildings.

Link

Largest Rectangle

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Best explained on Geeks for Geeks.

Solution:
def computeLargestArea(hist, N):
    stack = []
    
    max_area = 0
    
    idx = 0
    while (idx < N):
        if not stack or hist[stack[-1]] <= hist[idx]:
            stack.append(idx)
            idx += 1
        else:
            
            height_idx = stack.pop()
            
            depth = idx
            if stack:
                depth = idx - stack[-1] - 1
            
            area = hist[height_idx] * depth
            max_area = max(area, max_area)
     
    while stack:
        height_idx = stack.pop()
            
        depth = idx
        if stack:
            depth = idx - stack[-1] - 1
            
        area = hist[height_idx] * depth
        max_area = max(area, max_area)
            
    return max_area

def main():
    N = int(raw_input())
    
    hist = map(int, raw_input().split())
    
    print computeLargestArea(hist, N)
    


if __name__ == '__main__':
    main()

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

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

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

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

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

Facebooktwittergoogle_plusredditpinterestlinkedin
01/25/16

HackerRank ‘Balanced Parentheses’ Solution

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

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

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

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

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

Facebooktwittergoogle_plusredditpinterestlinkedin
01/19/16

Codility ‘CyclicRotation’ Solution

Short Problem Definition:

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

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
08/31/15

HackerRank ‘Pairs’ Solution

Short Problem Definition:

Given N integers, count the number of pairs of integers whose difference is K.

Link

Pairs

Complexity:

time complexity is O(N*log(N))

space complexity is O(N)

Execution:

The solution is pretty straight-forward, just read the code :). The runtime complexity is calculated with log(N) access times for tree-based sets (not the case in Python).

Solution:
#!/usr/bin/py
def pairs(a,k):
    answer = 0
    s = set(a)
    for v in s:
        if v+k in s:
            answer += 1
    
    return answer
if __name__ == '__main__':
    n, k = map(int, raw_input().split())
    b = map(int, raw_input().split())
    print pairs(b, k)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/30/15

Hacker Rank ‘Common Child’ Solution

Short Problem Definition:

Given two strings a and b of equal length, what’s the longest string (S) that can be constructed such that it is a child of both?

A string x is said to be a child of a string y if x can be formed by deleting 0 or more characters from y.

Link

Common Child

Complexity:

time complexity is O(N*M)

space complexity is O(N*M)

Execution:

This is a longest common subsequence problem in disguise. I encourage you to look at a good explanation here.

Solution:
#!/usr/bin/py

def lcs(a, b):
    lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i+1][j+1] = lengths[i][j] + 1
            else:
                lengths[i+1][j+1] = \
                    max(lengths[i+1][j], lengths[i][j+1])
    
    return lengths[-1][-1]

def main():
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1,s2)
    
if __name__ == '__main__':
    main()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/29/15

HackerRank ‘Palindrome Index’ Solution

Short Problem Definition:

You are given a string of lower case letters. Your task is to figure out the index of the character on whose removal it will make the string a palindrome. There will always be a valid solution.

Link

Palindrome Index

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

The solution seems n^2 but isPalindrome is executed only once. Due to the problem specification there exists only one valid solution (and it always exists). Therefore I process the string as in a normal palindrome check, if it fails I try to figure out if the removal of the left index helps or not. If it helps the left index is the answer, if it does not, the right index is the answer. It can be further optimised, by not making a copy of the string in the isPalindrome input parameters.

Solution:
#!/usr/bin/py

def isPalindrome(s):
    for idx in xrange(len(s)//2):
        if s[idx] != s[len(s)-idx-1]:
            return False
    return True

def palindromeIndex(s):
    for idx in xrange((len(s)+1)//2):
        if s[idx] != s[len(s)-idx-1]:
            if isPalindrome(s[:idx]+s[idx+1:]):
                return idx
            else:
                return len(s)-idx-1
    return -1


def main():
    t = input()
    for _ in xrange(t):
        s = raw_input()
        print palindromeIndex(s)
    
if __name__ == '__main__':
    main()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
07/21/15

HackerRank ‘Counter Game’ Solution

Short Problem Definition:

Louise and Richard play a game. They have a counter set to N. Louise gets the first turn and the turns alternate thereafter. In the game, they perform the following operations.

  • If N is not a power of 2, reduce the counter by the largest power of 2 less than N.
  • If N is a power of 2, reduce the counter by half of N.
  • The resultant value is the new N which is again used for subsequent operations.

The game ends when the counter reduces to 1, i.e., N == 1, and the last person to make a valid move wins.

Given N, your task is to find the winner of the game.

Link

Counter Game

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I really enjoyed this one. It can be solved without any while loops as long as you are aware of the input size. You get the previous power of two by computing the next one and shifting right. I consider it funny that this simple solution is not mentioned in the editorial.

Solution:
#!/usr/bin/py

def getClosestSmaller(x):
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    x = x + 1
    x = x >> 1
    return x

def getNrReductions(x):
    reductions = 1

    while (x != 1):
        #print x
        if x & (x - 1):
            #print "x is not power of two"
            x -= getClosestSmaller(x)
        else:
            #print "x is power of two"
            x /= 2
        reductions += 1    

    return reductions

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        if getNrReductions(n) % 2 != 0:
            print "Richard"
        else:
            print "Louise"

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

Facebooktwittergoogle_plusredditpinterestlinkedin