06/14/19

HackerRank ‘Happy Ladybugs’ Solution

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.
Link

Happy Ladybugs

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.
def happyLadybugs(b):
    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()

        result = happyLadybugs(b)

        fptr.write(result + '\n')

    fptr.close()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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
Link

Climbing The Leaderboard

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.
def climbingLeaderboard(scores, alice):
    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())
    result = climbingLeaderboard(scores, alice)
    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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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;
 
                NuoXADataSource nuodbDs = NEW NuoXADataSource();
                XAConnection nuodbXAconn = nuodbDs.getXAConnection(DBA_USER, DBA_PASSWORD);
 
                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);
            }
        };
Continue reading
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

If you have solved this in a readable way, please share!

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/5/19

HackerRank ‘Picking Numbers’ Solution

Short Problem Definition:

Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is less than or equal to 1. For example, if your array is a = [1, 1, 2, 2, 4, 4, 5, 5, 5], you can create two subarrays meeting the criterion:  [1 ,1 ,2 ,2] and [4, 4, 5, 5, 5]. The maximum length subarray has 5 elements.

Link

Picking Numbers

Complexity:

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

space complexity is O(N)

Execution:

There is a simple solution. Sort the array and iterate over it, counting pairs. But I don’t like it.

The solution proposed here never sorts the array. Depending on the O-complexity of a map implementation, it could be O(N) or O(NlogN).

The idea is to check the +/-1 neighbors of each value as you iterate over them.

Solution:
from collections import defaultdict

def pickingNumbers(a):
    d = defaultdict(int)
    r_val = 0
    for val in a:
        d[val] += 1
        r_val = max(r_val, d[val]+d[val+1], d[val]+d[val-1])

    return r_val

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/4/19

HackerRank ‘Cats And A Mouse’ Solution

Short Problem Definition:

Two cats and a mouse are at various positions on a line. You will be given their starting positions. Your task is to determine which cat will reach the mouse first, assuming the mouse doesn’t move and the cats travel at equal speed. If the cats arrive at the same time, the mouse will be allowed to move and it will escape while they fight.

Link

Cats And A Mouse

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

This feels like a very simplistic version of Codility Fish. Just implement the specification.

Solution:
#!/bin/python

import sys

q = int(raw_input().strip())
for a0 in xrange(q):
    x,y,z = raw_input().strip().split(' ')
    x,y,z = [int(x),int(y),int(z)]
    catA = abs(x-z)
    catB = abs(y-z)
    if (catA < catB):
        print "Cat A"
    elif (catB < catA):
        print "Cat B"
    else:
        print "Mouse C"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/3/19

HackerRank ‘Electronics Shop’ Solution

Short Problem Definition:

Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the 2 items, given her budget.

Given the price lists for the store’s keyboards and USB drives, and Monica’s budget, find and print the amount of money Monica will spend. If she doesn’t have enough money to both a keyboard and a USB drive, print -1 instead. She will buy only the two required items.

Link

Electronics Shop

Complexity:

time complexity is O(N*M)

space complexity is O(1)

Execution:

This is one of the problem specifications that feel like there has to be a better solution. The solution presented here is naive and is O(N*M). Given that this is categorized as easy, I assumed that I can get away with this simple solution.

One could sort one of the arrays and use binary search to find the ideal match, this would result in O(N*log(N)).

Solution:
#!/bin/python

def getMoneySpent(keyboards, drives, s):
    spend = -1
    for dr in drives:
        for kb in keyboards:
            cnt = dr+kb
            if cnt <= s and cnt > spend:
                spend = cnt
    return spend
            
s,n,m = raw_input().strip().split(' ')
s,n,m = [int(s),int(n),int(m)]

keyboards = map(int, raw_input().strip().split(' '))
drives = map(int, raw_input().strip().split(' '))

moneySpent = getMoneySpent(keyboards, drives, s)
print(moneySpent)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/3/19

HackerRank ‘Minimum Time Required’ Solution

Short Problem Definition:

You are planning production for an order. You have a number of machines that each have a fixed number of days to produce an item. Given that all the machines operate simultaneously, determine the minimum number of days to produce the required order.

Link

Minimum Time Required

Complexity:

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

space complexity is O(1)

Execution:

This problem statement is a typical binary search challenge. It has a function (the sum of production) that changes in relation to some linear variable (time).

The bounds can be limited by the minimal and maximal production of each machine in the array. This means that the range is 1-10*9, but for most cases, it will be more constrained. It is a big number, but if the function is fast enough, it can be solved in a reasonable time.

There are 10*5 machines, there are completely independent and we have to visit all of them for each iteration. There is no point in memoizing or preprocessing any values, since they change with every iteration.

Hence the time complexity is O(N * log(10*9)).

P.S I always take forever to get binary search right. I should keep a templated (lambda) version of it available, for problems such as this one.

Solution:
#!/bin/python

import math
import os
import random
import re
import sys

# Complete the minTime function below.
def minTime(machines, goal):
    low_bound = goal * min(machines) // len(machines)
    high_bound = goal * max(machines) // len(machines) + 1

    while low_bound < high_bound:
        days = (low_bound+high_bound) // 2
        produced = sum([days // machine for machine in machines])
        if produced >= goal:
            high_bound = days
        else:
            low_bound = days + 1
    
    return low_bound

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

    nGoal = raw_input().split()

    n = int(nGoal[0])

    goal = int(nGoal[1])

    machines = map(long, raw_input().rstrip().split())

    ans = minTime(machines, goal)

    fptr.write(str(ans) + '\n')

    fptr.close()


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

Facebooktwittergoogle_plusredditpinterestlinkedin