Bài tập List - Nâng cao

def flatten_list(nested_list):
    # Chuyển [1, [2, [3, 4], 5], 6] -> [1, 2, 3, 4, 5, 6]
    pass
 
# Test
nested = [1, [2, [3, 4], 5], 6]
flat = flatten_list(nested)
print(flat)  # [1, 2, 3, 4, 5, 6]

def chunk_list(lst, chunk_size):
    # Chia list thành các nhóm
    pass
 
# Test
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
chunks = chunk_list(numbers, 3)
print(chunks)  # [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

def rotate_list(lst, n, direction="right"):
    # n > 0: xoay, n < 0: xoay ngược
    pass
 
# Test
numbers = [1, 2, 3, 4, 5]
print(rotate_list(numbers, 2, "right"))  # [4, 5, 1, 2, 3]
print(rotate_list(numbers, 2, "left"))   # [3, 4, 5, 1, 2]

def find_all_indices(lst, value):
    pass
 
# Test
numbers = [1, 2, 3, 2, 4, 2, 5]
indices = find_all_indices(numbers, 2)
print(indices)  # [1, 3, 5]

def sliding_window(lst, window_size):
    # Trả về list of windows
    pass
 
# Test
numbers = [1, 2, 3, 4, 5]
windows = sliding_window(numbers, 3)
print(windows)  # [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

def merge_sorted_lists(*lists):
    pass
 
# Test
list1 = [1, 3, 5]
list2 = [2, 4, 6]
list3 = [0, 7, 8]
merged = merge_sorted_lists(list1, list2, list3)
print(merged)  # [0, 1, 2, 3, 4, 5, 6, 7, 8]

def list_difference(list1, list2):
    # Giữ thứ tự và duplicates
    pass
 
# Test
list1 = [1, 2, 3, 2, 4]
list2 = [2, 4, 5]
diff = list_difference(list1, list2)
print(diff)  # [1, 3]

def list_intersection_with_duplicates(list1, list2):
    pass
 
# Test
list1 = [1, 2, 2, 3, 4]
list2 = [2, 2, 3, 5]
intersection = list_intersection_with_duplicates(list1, list2)
print(intersection)  # [2, 2, 3]

def partition_list(lst, predicate):
    # Trả về (matching, not_matching)
    pass
 
# Test
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
evens, odds = partition_list(numbers, lambda x: x % 2 == 0)
print(evens)  # [2, 4, 6, 8]
print(odds)   # [1, 3, 5, 7, 9]

def longest_increasing_subsequence(lst):
    pass
 
# Test
numbers = [10, 9, 2, 5, 3, 7, 101, 18]
lis = longest_increasing_subsequence(numbers)
print(lis)  # [2, 3, 7, 18] hoặc [2, 3, 7, 101]

def group_consecutive(lst):
    pass
 
# Test
numbers = [1, 2, 3, 5, 6, 8, 9, 10]
groups = group_consecutive(numbers)
print(groups)  # [[1, 2, 3], [5, 6], [8, 9, 10]]

def run_length_encoding(lst):
    # [1, 1, 1, 2, 2, 3] -> [(1, 3), (2, 2), (3, 1)]
    pass
 
def run_length_decoding(encoded):
    # Ngược lại
    pass
 
# Test
data = [1, 1, 1, 2, 2, 3, 3, 3, 3]
encoded = run_length_encoding(data)
print(encoded)  # [(1, 3), (2, 2), (3, 4)]
decoded = run_length_decoding(encoded)
print(decoded)  # [1, 1, 1, 2, 2, 3, 3, 3, 3]

def cartesian_product(*lists):
    pass
 
# Test
list1 = [1, 2]
list2 = ['a', 'b']
list3 = ['x', 'y']
product = cartesian_product(list1, list2, list3)
print(product)
# [(1, 'a', 'x'), (1, 'a', 'y'), (1, 'b', 'x'), ...]

def permutations_custom(lst):
    pass
 
# Test
items = [1, 2, 3]
perms = permutations_custom(items)
print(len(perms))  # 6
print(perms)  # [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

def combinations_custom(lst, k):
    pass
 
# Test
items = [1, 2, 3, 4]
combs = combinations_custom(items, 2)
print(combs)  # [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

def find_majority_element(lst):
    # Trả về phần tử hoặc None
    pass
 
# Test
numbers = [3, 3, 4, 2, 3, 3, 3]
majority = find_majority_element(numbers)
print(majority)  # 3

