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.

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:
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

return min_length_string

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

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.

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.

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.

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.

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…

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
if prev == c:
length += 1
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.

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.

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.