03/31/15

HackerRank ‘Sherlock and Array’ Solution

Short Problem Definition:

Watson gives Sherlock an array A of length N. Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero.
Formally, find an i, such that, A1+A2…Ai-1 =Ai+1+Ai+2…AN

Link

Sherlock and Array

Complexity:

time complexity is O(n)

space complexity is O(1)

Execution:

I first solved the problem using prefix sums. Afterwards I realized that it can be done without additional space complexity.

Solution:
#!/usr/bin/py
def arraySherlock(a):   
   
    left_idx = 0
    right_idx = len(a) - 1
    
    left_sum = a[left_idx]
    right_sum = a[right_idx]
    
    while left_idx != right_idx:
        if left_sum < right_sum:
            left_idx += 1
            left_sum += a[left_idx]
        else:
            right_idx -= 1
            right_sum += a[right_idx]
    
    return left_sum == right_sum
    
if __name__ == '__main__':
    t = int(raw_input())
    for _ in xrange(t):
        n = int(raw_input())
        a = map(int, raw_input().split())
        if arraySherlock(a):
            print "YES"
        else:
            print "NO"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/30/15

Verbalize Your Thinking!

Solving new challenges can be hard. The harder it is, the more rewarding a solution feels. Sometimes, solutions written by other people work as a miraculous food for thought that opens doors into concepts you never thought of before. I would like this blog to be more than a reference that you know to visit when you are on search for solutions that you can copy-paste into the appropriate test window. I first started it as a self reference to keep track of my learning. The user base grows with every day and I think that we can do something positive with it. Not only will it support our learning process, but it will create interesting networking opportunities as well. Continue reading


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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/27/15

HackerRank ‘Count Luck’ Solution

Short Problem Definition:

Hermione Granger is lost in the Forbidden Forest while collecting some herbs for a magical potion. The forest is magical and has only one exit point, which magically transports her back to the Hogwarts School of Witchcraft and Wizardry.

Link

Count Luck

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

I solve this challenge using DFS and dynamic programming. I iterate over all n positions (denoted with .) using DFS. For each node, I remember the number of crossroads Hermione encountered up to that point. DFS does not guarantee to find the optimal solution in terms of path length.

Solution:
#!/usr/bin/py
from collections import defaultdict

def hermionesWand(arr, K, max_x, max_y):
    # find both entry and exit points
    for idx, line in enumerate(arr):
        for inner_idx in xrange(len(line)):
            if line[inner_idx] == 'M':
                h = (idx, inner_idx)
            if line[inner_idx] == '*':
                e = (idx, inner_idx)

    st = [h]
    tracker = defaultdict(int)
    tracker[h] = 0

    # iterate the DFS list
    while st:
        curr = st.pop()

        # exit found
        if (curr == e):
            return tracker[curr] == K

        # save all exits that were not visited before
        inner_st = set()
        if (curr[0] > 0 and (arr[curr[0]-1][curr[1]] == "." or arr[curr[0]-1][curr[1]] == "*")) \
        and (curr[0]-1, curr[1]) not in tracker:
            inner_st.add((curr[0]-1, curr[1]))
        if (curr[1] > 0 and (arr[curr[0]][curr[1]-1] == "." or arr[curr[0]][curr[1]-1] == "*")) \
        and (curr[0], curr[1]-1) not in tracker:
            inner_st.add((curr[0], curr[1]-1))
        if (curr[0] < max_y -1 and (arr[curr[0]+1][curr[1]] == "." or arr[curr[0]+1][curr[1]] == "*")) \
        and (curr[0]+1, curr[1]) not in tracker:
            inner_st.add((curr[0]+1, curr[1]))
        if (curr[1] < max_x -1 and (arr[curr[0]][curr[1]+1] == "." or arr[curr[0]][curr[1]+1] == "*")) \
        and (curr[0], curr[1]+1) not in tracker:
            inner_st.add((curr[0], curr[1]+1))

        # a crossroad
        if len(inner_st) > 1:
            tracker[curr] += 1

        # save the nodes to DFS list
        for n in inner_st:
            tracker[n] = tracker[curr]
            st.append(n)

    return False

