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 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 338 insertions(+) create mode 100644 sources/hacker_rank_leet_code.py (limited to 'sources') 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 -- cgit v1.2.3