05/8/19

HackerRank ‘Birthday Cake Candles’ Solution

Short Problem Definition:

You are in charge of the cake for your niece’s birthday and have decided the cake will have one candle for each year of her total age. When she blows out the candles, she’ll only be able to blow out the tallest ones. Your task is to find out how many candles she can successfully blow out.

Birthday Cake Candles

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Keep track of the tallest one along with the count.

Solution:
#!/bin/python

import sys

n = int(raw_input().strip())
height = map(int,raw_input().strip().split(' '))

cnt = 0
running_top = 0
for candle in height:
if (candle > running_top):
cnt = 1
running_top = candle
elif candle == running_top:
cnt += 1

print cnt


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

05/7/19

HackerRank ‘A Very Big Sum’ Solution

Short Problem Definition:

Calculate and print the sum of the elements in an array, keeping in mind that some of those integers may be quite large.

A Very Big Sum

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Just add all of this together. No magic.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
t = input()
n = map(int, raw_input().split())
print sum(n)


# 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() {
get_number();
let sum = get_numbers().iter().fold(0u64, |a, &amp;b| a + b as u64);
println!("{}", sum)
}


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

05/6/19

HackerRank ‘New Year Chaos’ Solution

Short Problem Definition:

It’s New Year’s Day and everyone’s in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to N at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n = 8 and Person 5 bribes Person 4, the queue will look like this: 1, 2, 3, 5, 4, 6, 7, 8.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

New Year Chaos

Complexity:

time complexity is O(N^2)

space complexity is O(1)

Execution:

This task is solvable in O(N), but I first attempted to solve the Naive way. This same solution times if the inner loop is allowed to start at 0. Limiting the search to one position ahead of the original position passes all HR tests cases.

The moral of the story? Why write 100 lines of code, if 8 are enough.

Solution:
def minimumBribes(q):
moves = 0
for pos, val in enumerate(q):
if (val-1) - pos > 2:
return "Too chaotic"
for j in xrange(max(0,val-2), pos):
if q[j] > val:
moves+=1
return moves


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

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.

04/3/19

Distributed Transactional Locks

As I explained in a previous blog post, sometimes MVCC is not sufficient and an operation needs to block out all other concurrent modifications. NuoDB is able to lock three types of lockable resources: tables, schemas, and sequences. A resource can either be locked in SHARED mode (which still allows record modification, but no metadata modification) or EXCLUSIVE which prevents any concurrent modification.

EXCLUSIVE access is required for DDL that visits all records (various index operations for example) and distributed concurrent access is not possible. Exclusive access can also be used by operations that need to work around MVCC write skew anomalies.

SHARED locks need to be fast, consume as little memory as possible, involve no additional nodes in the cluster, and cause no additional messaging.

EXCLUSIVE locks, on the other hand, need to pay the cost.

MVCC uses row locks to serialise updates to a single record. Both transactional locks and row locks participate in the same deadlock detection process, but are otherwise independent. The following table explains the interaction between transactional locks and MVCC row locks. If you are interested in how row locks work, I recommend reading our MVCC blog series.

Row Locks (DML) / Transactional LocksSharedExclusive
selectNo ConflictNo Conflict
insert, update, delete, select for updateNo ConflictConflict
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

04/3/19

How Transaction Locks support Zero Overhead Distributed DML

Let us imagine a scenario that needs to prevent MVCC write skews…

One transaction increases the salary of everyone in a department by 10%; another transaction inserts a new employee with a salary X. Since the two transactions do not conflict, MVCC does not prevent either of them from committing. After both resolve, the overall salary in the department could be above the budget. To prevent a similar situation, the application developer might want to have exclusive access to the table.

NuoDB 3.2.2 exposes a new type of lock that guarantees exclusive access to a resource across the distributed cluster. We call them Transactional Locks and they are the underlying mechanism powering the new NuoDB LOCK statement.

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

09/24/18

What I discovered using a simple challenge during interviews

Can coders code?

When I was looking for a simple programming task that I can use to evaluate candidates, I had the following criteria in mind:

• solvable within 10 min
• does not require obscure algorithmic knowledge
• has potential for further discussion
• not language specific

I went through my list of simple problems (I only considered the easy ones) and I stumbled across Pairs. I instantly realized, that it is the perfect question. There is a brute force solution, the specification can be expanded, we can talk about sorting, hashing, hash collisions, Big-O notation and cases when the input does not fit in memory. Even Bloom Filters are a viable topic of discussion.

My first interview was planned and I was thrilled. I would use the challenge and it would be great! The first three candidates I exposed to the task failed horribly. They could not implement the brute force solution O(n^2) without bugs in the code. I was horrified. Is the industry really this bad? Can programmers really not program?