if __name__ == '__main__':
    t = int(raw_input())
    for _ in xrange(t):
        n, m = map(int, raw_input().split())
        a = []
        for line in xrange(n):
            a.append(list(raw_input()))
        k = int(raw_input())
        if hermionesWand(a, k, m, n):
            print "Impressed"
        else:
            print "Oops!"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/26/15

HackerRank ‘Encryption’ Solution

Short Problem Definition:

An English text needs to be encrypted using the following encryption scheme.
First, the spaces are removed from the text. Let L be the length of this text.

Link

Encryption

Complexity:

time complexity is O(n)

space complexity is O(1)

Execution:

You do not need to create all the arrays. Just work with an offset and array slices.

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

if __name__ == '__main__':
    s = raw_input().replace(" ", "")
    columns = int(ceil(sqrt(len(s))))
    for c in xrange(columns):
        print s[[c::columns]],


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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/25/15

HackerRank ‘Ice Cream Parlor’ Solution

Short Problem Definition:

Sunny and Johnny together have M dollars they want to spend on ice cream. The parlor offers N flavors, and they want to choose two flavors so that they end up spending the whole amount.

You are given the cost of these flavors. The cost of the ith flavor is denoted by ci. You have to display the indices of the two flavors whose sum is M.

Link

Ice Cream Parlor

Complexity:

time complexity is O(n)

space complexity is O(1)

Execution:

I genuinely don’t like n^2 solutions. They scream for a better way. For this task, I struggled to find a better one. Binary search won’t work because of the possible duplicates. Especially special cases where every element is the same and M is double this element. You have to generate all combinations anyways (which is n^2 pairs).

UPDATE(18/05/16): I found an O(N) solution. As always the complexity of the hash-map can be disputed. I prefer tree-maps which would give us a guaranteed runtime complexity of O(N*log(N)).

Solution:
#!/usr/bin/py
def icecream(flavors, M):
    # O(N) complexity
    flavor_map = {}
    for idx, flavor in enumerate(flavors):
        residual = (M - flavor)
        if residual in flavor_map:
            return sorted([flavor_map[residual], idx])
        if not flavor in flavor_map:
            flavor_map[flavor] = idx
 
if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        m = input()
        n = input()
        flavors = map(int, raw_input().split())
        result_arr = icecream(flavors, m)
        print result_arr[0]+1, result_arr[1]+1

#!/usr/bin/py
def icecream(flavors, M):
    # O(N^2) complexity
    for idx in xrange(len(flavors)-1):
        for idx2 in xrange(idx+1, len(flavors)):
            if flavors[idx] + flavors[idx2] == M:
                return [idx+1, idx2]

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        m = input()
        n = input()
        flavors = map(int, raw_input().split())
        result_arr = icecream(flavors, m)
        print result_arr[0]+1, result_arr[1]+1

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/24/15

HackerRank ‘Sherlock and Pairs’ Solution

Short Problem Definition:

Sherlock is given an array of N integers A0, A1 … AN-1 by Watson. Now Watson asks Sherlock how many different pairs of indices i and j exist such that i is not equal to j but Ai is equal to Aj.

That is, Sherlock has to count total number of pairs of indices (i, j) where Ai = Aj AND i ≠ j.

Link

Sherlock and Pairs

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

The first step is to create a count of all integers. Next there are choose(k,2)*2 distinct pairs for each integer count (this step similar to Handshake, but you count i,j and j,i as two distinct pairs). Count those together and you arrive at the answer.

Solution:
#!/usr/bin/py
def cnt_equals(arr):
    the_map = {}
    final_cnt = 0
    for value in arr:
        if value not in the_map:
            the_map[value] = 1
        else:
            the_map[value] += 1

    for value in the_map.values():
        if value != 1:
            final_cnt += (value*(value-1))

    return final_cnt

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        arr = map(int, raw_input().split())
        print cnt_equals(arr)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/23/15

HackerRank ‘Handshake’ Solution

Short Problem Definition:

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Link

Handshake

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

