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?

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.

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.

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.

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.,

Majority

##### Complexity:

time complexity is O(N^2)

space complexity is O(1)

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.

01/25/21

# Friend Circle Queries

##### Short Problem Definition:

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.

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

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.

10/25/20

# HackerRank ‘Simple Array Sum’ Solution

##### Short Problem Definition:

Given an array of integers, find the sum of its elements.

Simple Array Sum

##### Complexity:

time complexity is O(N)

space complexity is O(1)

Just sum it up.

##### Solution:
```def simpleArraySum(ar):
return sum(ar)
```

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

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.

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 = []

result.append(len(rows)*len(columns))

return result

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

print (' '.join(map(str, out_)))
```

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

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.

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.

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.

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

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])]

insort_left(running_median, ele)

return warnings

```

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

08/21/20

# HackerRank ‘Box It!’ Solution

##### Short Problem Definition:

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

Box It!

Does not apply.

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 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;}

//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.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}