Run the following cell first!!!
¶# This function is for testing, do not modify
def check(actual, expected):
if expected != actual:
print(
f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
You are given an array of strings names, and an array of numberes heights. Both arrays are of length n.
For each index i, names[i] and heights[i] denote the name and height of the ith person.
Return names sorted in descending
order by the people's heights.
If there is a tie in heights
, then sort the names alphabetically in ascending
order.
Example 1:
Input: names = ["Mary","John","Emma"]
, heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.
Example 2:
Input: names = ["Tony", "Noam", "Abraham", "Georg"]
, heights = [200,160, 160, 170]
Output: ["Tony", "Georg", "Abraham", "Noam"]
Explanation: Abraham and Noam have the same height, but "Noam"is alphabetically larger than "Abraham", so you need to put "Noam" after "Abraham".
def sortHeights(names, heights):
pass # delete this line and add your code here.?
check(sortHeights(["Mary","John","Emma"],[180,165,170]),["Mary","Emma","John"])
check(sortHeights(["Tony", "Noam", "Abraham", "Georg"],[200,160, 160, 170]),["Tony", "Georg", "Abraham", "Noam"])
Now you know how use the recursive approach to implement merge sort algorithm. Let's try to implement it iteratively.
Hint: During the algorithm, we mantain a nested list sublists
containing sorted lists. In each pass of merging
, we pop the first two sub-lists, merge them together and add the merged list to the end of sublists
. In the end, once sublists
contains only a single list, we extract and return the inner list.
def mergeSortIter(lst):
sublists = [[i] for i in lst]
pass # remove this line and add your code here
import random
L = list(range(100))
P = list(L)
random.shuffle(L)
check(mergeSortIter(L), P)
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Use a dictionary to solve it. You solution should have time complexity O(n), where n is the length of the input list nums
.
def majority(nums):
pass # remove this line and add your own code
check(majority([3, 2, 3]), 3)
check(majority([2, 2, 1, 1, 1, 2, 2]), 2)
import random
L = [2] * 10 + [4] * 14 + [3] * 6 + [1] * 31
random.shuffle(L)
check(majority(L), 1)
Use recursion to solve it. Do not use a dictionary. Hint: Divide the list into two. How can you find the majority given the majority of each sublist?
def rec_majority(nums):
pass # remove this line and add your own code
check(rec_majority([3, 2, 3]), 3)
check(rec_majority([2, 2, 1, 1, 1, 2, 2]), 2)
import random
L = [2] * 10 + [4] * 14 + [3] * 6 + [1] * 31
random.shuffle(L)
check(rec_majority(L), 1)
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1]
, nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5]
, nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4]
is also accepted.
You are not allowed to use a dictionary.
def intersect(lst1, lst2):
pass # remove this line and add your code here.
check(sorted(intersect([1, 2, 2, 1], [2, 2])), [2, 2])
check(sorted(intersect([4, 9, 5], [9, 4, 9, 8, 4])), [4, 9])
import random
L = [1, 2, 3, 4, 5] + list(range(6, 20))
P = [1, 2, 3, 4, 5] + list(range(21, 30))
random.shuffle(L)
random.shuffle(P)
check(sorted(intersect(L, P)), [1, 2, 3, 4, 5])