04/27/15

Codility ‘NumberOfDiscIntersections’ 2010 Beta Solution

Short Problem Definition:

Compute intersections between sequence of discs.

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.

Link

Number of Disc Intersections

Complexity:

expected worst-case time complexity is O(N*log(N))

expected worst-case space complexity is O(N)

Execution:

In my mind this problem is very similar to the Codility Fish. You keep count of how many not-yet-ended disks there are. Every beginning has to cross all not-yet-ended disks. The best explanation on the web was written by Luca. His solution is much better than my C-style double-checked while loop. I therefore created a mixture of both 🙂

  • Keep in mind that any pair of circles can intersect only once.
  • If 1+ beginnings have the same point as 1+ endings. You first have to process the beginnings. The old and new ones have per definition a meeting point.
Solution:
def solution(A):
    circle_endpoints = []
    for i, a in enumerate(A):
        circle_endpoints += [(i-a, True), (i+a, False)]

    circle_endpoints.sort(key=lambda x: (x[0], not x[1]))

    intersections, active_circles = 0, 0

    for _, is_beginning in circle_endpoints:
        if is_beginning:
            intersections += active_circles
            active_circles += 1
        else:
            active_circles -= 1
        if intersections > 10E6:
            return -1

    return intersections

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/24/15

Codility ‘PrefixSet’ 2010 Alpha Solution

Short Problem Definition:

Given a table A of N integers from 0 to N-1 calculate the smallest such index P, that that {A[0],…,A[N-1]} = {A[0],…,A[P]}.

Link

PrefixSet

Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

Execution:

Based on the number of elements that can occur in N, you either mark the occurrences in a boolean array, or put them in a set. The last occurrence of an element that was not seen before is the result.

Solution:
def solution(A):
    seen = set()
    smallest_prefix_idx = 0
    
    for idx in xrange(len(A)):
        if A[idx] not in seen:
            seen.add(A[idx])
            smallest_prefix_idx = idx
            
    return smallest_prefix_idx

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/23/15

HackerRank ‘Make it Anagram’ Solution

Short Problem Definition:

Alice recently started learning about cryptography and found that anagrams are very useful. Two strings are anagrams of each other if they have same character set. For example strings"bacdc" and "dcbac" are anagrams, while strings "bacdc" and "dcbad" are not.

Alice decides on an encryption scheme involving 2 large strings where encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. She need your help in finding out this number.

Given two strings (they can be of same or different length) help her in finding out the minimum number of character deletions required to make two strings anagrams. Any characters can be deleted from any of the strings.

Link

Make it Anagram

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Compare the frequency counts of the two parts.

The buildMap function can be replaced by:  from collections import Counter

Solution:
#!/usr/bin/py
def buildMap(s):
    the_map = {}
    for char in s:
        if char not in the_map:
            the_map[char] = 1
        else:
            the_map[char] +=1

    return the_map       

def anagram(s1, s2):
    map1 = buildMap(s1)
    map2 = buildMap(s2)

    diff_cnt = 0
    for key in map2.keys():
        if key not in map1:
            diff_cnt += map2[key]
        else:
            diff_cnt += max(0, map2[key]-map1[key])

    for key in map1.keys():
        if key not in map2:
            diff_cnt += map1[key]
        else:
            diff_cnt += max(0, map1[key]-map2[key])

    return diff_cnt

if __name__ == '__main__':
    s1 = raw_input()
    s2 = raw_input()
    print anagram(s1, s2)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/22/15

HackerRank ‘Anagram’ Solution

Short Problem Definition:

Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency analysis with the books. He chooses strings S1 and S2 in such a way that |len(S1)−len(S2)|≤1

Link

Anagram

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Compare the frequency counts of the two parts.

Solution:
#!/usr/bin/py

def buildMap(s):
    the_map = {}
    for char in s:
        if char not in the_map:
            the_map[char] = 1
        else:
            the_map[char] +=1
            
    return the_map       
    

def anagram(s):
    if len(s)%2 == 1:
        return -1
        
    mid = len(s)//2
    s1 = s[:mid]
    s2 = s[mid:]
    
    map1 = buildMap(s1)
    map2 = buildMap(s2)
    
    diff_cnt = 0
    for key in map2.keys():
        if key not in map1:
            diff_cnt += map2[key]
        else:
            diff_cnt += max(0, map2[key]-map1[key])
    
    return diff_cnt

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

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/15/15

HackerRank ‘Gemstones’ Solution

Short Problem Definition:

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lower-case Latin letter from ‘a’ to ‘z’. An element can be present multiple times in a rock. An element is called a gem-element if it occurs at least once in each of the rocks.

Given the list of N rocks with their compositions, display the number of gem-elements that exist in those rocks.

Link

Gemstones

Complexity:

time complexity is O(N*T)

space complexity is O(N)

Execution:

We count the number of elements that occur in all characters  sets. Just use set intersection.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    t = input()
    all_elements = set(raw_input())
    
    for _ in xrange(t-1):
        all_elements &= set(raw_input())
        
    print len(all_elements)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/13/15

HackerRank ‘Pangrams’ Solution

Short Problem Definition:

Roy wanted to increase his typing speed for programming contests. So, his friend advised him to type the sentence “The quick brown fox jumps over the lazy dog” repeatedly, because it is a pangram. (Pangrams are sentences constructed by using every letter of the alphabet at least once.)

Link

Pangrams

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

There are 26 letters in the English alphabet. A sentence is a pangram, if it contains all 26 characters.

Solution:
#!/usr/bin/py

def getCharCnt(s):
    return len(set(c.lower() for c in s if c != ' '))