def two_sum(lst, target):
    # Trả về indices của hai số
    pass
 
# Test
numbers = [2, 7, 11, 15]
result = two_sum(numbers, 9)
print(result)  # [0, 1] (vì 2 + 7 = 9)

def three_sum(lst, target):
    # Trả về tất cả triplets unique
    pass
 
# Test
numbers = [-1, 0, 1, 2, -1, -4]
result = three_sum(numbers, 0)
print(result)  # [[-1, -1, 2], [-1, 0, 1]]

def max_subarray_sum(lst):
    # Kadane's Algorithm
    pass
 
# Test
numbers = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray_sum(numbers)
print(max_sum)  # 6 (subarray: [4, -1, 2, 1])

def product_except_self(lst):
    # Không được dùng phép chia
    pass
 
# Test
numbers = [1, 2, 3, 4]
result = product_except_self(numbers)
print(result)  # [24, 12, 8, 6]

def find_duplicate(lst):
    # List chứa các số từ 1 đến n, với đúng một số xuất hiện 2 lần
    # O(n) time, O(1) space
    pass
 
# Test
numbers = [1, 3, 4, 2, 2]
duplicate = find_duplicate(numbers)
print(duplicate)  # 2

def sort_by_frequency(lst):
    # Phần tử xuất hiện nhiều lên đầu
    # Nếu tần suất bằng nhau, giữ thứ tự xuất hiện
    pass
 
# Test
items = [4, 5, 6, 5, 4, 3, 4]
sorted_items = sort_by_frequency(items)
print(sorted_items)  # [4, 4, 4, 5, 5, 6, 3]

def dutch_national_flag(lst):
    # In-place sort, O(n) time, O(1) space
    pass
 
# Test
numbers = [2, 0, 1, 2, 0, 1, 0]
dutch_national_flag(numbers)
print(numbers)  # [0, 0, 0, 1, 1, 2, 2]

def next_greater_element(lst):
    # Trả về list, -1 nếu không có
    pass
 
# Test
numbers = [4, 5, 2, 10, 8]
result = next_greater_element(numbers)
print(result)  # [5, 10, 10, -1, -1]

def trapping_rain_water(heights):
    # heights: list độ cao của các cột
    pass
 
# Test
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
water = trapping_rain_water(heights)
print(water)  # 6

class CircularList:
    def __init__(self, capacity):
        self.capacity = capacity
        self.buffer = [None] * capacity
        self.head = 0
        self.size = 0
 
    def append(self, item):
        # Thêm item, ghi đè nếu đầy
        pass
 
    def get(self, index):
        # Lấy item theo index
        pass
 
    def __len__(self):
        return self.size
 
# Test
cl = CircularList(3)
cl.append(1)
cl.append(2)
cl.append(3)
cl.append(4)  # Ghi đè item đầu tiên
print(list(cl))  # [4, 2, 3]

def sparse_list_compress(lst, default=0):
    # Chỉ lưu (index, value) của các phần tử khác default
    pass
 
def sparse_list_decompress(compressed, length, default=0):
    pass
 
# Test
sparse = [0, 0, 5, 0, 0, 0, 3, 0, 0, 7]
compressed = sparse_list_compress(sparse)
print(compressed)  # [(2, 5), (6, 3), (9, 7)]
decompressed = sparse_list_decompress(compressed, 10)
print(decompressed)  # [0, 0, 5, 0, 0, 0, 3, 0, 0, 7]

def list_to_tree(lst, id_key="id", parent_key="parent_id"):
    # Chuyển flat list thành nested dict tree
    pass
 
# Test
items = [
    {"id": 1, "parent_id": None, "name": "Root"},
    {"id": 2, "parent_id": 1, "name": "Child 1"},
    {"id": 3, "parent_id": 1, "name": "Child 2"},
    {"id": 4, "parent_id": 2, "name": "Grandchild"}
]
tree = list_to_tree(items)
print(tree)

def moving_average(lst, window_size):
    pass
 
# Test
numbers = [1, 2, 3, 4, 5, 6, 7, 8]
averages = moving_average(numbers, 3)
print(averages)  # [2.0, 3.0, 4.0, 5.0, 6.0, 7.0]

def list_binary_search(sorted_list, target):
    # Trả về index hoặc -1
    pass
 
# Test
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
index = list_binary_search(numbers, 7)
print(index)  # 3