I love this problem as it is a great reference for other pair solutions. There are choose(n,2) pairs in k elements. This reduces to n*(n-1)/2. The if/else branch is not required, but I like to keep it in to be more verbose.

Solution:
#!/usr/bin/py
def main():
    n = input()
    for _ in xrange(n):
        t = input()
        if (t == 1):
            print 0
        else:
            print t*(t-1)/2
            
    
if __name__ == '__main__':
    main()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/20/15

HackerRank ‘Sherlock and Watson’ Solution

Short Problem Definition:

John Watson performs an operation called Right Circular Rotation on an integer array [a0, a1, … an-1]. Right Circular Rotation transforms the array from [a0, a1, … aN-1] to [aN-1, a0,… aN-2].

He performs the operation K times and tests Sherlock’s ability to identify the element at a particular position in the array. He asks Q queries. Each query consists of one integer, idx, for which you have to print the element at index idx in in the rotated array, i.e., aidx.

Link

Sherlock and Watson

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

I could rotate the array before going into the test cases, but I can simply rotate the array on the fly by adding the rotation to the element index.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    n,k,q = map(int, raw_input().split())
    arr = map(int, raw_input().split())
    for _ in xrange(q):
        x = int(raw_input())
        print arr[(x-k)%n]

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/19/15

HackerRank ‘Closest Numbers’ Solution

Short Problem Definition:

Given a list of unsorted integers, A={a1,a2,…,aN}, can you find the pair of elements that have the smallest absolute difference between them? If there are multiple pairs, find them all.

Link

Closest Numbers

Complexity:

time complexity is O(n*log(n)) // sorting

space complexity is O(n)

Execution:

Just sort the array and print the smallest difference.

Solution:
#!/usr/bin/py
from sys import maxint

def closest(a):
    a.sort()
    smallest_difference = maxint
    smallest_pairs = []
    
    for idx in xrange(len(a)-1):
        diff = a[idx+1] - a[idx]
        if diff < smallest_difference:
            smallest_difference = diff
            smallest_pairs = [(a[idx], a[idx+1])]
        elif diff == smallest_difference:
            smallest_pairs.append((a[idx], a[idx+1]))
    
    for pair in smallest_pairs:
        print pair[0], pair[1],
    
if __name__ == '__main__':
    n = input()
    vec = map(int, raw_input().split())
    closest(vec)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/18/15

HackerRank ‘Service Lane’ Solution

Short Problem Definition:

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the highway and the service lane is N units. The service lane consists of N segments of equal length and different width.

Link

Service Lane

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

This challenge can be solved in a brute force manner. You just check for every entry/exit combination the biggest possible vehicle by min(arr[entry:exit+1]). Here, I will present a prefix sum solution with better runtime.

I create a prefix array, that saves the last entry point (or -1 if not possible) for this type of vehicle that comes before the current index (the exit point). Therefore, I can check for every entry/exit point the biggest possible type in constant time.

Solution:
#read
n,t = raw_input().split()
n = int(n)
t = int(t)
arr = map(int, raw_input().split())

#preprocess
last_possible_entry = []
for i, lane_width in enumerate(arr):
    last_car_entry = -1
    last_truck_entry = -1
    if lane_width > 1:
        last_car_entry = i
        if len(last_possible_entry) > 0 and last_possible_entry[-1][0] >= 0:
            last_car_entry = last_possible_entry[-1][0]
    
    if lane_width > 2:
        last_truck_entry = i
        if len(last_possible_entry) > 0 and last_possible_entry[-1][1] >= 0:
            last_truck_entry = last_possible_entry[-1][1]
       
    last_possible_entry.append([last_car_entry, last_truck_entry])

#get test cases    
for _ in xrange(t):
    i, j = map(int, raw_input().split())
    
    access_pattern = last_possible_entry[j]
    if access_pattern[1] != -1 and access_pattern[1] <= i:
        print "3"
    elif access_pattern[0] != -1 and access_pattern[0] <= i:
        print "2"
    else:
        print "1"
    
    

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

Facebooktwittergoogle_plusredditpinterestlinkedin