09/19/18

HackerRank ‘Sherlock and The Valid String’ Solution

Short Problem Definition:

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

Link

Sherlock and The Valid String

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

This is one of the easier medium problems. Create a character occurrence map. Then create an occurrence-occurrence map. If all the occurrences are the same (size is 1) the string is valid. If there is exactly one character that occurs exactly once, it is also valid. Otherwise invalid

Solution:
def isValid(S):
    char_map = Counter(S)
    char_occurence_map = Counter(char_map.values())

    if len(char_occurence_map) == 1:
        return True

    if len(char_occurence_map) == 2:
        for v in char_occurence_map.values():
            if v == 1:
                return True

    return False

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/18/18

HackerRank ‘String Construction’ Solution

Short Problem Definition:

Amanda has a string of lowercase letters that she wants to copy to a new string. She can perform the following operations with the given costs. She can perform them any number of times to construct a new string p:

  • Append a character to the end of string p at a cost of 1 dollar.
  • Choose any substring of p and append it to the end of  at no charge.
Link

String Construction

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

The solution sounds too easy, but it is still very simple. A substring of length 1 is still a substring. Each character in the final string needs to be copied once for 1$. Each other occurrence of that string can be copied for 0$. Aka just count the number of distinct letters in the expected string.

Solution:
def stringConstruction(s):
    return len(set(s))

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/17/18

HackerRank ‘Weighted Uniform Strings’ Solution

Short Problem Definition:

A weighted string is a string of lowercase English letters where each letter has a weight. Character weights are 1 to  26 from a to z…

Link

Weighted Uniform String

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Parsing the string for every query is suboptimal, so I first preprocess the string. Now we know that uniform strings contain the same characters. A string can be of length 1. Do a single pass of the string and create all uniform substrings.

Solution:
def weightedUniformStrings(s, queries):
    weights = set()
    prev = -1
    length = 0
    for c in s:
        weight = ord(c) - ord('a') + 1
        weights.add(weight)
        if prev == c:
            length += 1
            weights.add(length*weight)
        else:
            prev = c
            length = 1
    
    rval = []
    for q in queries:
        if q in weights:
            rval.append("Yes")
        else:
            rval.append("No")
    return rval

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/16/18

HackerRank ‘HackerRank in a String!’ Solution

Short Problem Definition:

We say that a string contains the word hackerrank if a subsequence of its characters spell the word hackerrank. For example, if string s = haacckkerrannkk  it does contain hackerrank, but s = haacckkerannk does not. In the second case, the second r is missing. If we reorder the first string as , it no longer contains the subsequence due to ordering.

Link

HackerRank in a String!

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Keep two pointers. One to the expected string (needle) and one to the input string. If you find the needle in the haystack before you run out of characters, you are good.

Solution:
def hackerrankInString(s):
    needle = 'hackerrank'
    idx_in_needle = 0
    for c in s:
        if c == needle[idx_in_needle]:
            idx_in_needle += 1
        if idx_in_needle == len(needle):
            break
            
    if idx_in_needle == len(needle):
        return "YES"
    else: 
        return "NO"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/15/18

HackerRank ‘Mars Exploration’ Solution

Short Problem Definition:

Sami’s spaceship crashed on Mars! She sends a series of SOS messages to Earth for help.

Link

Mars Exploration

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

We know that the message is basically a lot of concatenated SOS strings. There is no magic to this one.

Solution:
S = raw_input().strip()

errors = 0

for i in xrange(len(S)):
    if i % 3 == 0 and S[i] != 'S':
        errors += 1
    if i % 3 == 1 and S[i] != 'O':
        errors += 1
    if i % 3 == 2 and S[i] != 'S':
        errors += 1
        
        
print errors

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/13/18

HackerRank ‘CamelCase’ Solution

Short Problem Definition:

Alice wrote a sequence of words in CamelCase as a string of letters, , having the following properties:

  • It is a concatenation of one or more words consisting of English letters.
  • All letters in the first word are lowercase.
  • For each of the subsequent words, the first letter is uppercase and rest of the letters are lowercase.

Given s , print the number of words in s on a new line.

For example, s = OneTwoThree . There are 3 words in the string.

Link

