08/21/20

# HackerRank ‘C++ Rectangle Area’ Solution

##### Short Problem Definition:

Create two classes:

Rectangle
The Rectangle class should have two data fields-width and height of int types. The class should have display() method, to print the width and height of the rectangle separated by space.

RectangleArea
The RectangleArea class is derived from Rectangle class, i.e., it is the sub-class of Rectangle class. The class should have read_input() method, to read the values of width and height of the rectangle. The RectangleArea class should also overload the display() method to print the area width*height of the rectangle.

Rectangle Area

Does not apply.

##### Solution:
```// because cstdio is superior!
#include <cstdio>
/*
* Create classes Rectangle and RectangleArea
*/

class Rectangle {
public:
int width = 0;
int height = 0;

virtual void display() {
printf("%d %d\n", width, height);
}
};

class RectangleArea: public Rectangle {
public:
scanf("%d %d", &width, &height);
}

void display() override {
printf("%d\n", width*height);
}
};
```

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

08/21/20

##### Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. Two integers P and Q are called adjacent in array A if there exists an index 0 ≤ K < N−1 such that:

• P = A[K] and Q = A[K+1], or
• Q = A[K] and P = A[K+1].

A non-empty zero-indexed sequence B consisting of M integers is called adjacent in array A if the following conditions hold:

• B = A;
• B[M−1] = A[N−1];
• B[K] and B[K+1] are adjacent in A for 0 ≤ K < M−1.

##### Complexity:

time complexity is O(NlogN)

space complexity is O(N)

##### Execution:

This is a graph problem, the shortest adjacent sequence is basically a shortest path in a bidirectional graph.

To calculate the shortest path I am using Breath-first-search or Dijkstra’s algorithm.

I don’t agree with the problem specification of one of the extreme cases such as [1,2,1]. I believe that the shortest path is 3, since the beginning and end are not adjacent. But it seems that Codility expects 1.

##### Solution:
```from collections import defaultdict

def bfs_shortest_path(paths, start, end):
q = [(start, 1)]

visited_paths = set()

while q:
key, distance = q.pop(0)
new_distance = distance + 1
for path in paths[key]:
if path == end:
return new_distance
elif path not in visited_paths:
q.append((path, new_distance))

def solution(A):
if len(A) <= 2:
return len(A)

# I dont agree with this edge case based on the problem statement
if A == A[-1]:
return 1

paths = defaultdict(set)

for i in range(1, len(A)-1):

return bfs_shortest_path(paths, A, A[-1])
```

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

08/4/20

# HackerRank ‘Connecting Towns’ Solution

##### Short Problem Definition:

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Connecting Towns

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

This is a simple combinatorics problem. Even though python ints don’t overflow easily, I added the MOD anyways. The code in GoLang is also available.

##### Solution:
```MOD = 1234567

def main():
t = input()
for _ in xrange(t):
n = input()
arr = map(int, raw_input().split())
routes = 1
for value in arr:
routes = ( routes * value ) % MOD
print routes

if __name__ == '__main__':
main()
```

```func connectingTowns(n int32, routes []int32) int32 {
result := int32(1)
for _, value := range routes {
result = (result*value) % 1234567
}
return result
}
```

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

07/30/20

# HackerRank ‘Coffee Break Puzzle at Cisco: String Generation’ Solution

##### Short Problem Definition:

Watson and Sherlock are two leading researchers in Security and Cryptography at Cisco. They love to solve puzzles related to strings, number theory, encryptions and mapping in their free time. One fine day, during the coffee break, Watson comes up with a puzzle for Sherlock.

You know my powers, my dear Watson, and yet at the end of three months I was forced to confess that I had at last met an antagonist who was my intellectual equal.

Coffee Break Puzzle at Cisco: String Generation

Alternative name: Sherlock and String Generation

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

The rules are explained pretty clearly. There are three rules
1) each element has to occur at least once
2) odd elements occur odd number of times, even elements occur even times
3) the string has to be of length N

Let us compact those rules into examples:
1+2) mean that each element has to occur at least 1 or 2 times. The minimal string (a suffix really) is “abbcddeff” etc.
2+3) because of the length limitation, the string can only be the length of the minimal viable suffix (explained above) + a multiply of 2. You could add 2xA, 2xB etc making it “abbcddeffaa” for example. But not “abbcddeffa” because that would violate rule 2).
extra) the string has to be the minimal lexical variant of all the above rules. That means that you want to be pre-pending A’s to your string. Aka the previous one becomes “aaabbcddeff”.

