05/6/19

# Posting Schedule Sprint/Summer 2019

This page has 85 HackerRank Tasks posted as of May 2019. After looking over my HR profile, I noticed that I had solved a total of 200 Tasks there. In other words, I have not posted the majority of them 🙂

I have also run out of Tasks marked as Easy. I still have around 60 Medium ones that need solving.

It is unlikely, that I can just clean all of that up in a single session. I have therefore created a posting rhythm that should allow me to get all that code up here within a reasonable time frame.

I will be posting five posts every week until the end of September. Four of those will be Tasks that I have solved in the past, and only minor cleanups are required. Additionally, I will be posting one new Medium or harder Task every week.

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

07/11/19

# HackerRank ‘Halloween Sale’ Solution

##### Short Problem Definition:

You wish to buy video games from the famous online video game store Mist.

Usually, all games are sold at the same price, p dollars. However, they are planning to have the seasonal Halloween Sale next month in which you can buy games at a cheaper price. Specifically, the first game you buy during the sale will be sold at dollars, but every subsequent game you buy will be sold at exactly d dollars less than the cost of the previous one you bought. This will continue until the cost becomes less than or equal to m dollars, after which every game you buy will cost m dollars each.

Halloween Sale

##### Complexity:

time complexity is O(1)

space complexity is O(1)

##### Execution:

The solution is based on the Arithmetic Progression. It makes it a bit more complex due to the floor m.

Another option is either a while loop or a recursion.

##### Solution:
```// Complete the howManyGames function below.
int howManyGames(int p, int d, int m, int s) {
int n=floor( (p-m)/d +1);
if( (n*(2*p-(n-1)*d))/2 <= s)
{
return n + (s-(n*(2*p-(n-1)*d)/2))/m;
}
else
{
return floor(((-d-2*p)+sqrt((-2*p-d)*(-2*p-d)-(8*d*s)))/(-2*d));
}
}
```

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

07/10/19

# HackerRank ‘The Time In Words’ Solution

##### Short Problem Definition:

Given the time in numerals we may convert it into words.

The Time In Words

##### Complexity:

time complexity is O(?)

space complexity is O(?)

##### Execution:

I might have hinted at my opinion in the past: Why do “challenges” like this even exist? It requires 0 brain power, but you will spend an hour figuring out the fine details of English and fixing bugs.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys

# Complete the timeInWords function below.
def timeInWords(h, m):
raise RuntimeError("Nope!")

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

h = int(raw_input())

m = int(raw_input())

result = timeInWords(h, m)

fptr.write(result + '\n')

fptr.close()

```

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

07/9/19

# HackerRank ‘Fair Rations’ Solution

##### Short Problem Definition:

You are the benevolent ruler of Rankhacker Castle, and today you’re distributing bread. Your subjects are in a line, and some of them already have some loaves. Times are hard and your castle’s food stocks are dwindling, so you must distribute as few loaves as possible according to the following rules:

1. Every time you give a loaf of bread to some person i, you must also give a loaf of bread to the person immediately in front of or behind them in the line (i.e., persons i+1 or i-1).
2. After all the bread is distributed, each person must have an even number of loaves.

Fair Rations

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

The solution can be approached from either the beginning or the end of the array.

Let’s examine the following observation: The first and last person in the array can only receive a loaf if the person next to them also got one.

If there is only one person in the array, it can never receive a loaf of bread. If there are two people in the array, both need to receive a loaf. If there are three people in the array either 0, 2 or 3 people receive a loaf. If there are any loaves awarded, the middle person has to receive at least 1.

Iterate the array from the beginning and always give the loaf to any person that does not meet criteria #2. Since the last person can never receive a loaf alone, check that for the final YES/NO decision.

##### Solution:
```#!/bin/python

import sys

N = int(raw_input().strip())
B = map(int,raw_input().strip().split(' '))

loafs = 0

for idx in xrange(N-1):
if B[idx] % 2 == 0:
continue
B[idx] += 1
B[idx+1] += 1
loafs += 2

if B[-1] % 2 == 1:
print "NO"
else:
print loafs
```
```# Rust
use std::io;

fn get_number() -> u32 {
let mut line = String::new();
line.trim().parse::<u32>().unwrap()
}

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn main() {
let n = get_number() as usize;
let mut b = get_numbers();
let mut loafs = 0;

for idx in 0..(n-1) {
if b[idx] % 2 == 0 {
continue;
}

b[idx] += 1;
b[idx+1] += 1;
loafs += 2;
}

if b[n-1] % 2 == 1 {
println!("{}", "NO");
} else {
println!("{}", loafs);
}

}
```

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

07/8/19

# HackerRank ‘Strange Counter’ Solution

##### Short Problem Definition:

Bob has a strange counter. At the first second, it displays the number 3. Each second, the number displayed by the counter decrements by 1 until it reaches 1.

The counter counts down in cycles. In next second, the timer resets to 2x the initial number for the prior cycle and continues counting down.

Strange Counter

##### Complexity:

time complexity is O(log(N))

space complexity is O(1)

##### Execution:

This is a ‘simple’ mathematical problem that requires no while loops. First, find out what cycle the value T belongs to. Secondly, determine the value at the end of the cycle. Go back T steps to figure out the exact value at T.

Be careful, this can easily int overflow in C++, if the input is large enough.

##### Solution:
```#include <bits/stdc++.h>

