Short Problem Definition:

There is an array of  integers. There are also 2 disjoint sets, A and ,B each containing m integers. You like all the integers in set A and dislike all the integers in set B. Your initial happiness is 0. For each a integer in the array, if A, you add 1 to your happiness. If b in B, you add -1 to your happiness. Otherwise, your happiness does not change. Output your final happiness at the end.

Link

No Idea!

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Make sure that you convert A and B into sets to reduce the lookup times.

Solution:

def noIdea(N, A, B):
    happiness = 0

    A = set(A)
    B = set(B)

    for n in N:
        if n in A:
            happiness += 1
        elif n in B:
            happiness -= 1
    
    return happiness

Short Problem Definition:

Split the string S into chunks T. Remove duplicates from T.

Link

Merge The Tools

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

First, split the string into chunks. In Python 2, use an ordered dictionary (that preserves insertion order) to discard duplicates. An ordered set would work too. The basic Sets/Maps are already ordered in Python 3.

Solution:

from collections import OrderedDict

def merge_the_tools(string, k):
    chunks = [string[i:i+k] for i in range(0, len(string), k)]
    for chunk in chunks:
        print "".join(OrderedDict.fromkeys(chunk))

Short Problem Definition:

Kevin and Stuart want to play the ‘The Minion Game‘.

Game Rules

Both players are given the same string, S.
Both players have to make substrings using the letters of the string S.
Stuart has to make words starting with consonants.
Kevin has to make words starting with vowels.
The game ends when both players have made all possible substrings.

Link

The Minion Game

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Now, your brain might go straight to the generation of subsets. You might even start thinking about overlapping subsets. But you already know that each substring at position P starts with the same letter. Hence the solution is to iterate over the list once.

Solution:

def minion_game(string):
    vowels_list = set(['a','e','i','o','u','A','E','I','O','U'])
    consonants = 0
    vowels = 0

    n = len(string)
    for i, l in enumerate(string):
        if l in vowels_list:
            vowels += n-i
        else:
            consonants += n-i

    if vowels == consonants:
        print "Draw"
    elif vowels > consonants:
        print "Kevin {}".format(vowels)
    else:
        print "Stuart {}".format(consonants)

Short Problem Definition:

You are given a string and your task is to swap cases. In other words, convert all lowercase letters to uppercase letters and vice versa.

Link

sWAP cASE

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

I had too much fun with this one, so I refuse to admit that there is a buildin swapcase() function. ASCII can be fun.

Solution:

def swap_case(s):
    result = ""
    for idx in xrange(len(s)):
        ordinal = ord(s[idx])
        if (ordinal >= ord('a') and ordinal <= ord('z')) or \
            (ordinal >= ord('A') and ordinal <= ord('Z')):
            result += chr(ordinal-ord('A')+32)%64+ord('A'))
        else:
            result += s[idx]
    return result

Short Problem Definition:

A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given n integers, determine the primality of each integer and print whether it is Prime or Not prime on a new line.

Note: If possible, try to come up with an O(sqrt(N)) primality algorithm, or see what sort of optimizations you can come up with for an O(N) algorithm.

Link

Time Complexity: Primality

Complexity:

time complexity is O(sqrt(N))

space complexity is O(1)

Execution:

The point of this question is to make sure that you only iterate up to (including) sqrt(N).

Solution:

def primality(n):
    if n == 1:
        return False

    for i in xrange(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

Short Problem Definition:

You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

Link

Minimum Swaps 2

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This solution runs in O(N) since it will visit every element at most 2 times. No need for complex cycle algorithms, stacks, etc.

The trick is to put every element in the place it belongs to and swap it with the element at that position. It is possible that the swapped element wont be the correct once, hence the while loop.

Solution:

def minimumSwaps(arr):
    swaps = 0
    n = len(arr)

    for idx in xrange(n):
        while arr[idx]-1 != idx:
            ele = arr[idx]
            arr[ele-1], arr[idx] = arr[idx], arr[ele-1]
            swaps += 1
    return swaps

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(N)

Execution:

Anna is being fairly difficult. I hope that their relationship is otherwise healthy. As for the code: just follow the description.

Solution:

def bonAppetit(bill, k, b):
    should_have = (sum(bill) - bill[k])/2
    diff = b - should_have
    if (not diff):
        return "Bon Appetit"
    else:
        return diff

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

Sales By Match

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Count the occurrence of every element. Use integer division to eliminate unpaired socks.

Solution:

from collections import defaultdict

def sockMerchant(n, ar):
    d = defaultdict(int)

    for k in ar:
        d[k] += 1
        
    cnt = 0
    for ele in d.values():
        cnt += ele // 2
        
    return cnt

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. 

Link

Drawing Book

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

Think of this as a 0-indexed book. Use integer division.

Solution:

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

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  unit change in altitude. We define the following terms:

• A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
• A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Link

Counting Valleys

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I am a hiker myself, so this challenge is kinda funny. The description looks complex, but realistically one only needs to calculate whether the section was above or below sea level.

Solution:

def countingValleys(n, s):
    level = 0
    valleys = 0
    for direction in s:
        if direction == "U":
            level += 1
            if level == 0:
                valleys += 1
        else:
            level -= 1
            
    return valleys