05/16/21

HackerRank ‘Real Estate Broker’ Solution

Short Problem Definition:

You are a real estate broker in ancient Knossos. You have m unsold houses, and each house j has an area, xj, and a minimum price, yj. You also have n clients, and each client i wants a house with an area greater than ai and a price less than or equal to bi.

Each client can buy at most one house, and each house can have at most one owner. What is the maximum number of houses you can sell?

Link

Real Estate Broker

Complexity:

time complexity is O(NlogN + MlogM + N*M)

space complexity is O(1)

Execution:

This challenge sounds pretty complex, but this greedy solution works perfectly. Sort houses by size, start selling the smallest houses first. Bigger houses can always be sold since there is a bigger pool of buyers for them. Sell each house to the buyer that has the smallest pool of money available.

Don’t overcomplicate the problem with graph algorithms 🙂

Solution:
#!/bin/python

from __future__ import print_function

import os
import sys

#
# Complete the realEstateBroker function below.
#
def realEstateBroker(clients, houses):
    houses = sorted(houses)
    clients = sorted(clients, key = lambda x: x[1])
    
    sold = 0
    
    for house in houses:
        for client in clients:
            if house[0] >= client[0] and house[1] <= client[1]:
                sold += 1
                clients.remove(client)
                break
    
    return sold

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

    nm = raw_input().split()

    n = int(nm[0])

    m = int(nm[1])

    clients = []

    for _ in xrange(n):
        clients.append(map(int, raw_input().rstrip().split()))

    houses = []

    for _ in xrange(m):
        houses.append(map(int, raw_input().rstrip().split()))

    result = realEstateBroker(clients, houses)

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

    fptr.close()


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

Facebooktwitterredditpinterestlinkedin
05/16/21

HackerRank ‘Balanced Strings’ Solution

Short Problem Definition:

Consider a string, s, consisting only of the letters a and b. We say that string s is balanced if both of the following conditions are satisfied:

  1. s has the same number of occurrences of a and b.
  2. In each prefix of s, the number of occurrences of a and b differ by at most 1.

Your task is to write a regular expression accepting only balanced strings.

Link

Balanced Strings

Execution:

Substrings can differ by at most 1 which means that the string must consist of either “ab” or “ba”. Write a regex as such.

Solution:
Regex_Pattern = r"^((ab)|(ba))*$"	# Do not delete 'r'.


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

Facebooktwitterredditpinterestlinkedin
02/5/21

HackerRank ‘Majority’ Solution

Short Problem Definition:

Neo has to save the world one last time. One of the battles has cost Neo his eyes. He has to fight the battle with the Deus ex machina.

In front of Neo is a set of N balls, each ball is color coded 0/1. Deus ex machina wants Neo to figure out which ball’s color is the majority ( appears more than > N/2 ). If his choice of ball is correct, Deus ex machina will reach a truce and let humans live and if Neo fails to identify the ball with the majority, the entire human race would be put back into matrix.

Neo being blind won’t be able to see the balls let alone figure out the ball with the majority. He seeks the Oracle’s help. Neo picks any two balls from the set and asks Oracle if they are of the same color or not. If they are the same color, the Oracle answers YES and if they are not, Oracle answers NO. We will call b0/1 as ball b with color 0/1 respectively. Majority exists in this set, i.e.,

Link

Majority

Complexity:

time complexity is O(N^2)

space complexity is O(1)

Requested By:

Soha

Execution:

I use exceptions to simplify the flow of the algorithm. The algorithm itself can be tested locally if you replace the areEqual function and create an array locally. This abstraction should make the flow of the algorithm clearer.

Disclaimer: the code gets 16/23 points. There must be more improvements possible. I am open to suggestions in the comments below.

The algorithm itself assumes that if two groups of elements of equal size are not equal they become irrelevant. Let’s say that we know that elements 0 and 1 are different. Hence we never have to look at them again.

Otherwise the algorithm uses an adapted N(logN) algorithm to compare all elements.

Solution:
#!/usr/bin/py

class MissingElementException(Exception):
    def __init__(self, a, b):
        self.a = a
        self.b = b
        
        
def areEqual(query, a ,b):
    if not a in query or not b in query[a]:
        raise MissingElementException(a, b)
    return query[a][b]