if __name__ == '__main__':
    s = raw_input()
    if getCharCnt(s) == 26:
        print "pangram"
    else:
        print "not pangram"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/10/15

HackerRank ‘Funny String’ Solution

Short Problem Definition:

Suppose you have a string S which has length N and is indexed from 0 to N−1. String R is the reverse of the string S. The string S is funny if the condition |Si−Si−1|=|Ri−Ri−1| is true for every i from 1 to N−1.

Link

Funny String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Just follow the instructions.

Solution:
#!/usr/bin/py
def isStrFunny(s):
    s_len = len(s)
    idx = 0
    while idx < s_len//2:
        left_diff = abs(ord(s[idx]) - ord(s[idx+1]))
        right_diff = abs(ord(s[s_len-idx-1]) - ord(s[s_len-idx-2]))
        if left_diff != right_diff:
            return False
        idx += 1
    
    return True
    

if __name__ == '__main__':
    t = input()
    for _ in range(t):
    	s = raw_input()
        if isStrFunny(s):
            print "Funny"
        else:
            print "Not Funny"


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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/9/15

HackerRank ‘Number List’ Solution

Short Problem Definition:

Shashank loves to play with arrays a lot. Today, he has an array A consisting of N positive integers. At first, Shashank listed all the subarrays of his array A on a paper and later replaced all the subarrays on the paper with the maximum element present in the respective subarray.

Link

Number List

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

You do not actually need to construct all the sub-arrays, as they reduce to only one element. You also can ignore all sub-arrays, that do not contain elements E > K. I also observed that there are x*y sub-arrays that match the above specified criteria for each element E > K. X is the distance from E to any previous e > K. Y is the distance from E to the end of the array. This way you crate all the sub-arrays that contain E and are not part of another e.

Solution:
#!/usr/bin/py
def numberList(a ,k):
    result = 0

    last_biggest = -1
    a_len = len(a)

    for idx in xrange(a_len):
        if a[idx] > k:
            result += (idx-last_biggest)*(a_len-idx)
            last_biggest = idx

    return result

if __name__ == '__main__':
    t = int(raw_input())
    for _ in xrange(t):
        n,k = map(int, raw_input().split())
        a = map(int, raw_input().split())
        print numberList(a ,k)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/8/15

HackerRank ‘Circle City’ Solution

Short Problem Definition:

Roy lives in a city that is circular in shape on a 2D plane that has radius r. The city center is located at origin (0,0) and it has suburbs lying on the lattice points (points with integer coordinates). The city Police Department Headquarters can only protect those suburbs which are located strictly inside the city. The suburbs located on the border of the city are still unprotected. So the police department decides to build at most k additional police stations at some suburbs. Each of these police stations can protect the suburb it is located in.

Link

Circle City

Complexity:

time complexity is O(sqrt(N))

space complexity is O(1)

Execution:

You have to solve the circle equation M^2 + N^2 = D where M and N are integral numbers. There is an article on wiki.

Solution:
#!/usr/bin/py
from math import sqrt, ceil

def isCircleProtected(d, K):
    count = 0
    for m in xrange(int(ceil(sqrt(d)))):
        if sqrt(d - m*m).is_integer():
            count += 4
    
    return count <= K

if __name__ == '__main__':
    t = input()
    for _ in range(t):
    	d, k = map(int, raw_input().split())
        if (isCircleProtected(d, k)):
            print "possible"
        else:
            print "impossible"


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

Facebooktwittergoogle_plusredditpinterestlinkedin
04/6/15

The Aha! Moment

We have all experienced the great moments of clarity, when suddenly everything makes sense. Your heart starts beating faster, a smile creeps up on your face and you gain real wisdom – wisdom that changes your perception of the world. Some call this feeling the Eureka Effect based on a story of Archimedes jumping out of a public bathroom and shouting Eureka! as he realized how to solve a difficult problem he was facing. I prefer to call this experience the Aha! Moment based on the German Aha-Erlebnis as I am not an ancient Greek philosopher and I certainly do not like public bathrooms.

eureka-aha

You do not only encounter these moments when finally solving coding challenges, but when hearing jokes also. Have you ever heard a joke that did not seem funny at first? And right the second silence fell on the room, your brain finally made a click, you realized why the cute girl on the other side of the table was laughing so hysterically and you start laughing too. Just like… 3 seconds too late. It maybe does not happen to you, but it surely does happen to me and the wave of emotional satisfaction feels exactly the same like solving a hard coding problem.

These Aha! moments occur when your brain redistributes and reanalyzes the available information to forms a novel conclusion. The region of the brain responsible for this change is the hippocampus, widely know for its role in the formation of long- and short-term memory as well as spatial navigation.

Theoretically, “insight” means the reorientation of one’s thinking, including breaking of the unwarranted “fixation” and forming of novel, task-related associations among the old nodes of concepts or cognitive skills. Processes closely related to these aspects have been implicated in the hippocampus.

In their fMRI study Jing Luo & Kazuhisa Niki (abstract cited above) fabricated these experiences on a study group using Japanese riddles. As far as the riddles go I do understand that there are concepts that can not move a nail, but.. I do not feel any smarter after reading that the answer to the riddle is a river. I would not be a good study candidate. (I do love participating in brain imagining studies though and whenever I get the opportunity I participate gladly). What we should learn from that research (jokes aside) is that whenever you experience a Aha! moment, your brain just integrated new information into your memory and somehow connected it to whatever already was in there. That is important. That is why we all push our boundaries and challenge ourselves with previously unseen programming tasks. To force ourselves to be better, smarter and more versatile thinkers. Because after your hippocampus formed new connections, you will later discover them again and again, when you need them most.

Hippocampus


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

Facebooktwittergoogle_plusredditpinterestlinkedin