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