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(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 &amp;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&amp; b)
        bool operator<(Box&amp; b) {
            return this->l < b.l ||
                (this->b < b.b &amp;&amp; this->l == b.l) ||
                (this->h < b.h &amp;&amp; this->b == b.b &amp;&amp; this->l == b.l);
        }
};

ostream&amp; operator<<(ostream&amp; out, Box&amp; 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
08/21/20

HackerRank ‘C++ Rectangle Area’ Solution

Short Problem Definition:

Create two classes:

Rectangle
The Rectangle class should have two data fields-width and height of int types. The class should have display() method, to print the width and height of the rectangle separated by space.

RectangleArea
The RectangleArea class is derived from Rectangle class, i.e., it is the sub-class of Rectangle class. The class should have read_input() method, to read the values of width and height of the rectangle. The RectangleArea class should also overload the display() method to print the area width*height of the rectangle.

Link

Rectangle Area

Complexity:

Does not apply.

Execution:

Solution:
// because cstdio is superior!
#include <cstdio>
/*
 * Create classes Rectangle and RectangleArea
 */

class Rectangle {
    public:
        int width = 0;
        int height = 0;

        virtual void display() {
            printf("%d %d\n", width, height);
        }
};

class RectangleArea: public Rectangle {
    public:
        void read_input() {
            scanf("%d %d", &amp;width, &amp;height);
        }

        void display() override {
            printf("%d\n", width*height);
        }
};


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

Facebooktwitterredditpinterestlinkedin
08/21/20

Codility ‘ShortestAdjSeq’ Solution

Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. Two integers P and Q are called adjacent in array A if there exists an index 0 ≤ K < N−1 such that:

  • P = A[K] and Q = A[K+1], or
  • Q = A[K] and P = A[K+1].

A non-empty zero-indexed sequence B consisting of M integers is called adjacent in array A if the following conditions hold:

  • B[0] = A[0];
  • B[M−1] = A[N−1];
  • B[K] and B[K+1] are adjacent in A for 0 ≤ K < M−1.
Link

ShortestAdjSeq

Complexity:

time complexity is O(NlogN)

space complexity is O(N)

Execution:

This is a graph problem, the shortest adjacent sequence is basically a shortest path in a bidirectional graph.

To calculate the shortest path I am using Breath-first-search or Dijkstra’s algorithm.

I don’t agree with the problem specification of one of the extreme cases such as [1,2,1]. I believe that the shortest path is 3, since the beginning and end are not adjacent. But it seems that Codility expects 1.

Solution:
from collections import defaultdict

def bfs_shortest_path(paths, start, end):
    q = [(start, 1)]

    visited_paths = set()
    visited_paths.add(start)

    while q:
        key, distance = q.pop(0)
        new_distance = distance + 1
        for path in paths[key]:
            if path == end:
                return new_distance
            elif path not in visited_paths:
                visited_paths.add(path)
                q.append((path, new_distance))


def solution(A):
    if len(A) <= 2:
        return len(A)

    # I dont agree with this edge case based on the problem statement
    if A[0] == A[-1]:
        return 1

    paths = defaultdict(set)

    paths[A[0]].add(A[1])
    paths[A[-1]].add(A[-2])

    for i in range(1, len(A)-1):
        paths[A[i]].add(A[i-1])
        paths[A[i]].add(A[i+1])

    return bfs_shortest_path(paths, A[0], A[-1])


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

Facebooktwitterredditpinterestlinkedin
08/4/20

HackerRank ‘Connecting Towns’ Solution

Short Problem Definition:

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Link

Connecting Towns

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This is a simple combinatorics problem. Even though python ints don’t overflow easily, I added the MOD anyways. The code in GoLang is also available.

Solution:
MOD = 1234567

def main():
    t = input()
    for _ in xrange(t):
        n = input()
        arr = map(int, raw_input().split())
        routes = 1
        for value in arr:
            routes = ( routes * value ) % MOD
        print routes
    
if __name__ == '__main__':
    main()

func connectingTowns(n int32, routes []int32) int32 {
    result := int32(1)
    for _, value := range routes {
        result = (result*value) % 1234567
    }
    return result
}

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

Facebooktwitterredditpinterestlinkedin
07/31/20

HackerRank ‘Product Distribution’ Solution

Short Problem Definition:

A company has requested to streamline their product allocation strategy, and given n products, each of which has an associated value, you are required to arrange these products into segments for processing. There are infinite segments indexed as 1, 2, 3 and so on.

Link

Product Distribution

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

There are a few things you need to keep in mind here:

  • the buckets must all be the same size and can not be empty
  • the last bucket can contain the remainder of the N/M elements
  • sort the array so that the largest values are as far out as possible

Keep an eye out for the edge conditions.

Solution:
MODULO = 1000000007

def maxScore(a, m):
    n = len(a)
    bucket = 1
    result = 0
    
    a.sort()
    
    i = 0
    while i + (2*m) <= n:
        result += sum(a[i:i+m])*bucket
        i += m
        bucket += 1
        
        result %= MODULO
        
    result += sum(a[i:])*bucket
    
    return result % MODULO


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

Facebooktwitterredditpinterestlinkedin
07/30/20

HackerRank ‘Coffee Break Puzzle at Cisco: String Generation’ Solution

Short Problem Definition:

Watson and Sherlock are two leading researchers in Security and Cryptography at Cisco. They love to solve puzzles related to strings, number theory, encryptions and mapping in their free time. One fine day, during the coffee break, Watson comes up with a puzzle for Sherlock.

You know my powers, my dear Watson, and yet at the end of three months I was forced to confess that I had at last met an antagonist who was my intellectual equal.

Link

Coffee Break Puzzle at Cisco: String Generation

Alternative name: Sherlock and String Generation

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

The rules are explained pretty clearly. There are three rules
1) each element has to occur at least once
2) odd elements occur odd number of times, even elements occur even times
3) the string has to be of length N

Let us compact those rules into examples:
1+2) mean that each element has to occur at least 1 or 2 times. The minimal string (a suffix really) is “abbcddeff” etc.
2+3) because of the length limitation, the string can only be the length of the minimal viable suffix (explained above) + a multiply of 2. You could add 2xA, 2xB etc making it “abbcddeffaa” for example. But not “abbcddeffa” because that would violate rule 2).
extra) the string has to be the minimal lexical variant of all the above rules. That means that you want to be pre-pending A’s to your string. Aka the previous one becomes “aaabbcddeff”.

Solution:
def transform(x):
    return chr(x+96)

def solve(N,K):
    word = []
    for i in xrange(1,K+1):
        if i%2 == 0:
            occurence = 2
        else:
            occurence = 1
        word.extend([i]*occurence)
    
    if (len(word) > N):
        return "No such string."
    
    remaining = N - len(word)
    if remaining%2:
        return "No such string."

    prefix = [1]*remaining
    prefix.extend(word)
    
    return ''.join(map(transform, prefix))


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

Facebooktwitterredditpinterestlinkedin