CamelCase

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Since the input always has at least 1 character, we can assume that there will always be at least one word. Each upper case later identifies the next word. So the result is number of capital letters + 1.

Solution:
s = raw_input().strip()

cnt = 1

for c in s:
    if c.isupper():
        cnt += 1
        
print cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/12/18

HackerRank ‘Super Reduced String’ Solution

Short Problem Definition:

Steve has a string of lowercase characters in range ascii[‘a’..’z’]. He wants to reduce the string to its shortest length by doing a series of operations. In each operation he selects a pair of adjacent lowercase letters that match, and he deletes them. For instance, the string aab could be shortened to b in one operation.

Steve’s task is to delete as many characters as possible using this method and print the resulting string. If the final string is empty, print Empty String

Link

Super Reduced String

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

The solution creates a stack of values. If the top value on the stack is equivalent to the next value, simply remove both. This solution assumes that there are only ever 2 values next to each other. If any adjacent values were to be removed, I would require more loops.

Solution:
i = raw_input()

s = []

for c in i:
    if not s:
        s.append(c)
    else:
        if s[-1] == c:
            s.pop()
        else:
            s.append(c)
            
if not s:
    print "Empty String"
else:
    print ''.join(s)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/2/18

Why A Chairman Ain’t the Master Replica

INTRO

As a distributed, ACID-compliant database, we get a lot of questions about how NuoDB works, and how it compares to more well-known architectures. In particular, people want to understand how NuoDB compares to a master / master architecture, and (related) how we handle lock management. This post will discuss both. We will also discuss when shared-nothing architecture is viable and when conflicting decisions need to coordinated.

In this blog post, we will discuss the concept of Chairmanship, NuoDB’s answer to distributed coordination. We will prove that Chairmanship is both consistent and resilient to failure. But before we go into the details, let us explore the basics of NuoDB architecture.

Continue reading


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

Facebooktwittergoogle_plusredditpinterestlinkedin
07/5/18

Quick dive into NuoDB Architecture

Introduction

Traditionally, relational databases were designed for scale-up architectures. Supporting more clients or higher throughput required an upgrade to a larger server. Until recently, this meant that implementing a read & write scale-out architecture either required a NoSQL database and abandoning traditional relational database benefits, or relying on sharding and explicit replication. There were no solutions that could scale-out and still provide complete ACID (Atomicity, Consistency, Isolation, and Durability) -compliant semantics. This tension is what inspired the NewSQL movement and ultimately led to today’s modern “elastic SQL” databases.

NuoDB is an elastic SQL database designed with distributed application deployment challenges in mind. It’s a full SQL solution that provides all the properties of ACID-compliant transactions and standard relational SQL language support. It’s also designed from the start as a distributed system that scales the way a cloud service has to scale, providing high availability and resiliency with no single points of failure. Different from traditional shared-disk or shared nothing architectures, NuoDB’s patented database presents a new kind of peer-to-peer, on-demand independence that yields high availability, low-latency, and a deployment model that is easy to manage.

This article highlights the key concepts and architectural differences that set NuoDB apart from traditional relational databases and even other elastic SQL databases.

Continue reading


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

Facebooktwittergoogle_plusredditpinterestlinkedin
05/27/18

This page is GDPR compliant

Important Stuff

I haven’t posted in some period of time and I think that the time has finally come to,… *drum roll*… talk about something important.

I am proud to announce that Martinkysel.com is GDPR compliant. I know you are intrigued so let us examine how I managed this:

What is GDPR?

The goal of GDPR is to protect user’s personally identifying information (PII) and hold businesses to a higher standard when it comes to how they collect, store, and use this data.

Article 4 states that personal data means any information relating to an identified or identifiable natural person (‘data subject’)”.

“… an identifiable natural person is one who can be identified, directly or indirectly, in particular by reference to an identifier such as a name, an identification number, location number, an online identifier or to one or more factors specific to the physical, physiological, genetic, mental, economic, cultural or social identity of that natural person.”

What does this page store?

Nothing. Wicked cool, right?

Moral of the story

Don’t store data you don’t need.

In Related News

I am working on a large series of articles about SQL, that should appear on the NuoDB Techblog, stay tuned!


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

Facebooktwittergoogle_plusredditpinterestlinkedin