using namespace std;

// Complete the strangeCounter function below.
long strangeCounter(long t) {
return 6 * pow(2, floor(log2((t+2)/3))) - 2 - t;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

long t;
cin >> t;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

long result = strangeCounter(t);

fout << result << "\n";

fout.close();

return 0;
}
```

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

06/14/19

##### Short Problem Definition:

Happy Ladybugs is a board game having the following properties:

• A ladybug is happy only when it’s left or right adjacent cell (i.e., ) b[i+/-1] is occupied by another ladybug having the same color.

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

This challenge definition does not require a full sort. It only wants to know whether the array is sortable. Therefore we will assume that if there is at least one free slot, the array is sortable by color.

Further we will assume that each ladybug wants to have at least one neighbor with the same color. If there are two of the same color, the ladybug is happy.

If there is no empty space, the input array needs to be sorted correctly.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the happyLadybugs function below.
counter = Counter(b)
for key, value in counter.items():
if key != "_" and value == 1:
return "NO"

if "_" in b:
return "YES"

for idx in xrange(1, len(b)):
if b[idx] == b[idx-1] or b[idx] == b[idx+1]:
continue
else:
return "NO"

return "YES"

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

g = int(raw_input())

for g_itr in xrange(g):
n = int(raw_input())

b = raw_input()

fptr.write(result + '\n')

fptr.close()
```

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

06/13/19

# HackerRank ‘Absolute Permutation’ Solution

##### Short Problem Definition:

We define P to be a permutation of the first n natural numbers in the range
[1,n]. Let pos[i] denote the value at position i in permutation P using 1-based indexing.

P is considered to be an absolute permutation if |pos[i]-i| = K holds true for every i.

Absolute Permutation

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

The time complexity of this solution is a question as is always true with hash maps. It is either O(N), O(NlogN) or O(N^2) depending on your particular implementation and hash algorithm.

After I solved this, I looked at the editorial and was amazed by the complex algorithm that they proposed. This is much simpler. Yet I agree that the editorial is more time/space effective.

Iterate over the list of all values [1,N]. Use the lowest available value from the [1,N] pool. Either i-K or i+k, if i-K is not available.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys

# Complete the absolutePermutation function below.
def absolutePermutation(n, k):
solution = []
s = set(range(1,n+1))

for pos in xrange(1, n+1):
if pos-k in s:
solution.append(pos-k)
s.remove(pos-k)
elif pos+k in s:
solution.append(pos+k)
s.remove(pos+k)
else:
return [-1]

return solution

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(raw_input())

for t_itr in xrange(t):
nk = raw_input().split()

n = int(nk[0])

k = int(nk[1])

result = absolutePermutation(n, k)

fptr.write(' '.join(map(str, result)))
fptr.write('\n')

fptr.close()
```

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

06/12/19

# HackerRank ‘Repeated String’ Solution

##### Short Problem Definition:

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times. Given an integer, n, find and print the number of letters `a` in the first n letters of Lilah’s infinite string.

For example, if the string s = ‘abcac’ and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of `a` in the substring.

Repeated String

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

As with most simple problems, there are many ways to write the code that can achieve the correct result. I picked the one that seems the simplest and most Pythonesque.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys

# Complete the repeatedString function below.
def repeatedString(s, n):
n_per_string = s.count('a')
n_per_substring = s[0:n%len(s)].count('a')
return n_per_string * (n/len(s)) + n_per_substring

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
s = raw_input()
n = int(raw_input())
result = repeatedString(s, n)
fptr.write(str(result) + '\n')
fptr.close()
```

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

06/11/19

# HackerRank ‘Climbing The Leatherboard’ Solution

##### Short Problem Definition:

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

• The player with the highest score is ranked number 1 on the leaderboard.
• Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number

##### Complexity:

time complexity is O(N*log(N))

space complexity is O(1)

##### Execution:

I am not a fan of the Dense Rank. Standard Competition ranking makes much more sense.

1) In the Dense Rank, duplicates have no impact on the ranking, so they can be safely removed.

2) The array should be sorted. Since the value range is fairly small (10^5), counting sort would improve the theoretical O-notation to O(N).

3) Take advantage of built-in Python functionality. Bisect right finds an insertion point after potential duplicates, giving us the correct Dense Rank.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys
import bisect

# Complete the climbingLeaderboard function below.
res = []
s = sorted(list(set(scores)))
l = len(s)
for v in alice:
res.append(l - bisect.bisect_right(s, v) +1)

