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
06/2/19

HackerRank ‘Counting Valleys’ Solution

Short Problem Definition:

Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary’s hikes start and end at sea level and each step up or down represents a 1 unit change in altitude.

Link

Counting Valleys

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

All is required is a simple counter.

I find this problem specification oddly satisfying since I am currently finishing off my list of 48 4000 footers in New Hampshire, US.

Solution:
#!/bin/python

n = input()
s = raw_input()

level = 0
valleys = 0
for direction in s:
    if direction == "U":
        level += 1
        if level == 0:
            valleys += 1
    else:
        level -= 1
        
print valleys

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/2/19

HackerRank ‘Drawing Book’ Solution

Short Problem Definition:

Brie’s Drawing teacher asks her class to open their books to a page number. Brie can either start turning pages from the front of the book or from the back of the book. She always turns pages one at a time. When she opens the book, page 1 is always on the right side.

Link

Drawing Book

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

Integral division here again. No padding required.

Solution:
#!/bin/python

import sys

def solve(n, p):
    last_letter = n // 2
    goal_letter = p // 2
    return min(goal_letter, last_letter-goal_letter)

n = int(raw_input().strip())
p = int(raw_input().strip())
result = solve(n, p)
print(result)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/2/19

HackerRank ‘Sock Merchant’ Solution

Short Problem Definition:

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

Link

Sock Merchant

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Group the same color together. Look out for the integer division // that discards the odd socks.

Solution:
#!/bin/python

import sys
from collections import defaultdict

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

d = defaultdict(int)
for k in c:
    d[k] += 1
    
cnt = 0
for ele in d.values():
    cnt += ele//2
    
print cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/2/19

HackerRank ‘Bon Appétit’ Solution

Short Problem Definition:

Anna and Brian are sharing a meal at a restaurant and they agree to split the bill equally. Brian wants to order something that Anna is allergic to though, and they agree that Anna won’t pay for that item. Brian gets the check and calculates Anna’s portion. You must determine if his calculation is correct.

Link

Bon Appétit

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Follow the specification.

Solution:
#!/bin/python

n, k = map(int, raw_input().split())
c = map(int, raw_input().split())
charge = input()

should_have = (sum(c) - c[k])/2
diff = charge - should_have
if not diff:
    print "Bon Appetit"
else:
    print diff

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

Facebooktwittergoogle_plusredditpinterestlinkedin
05/23/19

HackerRank ‘Day Of The Programmer’ Solution

Short Problem Definition:

Marie invented a Time Machine and wants to test it by time-traveling to visit Russia on the Day of the Programmer (the 256th day of the year) during a year in the inclusive range from 1700 to 2700.

Link

Day of The Programmer

Complexity:

time complexity is O(-1)

space complexity is O(-1)

Execution:

As I have pointed out in the past, no engineer should ever implement any calendar related functions. It should be done natively by the language or by a library.

I am fairly certain that the conventions will change by 2700 🙂 and the calculation will be invalid.

Solution:
#!/bin/python

import math
import os
import random
import re
import sys

# Complete the dayOfProgrammer function below.
def dayOfProgrammer(year):
    raise SystemError("This challenge is stupid")

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

    year = int(raw_input().strip())

    result = dayOfProgrammer(year)

    fptr.write(result + '\n')

    fptr.close()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
05/22/19

HackerRank ‘Migratory Birds’ Solution

Short Problem Definition:

You have been asked to help study the population of birds migrating across the continent. Each type of bird you are interested in will be identified by an integer value. Each time a particular kind of bird is spotted, its id number will be added to your array of sightings. You would like to be able to find out which type of bird is most common given a list of sightings. Your task is to print the type number of that bird and if two or more types of birds are equally common, choose the type with the smallest ID number.

Link

Migratory Birds

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I provide two solutions to this challenge. Solution #1 is using the Counter collection in python and works well.

The second solution is more explicit and takes advantage of the restrictive challenge specification.

Solution:
#!/bin/python

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

# Complete the migratoryBirds function below.
def migratoryBirds(arr):
    mc = Counter(arr)
    return mc.most_common(1)[0][0]

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

    arr_count = int(raw_input().strip())

    arr = map(int, raw_input().rstrip().split())

    result = migratoryBirds(arr)

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

    fptr.close()
# Complete the migratoryBirds function below.
def migratoryBirds(arr):
    frequencies = [0] * 6

    for ele in arr:
        frequencies[ele] += 1

    max_val = 0
    max_idx = 5
    
    for idx in xrange(5, 0, -1):
        if frequencies[idx] >= max_val:
            max_idx = idx
            max_val = frequencies[idx]

    return max_idx

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

Facebooktwittergoogle_plusredditpinterestlinkedin
05/21/19

HackerRank ‘Birthday Chocolate’ Solution

Short Problem Definition:

The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID’s. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.

Link

Birthday Chocolate

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Keep track of Melements at a time. Basically a simplified prefix sum.

Solution:
#!/bin/python

import sys

def getWays(squares, d, m):
    cnt = 0
    q = squares[:m-1]
    for ele in squares[m-1:]:
        q.append(ele)
        if (sum(q) == d):
            cnt += 1
        q.pop(0)
    return cnt

n = int(raw_input().strip())
s = map(int, raw_input().strip().split(' '))
d,m = raw_input().strip().split(' ')
d,m = [int(d),int(m)]
result = getWays(s, d, m)
print(result)


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

Facebooktwittergoogle_plusredditpinterestlinkedin