In the last 3 years I used this little coding task in almost 50 interviews and the failure rate is alarming. Only two people managed to solve it flawlessly. They both accepted the offer and I have been thrilled to work with them ever since. There have been others that got stuck in the weeds but nevertheless showed an ability to think. Kudos to those! I will expand on the definition of flawlessly below.

I adjust the -pass- criteria accordingly to the person’s experience (people who graduated a long time ago might not remember what Big-O is), title (did they code in the last job?), future job duties (are they supposed to code?) and the prowess with which they claim that they know how to program. Support engineers that have had limited exposure to python and shell are fine with something that resembles code. People that have been in the industry for a decade better be ready to go through at least 3 iterations of increasing complexity.

Before reading on, I suggest that you go and solve that challenge. I will wait….

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

09/22/18

HackerRank ‘The Power Sum’ Solution

Short Problem Definition:

Find the number of ways that a given integer, X , can be expressed as the sum of the Nth powers of unique, natural numbers.

For example, if X = 13 and N = 2, we have to find all combinations of unique squares adding up to 13. The only solution is 2^2 + 3^2.

The Power Sum

Complexity:

time complexity is O(N!)

space complexity is O(1)

Execution:

This solution does not use DP or memoisation, but it does not time out. We know that it needs to explore all P! possible combinations where P is floor(sqrt(X, N)). Since maximum X is 1000, this should still compute in real time.

Keep in mind that all integers in the solution have to be unique. So for X = 3, the solution 1^2 + 1^2 + 1^2 is not acceptable.

Did I mention that I dislike both NP-Hard problems and recursion? No? So, now you know.

Solution:
def powerSum(X, N, current = 1):
pw = pow(current, N)
if pw &gt; X:
return 0
elif pw == X:
return 1
else:
return powerSum(X, N, current+1) + powerSum(X-pw, N, current+1)


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

09/21/18

HackerRank ‘Lily’s Homework’ Solution

Short Problem Definition:

Whenever George asks Lily to hang out, she’s busy doing homework. George wants to help her finish it faster, but he’s in over his head! Can you help George understand Lily’s homework so she can hang out with him?

Consider an array of m distinct integers, arr = [a[0], a[1], …, a[n-1]]. George can swap any two elements of the array any number of times. An array is beautiful if the sum of |a[i] – a[i-1] among 0 < i < n is minimal.

Lily’s Homework

Complexity:

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

space complexity is O(N)

Execution:

Let us rephrase the problem to a sorting problem: Find the number of swaps to make the array sorted. We need to consider both ascending and descending arrays. The solution assumes no duplicates.

Solution:
def cntSwaps(arr):
positions = sorted(list(enumerate(arr)), key=lambda e: e[1])
swaps = 0

for idx in xrange(len(arr)):
while True:
if (positions[idx][0] == idx):
break
else:
swaps += 1
swapped_idx = positions[idx][0]
positions[idx], positions[swapped_idx] = positions[swapped_idx], positions[idx]

return swaps

def lilysHomework(arr):
return min(cntSwaps(arr), cntSwaps(arr[::-1]))


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

09/20/18

HackerRank ‘HackerRank Bear and Steady Gene’ Solution

Short Problem Definition:

A gene is represented as a string of length N (where  is divisible by 4), composed of the letters A, C, G, and T. It is considered to be steady if each of the four letters occurs exactly 1/4 times. For example, GACT and AAGGCCTT are both steady genes.

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

A bit of trivia: I’ve looked at this problem a couple times 2 years ago and I could not figure it out. Sometimes it is good to take a long break 🙂

In the first pass I establish how many occurrences there are of each character. Then I establish how many are missing to make the string steady. Remember that the number of occurrences needs to be evenly distributed.

The second pass takes advantage of the caterpillar method. I am looking for the shortest string that contains all the extra characters. They need to be replaced by the missing characters. All others can just be replaced with the same character. The caterpillar extends as long as it does not hit one of the extra characters. It shortens if it contains more extra characters than are needed.

Solution:
def steadyGene(gene):
min_length_string = len(gene)

occurences = dict()
occurences['A'] = 0
occurences['G'] = 0
occurences['C'] = 0
occurences['T'] = 0

expected = len(gene) // 4

for g in gene:
occurences[g] += 1

for x in occurences:
occurences[x] = max(0, occurences[x] - expected)

if occurences['A'] == 0 and occurences['G'] == 0 and occurences['C'] == 0 and occurences['T'] == 0:
return 0

found = dict()
found['A'] = 0
found['G'] = 0
found['C'] = 0
found['T'] = 0

tail = 0

if found['A'] >= occurences['A'] and \
found['C'] >= occurences['C'] and \
found['G'] >= occurences['G'] and \
found['T'] >= occurences['T']:
# this is a valid candidate

# try to shorten it
while found[gene[tail]] > occurences[gene[tail]]:
found[gene[tail]] -= 1
tail += 1