return res

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
scores_count = int(raw_input())
scores = map(int, raw_input().rstrip().split())
alice_count = int(raw_input())
alice = map(int, raw_input().rstrip().split())
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()

```

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

06/10/19

# The Various Flavors of Two-Phase Commits — Explained

Internally, NuoDB uses the two-phase commit protocol to manage the durability of user data. NuoDB also supports the X/Open XA protocol for synchronizing global transactions across multiple data stores. XA is also sometimes referred to as two-phase commit. The fundamental principles in both protocols are similar but serve different purposes. Let us explore the difference between these two protocols.

## A SINGLE TRANSACTION ACROSS TWO RESOURCES

Let us explore a simple use case. A simple application takes messages from one data source (outgoing_messages) and writes them to a new data source (incoming_messages). This is a fairly common use case if you read messages from a message queue such as Apache ActiveMQ and you write them to a database (such as NuoDB). The following code snippet shows this example in the corresponding SQL form.

```SQL> SELECT * FROM outgoing_messages;

ID     MSG
--- ---------

1  message 1

SQL> START TRANSACTION;
SQL> SELECT * FROM outgoing_messages;

ID     MSG
--- ---------

1  message 1

SQL> DELETE FROM outgoing_messages WHERE id=1;
SQL> INSERT INTO incoming_messages(id, msg) VALUES(1, 'message 1');
SQL> commit;
```

When executed in a single relational database, the two statements (insert and delete) are expected to behave according to the ACID guarantees. They either both succeed or they both fail. Throughout this article, we focus on the A(tomic) guarantee of ACID.

XA abstracts away the statements and transaction lifetime for scenarios where the tables live in different data stores. The following example is a simplified version of an ActiveMQ consumer that receives a message and writes it to NuoDB. Due to space constraints in this article, the code does not contain any setup or failure handling.

```​javax.jms.MessageConsumer consumer=xasession.createConsumer(queue);
MessageListener listener = NEW MessageListener() {
@Override
public void onMessage(Message msg) {
TextMessage msg1=(TextMessage)msg;

XAResource mqRes = xasession.getXAResource();
XAResource nuoRes = nuodbXAconn.getXAResource();

nuodbStmt.executeUpdate(String.format("insert into incoming_messages(id, msg) values(1, '%s')", msg1.getText()));

mqRes.END(xid, XAResource.TMSUCCESS);
nuoRes.END(xid, XAResource.TMSUCCESS);

mqRes.PREPARE(xid);
nuoRes.PREPARE(xid);

mqRes.commit(xid, FALSE);
nuoRes.commit(xid, FALSE);
}
};
```
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/6/19

# HackerRank ‘Almost Sorted’ Solution

##### Short Problem Definition:

Given an array of integers, determine whether the array can be sorted in ascending order using only one of the following operations one time.

1. Swap two elements.
2. Reverse one sub-segment.

Determine whether one, both or neither of the operations will complete the task. If both work, choose swap. For instance, given an array [2, 3, 5, 4] either swap the 4 and 5; or reverse them to sort the array. Choose swap.

Almost Sorted

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

I wrote this code 4 years ago and I already have no clue what it does. It is linear time and it works even today.

Today, I would have broken this logic down into smaller functions with clear purpose.

##### Solution:
```#!/usr/bin/py
def getReverseAction(arr):
is_sorted = True

low_idx = 0
high_idx = len(arr)-1

while (low_idx < high_idx and arr[low_idx] < arr[low_idx+1]):
low_idx += 1

if low_idx == high_idx:
print "yes"
return

while (high_idx > 0 and arr[high_idx] > arr[high_idx-1]):
high_idx -= 1

#print "low", low_idx, arr[low_idx]
#print "high", high_idx, arr[high_idx]

if low_idx == 0 or arr[high_idx] > arr[low_idx -1]:
#print "high index swapable"
if arr[high_idx] < arr[low_idx +1] or low_idx+1 == high_idx:
#print "high index swapable"
if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]:
#print "low index swapable"
if arr[low_idx] > arr[high_idx -1] or low_idx == high_idx-1:
#print "low index swapable"
low_idx_runner = low_idx+1
while (low_idx_runner < high_idx and arr[low_idx_runner] < arr[low_idx_runner+1]):
low_idx_runner += 1
if low_idx_runner == high_idx-1 or low_idx == high_idx-1:
print "yes"
print "swap", low_idx+1, high_idx+1
return

low_idx_runner = low_idx+1
while (low_idx_runner < high_idx and arr[low_idx_runner] > arr[low_idx_runner+1]):
low_idx_runner += 1

if low_idx_runner == high_idx:
if low_idx == 0 or arr[high_idx] > arr[low_idx -1]:
if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]:
print "yes"
print "reverse", low_idx+1, high_idx+1
return

print "no"

if __name__ == '__main__':
n = input()
arr = map(int, raw_input().split())
getReverseAction(arr)
```

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