def algo(n, query):

    relevant_groups = []
    for i in xrange(0, n, 2):
        group = [i, i+1]
        relevant_groups.append(group)

    while relevant_groups:
        group_a = relevant_groups.pop(0)
        group_len = len(group_a)
        if areEqual(query, group_a[0], group_a[group_len//2]):
            while relevant_groups:
                group_b = relevant_groups.pop(0)
                group_len_b = len(group_b)
                if areEqual(query, group_b[0], group_b[group_len_b//2]):
                    if areEqual(query, group_a[0], group_b[0]):
                        group = group_a
                        group.extend(group_b)
                        relevant_groups.append(group)
                        break
                    else:
                        if group_len > group_len_b:
                            relevant_groups.append(group_a)
                            break
                        elif group_len < group_len_b:
                            relevant_groups.append(group_b)
                            break
                        else:
                            break
            if not relevant_groups:
                # this should be the answer
                return group_a[0]
    return query


def nextQuestion(n, plurality, lies, color, exact_lies, query):
    try:
        print algo(n, query)
    except MissingElementException as e:
        print "%ld % ld" % (e.a, e.b)
        
if __name__ == '__main__':
    vals = [int(i) for i in raw_input().strip().split()]
    query_size = input()
    query = {}
    for i in range(vals[0]):
        query[i] = {}

    for i in range(query_size):
        temp = [j for j in raw_input().strip().split()]
        if temp[2] == "YES":
            query[int(temp[0])][int(temp[1])] = 1
            query[int(temp[1])][int(temp[0])] = 1
        else:
            query[int(temp[0])][int(temp[1])] = 0
            query[int(temp[1])][int(temp[0])] = 0

    nextQuestion(vals[0], vals[1], vals[2], vals[3], vals[4], query)


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

Facebooktwitterredditpinterestlinkedin
01/25/21

Friend Circle Queries

Short Problem Definition:

Link

Friend Circle Queries

Complexity:

time complexity is O(n(logq+logn))

space complexity is O(N)

Execution:

This is a typical Union-find problem statement. The particular UF implementation I use does not track groups and their sizes. The best way to determine the current largest group is to assume that the group that was just merged is the largest one.

Solution:
#!/bin/python

import math
import os
import random
import re
import sys
from collections import defaultdict
 
"""UnionFind.py
 
Union-find data structure. Based on Josiah Carlson's code,
<a class="vglnk" href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912" rel="nofollow"><span>http</span><span>://</span><span>aspn</span><span>.</span><span>activestate</span><span>.</span><span>com</span><span>/</span><span>ASPN</span><span>/</span><span>Cookbook</span><span>/</span><span>Python</span><span>/</span><span>Recipe</span><span>/</span><span>215912</span></a>
with significant additional changes by D. Eppstein.
"""
 
class UnionFind:
    """Union-find data structure.
 
    Each unionFind instance X maintains a family of disjoint sets of
    hashable objects, supporting the following two methods:
 
    - X[item] returns a name for the set containing the given item.
      Each set is named by an arbitrarily-chosen one of its members; as
      long as the set remains unchanged it will keep the same name. If
      the item is not yet part of a set in X, a new singleton set is
      created for it.
 
    - X.union(item1, item2, ...) merges the sets containing each item
      into a single larger set.  If any item is not yet part of a set
      in X, it is added to X as one of the members of the merged set.
    """
 
    def __init__(self):
        """Create a new empty union-find structure."""
        self.weights = {}
        self.parents = {}
 
    def __getitem__(self, object):
        """Find and return the name of the set containing the object."""
 
        # check for previously unknown object
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object
 
        # find path of objects leading to the root
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]
 
        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root
 
    def __iter__(self):
        """Iterate through all items ever found or unioned by this structure."""
        return iter(self.parents)
 
    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        heaviest = max([(self.weights[r],r) for r in roots])[1]
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

# Complete the maxCircle function below.
def maxCircle(queries):
    uf = UnionFind()
    
    largest_element = 0
    result = []
    
    for query in queries:
        uf.union(query[0], query[1])
        current_grouping = uf.weights[uf[query[0]]]
        largest_element = max(largest_element, current_grouping)
        result.append(largest_element)
        
    return result

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

    q = int(raw_input())

    queries = []

    for _ in xrange(q):
        queries.append(map(int, raw_input().rstrip().split()))

    ans = maxCircle(queries)

    fptr.write('\n'.join(map(str, ans)))
    fptr.write('\n')

    fptr.close()


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

Facebooktwitterredditpinterestlinkedin
01/24/21

HackerRank ‘Game of Maximization’ Solution

Short Problem Definition:

There are n piles of stones, where the ith pile has ai stones. You need to collect the maximum number of stones from these piles

Link

Stones Problem

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This challenge is fairly simple. It does not matter how those stones are arranged. The only important bit is that either the sum of all even elements is bigger than the sum of all odd elements or vice versa.

Solution:
def maximumStones(arr):
    return 2*min(sum(arr[0::2]), sum(arr[1::2]))

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

Facebooktwitterredditpinterestlinkedin
10/25/20

HackerEarth ‘Cells in a matrix’ Solution

Short Problem Definition:

You are given an integer N denoting an N×N matrix. Initially, each cell of the matrix is empty. You are given K tasks. In each task, you are given a cell (i,j) where cell (i,j) represents the ith row and jth column of the given matrix.

You have to perform each task sequentially in the given order. Each task is described in cell (i,j). For each task, you have to place X in each cell of row i and each cell column j. After you complete each task, you are required to print the number of empty cells in the matrix.  

Link

Cells In A Matrix

Complexity:

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

space complexity is O(N)

Execution:

There are many solutions to this problem statement. I picked this one, since its easy to understand and is correct.

Solution:
def cells_sol (N, K, tasks):
    rows = set([i+1 for i in xrange(N)])
    columns = set([i+1 for i in xrange(N)])
    result = []

    for task in tasks:
        rows.discard(task[0])
        columns.discard(task[1])
        result.append(len(rows)*len(columns))

    return result
    

N, K = map(int, raw_input().split())
task = []
for _ in range(K):
    i, j = map(int, raw_input().split())
    X = i, j
    task.append(X)


out_ = cells_sol(N, K, task)
print (' '.join(map(str, out_)))


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

Facebooktwitterredditpinterestlinkedin
10/25/20

HackerRank ‘Possible Path’ Solution

Short Problem Definition:

Adam is standing at point (a,b) in an infinite 2D grid. He wants to know if he can reach point (x,y) or not. The only operation he can do is to move to point (a+b, b) (a, b+a) (a-b, b), or (a, b-a) from some point (a,b). It is given that he can move to any point on this 2D grid, i.e., the points having positive or negative (or ) co-ordinates.

Tell Adam whether he can reach  or not.

Link

Possible Path

Complexity:

time complexity is O(log(N))

space complexity is O(1)

Execution:

The problem statement is not requesting the path from A,B to X,Y, just that a path exists. This makes it a mathematical problem.

We know that GCD(a, b) == GCD(a+b, b) == GCD(a-b, b). Why? Because if something is a divisor D of B, adding/subtracting B from any number A that is also divisible by D will not change the divisibility requirement.

Hence GCD(a, b) == GCD(a+n*b, b+m*a) where n, m are integers.

Following the rules, we can realize that GCD(a+n*b, b+m*a) is GCD(x, y), which leads us to the final solution.

Solution:
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def solve(a, b, x, y):
    return gcd(a,b) == gcd(x,y)


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

Facebooktwitterredditpinterestlinkedin
08/28/20

HackerRank ‘Fraudulent Activity Notifications’ Solution

Short Problem Definition:

HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is greater than or equal to 2x the client’s median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn’t send the client any notifications until they have at least that trailing number of prior days’ transaction data.

Link

Fraudulent Activity Notification

Complexity:

time complexity is O(N^2)

space complexity is O(N)

Execution:

I am not very happy with this solution, but it passes the tests, so I am posting it. This solution is running in O(N^2) due to the element removal from the running_median. del l[i] is O(N). O(NlogN) would be preferable.

The expenditures are actually not very large numbers [0..200], so there might be space for optimization there.

Solution:
from bisect import bisect_left, insort_left


def activityNotifications(expenditure, d):
    warnings = 0
    
    running_median = sorted(expenditure[:d])
    for i,ele in enumerate(expenditure):
        if i < d:
            continue
                            
        if d % 2 == 1:
            median = running_median[d//2]
        else:
            median = (running_median[d//2 - 1] + running_median[d//2])/float(2)
            
        if ele >= median*2:
            warnings += 1
            
        # remove previous element
        del running_median[bisect_left(running_median, expenditure[i-d])]
        
        # add new element
        insort_left(running_median, ele)

    return warnings


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

Facebooktwitterredditpinterestlinkedin
08/21/20

HackerRank ‘Box It!’ Solution

Short Problem Definition:

Design a class named Box whose dimensions are integers and private to the class.

Link

Box It!

Complexity:

Does not apply.

Execution:

Does not apply.

Solution:
// The class should have the following functions : 
class Box {
    private:
        int l=0;
        int b=0;
        int h=0;
    public:
// Constructors: 
        // Box();
        Box() = default;
        // Box(int,int,int);
        Box(int len, int bre, int hei):
            l(len), b(bre), h(hei) {};
        // Box(Box);
        Box(Box &other):
            l(other.l), b(other.b), h(other.h) {};

        // int getLength(); // Return box's length
        int getLength() { return l;}
        // int getBreadth (); // Return box's breadth
        int getBreadth() { return b;}
        // int getHeight ();  //Return box's height
        int getHeight() { return h;}

        // long long CalculateVolume(); // Return the volume of the box
        long long CalculateVolume() { return (long long) l*b*h;}

        //Overload operator < as specified
        //bool operator<(Box& b)
        bool operator<(Box& b) {
            return this->l < b.l ||
                (this->b < b.b && this->l == b.l) ||
                (this->h < b.h && this->b == b.b && this->l == b.l);
        }
};

ostream& operator<<(ostream& out, Box& b) {
    out << b.getLength() << " ";
    out << b.getBreadth() << " ";
    out << b.getHeight() << " ";

    return out;
}


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

Facebooktwitterredditpinterestlinkedin