コーディング試験用基礎問 from HackerRank

f:id:trafalbad:20210127054815j:plain

Type : Array

Arrays: Left Rotation

Explanation
When we perform left rotations, the array undergoes the following sequence of changes:

Sample Input

5 4
1 2 3 4 5

Sample Output

5 1 2 3 4

Solution

def rotLeft(a, d):
    return a[d:] + a[:d]

2D Array - DS

6×6のarrayのうちhourglassは下の位置要素で16こ存在する。

a b c
  d
e f g

maximum hourglass sumを求めよ
Solution

def hourglass_sums(arr):
    sums=[]
    for w in range(4):
        for h in range(4):
            hourglass = arr[h][w]+arr[h][w+1]+arr[h][w+2]+arr[h+1][w+1]+arr[h+2][w]+arr[h+2][w+1]+arr[h+2][w+2]
            sums.append(hourglass)
    return max(sums)

New Year Chaos

Sample Input

STDIN       Function
-----       --------
2           t = 2
5           n = 5
2 1 5 3 4   q = [2, 1, 5, 3, 4]
5           n = 5
2 5 1 3 4   q = [2, 5, 1, 3, 4]

Sample Output

3
Too chaotic

Solution

def minimumBribes(q):
    bribes = 0
    q = [i-1 for i in q]
    # reverse loop
    for i in range(len(q)-1,-1,-1):
        if q[i] - i > 2:
            print('Too chaotic')
            return
        # get specified value in loop
        for j in range(max(0, q[i] - 2),i):
            if q[j] > q[i]:
                bribes+=1
    print(bribes)

Type：Dictionaries and Hashmaps

Two Strings

Sample Input

2
hello
world
hi
world

sample output

YES
NO

Solution

def twoStrings(s1, s2):
    for s in s1:
        if s in s2:
            return 'YES'
    return 'NO'

Count Triplets

For example, sample input

len=5 ratio=5
1 5 5 25 125

Sample Output

The triplets satisfying are index (0, 1,3), (0,2,3), (1,3,4), (2,3,4)

Solution

from collections import Counter

def countTriplets(arr, r):
    r2 = Counter()
    r3 = Counter()
    count = 0
    for p in arr:
        if p in r3:
            count += r3[p]
        if p in r2:
            r3[p*r] += r2[p]
        r2[p*r] +=1
    return count

type：Sorting

Mark and Toys

Prices = [1, 2, 3,4 ]
k=7

The budget is 7 units of currency. He can buy items that cost [1, 2, 3]for 6, or [3, 4]for 7units. The maximum is 3 items.
Sample input

7 50
1 12 5 111 200 1000 10]

Sample outout

He can buy only 4 toys at most. These toys have the following prices: .[1, 12,5, 10]

Solution

def maximumToys(prices, k):
    total = 0
    count = 0
    prices = sorted(prices)
    for p in prices:
        if p+total <= k:
            total += p
            count += 1
        else:
            return count

Fraudulent Activity Notifications

Sample Input 1

lens=5 days lens=4
1 2 3 4 4

Sample Output

There are 4 days of data required so the first day a notice might go out is 5 day . Our trailing expenditures are [1,2,3,4] with a median of The client spends 4 which is less than 2✖️2.5(median of [1,2,3,4]) so no notification is sent.

Solution

import bisect as bs
def index(arr, x):
    return bs.bisect_left(arr, x)


def median(days, d):
    half = len(days)//2
    if d%2==0:
        med = (days[half]+days[half-1])/2
    else:
        med = days[half]
    return med

def activityNotifications(expenditure, d):
    notifications = 0
    days = sorted(expenditure[:d])
    for i in range(d, len(expenditure)-1): 
        med = median(days, d)
        if expenditure[i]>=med*2:
            notifications+=1
        del days[index(days, expenditure[i-d])]
        idx = bs.bisect_left(days, expenditure[i])
        days.insert(idx, expenditure[i])
    return notifications

Greedy Algorithms

Minimum Absolute Difference in an Array

Given an array of integers, find the minimum absolute difference between any two elements in the array.

Sample input

5
1 -3 71 68 17

Sample output

Explanation
The minimum absolute difference is |71-68|=3

Solution

def minimumAbsoluteDifference(arr):
    arr = sorted(arr)
    minabs = abs(arr[0] - arr[1])
    for i in range(0, len(arr)-1):
        if abs(arr[i] - arr[i+1])<minabs:
            minabs = abs(arr[i] - arr[i+1])
    return minabs