From 67b9dea15af0368e171925d2992bb4a4c17d9cd6 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Mon, 25 Apr 2022 21:10:21 -0500
Subject: some hacker rank and leetcode code for aws interview prep. It turned
 out I was not tested with either code or whiteboard.

---
 sources/hacker_rank_leet_code.py    | 338 ++++++++++++++++++++++++++++++++++++
 tests/test_hacker_rank_leet_code.py | 212 ++++++++++++++++++++++
 2 files changed, 550 insertions(+)
 create mode 100644 sources/hacker_rank_leet_code.py
 create mode 100644 tests/test_hacker_rank_leet_code.py

diff --git a/sources/hacker_rank_leet_code.py b/sources/hacker_rank_leet_code.py
new file mode 100644
index 0000000..19ae189
--- /dev/null
+++ b/sources/hacker_rank_leet_code.py
@@ -0,0 +1,338 @@
+from typing import Callable, Any
+
+
+def is_leap(year):
+    if year % 4 == 0:
+        if year % 100 == 0:
+            if year % 400 == 0:
+                return True
+            else:
+                return False
+        else:
+            return True
+    else:
+        return False
+
+
+def runner_up(arr, reverse=False):
+    if reverse:
+        arr.sort(reverse=True)
+    else:
+        arr.sort()
+    max = arr[-1]
+
+    for i in range(len(arr) - 1, -1, -1):
+        if arr[i] == max:
+            continue
+        else:
+            return arr[i]
+    return max
+
+
+def second_lowest(records):
+    arr = [a[1] for a in records]
+    second_l = runner_up(arr, True)
+    ans = [a[0] for a in records if a[1] == second_l]
+    ans.sort()
+    return ans
+
+
+def average_mark(records, name):
+    return sum(records[name]) / len(records[name])
+
+
+def diagnoal_diff(square_matrix):
+    sum1 = 0
+    sum2 = 0
+    n = len(square_matrix)
+    for i in range(len(square_matrix)):
+        sum1 = sum1 + square_matrix[i][i]
+        sum2 = sum2 + square_matrix[i][n - i - 1]
+    return abs(sum1 - sum2)
+
+
+def substring_count(s, subs):
+    ans = 0
+    for i in range(len(s)):
+        j = s[i:].find(subs)
+        if j >= 0:
+            ans = ans + 1
+            if j == len(s) - 1:
+                return ans
+            else:
+                return ans + substring_count(s[j + 1:], subs)
+        else:
+            return ans
+
+
+def minion_game(s):
+    ans = {}
+    s = s.lower()
+    vowels = ['a', 'e', 'i', 'o', 'u']
+
+    # l = len(s)
+    # for i in range(l):
+    #     for j in range(l-i):
+    #         if s[i:i+j+1] in ans:
+    #             ans[s[i:i+j+1]] = ans[s[i:i+j+1]] + 1
+    #         else:
+    #             ans[s[i:i+j+1]] = 1
+    # stuart = 0
+    # kevin = 0
+    # for k in ans:
+    #     if k[0] in vowels:
+    #         kevin = kevin + ans[k]
+    #     else:
+    #         stuart = stuart + ans[k]
+
+    stuart = 0
+    kevin = 0
+    for i in range(len(s)):
+        if s[i] in vowels:
+            kevin = kevin + len(s) - i
+        else:
+            stuart = stuart + len(s) - i
+
+    if stuart > kevin:
+        return "Stuart " + str(stuart)
+    else:
+        if stuart == kevin:
+            return "Draw"
+        else:
+            return "Kevin " + str(kevin)
+
+
+def top_k_words_692(string_list, k):
+    string_list = sorted(string_list)
+    freq_dict = {}
+    for i in string_list:
+        if i in freq_dict:
+            freq_dict[i] = freq_dict[i] + 1
+        else:
+            freq_dict[i] = 1
+
+    freq_dict = dict(sorted(freq_dict.items(), key=lambda item: (item[1], ord(item[0][0]) * -1), reverse=True))
+    ans = [None] * k
+    for i in range(k):
+        ans[i] = list(freq_dict)[i]
+
+    return ans
+
+
+def reorder_data_in_log_937(logs):
+    letter_log = [l for l in logs if not l.split()[1].isdigit()]
+    digit_log = [l for l in logs if l.split()[1].isdigit()]
+    letter_log = sorted(letter_log, key=lambda x: (x.split(" ", 1)[1], x.split()[0]))
+    return letter_log + digit_log
+
+
+def run_length(input):
+    if len(input) == 0:
+        return ""
+    running_character = input[0]
+    running_count = 0
+    output = ""
+
+    for i in range(len(input)):
+        if input[i] == running_character:
+            running_count = running_count + 1
+        else:
+            output = output + str(running_count) + running_character
+            running_character = input[i]
+            running_count = 1
+    return output + str(running_count) + input[-1]
+
+
+def binary_search(input, element):
+    left = 0
+    right = len(input) - 1
+    while left <= right:
+        mid = left + int((right - left) / 2)
+        if input[mid] == element:
+            return mid
+        if input[mid] > element:
+            right = mid - 1
+        else:
+            left = mid + 1
+    return -1
+
+
+def find_boundary_brute(input):
+    if input[0]:
+        return 0
+    left = 0
+    right = len(input) - 1
+    while left <= right:
+        mid = left + int((right - left) / 2)
+        if not input[mid]:
+            left = mid + 1
+        if input[mid]:
+            while input[mid]:
+                mid = mid - 1
+            return mid + 1
+    return -1
+
+
+def find_boundary(input):
+    ans = -1
+    left = 0
+    right = len(input) - 1
+    while left <= right:
+        mid = left + int((right - left) / 2)
+        if input[mid]:
+            ans = mid
+            right = mid - 1
+        else:
+            left = mid + 1
+    return ans
+
+
+def first_not_smaller(input, target):
+    ans = -1
+    left, right = 0, len(input) - 1
+    while left <= right:
+        mid = left + (right - left) // 2
+        if input[mid] >= target:
+            ans = mid
+            right = mid - 1
+        else:
+            left = mid + 1
+    return ans
+
+
+def find_first_occurrence(input, target):
+    ans = -1
+    left, right = 0, len(input) - 1
+    while left <= right:
+        mid = left + (right - left) // 2
+        if input[mid] == target:
+            ans = mid
+            right = mid - 1
+        else:
+            left = mid + 1
+    return ans
+
+
+def square_root(input):
+    if input == 0:
+        return 0
+    ans = 0
+    left, right = 1, input
+    while left <= right:
+        mid = left + (right - left) // 2
+        if mid ** 2 > input:
+            ans = mid
+            right = mid - 1
+        else:
+            left = mid + 1
+    return ans - 1
+
+
+def find_min_rotated(input):
+    for i in range(1, len(input)):
+        if input[i] <= input[0]:
+            return i
+    return 0
+
+
+def peak_of_mountain_array(input):
+    ans = -1
+    left = 0
+    right = len(input) - 1
+    while left <= right:
+        mid = left + int((right - left) / 2)
+        if input[mid] > input[mid + 1]:
+            ans = mid
+            right = mid - 1
+        else:
+            left = mid + 1
+    return ans
+
+
+def min_max_weight(weights, days):
+    return 0
+
+
+def countAnalogusArrays(consecutiveDifference, lowerBound, upperBound):
+    arrayLength = len(consecutiveDifference) + 1
+    counter = 0
+    candidateArray = []
+
+    for i in range(arrayLength):
+        seed = lowerBound + i
+        candidateArray.append(seed)
+        currentMember = seed
+        for j in range(lowerBound, upperBound + 1, 1):
+            if len(candidateArray) == arrayLength:
+                break
+            nextMember = currentMember - consecutiveDifference[j - lowerBound]
+            if nextMember > upperBound:
+                candidateArray = []
+                break
+            if nextMember < lowerBound:
+                candidateArray = []
+                break
+            candidateArray.append(nextMember)
+            currentMember = nextMember
+        if len(candidateArray) == arrayLength:
+            counter = counter + 1
+        candidateArray = []
+    return counter
+
+def minimalHeaviestSetA(arr):
+    arr.sort(reverse = True)
+    total_weight = sum(arr)
+    running_total = 0
+    ans = []
+
+    for i in range(len(arr)):
+        ans.append(arr[i])
+        running_total = running_total + arr[i]
+        if running_total > total_weight / 2:
+            break
+    ans.sort()
+    return ans
+
+def getNumberOfOptions(priceOfJeans, priceOfShoes, priceOfSkirts, priceOfTops, dollars):
+    count = 0
+    running_total = 0
+    for a in priceOfTops:
+        for b in priceOfSkirts:
+            for c in priceOfJeans:
+                for d in priceOfShoes:
+                    if a + b + c + d <= dollars:
+                        count = count + 1
+    return count
+
+def howManySwaps(arr):
+    swaps = 0
+    temp = 0
+    for i in range(len(arr)):
+        for j in range(i+1, len(arr)):
+            if arr[i] > arr[j]:
+                temp = arr[i]
+                arr[i] = arr[j]
+                arr[j] = temp
+                swaps = swaps + 1
+    return swaps
+
+def storage(n, m, h, v):
+    h_list = list(range(n))
+    v_list = list(range(m))
+
+    for i in h:
+        del h_list[i - 1]
+    for i in v:
+        del v_list[i - 1]
+
+    max_width = 0
+    for i in range(len(h_list) - 1):
+        if h_list[i+1] - h_list[i] > max_width:
+            max_width = h_list[i+1] - h_list[i]
+
+    max_height = 0
+    for i in range(len(v_list) - 1):
+        if v_list[i+1] - v_list[i] > max_height:
+            max_height = v_list[i+1] - v_list[i]
+
+    return abs(max_width * max_width)
\ No newline at end of file
diff --git a/tests/test_hacker_rank_leet_code.py b/tests/test_hacker_rank_leet_code.py
new file mode 100644
index 0000000..0e6b4a6
--- /dev/null
+++ b/tests/test_hacker_rank_leet_code.py
@@ -0,0 +1,212 @@
+import unittest
+from sources.hacker_rank_leet_code import is_leap, \
+    runner_up, second_lowest, average_mark, diagnoal_diff, \
+    minion_game, substring_count, top_k_words_692, reorder_data_in_log_937, \
+    run_length, binary_search, find_boundary, first_not_smaller, \
+    find_first_occurrence, square_root, find_min_rotated, \
+    peak_of_mountain_array, min_max_weight, countAnalogusArrays, \
+    minimalHeaviestSetA, getNumberOfOptions, howManySwaps, storage
+
+
+class MyTestCase(unittest.TestCase):
+    def test_is_leap(self):
+        self.assertEqual(False, is_leap(1990))
+        self.assertEqual(True, is_leap(2000))
+        self.assertEqual(True, is_leap(2400))
+        self.assertEqual(False, is_leap(1800))
+        self.assertEqual(False, is_leap(1900))
+        self.assertEqual(False, is_leap(2100))
+        self.assertEqual(False, is_leap(2200))
+        self.assertEqual(False, is_leap(2300))
+        self.assertEqual(False, is_leap(2500))
+
+    def test_runner_up(self):
+        arr = [2, 3, 6, 6, 5]
+        self.assertEqual(5, runner_up(arr))
+        self.assertEqual(3, runner_up(arr, True))
+
+    def test_second_lowest(self):
+        # students = [["Harry", 37.21], ["Berry", 37.21], ["Tina", 37.2], ["Akriti", 41], ["Harsh", 39]]
+        students = [[]] * 5
+        students[0] = ["Harry", 37.21]
+        students[1] = ["Berry", 37.21]
+        students[2] = ["Tina", 37.2]
+        students[3] = ["Akriti", 41]
+        students[4] = ["Harsh", 39]
+        self.assertEqual('Berry', second_lowest(students)[0])
+
+    def test_average_mark(self):
+        student_marks = {}
+        student_marks['Krishna'] = [67, 68, 69]
+        student_marks['Arjun'] = [70, 98, 63]
+        student_marks['Malika'] = [52, 56, 60]
+        self.assertEqual(56, average_mark(student_marks, 'Malika'))
+        student_marks.clear()
+        student_marks['Harsh'] = [25, 26.5, 28]
+        student_marks['Malika'] = [26, 28, 30]
+        self.assertEqual(26.5, average_mark(student_marks, 'Harsh'))
+
+    def test_diagnoal_diff(self):
+        square_matrix = [[]] * 3
+        square_matrix[0] = [1, 2, 3]
+        square_matrix[1] = [4, 5, 6]
+        square_matrix[2] = [9, 8, 9]
+        self.assertEqual(2, diagnoal_diff(square_matrix))
+        square_matrix = [[]] * 3
+        square_matrix[0] = [11, 2, 4]
+        square_matrix[1] = [4, 5, 6]
+        square_matrix[2] = [10, 8, -12]
+        self.assertEqual(15, diagnoal_diff(square_matrix))
+
+    def test_substring_count(self):
+        s = "banana"
+        subs = "ana"
+        self.assertEqual(2, substring_count(s, subs))
+        subs = "a"
+        self.assertEqual(3, substring_count(s, subs))
+
+    def test_minion_game(self):
+        s = "BANANA"
+        self.assertEqual("Stuart 12", minion_game(s))
+
+    def test_top_k_words_692(self):
+        words = ["i", "love", "leetcode", "i", "love", "coding"]
+        self.assertEqual("i", top_k_words_692(words, 2)[0])
+        self.assertEqual("love", top_k_words_692(words, 2)[1])
+
+        words = ["i", "love", "leetcode", "i", "love", "coding"]
+        self.assertEqual("i", top_k_words_692(words, 3)[0])
+        self.assertEqual("love", top_k_words_692(words, 3)[1])
+        self.assertEqual("coding", top_k_words_692(words, 3)[2])
+
+        words = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"]
+        self.assertEqual("the", top_k_words_692(words, 4)[0])
+        self.assertEqual("is", top_k_words_692(words, 4)[1])
+        self.assertEqual("sunny", top_k_words_692(words, 4)[2])
+        self.assertEqual("day", top_k_words_692(words, 4)[3])
+
+        words = ["aaa", "aa", "a"]
+        self.assertEqual("a", top_k_words_692(words, 1)[0])
+
+    def test_reorder_data_in_log_937(self):
+        logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]
+        self.assertEqual(["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 8 1 5 1", "dig2 3 6"],
+                         reorder_data_in_log_937(logs))
+
+        logs = ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"]
+        self.assertEqual(["g1 act car", "a8 act zoo", "ab1 off key dog", "a1 9 2 3 1", "zo4 4 7"],
+                         reorder_data_in_log_937(logs))
+
+        logs = ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo", "a2 act car"]
+        self.assertEqual(["a2 act car", "g1 act car", "a8 act zoo", "ab1 off key dog", "a1 9 2 3 1", "zo4 4 7"],
+                         reorder_data_in_log_937(logs))
+
+    def test_run_length(self):
+        input = "aaaabbccc"
+        self.assertEqual("4a2b3c", run_length(input))
+        input = "aaaabbccca"
+        self.assertEqual("4a2b3c1a", run_length(input))
+        input = "abcd"
+        self.assertEqual("1a1b1c1d", run_length(input))
+        input = ""
+        self.assertEqual("", run_length(input))
+        input = "a"
+        self.assertEqual("1a", run_length(input))
+
+    def test_binary_search(self):
+        input = [1, 2, 3, 4, 5, 6]
+        self.assertEqual(2, binary_search(input, 3))
+        input = [1, 2, 3, 4, 5, 6]
+        self.assertEqual(-1, binary_search(input, 7))
+        input = [1]
+        self.assertEqual(-1, binary_search(input, 7))
+        input = [1]
+        self.assertEqual(0, binary_search(input, 1))
+        input = [1, 3, 5, 7, 8]
+        self.assertEqual(2, binary_search(input, 5))
+
+    def test_find_boundary(self):
+        input = [False, False, False, True, True, True]
+        self.assertEqual(3, find_boundary(input))
+        input = [False]
+        self.assertEqual(-1, find_boundary(input))
+        input = [False, False, True, True, True]
+        self.assertEqual(2, find_boundary(input))
+        input = [True]
+        self.assertEqual(0, find_boundary(input))
+        input = [True, True, True, True, True]
+        self.assertEqual(0, find_boundary(input))
+
+    def test_first_not_smaller(self):
+        input = [1, 3, 3, 5, 8, 8, 10]
+        target = 2
+        self.assertEqual(1, first_not_smaller(input, target))
+        input = [2, 3, 5, 7, 11, 13, 17, 19]
+        target = 6
+        self.assertEqual(3, first_not_smaller(input, target))
+
+    def test_find_first_occurence(self):
+        input = [1, 3, 3, 3, 3, 6, 10, 10, 10, 100]
+        target = 3
+        self.assertEqual(1, find_first_occurrence(input, target))
+        input = [2, 3, 5, 7, 11, 13, 17, 19]
+        target = 6
+        self.assertEqual(-1, find_first_occurrence(input, target))
+
+    def test_square_root(self):
+        input = 16
+        self.assertEqual(4, square_root(input))
+        input = 8
+        self.assertEqual(2, square_root(input))
+        input = 25
+        self.assertEqual(5, square_root(input))
+        input = 10
+        self.assertEqual(3, square_root(input))
+
+    def test_find_min_rotated(self):
+        input = [30, 40, 50, 10, 20]
+        self.assertEqual(3, find_min_rotated(input))
+        input = [3, 5, 7, 11, 13, 17, 19, 2]
+        self.assertEqual(7, find_min_rotated(input))
+
+    def test_peak_of_mountain_array(self):
+        input = [0, 1, 2, 3, 2, 1, 0]
+        self.assertEqual(3, peak_of_mountain_array(input))
+
+    def test_peak_min_max_weight(self):
+        weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
+        d = 5
+        self.assertEqual(15, min_max_weight(weights, d))
+
+    def test_countAnalogusArrays(self):
+        consecutiveDifference = [-2, -1, -2, 5]
+        lowerBound = 3
+        upperBound = 10
+        self.assertEqual(3, countAnalogusArrays(consecutiveDifference, lowerBound, upperBound))
+
+    def test_countAnalogusArrays(self):
+        weights = [3,7,5,6,2]
+        self.assertEqual([6, 7], minimalHeaviestSetA(weights))
+
+    def test_getNumberOfOptions(self):
+        priceOfJeans = [2,3]
+        priceOfShoes = [4]
+        priceOfSkirts = [2,3]
+        priceOfTops = [1,2]
+        dollars = 10
+        self.assertEqual(4, getNumberOfOptions(priceOfJeans, priceOfShoes,priceOfSkirts,priceOfTops,dollars))
+
+    def test_howManySwaps(self):
+        arr = [5,1,4,2]
+        self.assertEqual(4, howManySwaps(arr))
+
+    def test_storage(self):
+        n = 6
+        m = 6
+        h = [4]
+        v = [2]
+        self.assertEqual(4, storage(n, m, h, v))
+
+
+if __name__ == '__main__':
+    unittest.main()
-- 
cgit v1.2.3