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

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.

03/30/15

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.

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.

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 and (arr[curr-1][curr] == "." or arr[curr-1][curr] == "*")) \
and (curr-1, curr) not in tracker:
if (curr > 0 and (arr[curr][curr-1] == "." or arr[curr][curr-1] == "*")) \
and (curr, curr-1) not in tracker:
if (curr < max_y -1 and (arr[curr+1][curr] == "." or arr[curr+1][curr] == "*")) \
and (curr+1, curr) not in tracker:
if (curr < max_x -1 and (arr[curr][curr+1] == "." or arr[curr][curr+1] == "*")) \
and (curr, curr+1) not in tracker:

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.

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.

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.

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.

Ice Cream Parlor

##### Complexity:

time complexity is O(n)

space complexity is O(1)

##### Execution:

I genuinely don’t like n^2 solutions. But I could not find anything better.

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+1, result_arr+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+1, result_arr+1
```

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

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.

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.

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?

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.

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.

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.

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.

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, pair,

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.

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.

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:
last_car_entry = last_possible_entry[-1]

if lane_width > 2:
last_truck_entry = i
if len(last_possible_entry) > 0 and last_possible_entry[-1] >= 0:
last_truck_entry = last_possible_entry[-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 and access_pattern <= i:
print "3"
elif access_pattern != -1 and access_pattern <= i:
print "2"
else:
print "1"

```

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