##### Solution:
```def transform(x):
return chr(x+96)

def solve(N,K):
word = []
for i in xrange(1,K+1):
if i%2 == 0:
occurence = 2
else:
occurence = 1
word.extend([i]*occurence)

if (len(word) > N):
return "No such string."

remaining = N - len(word)
if remaining%2:
return "No such string."

prefix = *remaining
prefix.extend(word)

return ''.join(map(transform, prefix))
```

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

07/30/20

# HackerRank ‘No Idea!’ Solution

##### Short Problem Definition:

There is an array of  integers. There are also 2 disjoint sets, A and ,B each containing m integers. You like all the integers in set A and dislike all the integers in set B. Your initial happiness is 0. For each a integer in the array, if A, you add 1 to your happiness. If b in B, you add -1 to your happiness. Otherwise, your happiness does not change. Output your final happiness at the end.

No Idea!

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

Make sure that you convert A and B into sets to reduce the lookup times.

##### Solution:
```def noIdea(N, A, B):
happiness = 0

A = set(A)
B = set(B)

for n in N:
if n in A:
happiness += 1
elif n in B:
happiness -= 1

return happiness
```

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

07/30/20

# HackerRank ‘Merge The Tools’ Solution

##### Short Problem Definition:

Split the string S into chunks T. Remove duplicates from T.

Merge The Tools

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

First, split the string into chunks. In Python 2, use an ordered dictionary (that preserves insertion order) to discard duplicates. An ordered set would work too. The basic Sets/Maps are already ordered in Python 3.

##### Solution:
```from collections import OrderedDict

def merge_the_tools(string, k):
chunks = [string[i:i+k] for i in range(0, len(string), k)]
for chunk in chunks:
print "".join(OrderedDict.fromkeys(chunk))
```

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

07/30/20

# HackerRank ‘The Minion Game’ Solution

##### Short Problem Definition:

Kevin and Stuart want to play the ‘The Minion Game‘.

Game Rules

Both players are given the same string, S.
Both players have to make substrings using the letters of the string S.
Stuart has to make words starting with consonants.
Kevin has to make words starting with vowels.
The game ends when both players have made all possible substrings.

The Minion Game

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

Now, your brain might go straight to the generation of subsets. You might even start thinking about overlapping subsets. But you already know that each substring at position P starts with the same letter. Hence the solution is to iterate over the list once.

##### Solution:
```def minion_game(string):
vowels_list = set(['a','e','i','o','u','A','E','I','O','U'])
consonants = 0
vowels = 0

n = len(string)
for i, l in enumerate(string):
if l in vowels_list:
vowels += n-i
else:
consonants += n-i

if vowels == consonants:
print "Draw"
elif vowels > consonants:
print "Kevin {}".format(vowels)
else:
print "Stuart {}".format(consonants)
```

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

07/28/20

# HackerRank ‘sWAP cASE’ Solution

##### Short Problem Definition:

You are given a string and your task is to swap cases. In other words, convert all lowercase letters to uppercase letters and vice versa.

sWAP cASE

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

I had too much fun with this one, so I refuse to admit that there is a buildin swapcase() function. ASCII can be fun.

##### Solution:
```def swap_case(s):
result = ""
for idx in xrange(len(s)):
ordinal = ord(s[idx])
if (ordinal >= ord('a') and ordinal <= ord('z')) or \
(ordinal >= ord('A') and ordinal <= ord('Z')):
result += chr(ordinal-ord('A')+32)%64+ord('A'))
else:
result += s[idx]
return result
```

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

07/27/20

# HackerRank ‘Time Complexity: Primality’ Solution

##### Short Problem Definition:

prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given n integers, determine the primality of each integer and print whether it is `Prime` or `Not prime` on a new line.

Note: If possible, try to come up with an O(sqrt(N)) primality algorithm, or see what sort of optimizations you can come up with for an O(N) algorithm.

Time Complexity: Primality

##### Complexity:

time complexity is O(sqrt(N))

space complexity is O(1)

##### Execution:

The point of this question is to make sure that you only iterate up to (including) sqrt(N).

##### Solution:
```def primality(n):
if n == 1:
return False

for i in xrange(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
```

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

07/27/20

# HackerRank ‘Minimum Swaps 2’ Solution

##### Short Problem Definition:

You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

Minimum Swaps 2

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

This solution runs in O(N) since it will visit every element at most 2 times. No need for complex cycle algorithms, stacks, etc.

The trick is to put every element in the place it belongs to and swap it with the element at that position. It is possible that the swapped element wont be the correct once, hence the while loop.

##### Solution:
```def minimumSwaps(arr):
swaps = 0
n = len(arr)

for idx in xrange(n):
while arr[idx]-1 != idx:
ele = arr[idx]
arr[ele-1], arr[idx] = arr[idx], arr[ele-1]
swaps += 1
return swaps
```

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