08/31/15

# HackerRank ‘Pairs’ Solution

##### Short Problem Definition:

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

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

Note: The problem specification has a contraint on K: 0<K<10^9. If K was allowed to be 0, this challenge would become slightly more difficult.

##### Solution:
#!/usr/bin/py
def pairs(a,k):
s = set(a)
for v in s:
if v+k in s:

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.			
08/30/15

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

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

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.

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.