02/23/16

HackerRank ‘Sherlock and Valid String’ Solution

Short Problem Definition:

A “valid” string is a string S such that for all distinct characters in S each such character occurs the same number of times in S.

Link

Sherlock and Valid String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I optimised this solution to the minimal case that passes all tests on HackerRank. It seems that each character occurs 1 or 2 times. I did not pay the Hackos to verify the input :). The logic of the solution is as follows: count the character counts for each character.

  • if they are all equal – it means that all characters occur exactly N times and there is no removal needed
  • if 2 or more have less or more characters – there is no way to fix the string in just 1 removal
  • if exactly 1 char has a different count than all other characters – remove this char completely and S is fixed.
Solution:
from collections import Counter


def isValid(S):
    char_map = Counter(S)
    char_occurence_map = Counter(char_map.values())

    if len(char_occurence_map) == 1:
        return True

    if len(char_occurence_map) == 2:
        for v in char_occurence_map.values():
            if v == 1:
                return True

    return False


S = raw_input()
if isValid(S):
    print "YES"
else:
    print "NO"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/11/16

HackerRank ‘Poisonous Plants’ Solution

Short Problem Definition:

There are NN plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Link

Poisonous Plants

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

 

This challenge was really hard. I could not figure it out for a long time. The part with the stack is pretty obvious, but I missed the fact that older plants can have higher daysAlive values.

Solution:
class Plant:
    def __init__(self, pesticide, days):
        self.pesticide = pesticide
        self.days = days

def solvePlants(a):
    stack = []
    maxDaysAlive = 0
    
    for pesticide in a:
        daysAlive = 0
        while stack and pesticide <= stack[-1].pesticide:
            daysAlive = max(daysAlive, stack.pop().days)
            
        if not stack:
            daysAlive = 0
        else:
            daysAlive += 1
            
        maxDaysAlive = max(maxDaysAlive, daysAlive)
        
        stack.append(Plant(pesticide, daysAlive))
    
    print maxDaysAlive

def main():
    N = input()
     
    numbers = map(int, raw_input().split())
     
    solvePlants(numbers)
     
 
if __name__ == '__main__':
    main()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/10/16

HackerRank ‘Waiter’ Solution

Short Problem Definition:

You are a waiter at a party. There are NN stacked plates. Each plate has a number written on it. You start picking up the plates from the top one by one and check whether the number written on the plate is divisible by a prime….

Link

Waiter

Complexity:

time complexity is O(N*Q)

space complexity is O(N)

Execution:

First of all, generate primes using Sieve, or copy-paste a list of pre-generated primes. After each iteration the order of the remaining plates is reversed (you put the last on top and once finished you start from the top). That means that the solution has to have a stack, not a queue.

It is not possible to solve this in one pass. I would love to find such a solution.

Solution:
generated_primes = [...]

def solveWaiter(N, Q, numbers):
    stack = []
    
    for value in numbers:
        if value % generated_primes[0] != 0:
            stack.append(value)
        else:
            print value
    
    
    for prime_idx in xrange(1, Q):
        leftover = []
        
        while stack:
            value = stack.pop()
            if value % generated_primes[prime_idx] != 0:
                leftover.append(value)
            else:
                print value
        stack = leftover
    
    for value in stack:
        print value

def main():
    N, Q = map(int, raw_input().split())
    
    numbers = map(int, raw_input().split())
    
    solveWaiter(N, Q, numbers)
    

if __name__ == '__main__':
    main()


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

Facebooktwittergoogle_plusredditpinterestlinkedin
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