""" Suite de Pruebas Unitarias Automatizadas. Cubre todos los algoritmos desarrollados para las sesiones de Grokking Algorithms y CTCI Capítulo 1. Incluye casos felices, casos de borde (listas vacías, longitud 1, extremos, duplicados, matrices irregulares). """ import unittest from collections import defaultdict from typing import Any, Dict, List, Optional, Set, Tuple from practica.dia_01_binary_search import ( binary_search, search_insert_position, binary_search_first_occurrence, ) from practica.dia_02_big_o_examples import ( get_first_element, count_divisions_by_two, linear_sum, find_all_pairs, recursive_countdown_stack, iterative_countdown_memory, ) from practica.dia_03_arrays_strings_basics import ( is_unique_set, is_unique_bit_vector, is_unique_no_extra_ds, urlify, reverse_string_in_place, join_strings_efficient, ) from practica.dia_04_hash_tables_frequency import ( check_permutation_anagram, two_sum, group_anagrams, group_anagrams_frequency, is_palindrome_permutation, ) from practica.dia_05_two_pointers import ( is_valid_palindrome, remove_duplicates_sorted, two_sum_sorted, ) from practica.dia_06_string_compression import ( one_away, compress_string_basic, compress_in_place, is_string_rotation, ) from practica.dia_07_matrix_manipulation import ( rotate_matrix_in_place, set_matrix_zeroes, ) from practica.dia_08_memory_linked_list_selection_sort import ( ListNode, build_linked_list, to_list, insert_at_head, insert_at_tail, delete_value, delete_all_occurrences, search_value, selection_sort_array, selection_sort_copy, ) from practica.dia_09_recursion_call_stack import ( countdown_recursive, factorial_recursive, factorial_iterative, recursive_sum, recursive_count, recursive_max, reverse_linked_list_recursive, reverse_linked_list_iterative, ) from practica.dia_10_runner_technique_ctci import ( DoublyListNode, build_doubly_linked_list, to_list_doubly, to_list_doubly_reversed, insert_doubly_head, insert_doubly_tail, delete_doubly_node, remove_dups_buffer, remove_dups_no_buffer, kth_to_last_iterative, kth_to_last_recursive, ) from practica.dia_11_partition_delete_node import ( delete_middle_node, partition_stable, partition_head_tail, ) from practica.dia_12_sum_lists_palindrome import ( sum_lists_reverse, sum_lists_forward, sum_lists_forward_stack, sum_lists_forward_recursive, is_palindrome_stack, is_palindrome_in_place, ) from practica.dia_13_intersection_loop_detection import ( find_intersection_by_length, find_intersection_two_pointers, has_cycle, find_cycle_start, ) from practica.dia_14_linked_list_consolidation import ( get_middle_node, merge_two_sorted_lists, reorder_list, ) from practica.dia_15_divide_and_conquer_quicksort import ( recursive_sum as d15_recursive_sum, recursive_count as d15_recursive_count, recursive_max as d15_recursive_max, quicksort_functional, quicksort_in_place, quickselect, find_kth_largest, ) from practica.dia_16_advanced_hash_tables import ( HashTableChaining, HashTableLinearProbing, RandomizedSet, ) from practica.dia_17_stack_queue_basics_three_in_one import ( ArrayStack, LinkedStack, LinkedQueue, is_valid_parentheses, FixedMultiStack, ) from practica.dia_18_stack_min_and_set_of_stacks import ( MinStack, SetOfStacks, ) from practica.dia_19_queue_via_stacks_and_sort_stack import ( MyQueue, sort_stack, ) from practica.dia_20_animal_shelter import ( AnimalShelter, Dog, Cat, ) from practica.dia_21_monotonic_stack import ( daily_temperatures, next_greater_element, next_greater_element_circular, ) from practica.dia_22_graph_bfs_route_between_nodes import ( Graph, build_graph_from_edges, bfs_shortest_path, has_route_bfs, has_route_dfs, has_route_bidirectional_bfs, find_all_paths, ) from practica.dia_23_binary_tree_bst_traversals import ( TreeNode, inorder_traversal, inorder_traversal_iterative, preorder_traversal, preorder_traversal_iterative, postorder_traversal, postorder_traversal_iterative, level_order_traversal, sorted_array_to_minimal_bst, list_of_depths_bfs, list_of_depths_dfs, tree_height, build_tree_from_level_order, tree_to_level_order, ) from practica.dia_24_validate_balanced_bst import ( is_valid_bst_bounds, is_valid_bst_inorder, is_valid_bst_naive_fallacy, is_balanced_naive, check_balanced_optimal, is_balanced, is_balanced_iterative, ) from practica.dia_25_successor_lca import ( TreeNodeWithParent, inorder_successor_with_parent, inorder_successor_no_parent, lca_binary_tree, lca_with_parent_pointers_set, lca_with_parent_pointers_optimal, lca_bst, ) from practica.dia_26_topological_sort_build_order import ( build_order_kahn, build_order_dfs, has_cycle_directed, find_all_build_orders, ) from practica.dia_27_subtree_paths_with_sum import ( is_same_tree, check_subtree, check_subtree_serialization, paths_with_sum_naive, paths_with_sum_optimal, find_all_paths_with_sum, ) from practica.dia_28_dijkstra_shortest_path import ( WeightedGraph, dijkstra_shortest_path, reconstruct_shortest_path, dijkstra_grid_min_cost, ) from practica.dia_29_arrays_two_pointers_sliding_window import ( length_of_longest_substring, longest_substring_without_repeating, max_area_container, max_area_container_indices, ) from practica.dia_30_linked_lists_heaps import ( reverse_between, merge_k_lists_heap, merge_k_lists_divide_and_conquer, ) from practica.dia_31_monotonic_stack_dual_queue import ( largest_rectangle_area, largest_rectangle_area_details, decode_string, ) from practica.dia_32_trees_traversals_max_path import ( build_tree_preorder_inorder, build_tree_preorder_inorder_recursive, build_tree_preorder_inorder_iterative, max_path_sum, max_path_sum_recursive, max_path_sum_iterative, ) from practica.dia_33_graphs_word_ladder_cheapest_flights import ( ladder_length, find_cheapest_price, find_cheapest_price_bellman_ford, find_cheapest_price_dijkstra, ) from practica.dia_34_mock_faang_interview import ( LRUCache, find_order_kahn, find_order_dfs, find_order_dfs_recursive, find_order_dfs_iterative, evaluate_mock_interview, ) from practica.dia_35_evaluacion_global import ( get_all_questions, get_seniority_matrix, evaluate_student_answers, ) from practica.dia_36_greedy_interval_scheduling_set_cover import ( set_cover_greedy, interval_scheduling, erase_overlap_intervals, can_jump, jump, ) from practica.dia_37_backtracking_subsets_parens import ( subsets_backtracking, subsets_cascading, subsets_bit_manipulation, subsets_with_dup, generate_parentheses, is_valid_parens_combination, ) from practica.dia_38_backtracking_permutations_n_queens import ( permute_unique_elements, permute_string_without_dups, permute_with_duplicates, permute_string_with_dups, solve_n_queens, total_n_queens, ) from practica.dia_39_dp_triple_step_robot_grid import ( triple_step_memo, triple_step_tab, unique_paths, unique_paths_with_obstacles, robot_in_a_grid, robot_in_a_grid_recursive, robot_in_a_grid_iterative, ) from practica.dia_40_dp_knapsack_01_subset_sum import ( knapsack_01_table, knapsack_01_items, knapsack_01_optimized, knapsack_01_memo, can_partition_equal_subset_sum, find_partition_subsets, ) from practica.dia_41_dp_coin_change_unbounded import ( coin_change_min_coins, coin_change_min_coins_memo, coin_change_min_coins_path, coin_change_ways, coin_change_permutations, coin_change_memo, ) from practica.dia_42_dp_lcs_lis_box_stacking import ( longest_common_subsequence, longest_common_subsequence_optimized, longest_common_subsequence_memo, get_lcs_string, longest_common_substring, length_of_lis, length_of_lis_dp, stack_of_boxes, stack_of_boxes_with_path, stack_of_boxes_memo, ) from practica.dia_43_bit_manipulation_fundamentos import ( get_bit, set_bit, clear_bit, update_bit, clear_bits_msb_through_i, clear_bits_i_through_0, insertion, count_one_bits, count_bits, single_number, missing_number, ) from practica.dia_44_bit_manipulation_avanzada import ( flip_bit_to_win, conversion_distance, pairwise_swap, BitVector, find_duplicates_bit_vector, ) from practica.dia_45_sorting_searching_rotated import ( sorted_merge, merge_sorted_array_leetcode, search_rotated_array, find_min_rotated, sparse_search, ) from practica.dia_46_matrix_search_rank_stream import ( matrix_search_sorted_2d, matrix_search_2d, matrix_search_2d_coords, RankNode, RankTracker, peaks_and_valleys, ) from practica.dia_47_tries_prefix_trees_wildcards import ( TrieNode, Trie, WordDictionary, ) from practica.dia_48_union_find_disjoint_set_union import ( DisjointSetUnion, find_circle_num, find_redundant_connection, valid_tree, ) from practica.dia_49_cierre_magistral_consolidacion_semana_7 import ( BitwiseTrieNode, BitwiseTrie, find_maximum_xor, kruskal_mst, evaluate_semana_7_mastery, ) from practica.dia_50_trapping_rain_water import ( trap_rain_water_two_arrays, trap_rain_water_monotonic_stack, trap_rain_water_two_pointers, trap_rain_water_details, ) from practica.dia_51_monotonic_deque_sliding_window import ( MonotonicDeque, max_sliding_window, min_sliding_window, sliding_window_extremes, ) from practica.dia_52_fenwick_tree_binary_indexed_tree import ( FenwickTree, NumArrayBIT, ) from practica.dia_53_segment_tree import ( SegmentTree, NumArraySegmentTree, RangeMinMaxSegmentTree, ) from practica.dia_54_kadane_1d_circular_max_submatrix import ( kadane_1d, max_subarray_sum_circular, max_submatrix_2d, max_submatrix_sum, ) from practica.dia_55_high_performance_arithmetic import ( sieve_of_eratosthenes, count_primes, get_kth_multiple_ctci, nth_ugly_number_lc, binary_pow, modular_pow, ) from practica.dia_56_lfu_cache_and_final_certification import ( LFUNode, DoublyLinkedList, LFUCache, evaluate_staff_mastery, ) from practica.dia_57_knn_vector_distances import ( euclidean_distance, manhattan_distance, cosine_similarity, cosine_distance, min_max_normalize, knn_classify, knn_regress, k_closest_points_to_origin, ) from practica.dia_58_bloom_filter_hyperloglog import ( BloomFilter, HyperLogLog, ProbabilisticHashSet, ) from practica.dia_59_inverted_index_tfidf import ( tokenize, delta_encode, delta_decode, intersect_postings, union_postings, InvertedIndex, TFIDFSearchEngine, ) from practica.dia_60_simhash_lsh import ( tokenize_shingles, hamming_distance_bits, SimHash, SimHashLSH, find_repeated_dna_sequences, ) from practica.dia_61_extended_euclid_diffie_hellman import ( gcd as knuth_gcd, extended_gcd, mod_inverse, solve_diophantine, can_measure_water, super_pow, DiffieHellmanParty, ) from practica.dia_62_consistent_hashing_token_bucket import ( ConsistentHashRing, TokenBucketRateLimiter, LeakyBucketRateLimiter, LoggerRateLimiter, HitCounter, ) from practica.dia_63_super_egg_drop_consolidation import ( two_egg_drop, super_egg_drop_dp_binary_search, super_egg_drop_moves_dp, get_week_9_questions, evaluate_week_9_mastery, ) from practica.dia_64_test_diagnostico_1_dp_backtracking_regex import ( is_match_regex, is_match_regex_memo, is_match_regex_1d, is_match_wildcard, analyze_regex_feedback, ) from practica.dia_65_test_diagnostico_2_tries_dsu_compuestos import ( DisjointSetUnion as Dia65DSU, accounts_merge, TrieNode as Dia65TrieNode, WordSearchTrie, find_words, analyze_dsu_trie_feedback, ) from practica.dia_66_test_diagnostico_3_range_queries_monotonic_deque import ( constrained_subset_sum, trap_rain_water_2d, analyze_range_query_feedback, ) from practica.dia_67_test_diagnostico_4_sistemas_distribuidos_probabilisticos import ( TokenBucket as Dia67TokenBucket, DistributedRateLimiter, SimpleBloomFilter, LogDeduplicator, ) from practica.dia_68_gran_simulacro_onsite_faang_staff import ( alien_order, DualHeapMedianFinder, median_sliding_window, evaluate_staff_onsite_interview, ) from practica.dia_69_examen_maestria_active_recall import ( MASTERY_EXAM_QUESTIONS, get_all_mastery_questions, evaluate_mastery_exam, ) from practica.dia_70_matriz_certificacion_final_graduacion_staff import ( CURRICULUM_WEEKS, evaluate_full_curriculum_certification, ) class TestAlgoritmos(unittest.TestCase): # --- DÍA 1: Búsqueda Binaria --- def test_dia_01_binary_search_found(self): arr = [1, 3, 5, 7, 9, 11] self.assertEqual(binary_search(arr, 1), 0) self.assertEqual(binary_search(arr, 7), 3) self.assertEqual(binary_search(arr, 11), 5) def test_dia_01_binary_search_not_found(self): arr = [1, 3, 5, 7, 9, 11] self.assertEqual(binary_search(arr, 0), -1) self.assertEqual(binary_search(arr, 6), -1) self.assertEqual(binary_search(arr, 15), -1) def test_dia_01_binary_search_edge_cases(self): # Lista vacía self.assertEqual(binary_search([], 5), -1) # 1 solo elemento presente self.assertEqual(binary_search([5], 5), 0) # 1 solo elemento ausente self.assertEqual(binary_search([5], 3), -1) def test_dia_01_search_insert_position(self): arr = [1, 3, 5, 6] self.assertEqual(search_insert_position(arr, 5), 2) self.assertEqual(search_insert_position(arr, 2), 1) self.assertEqual(search_insert_position(arr, 7), 4) self.assertEqual(search_insert_position(arr, 0), 0) self.assertEqual(search_insert_position([], 5), 0) def test_dia_01_first_occurrence(self): arr = [1, 2, 2, 2, 3, 4] self.assertEqual(binary_search_first_occurrence(arr, 2), 1) self.assertEqual(binary_search_first_occurrence(arr, 5), -1) self.assertEqual(binary_search_first_occurrence([2, 2, 2], 2), 0) # --- DÍA 2: Big O & Espacio --- def test_dia_02_big_o(self): self.assertEqual(get_first_element([42, 99]), 42) with self.assertRaises(ValueError): get_first_element([]) self.assertEqual(count_divisions_by_two(1024), 10) self.assertEqual(count_divisions_by_two(1), 0) self.assertEqual(count_divisions_by_two(0), 0) self.assertEqual(linear_sum([1, 2, 3, 4]), 10) self.assertEqual(linear_sum([]), 0) pairs = find_all_pairs([1, 2]) self.assertEqual(len(pairs), 4) self.assertEqual(recursive_countdown_stack(10), 10) self.assertEqual(iterative_countdown_memory(10), 10) # --- DÍA 3: Arrays & Strings --- def test_dia_03_is_unique(self): # Set self.assertTrue(is_unique_set("abcdef")) self.assertFalse(is_unique_set("aba")) self.assertTrue(is_unique_set("")) # Bit vector (ASCII completo) self.assertTrue(is_unique_bit_vector("abcdef")) self.assertFalse(is_unique_bit_vector("aba")) self.assertTrue(is_unique_bit_vector("")) self.assertFalse(is_unique_bit_vector("AA")) self.assertFalse(is_unique_bit_vector("11")) self.assertFalse(is_unique_bit_vector("hello")) self.assertTrue(is_unique_bit_vector("Aa1!")) # Sin estructuras de datos adicionales (O(1) memoria estricta) self.assertTrue(is_unique_no_extra_ds("abcdef")) self.assertFalse(is_unique_no_extra_ds("aba")) self.assertTrue(is_unique_no_extra_ds("")) self.assertFalse(is_unique_no_extra_ds("AA")) self.assertFalse(is_unique_no_extra_ds("11")) self.assertFalse(is_unique_no_extra_ds("hello")) self.assertTrue(is_unique_no_extra_ds("Aa1!")) def test_dia_03_urlify(self): chars = list("Mr John Smith ") urlify(chars, 13) self.assertEqual("".join(chars), "Mr%20John%20Smith") # Sin espacios no_spaces = list("NoSpaces") urlify(no_spaces, 8) self.assertEqual("".join(no_spaces), "NoSpaces") # Múltiples espacios consecutivos multi = list("a b c ") urlify(multi, 6) self.assertEqual("".join(multi), "a%20b%20%20c") def test_dia_03_reverse_string(self): chars = ["h", "e", "l", "l", "o"] reverse_string_in_place(chars) self.assertEqual(chars, ["o", "l", "l", "e", "h"]) empty = [] reverse_string_in_place(empty) self.assertEqual(empty, []) single = ["a"] reverse_string_in_place(single) self.assertEqual(single, ["a"]) def test_dia_03_join_strings(self): self.assertEqual(join_strings_efficient(["algo", "ritmo"]), "algoritmo") self.assertEqual(join_strings_efficient([]), "") # --- DÍA 4: Hash Tables & Frecuencia --- def test_dia_04_anagram(self): self.assertTrue(check_permutation_anagram("anagram", "nagaram")) self.assertFalse(check_permutation_anagram("rat", "car")) self.assertFalse(check_permutation_anagram("a", "ab")) self.assertTrue(check_permutation_anagram("", "")) def test_dia_04_palindrome_permutation(self): # CTCI 1.4: Permutaciones de palíndromos self.assertTrue(is_palindrome_permutation("Tact Coa")) # 'taco cat' self.assertTrue(is_palindrome_permutation("civic")) self.assertTrue(is_palindrome_permutation("ivicc")) self.assertFalse(is_palindrome_permutation("Tact Boa")) self.assertTrue(is_palindrome_permutation("a")) self.assertTrue(is_palindrome_permutation("")) self.assertFalse(is_palindrome_permutation("abc")) def test_dia_04_two_sum(self): self.assertEqual(two_sum([2, 7, 11, 15], 9), [0, 1]) self.assertEqual(two_sum([3, 2, 4], 6), [1, 2]) self.assertEqual(two_sum([3, 3], 6), [0, 1]) self.assertEqual(two_sum([1, 2], 10), []) def test_dia_04_group_anagrams(self): strs = ["eat", "tea", "tan", "ate", "nat", "bat"] groups = group_anagrams(strs) sorted_groups = sorted([sorted(g) for g in groups]) expected = sorted([["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]) self.assertEqual(sorted_groups, expected) # Robustez con mayúsculas y caracteres variados mixed = ["Eat", "tea", "ate"] groups_mixed = group_anagrams(mixed) # "Eat" ordenado es "Eat", "tea" y "ate" ordenados son "aet" sorted_mixed = sorted([sorted(g) for g in groups_mixed]) expected_mixed = sorted([["Eat"], ["ate", "tea"]]) self.assertEqual(sorted_mixed, expected_mixed) # Versión de frecuencia groups_freq = group_anagrams_frequency(strs) sorted_groups_freq = sorted([sorted(g) for g in groups_freq]) self.assertEqual(sorted_groups_freq, expected) # --- DÍA 5: Two Pointers --- def test_dia_05_valid_palindrome(self): self.assertTrue(is_valid_palindrome("A man, a plan, a canal: Panama")) self.assertFalse(is_valid_palindrome("race a car")) self.assertTrue(is_valid_palindrome(" ")) self.assertTrue(is_valid_palindrome("a.")) def test_dia_05_remove_duplicates(self): nums = [1, 1, 2] k = remove_duplicates_sorted(nums) self.assertEqual(k, 2) self.assertEqual(nums[:k], [1, 2]) nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] k2 = remove_duplicates_sorted(nums2) self.assertEqual(k2, 5) self.assertEqual(nums2[:k2], [0, 1, 2, 3, 4]) self.assertEqual(remove_duplicates_sorted([]), 0) self.assertEqual(remove_duplicates_sorted([7]), 1) def test_dia_05_two_sum_sorted(self): self.assertEqual(two_sum_sorted([2, 7, 11, 15], 9), [1, 2]) self.assertEqual(two_sum_sorted([2, 3, 4], 6), [1, 3]) self.assertEqual(two_sum_sorted([-1, 0], -1), [1, 2]) self.assertEqual(two_sum_sorted([1, 2, 3], 10), []) # --- DÍA 6: Compresión & Edición --- def test_dia_06_one_away(self): self.assertTrue(one_away("pale", "ple")) # Eliminación self.assertTrue(one_away("pales", "pale")) # Inserción self.assertTrue(one_away("pale", "bale")) # Reemplazo self.assertFalse(one_away("pale", "bake")) # Dos reemplazos self.assertTrue(one_away("pale", "pale")) # Cero ediciones self.assertFalse(one_away("pale", "p")) # Diferencia > 1 def test_dia_06_compress_basic(self): self.assertEqual(compress_string_basic("aabcccccaaa"), "a2b1c5a3") # Si la compresión no es más corta, debe retornar la original self.assertEqual(compress_string_basic("abcdef"), "abcdef") self.assertEqual(compress_string_basic(""), "") self.assertEqual(compress_string_basic("a"), "a") def test_dia_06_compress_in_place(self): chars = ["a", "a", "b", "b", "c", "c", "c"] k = compress_in_place(chars) self.assertEqual(k, 6) self.assertEqual(chars[:k], ["a", "2", "b", "2", "c", "3"]) chars2 = ["a"] k2 = compress_in_place(chars2) self.assertEqual(k2, 1) self.assertEqual(chars2[:k2], ["a"]) chars3 = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"] k3 = compress_in_place(chars3) self.assertEqual(k3, 4) self.assertEqual(chars3[:k3], ["a", "b", "1", "2"]) def test_dia_06_string_rotation(self): # CTCI 1.9: Rotación de cadenas con is_substring / (s1 + s1) self.assertTrue(is_string_rotation("waterbottle", "erbottlewat")) self.assertFalse(is_string_rotation("abc", "acb")) self.assertTrue(is_string_rotation("rotation", "tionrota")) self.assertFalse(is_string_rotation("", "")) self.assertTrue(is_string_rotation("a", "a")) self.assertFalse(is_string_rotation("a", "b")) # --- DÍA 7: Matrices 2D --- def test_dia_07_rotate_matrix(self): matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] rotate_matrix_in_place(matrix) expected = [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ] self.assertEqual(matrix, expected) # Matriz 1x1 m1 = [[1]] rotate_matrix_in_place(m1) self.assertEqual(m1, [[1]]) def test_dia_07_set_matrix_zeroes(self): matrix = [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ] set_matrix_zeroes(matrix) expected = [ [1, 0, 1], [0, 0, 0], [1, 0, 1] ] self.assertEqual(matrix, expected) # Caso borde: Cero en la primera fila y columna matrix2 = [ [0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5] ] set_matrix_zeroes(matrix2) expected2 = [ [0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ] self.assertEqual(matrix2, expected2) # Casos borde rectangulares 1D (1 x N y M x 1) m_row = [[1, 0, 3]] set_matrix_zeroes(m_row) self.assertEqual(m_row, [[0, 0, 0]]) m_col = [[1], [0], [3]] set_matrix_zeroes(m_col) self.assertEqual(m_col, [[0], [0], [0]]) # Rectangular 2x3 m_rect = [[1, 0, 3], [4, 5, 6]] set_matrix_zeroes(m_rect) self.assertEqual(m_rect, [[0, 0, 0], [4, 0, 6]]) # ========================================================================= # --- SEMANA 2: DÍAS 08 AL 14 --- # ========================================================================= # --- DÍA 8: Memoria Física, Listas Enlazadas & Selection Sort --- def test_dia_08_linked_list_basics(self): # build_linked_list & to_list self.assertIsNone(build_linked_list([])) self.assertEqual(to_list(None), []) head = build_linked_list([1, 2, 3]) self.assertEqual(to_list(head), [1, 2, 3]) # insert_at_head head = insert_at_head(head, 0) self.assertEqual(to_list(head), [0, 1, 2, 3]) head_single = insert_at_head(None, 42) self.assertEqual(to_list(head_single), [42]) # insert_at_tail head = insert_at_tail(head, 4) self.assertEqual(to_list(head), [0, 1, 2, 3, 4]) head_tail_single = insert_at_tail(None, 99) self.assertEqual(to_list(head_tail_single), [99]) # search_value found = search_value(head, 2) self.assertIsNotNone(found) self.assertEqual(found.val, 2) self.assertIsNone(search_value(head, 999)) # delete_value (cabeza, intermedio, cola, inexistente) head = delete_value(head, 0) # Borrar cabeza self.assertEqual(to_list(head), [1, 2, 3, 4]) head = delete_value(head, 3) # Borrar intermedio self.assertEqual(to_list(head), [1, 2, 4]) head = delete_value(head, 4) # Borrar cola self.assertEqual(to_list(head), [1, 2]) head = delete_value(head, 999) # Inexistente self.assertEqual(to_list(head), [1, 2]) # Borrar hasta vaciar head = delete_value(head, 1) head = delete_value(head, 2) self.assertIsNone(head) # delete_all_occurrences (LeetCode 203) multi_dup = build_linked_list([2, 1, 2, 3, 2, 2]) res_del = delete_all_occurrences(multi_dup, 2) self.assertEqual(to_list(res_del), [1, 3]) # Eliminar todos de lista homogénea all_same = build_linked_list([7, 7, 7]) self.assertIsNone(delete_all_occurrences(all_same, 7)) # Eliminar de lista vacía o inexistente self.assertIsNone(delete_all_occurrences(None, 5)) single_no_match = build_linked_list([10]) self.assertEqual(to_list(delete_all_occurrences(single_no_match, 99)), [10]) # Detección de ciclo en to_list y __repr__ cyclic_node = ListNode(1, next=ListNode(2)) cyclic_node.next.next = cyclic_node # type: ignore[union-attr] with self.assertRaises(ValueError): to_list(cyclic_node) repr_str = repr(cyclic_node) self.assertIn("ciclo", repr_str) def test_dia_08_selection_sort(self): # In-place array self.assertEqual(selection_sort_array([]), []) self.assertEqual(selection_sort_array([5]), [5]) self.assertEqual(selection_sort_array([5, 2, 4, 6, 1, 3]), [1, 2, 3, 4, 5, 6]) self.assertEqual(selection_sort_array([1, 2, 3]), [1, 2, 3]) self.assertEqual(selection_sort_array([3, 2, 1]), [1, 2, 3]) self.assertEqual(selection_sort_array([-3, 5, -1, 0, 2]), [-3, -1, 0, 2, 5]) self.assertEqual(selection_sort_array([2, 2, 1, 1, 2]), [1, 1, 2, 2, 2]) # Out-of-place copy self.assertEqual(selection_sort_copy([5, 3, 6, 2, 10]), [2, 3, 5, 6, 10]) self.assertEqual(selection_sort_copy([]), []) self.assertEqual(selection_sort_copy([-1, -5, 0, 3]), [-5, -1, 0, 3]) # --- DÍA 9: Recursión y Call Stack --- def test_dia_09_recursion_and_stack(self): # countdown_recursive self.assertEqual(countdown_recursive(5), [5, 4, 3, 2, 1]) self.assertEqual(countdown_recursive(0), []) self.assertEqual(countdown_recursive(-3), []) # factorial_recursive & iterative self.assertEqual(factorial_recursive(0), 1) self.assertEqual(factorial_recursive(1), 1) self.assertEqual(factorial_recursive(5), 120) self.assertEqual(factorial_iterative(0), 1) self.assertEqual(factorial_iterative(5), 120) with self.assertRaises(ValueError): factorial_recursive(-1) with self.assertRaises(ValueError): factorial_iterative(-5) # recursive_sum, count, max self.assertEqual(recursive_sum([]), 0) self.assertEqual(recursive_sum([1, 2, 3, 4, 5]), 15) self.assertEqual(recursive_sum([-5, 5, 10]), 10) self.assertEqual(recursive_count([]), 0) self.assertEqual(recursive_count([10, 20, 30]), 3) self.assertEqual(recursive_max([7]), 7) self.assertEqual(recursive_max([1, 5, 2, 9, 3]), 9) self.assertEqual(recursive_max([-10, -3, -20]), -3) with self.assertRaises(ValueError): recursive_max([]) def test_dia_09_reverse_linked_list(self): # Iterativo y recursivo deben comportarse idénticamente for rev_fn in [reverse_linked_list_iterative, reverse_linked_list_recursive]: self.assertIsNone(rev_fn(None)) single = build_linked_list([42]) self.assertEqual(to_list(rev_fn(single)), [42]) two_nodes = build_linked_list([1, 2]) self.assertEqual(to_list(rev_fn(two_nodes)), [2, 1]) multi = build_linked_list([1, 2, 3, 4, 5]) self.assertEqual(to_list(rev_fn(multi)), [5, 4, 3, 2, 1]) # --- DÍA 10: Runner Technique & Duplicados (CTCI 2.1 & 2.2) --- def test_dia_10_remove_dups(self): for rm_fn in [remove_dups_buffer, remove_dups_no_buffer]: self.assertIsNone(rm_fn(None)) single = build_linked_list([1]) self.assertEqual(to_list(rm_fn(single)), [1]) no_dups = build_linked_list([1, 2, 3]) self.assertEqual(to_list(rm_fn(no_dups)), [1, 2, 3]) all_dups = build_linked_list([2, 2, 2, 2]) self.assertEqual(to_list(rm_fn(all_dups)), [2]) mixed = build_linked_list([1, 2, 1, 3, 2, 4, 1]) self.assertEqual(to_list(rm_fn(mixed)), [1, 2, 3, 4]) def test_dia_10_kth_to_last(self): for kth_fn in [kth_to_last_iterative, kth_to_last_recursive]: self.assertIsNone(kth_fn(None, 1)) ll = build_linked_list([10, 20, 30, 40, 50]) # k=1 -> último (50) self.assertEqual(kth_fn(ll, 1).val, 50) # k=2 -> penúltimo (40) self.assertEqual(kth_fn(ll, 2).val, 40) # k=5 -> primero (10) self.assertEqual(kth_fn(ll, 5).val, 10) # k > longitud -> None self.assertIsNone(kth_fn(ll, 6)) # k <= 0 -> None self.assertIsNone(kth_fn(ll, 0)) self.assertIsNone(kth_fn(ll, -2)) def test_dia_10_doubly_linked_list(self): # build_doubly_linked_list & to_list_doubly (forward y backward) self.assertIsNone(build_doubly_linked_list([])) self.assertEqual(to_list_doubly(None), []) self.assertEqual(to_list_doubly_reversed(None), []) dhead = build_doubly_linked_list([10, 20, 30]) self.assertEqual(to_list_doubly(dhead), [10, 20, 30]) # Encontrar la cola para recorrer hacia atrás dtail = dhead while dtail and dtail.next: dtail = dtail.next self.assertEqual(to_list_doubly_reversed(dtail), [30, 20, 10]) # insert_doubly_head dhead = insert_doubly_head(dhead, 5) self.assertEqual(to_list_doubly(dhead), [5, 10, 20, 30]) self.assertIsNone(dhead.prev) self.assertEqual(dhead.next.prev, dhead) # insert_doubly_tail dhead = insert_doubly_tail(dhead, 40) self.assertEqual(to_list_doubly(dhead), [5, 10, 20, 30, 40]) # delete_doubly_node (O(1) eliminación de nodo intermedio con reconexión bidireccional) # Ubicar nodo con valor 20 target = dhead.next.next # 20 self.assertEqual(target.val, 20) delete_doubly_node(target) self.assertEqual(to_list_doubly(dhead), [5, 10, 30, 40]) # Verificar integridad del puntero prev: 30.prev debe ser 10 node_30 = dhead.next.next self.assertEqual(node_30.val, 30) self.assertEqual(node_30.prev.val, 10) self.assertEqual(node_30.prev.next, node_30) # Borrado en cabeza de nodo doble old_head = dhead dhead = dhead.next delete_doubly_node(old_head) self.assertEqual(to_list_doubly(dhead), [10, 30, 40]) self.assertIsNone(dhead.prev) # --- DÍA 11: Delete Middle Node & Partition (CTCI 2.3 & 2.4) --- def test_dia_11_delete_middle_node(self): ll = build_linked_list([1, 2, 3, 4, 5]) # Localizar el nodo con valor 3 (nodo intermedio) node_3 = ll.next.next # 3 success = delete_middle_node(node_3) self.assertTrue(success) self.assertEqual(to_list(ll), [1, 2, 4, 5]) # Intentar borrar el último nodo directamente (debe retornar False) last_node = ll.next.next.next # 5 self.assertFalse(delete_middle_node(last_node)) # None como argumento self.assertFalse(delete_middle_node(None)) # Borrar nodo intermedio de lista de 3 elementos ll3 = build_linked_list([10, 20, 30]) self.assertTrue(delete_middle_node(ll3.next)) # Borrar 20 self.assertEqual(to_list(ll3), [10, 30]) def test_dia_11_partition(self): # Partición Estable ll_stable = build_linked_list([3, 5, 8, 5, 10, 2, 1]) res_stable = partition_stable(ll_stable, 5) res_list = to_list(res_stable) # Menores que 5: [3, 2, 1] en orden relativo preservado # Mayores o iguales que 5: [5, 8, 5, 10] en orden relativo preservado self.assertEqual(res_list, [3, 2, 1, 5, 8, 5, 10]) # Partición Head/Tail (verificar propiedad: todos los elementos antes de la frontera < x) ll_ht = build_linked_list([3, 5, 8, 5, 10, 2, 1]) res_ht = partition_head_tail(ll_ht, 5) res_ht_list = to_list(res_ht) self.assertEqual(len(res_ht_list), 7) self.assertEqual(sorted(res_ht_list), sorted([3, 5, 8, 5, 10, 2, 1])) # Encontrar punto de transición transition = False for val in res_ht_list: if val >= 5: transition = True if transition: self.assertGreaterEqual(val, 5) else: self.assertLess(val, 5) # Casos de borde para AMBAS variantes: vacía, 1 nodo, todos menores, todos mayores, alternados for part_fn in [partition_stable, partition_head_tail]: self.assertIsNone(part_fn(None, 5)) self.assertEqual(to_list(part_fn(build_linked_list([1]), 5)), [1]) self.assertEqual(to_list(part_fn(build_linked_list([1, 2, 3]), 10)), [1, 2, 3] if part_fn == partition_stable else [3, 2, 1]) self.assertEqual(to_list(part_fn(build_linked_list([10, 20]), 5)), [10, 20]) # Alternados alt_res = to_list(part_fn(build_linked_list([10, 1, 20, 2, 30]), 15)) self.assertEqual(len(alt_res), 5) self.assertEqual(sorted(alt_res), [1, 2, 10, 20, 30]) # Todos los < 15 deben preceder a todos los >= 15 found_ge = False for v in alt_res: if v >= 15: found_ge = True if found_ge: self.assertGreaterEqual(v, 15) else: self.assertLess(v, 15) # --- DÍA 12: Sum Lists & Palindrome (CTCI 2.5 & 2.6) --- def test_dia_12_sum_lists(self): # Inverso: (7 -> 1 -> 6) + (5 -> 9 -> 2) = 617 + 295 = 912 -> (2 -> 1 -> 9) l1 = build_linked_list([7, 1, 6]) l2 = build_linked_list([5, 9, 2]) res_rev = sum_lists_reverse(l1, l2) self.assertEqual(to_list(res_rev), [2, 1, 9]) # Inverso con longitudes dispares y acarreo final: 99 + 1 = 100 -> [9, 9] + [1] = [0, 0, 1] l3 = build_linked_list([9, 9]) l4 = build_linked_list([1]) self.assertEqual(to_list(sum_lists_reverse(l3, l4)), [0, 0, 1]) # Uno o ambos vacíos self.assertEqual(to_list(sum_lists_reverse(None, l4)), [1]) self.assertEqual(to_list(sum_lists_reverse(l4, None)), [1]) self.assertIsNone(sum_lists_reverse(None, None)) # Forward (Directo): Probar tanto la variante recursiva como la basada en Stacks iterativos for fwd_fn in [sum_lists_forward, sum_lists_forward_stack, sum_lists_forward_recursive]: # (6 -> 1 -> 7) + (2 -> 9 -> 5) = 617 + 295 = 912 -> (9 -> 1 -> 2) f1 = build_linked_list([6, 1, 7]) f2 = build_linked_list([2, 9, 5]) self.assertEqual(to_list(fwd_fn(f1, f2)), [9, 1, 2]) # Forward con distinto tamaño (len1 > len2) y acarreo extra: 99 + 1 = 100 -> [9, 9] + [1] = [1, 0, 0] f3 = build_linked_list([9, 9]) f4 = build_linked_list([1]) self.assertEqual(to_list(fwd_fn(f3, f4)), [1, 0, 0]) # Forward con distinto tamaño inverso (len1 < len2): 1 + 99 = 100 self.assertEqual(to_list(fwd_fn(build_linked_list([1]), build_linked_list([9, 9]))), [1, 0, 0]) # Ceros explícitos self.assertEqual(to_list(fwd_fn(build_linked_list([0]), build_linked_list([0]))), [0]) # Casos borde con None self.assertEqual(to_list(fwd_fn(None, build_linked_list([5]))), [5]) self.assertEqual(to_list(fwd_fn(build_linked_list([5]), None)), [5]) self.assertIsNone(fwd_fn(None, None)) # Stress-test de robustez: sum_lists_forward_stack con 2,000 nodos (excede sys.getrecursionlimit) deep_l1 = build_linked_list([1] * 2000) deep_l2 = build_linked_list([1] * 2000) deep_res = sum_lists_forward_stack(deep_l1, deep_l2) deep_digits = to_list(deep_res) self.assertEqual(len(deep_digits), 2000) self.assertEqual(deep_digits[0], 2) self.assertEqual(deep_digits[-1], 2) def test_dia_12_palindrome(self): for pal_fn in [is_palindrome_stack, is_palindrome_in_place]: # Casos vacíos y unitarios self.assertTrue(pal_fn(None)) self.assertTrue(pal_fn(build_linked_list([7]))) # Palíndromos impares y pares self.assertTrue(pal_fn(build_linked_list([1, 2, 1]))) self.assertTrue(pal_fn(build_linked_list([1, 2, 2, 1]))) self.assertTrue(pal_fn(build_linked_list([0, 1, 2, 1, 0]))) # No palíndromos self.assertFalse(pal_fn(build_linked_list([1, 2, 3]))) self.assertFalse(pal_fn(build_linked_list([1, 2]))) self.assertFalse(pal_fn(build_linked_list([1, 2, 3, 4, 2, 1]))) # Verificación explícita de restauración de lista en is_palindrome_in_place original_vals = [1, 2, 3, 2, 1] ll = build_linked_list(original_vals) self.assertTrue(is_palindrome_in_place(ll)) self.assertEqual(to_list(ll), original_vals) # La lista debe mantenerse intacta # --- DÍA 13: Intersection & Loop Detection (CTCI 2.7 & 2.8) --- def test_dia_13_intersection(self): for inter_fn in [find_intersection_by_length, find_intersection_two_pointers]: # Sin intersección l1 = build_linked_list([1, 2, 3]) l2 = build_linked_list([1, 2, 3]) # Mismos valores, pero distintas direcciones en RAM self.assertIsNone(inter_fn(l1, l2)) self.assertIsNone(inter_fn(None, l1)) self.assertIsNone(inter_fn(l1, None)) self.assertIsNone(inter_fn(None, None)) # Con intersección compartida en el nodo 8 shared = build_linked_list([8, 4, 5]) head_a = ListNode(4, next=ListNode(1, next=shared)) head_b = ListNode(5, next=ListNode(6, next=ListNode(1, next=shared))) intersected = inter_fn(head_a, head_b) self.assertIsNotNone(intersected) self.assertIs(intersected, shared) # Identidad de memoria ('is') # Intersección en la mismísima cabeza self.assertIs(inter_fn(shared, shared), shared) def test_dia_13_loop_detection(self): # Lista sin ciclo linear = build_linked_list([1, 2, 3, 4]) self.assertFalse(has_cycle(linear)) self.assertIsNone(find_cycle_start(linear)) self.assertFalse(has_cycle(None)) self.assertIsNone(find_cycle_start(None)) # Lista con ciclo: 3 -> 2 -> 0 -> -4 -> vuelve a 2 node1 = ListNode(3) node2 = ListNode(2) node3 = ListNode(0) node4 = ListNode(-4) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node2 # Ciclo hacia node2 self.assertTrue(has_cycle(node1)) cycle_start = find_cycle_start(node1) self.assertIs(cycle_start, node2) # Ciclo de 1 solo elemento apuntando a sí mismo self_loop = ListNode(99) self_loop.next = self_loop self.assertTrue(has_cycle(self_loop)) self.assertIs(find_cycle_start(self_loop), self_loop) # Ciclo que abarca la lista entera: 1 -> 2 -> 3 -> vuelve a 1 (inicio en cabeza) c1 = ListNode(1) c2 = ListNode(2) c3 = ListNode(3) c1.next = c2 c2.next = c3 c3.next = c1 self.assertTrue(has_cycle(c1)) self.assertIs(find_cycle_start(c1), c1) # --- DÍA 14: Consolidación y Simulacro FAANG --- def test_dia_14_consolidation(self): # get_middle_node self.assertIsNone(get_middle_node(None)) self.assertEqual(get_middle_node(build_linked_list([1])).val, 1) # Impar: 1->2->3->4->5 -> retorna 3 self.assertEqual(get_middle_node(build_linked_list([1, 2, 3, 4, 5])).val, 3) # Par: 1->2->3->4->5->6 -> retorna segundo central: 4 self.assertEqual(get_middle_node(build_linked_list([1, 2, 3, 4, 5, 6])).val, 4) # merge_two_sorted_lists la = build_linked_list([1, 2, 4]) lb = build_linked_list([1, 3, 4]) merged = merge_two_sorted_lists(la, lb) self.assertEqual(to_list(merged), [1, 1, 2, 3, 4, 4]) self.assertEqual(to_list(merge_two_sorted_lists(None, build_linked_list([5]))), [5]) self.assertEqual(to_list(merge_two_sorted_lists(build_linked_list([5]), None)), [5]) self.assertIsNone(merge_two_sorted_lists(None, None)) # Con elementos duplicados m_dup = merge_two_sorted_lists(build_linked_list([1, 2, 2]), build_linked_list([1, 3])) self.assertEqual(to_list(m_dup), [1, 1, 2, 2, 3]) # reorder_list # Caso par: [1, 2, 3, 4] -> [1, 4, 2, 3] ll_even = build_linked_list([1, 2, 3, 4]) reorder_list(ll_even) self.assertEqual(to_list(ll_even), [1, 4, 2, 3]) # Caso impar: [1, 2, 3, 4, 5] -> [1, 5, 2, 4, 3] ll_odd = build_linked_list([1, 2, 3, 4, 5]) reorder_list(ll_odd) self.assertEqual(to_list(ll_odd), [1, 5, 2, 4, 3]) # Caso 3 elementos: [1, 2, 3] -> [1, 3, 2] ll_3 = build_linked_list([1, 2, 3]) reorder_list(ll_3) self.assertEqual(to_list(ll_3), [1, 3, 2]) # Casos borde: vacía, 1 elemento, 2 elementos empty_ll = None reorder_list(empty_ll) self.assertIsNone(empty_ll) single_ll = build_linked_list([1]) reorder_list(single_ll) self.assertEqual(to_list(single_ll), [1]) two_items = build_linked_list([1, 2]) reorder_list(two_items) self.assertEqual(to_list(two_items), [1, 2]) # --- SEMANA 3: DÍAS 15 AL 21 --- # --- DÍA 15: Divide y Vencerás, Quicksort y Quickselect --- def test_dia_15_divide_and_conquer(self): # recursive_sum self.assertEqual(d15_recursive_sum([]), 0) self.assertEqual(d15_recursive_sum([7]), 7) self.assertEqual(d15_recursive_sum([2, 4, 6]), 12) self.assertEqual(d15_recursive_sum([-5, 5, -10, 10]), 0) # recursive_count self.assertEqual(d15_recursive_count([]), 0) self.assertEqual(d15_recursive_count([42]), 1) self.assertEqual(d15_recursive_count([1, 2, 3, 4, 5]), 5) # recursive_max self.assertIsNone(d15_recursive_max([])) self.assertEqual(d15_recursive_max([99]), 99) self.assertEqual(d15_recursive_max([1, 5, 10, 25, 16, 2]), 25) self.assertEqual(d15_recursive_max([-10, -50, -3, -100]), -3) # Validación D&C binario en arreglos grandes (N = 1200 > límite de recursión lineal de Python) large_arr = [1] * 1200 self.assertEqual(d15_recursive_sum(large_arr), 1200) self.assertEqual(d15_recursive_count(large_arr), 1200) self.assertEqual(d15_recursive_max(large_arr), 1) def test_dia_15_quicksort(self): # quicksort_functional self.assertEqual(quicksort_functional([]), []) self.assertEqual(quicksort_functional([1]), [1]) self.assertEqual(quicksort_functional([10, 5, 2, 3]), [2, 3, 5, 10]) self.assertEqual(quicksort_functional([5, 1, 1, 2, 0, 0]), [0, 0, 1, 1, 2, 5]) self.assertEqual(quicksort_functional([5, 4, 3, 2, 1]), [1, 2, 3, 4, 5]) self.assertEqual(quicksort_functional([-3, 10, -1, 0, 8]), [-3, -1, 0, 8, 10]) # quicksort_in_place arr_empty: List[int] = [] quicksort_in_place(arr_empty) self.assertEqual(arr_empty, []) arr_single = [42] quicksort_in_place(arr_single) self.assertEqual(arr_single, [42]) arr1 = [10, 5, 2, 3] quicksort_in_place(arr1) self.assertEqual(arr1, [2, 3, 5, 10]) arr2 = [3, 3, 3, 1, 2, 3] quicksort_in_place(arr2) self.assertEqual(arr2, [1, 2, 3, 3, 3, 3]) arr_rev = [9, 8, 7, 6, 5, 4, 3, 2, 1] quicksort_in_place(arr_rev) self.assertEqual(arr_rev, [1, 2, 3, 4, 5, 6, 7, 8, 9]) # Pruebas de estrés y mitigación de peor caso (N = 1200 > límite de recursión por defecto) arr_large_sorted = list(range(1200)) quicksort_in_place(arr_large_sorted) self.assertEqual(arr_large_sorted, list(range(1200))) arr_large_rev = list(range(1200, 0, -1)) quicksort_in_place(arr_large_rev) self.assertEqual(arr_large_rev, list(range(1, 1201))) arr_large_dups = [7] * 1200 quicksort_in_place(arr_large_dups) self.assertEqual(arr_large_dups, [7] * 1200) def test_dia_15_quickselect(self): nums = [3, 2, 1, 5, 6, 4] self.assertEqual(quickselect(nums, 0), 1) # Mínimo self.assertEqual(quickselect(nums, 1), 2) self.assertEqual(quickselect(nums, 2), 3) self.assertEqual(quickselect(nums, 3), 4) self.assertEqual(quickselect(nums, 4), 5) self.assertEqual(quickselect(nums, 5), 6) # Máximo # Con duplicados dups = [3, 2, 3, 1, 2, 4, 5, 5, 6] self.assertEqual(quickselect(dups, 0), 1) self.assertEqual(quickselect(dups, 8), 6) # Validación con arreglos grandes y duplicados self.assertEqual(quickselect(list(range(1200)), 500), 500) self.assertEqual(quickselect([9] * 1200, 700), 9) # find_kth_largest (LC 215) self.assertEqual(find_kth_largest([3, 2, 1, 5, 6, 4], 2), 5) self.assertEqual(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), 4) self.assertEqual(find_kth_largest([1], 1), 1) # Excepciones with self.assertRaises(ValueError): quickselect([], 0) with self.assertRaises(ValueError): quickselect([1, 2], -1) with self.assertRaises(ValueError): quickselect([1, 2], 5) with self.assertRaises(ValueError): find_kth_largest([1, 2], 0) with self.assertRaises(ValueError): find_kth_largest([1, 2], 3) # --- DÍA 16: Hash Tables Avanzadas, Rehashing y RandomizedSet O(1) --- def test_dia_16_hash_table_chaining(self): ht = HashTableChaining[str, int](initial_capacity=4) ht.put("manzana", 10) ht.put("banana", 20) self.assertEqual(ht.get("manzana"), 10) self.assertEqual(ht.get("banana"), 20) self.assertEqual(len(ht), 2) self.assertTrue("manzana" in ht) self.assertFalse("pera" in ht) # Actualización de clave existente ht.put("manzana", 99) self.assertEqual(ht.get("manzana"), 99) self.assertEqual(len(ht), 2) # Eliminación val = ht.remove("manzana") self.assertEqual(val, 99) self.assertEqual(len(ht), 1) self.assertFalse("manzana" in ht) with self.assertRaises(KeyError): ht.get("manzana") with self.assertRaises(KeyError): ht.remove("manzana") # Rehashing automático al insertar múltiples claves for i in range(50): ht.put(f"key_{i}", i) self.assertEqual(len(ht), 51) for i in range(50): self.assertEqual(ht.get(f"key_{i}"), i) self.assertGreater(ht.capacity, 4) def test_dia_16_hash_table_linear_probing(self): ht = HashTableLinearProbing[str, int](initial_capacity=4) ht.put("alpha", 1) ht.put("beta", 2) self.assertEqual(ht.get("alpha"), 1) self.assertEqual(ht.get("beta"), 2) self.assertEqual(len(ht), 2) # Actualizar ht.put("alpha", 100) self.assertEqual(ht.get("alpha"), 100) # Borrar y comprobar lápida (Tombstone) self.assertEqual(ht.remove("alpha"), 100) self.assertFalse("alpha" in ht) with self.assertRaises(KeyError): ht.get("alpha") # Re-insertar en celda con lápida ht.put("alpha", 500) self.assertEqual(ht.get("alpha"), 500) # Rehashing con Open Addressing for i in range(30): ht.put(f"item_{i}", i * 10) for i in range(30): self.assertEqual(ht.get(f"item_{i}"), i * 10) self.assertGreater(ht.capacity, 4) # Verificar que actualizar una clave existente no dispara rehash prematuro ht_update = HashTableLinearProbing[str, int](initial_capacity=4) ht_update.put("k1", 1) ht_update.put("k2", 2) ht_update.put("k3", 3) cap_before = ht_update.capacity ht_update.put("k1", 999) # Actualización de clave ya existente self.assertEqual(ht_update.capacity, cap_before) self.assertEqual(ht_update.get("k1"), 999) self.assertEqual(len(ht_update), 3) def test_dia_16_randomized_set(self): rs = RandomizedSet() self.assertTrue(rs.insert(1)) self.assertFalse(rs.insert(1)) self.assertTrue(rs.insert(2)) self.assertEqual(len(rs), 2) # GetRandom debe retornar 1 o 2 rand_val = rs.get_random() self.assertIn(rand_val, [1, 2]) # Remove existente y no existente self.assertTrue(rs.remove(1)) self.assertFalse(rs.remove(1)) self.assertEqual(len(rs), 1) self.assertEqual(rs.get_random(), 2) # Swap and pop con múltiples elementos rs.insert(10) rs.insert(20) rs.insert(30) # Estado: [2, 10, 20, 30] self.assertTrue(rs.remove(10)) self.assertEqual(len(rs), 3) self.assertIn(rs.get_random(), [2, 20, 30]) # Vaciar y verificar error en get_random rs.remove(2) rs.remove(20) rs.remove(30) self.assertEqual(len(rs), 0) with self.assertRaises(IndexError): rs.get_random() # --- DÍA 17: Stacks & Queues Fundamentals y CTCI 3.1 Three in One --- def test_dia_17_stack_and_queue_fundamentals(self): # ArrayStack s_arr = ArrayStack[int]() self.assertTrue(s_arr.is_empty()) s_arr.push(10) s_arr.push(20) self.assertEqual(s_arr.peek(), 20) self.assertEqual(s_arr.pop(), 20) self.assertEqual(s_arr.pop(), 10) self.assertTrue(s_arr.is_empty()) with self.assertRaises(IndexError): s_arr.pop() with self.assertRaises(IndexError): s_arr.peek() # LinkedStack s_link = LinkedStack[str]() s_link.push("a") s_link.push("b") self.assertEqual(s_link.size(), 2) self.assertEqual(s_link.peek(), "b") self.assertEqual(s_link.pop(), "b") self.assertEqual(s_link.pop(), "a") self.assertTrue(s_link.is_empty()) with self.assertRaises(IndexError): s_link.pop() with self.assertRaises(IndexError): s_link.peek() # LinkedQueue q = LinkedQueue[int]() self.assertTrue(q.is_empty()) q.enqueue(1) q.enqueue(2) q.enqueue(3) self.assertEqual(q.size(), 3) self.assertEqual(q.peek(), 1) self.assertEqual(q.dequeue(), 1) self.assertEqual(q.dequeue(), 2) self.assertEqual(q.dequeue(), 3) self.assertTrue(q.is_empty()) with self.assertRaises(IndexError): q.dequeue() with self.assertRaises(IndexError): q.peek() def test_dia_17_valid_parentheses(self): self.assertTrue(is_valid_parentheses("")) self.assertTrue(is_valid_parentheses("()")) self.assertTrue(is_valid_parentheses("()[]{}")) self.assertTrue(is_valid_parentheses("{[()]}")) self.assertTrue(is_valid_parentheses("((({[()]})))")) self.assertFalse(is_valid_parentheses("(]")) self.assertFalse(is_valid_parentheses("([)]")) self.assertFalse(is_valid_parentheses("]")) self.assertFalse(is_valid_parentheses("(")) self.assertFalse(is_valid_parentheses("(((")) def test_dia_17_fixed_multi_stack(self): # Capacidad 3 para cada una de las 3 pilas ms = FixedMultiStack[int](stack_capacity=3) # Pilas vacías inicialmente for i in range(3): self.assertTrue(ms.is_empty(i)) self.assertFalse(ms.is_full(i)) self.assertEqual(ms.size(i), 0) # Operaciones independientes sobre la pila 0 ms.push(0, 10) ms.push(0, 20) ms.push(0, 30) self.assertTrue(ms.is_full(0)) self.assertEqual(ms.peek(0), 30) with self.assertRaises(IndexError): ms.push(0, 40) # Overflow # Operaciones independientes sobre la pila 1 ms.push(1, 100) self.assertEqual(ms.size(1), 1) self.assertEqual(ms.peek(1), 100) # Operaciones independientes sobre la pila 2 ms.push(2, 500) ms.push(2, 600) self.assertEqual(ms.size(2), 2) # Desapilar pila 0 self.assertEqual(ms.pop(0), 30) self.assertEqual(ms.pop(0), 20) self.assertEqual(ms.pop(0), 10) self.assertTrue(ms.is_empty(0)) with self.assertRaises(IndexError): ms.pop(0) # Underflow # Pila 1 y 2 permanecen intactas self.assertEqual(ms.pop(1), 100) self.assertEqual(ms.pop(2), 600) self.assertEqual(ms.pop(2), 500) # Validaciones de límites with self.assertRaises(IndexError): ms.push(3, 1) with self.assertRaises(IndexError): ms.pop(-1) with self.assertRaises(ValueError): FixedMultiStack[int](0) # Almacenar valores None válidos sin fallo de assertion ms_none = FixedMultiStack[Optional[str]](stack_capacity=2) ms_none.push(0, None) self.assertIsNone(ms_none.peek(0)) self.assertIsNone(ms_none.pop(0)) self.assertTrue(ms_none.is_empty(0)) # --- DÍA 18: Stack Min (CTCI 3.2) y SetOfStacks (CTCI 3.3) --- def test_dia_18_min_stack(self): ms = MinStack() self.assertTrue(ms.is_empty()) ms.push(5) self.assertEqual(ms.get_min(), 5) self.assertEqual(ms.top(), 5) ms.push(3) self.assertEqual(ms.get_min(), 3) ms.push(7) self.assertEqual(ms.get_min(), 3) ms.push(3) # Mínimo duplicado self.assertEqual(ms.get_min(), 3) # Desapilar duplicado de mínimo self.assertEqual(ms.pop(), 3) self.assertEqual(ms.get_min(), 3) # Desapilar 7 self.assertEqual(ms.pop(), 7) self.assertEqual(ms.get_min(), 3) # Desapilar 3 (el mínimo original) -> el nuevo mínimo debe ser 5 self.assertEqual(ms.pop(), 3) self.assertEqual(ms.get_min(), 5) # Desapilar 5 -> vacía self.assertEqual(ms.pop(), 5) self.assertTrue(ms.is_empty()) with self.assertRaises(IndexError): ms.pop() with self.assertRaises(IndexError): ms.top() with self.assertRaises(IndexError): ms.get_min() def test_dia_18_set_of_stacks(self): sos = SetOfStacks[int](capacity=3) self.assertTrue(sos.is_empty()) self.assertEqual(sos.stack_count(), 0) # Insertar 7 elementos (debe ocupar 3 sub-pilas: [3], [3], [1]) for i in range(1, 8): sos.push(i) self.assertEqual(sos.stack_count(), 3) self.assertEqual(sos.total_size(), 7) self.assertEqual(sos.peek(), 7) # Pop elemento 7 -> la tercera sub-pila queda vacía y se remueve self.assertEqual(sos.pop(), 7) self.assertEqual(sos.stack_count(), 2) self.assertEqual(sos.peek(), 6) # pop_at en sub-pila intermedia (índice 0) # Pila 0 tiene [1, 2, 3], pop_at(0) debe extraer 3 self.assertEqual(sos.pop_at(0), 3) self.assertEqual(sos.total_size(), 5) # Vaciar sub-pila 0 completamente self.assertEqual(sos.pop_at(0), 2) self.assertEqual(sos.pop_at(0), 1) # La sub-pila 0 fue destruida, la antigua sub-pila 1 ahora es índice 0 self.assertEqual(sos.stack_count(), 1) self.assertEqual(sos.peek(), 6) with self.assertRaises(IndexError): sos.pop_at(5) # Vaciar el resto self.assertEqual(sos.pop(), 6) self.assertEqual(sos.pop(), 5) self.assertEqual(sos.pop(), 4) self.assertTrue(sos.is_empty()) with self.assertRaises(IndexError): sos.pop() # Intercalación compleja de push y pop_at con destrucción de pilas intermedias sos2 = SetOfStacks[int](capacity=2) for val in range(6): sos2.push(val) # Pilas: [[0, 1], [2, 3], [4, 5]] self.assertEqual(sos2.stack_count(), 3) self.assertEqual(sos2.pop_at(1), 3) # Pila 1 queda con [2] self.assertEqual(sos2.pop_at(1), 2) # Pila 1 queda vacía y se destruye self.assertEqual(sos2.stack_count(), 2) # Quedan [[0, 1], [4, 5]] self.assertEqual(sos2.peek(), 5) sos2.push(99) # La última pila [4, 5] está llena -> crea [[0, 1], [4, 5], [99]] self.assertEqual(sos2.stack_count(), 3) self.assertEqual(sos2.pop(), 99) self.assertEqual(sos2.pop(), 5) self.assertEqual(sos2.pop(), 4) self.assertEqual(sos2.pop(), 1) self.assertEqual(sos2.pop(), 0) self.assertTrue(sos2.is_empty()) # --- DÍA 19: Queue via Stacks (CTCI 3.4) y Sort Stack (CTCI 3.5) --- def test_dia_19_queue_via_stacks(self): q = MyQueue[int]() self.assertTrue(q.is_empty()) q.push(1) q.push(2) self.assertEqual(q.peek(), 1) self.assertEqual(q.pop(), 1) q.push(3) q.push(4) self.assertEqual(q.pop(), 2) self.assertEqual(q.pop(), 3) self.assertEqual(q.pop(), 4) self.assertTrue(q.is_empty()) with self.assertRaises(IndexError): q.pop() with self.assertRaises(IndexError): q.peek() def test_dia_19_sort_stack(self): # Caso vacío y de 1 elemento self.assertEqual(sort_stack([]), []) self.assertEqual(sort_stack([42]), [42]) # Caso orden inverso -> resultado con menor en el tope [-1] res1 = sort_stack([1, 2, 3, 4, 5]) self.assertEqual(res1, [5, 4, 3, 2, 1]) self.assertEqual(res1[-1], 1) # Caso desordenado con duplicados st = [34, 3, 31, 98, 92, 23] res2 = sort_stack(st) self.assertEqual(res2, [98, 92, 34, 31, 23, 3]) self.assertEqual(res2[-1], 3) st_dups = [5, 1, 5, 2, 2] res3 = sort_stack(st_dups) self.assertEqual(res3, [5, 5, 2, 2, 1]) # --- DÍA 20: Animal Shelter (CTCI 3.6) --- def test_dia_20_animal_shelter(self): shelter = AnimalShelter() self.assertTrue(shelter.is_empty()) self.assertIsNone(shelter.dequeue_any()) self.assertIsNone(shelter.dequeue_dog()) self.assertIsNone(shelter.dequeue_cat()) dog1 = Dog("Rex") cat1 = Cat("Mishi") dog2 = Dog("Bobby") cat2 = Cat("Luna") shelter.enqueue(dog1) shelter.enqueue(cat1) shelter.enqueue(dog2) shelter.enqueue(cat2) self.assertEqual(shelter.size(), 4) # dequeue_any debe retornar a Rex (llegó primero) first = shelter.dequeue_any() self.assertIsNotNone(first) self.assertEqual(first.name, "Rex") # dequeue_cat debe retornar a Mishi (la gata más antigua) first_cat = shelter.dequeue_cat() self.assertIsNotNone(first_cat) self.assertEqual(first_cat.name, "Mishi") # dequeue_dog debe retornar a Bobby first_dog = shelter.dequeue_dog() self.assertIsNotNone(first_dog) self.assertEqual(first_dog.name, "Bobby") # Ahora no quedan perros self.assertIsNone(shelter.dequeue_dog()) # dequeue_any debe entregar a Luna last = shelter.dequeue_any() self.assertIsNotNone(last) self.assertEqual(last.name, "Luna") self.assertTrue(shelter.is_empty()) # Excepción con tipo no admitido class Bird: pass with self.assertRaises(TypeError): shelter.enqueue(Bird()) # type: ignore # --- DÍA 21: Monotonic Stack (LC 739, LC 496, LC 503) --- def test_dia_21_daily_temperatures(self): # Casos clásicos LC 739 self.assertEqual( daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0] ) self.assertEqual(daily_temperatures([30, 40, 50, 60]), [1, 1, 1, 0]) self.assertEqual(daily_temperatures([30, 60, 90]), [1, 1, 0]) # Monótona estrictamente decreciente (ningún día más cálido) self.assertEqual(daily_temperatures([90, 80, 70, 60]), [0, 0, 0, 0]) # Casos borde: vacía y 1 elemento self.assertEqual(daily_temperatures([]), []) self.assertEqual(daily_temperatures([80]), [0]) def test_dia_21_next_greater_element(self): # LC 496 self.assertEqual( next_greater_element([4, 1, 2], [1, 3, 4, 2]), [-1, 3, -1] ) self.assertEqual( next_greater_element([2, 4], [1, 2, 3, 4]), [3, -1] ) self.assertEqual(next_greater_element([], [1, 2]), []) # LC 503: Circular self.assertEqual(next_greater_element_circular([1, 2, 1]), [2, -1, 2]) self.assertEqual( next_greater_element_circular([1, 2, 3, 4, 3]), [2, 3, 4, -1, 4] ) self.assertEqual( next_greater_element_circular([5, 4, 3, 2, 1]), [-1, 5, 5, 5, 5] ) self.assertEqual(next_greater_element_circular([]), []) self.assertEqual(next_greater_element_circular([10]), [-1]) # --- DÍA 22: Grafos, BFS y CTCI 4.1 Route Between Nodes --- def test_dia_22_graph_bfs_and_route_between_nodes(self): # Grafo dirigido g = Graph[str](directed=True) edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E"), ("E", "F"), ("F", "D")] # Ciclo D->E->F->D for u, v in edges: g.add_edge(u, v) # BFS camino más corto path = bfs_shortest_path(g, "A", "E") self.assertIn(path, [["A", "B", "D", "E"], ["A", "C", "D", "E"]]) self.assertEqual(len(path), 4) # Mismo origen y destino self.assertEqual(bfs_shortest_path(g, "A", "A"), ["A"]) # Nodos no conectados g.add_vertex("Z") self.assertIsNone(bfs_shortest_path(g, "A", "Z")) self.assertFalse(has_route_bfs(g, "A", "Z")) self.assertFalse(has_route_dfs(g, "A", "Z")) # CTCI 4.1: Rutas dirigidas existentes self.assertTrue(has_route_bfs(g, "A", "F")) self.assertTrue(has_route_dfs(g, "A", "F")) # Ruta en sentido inverso no existe self.assertFalse(has_route_bfs(g, "F", "A")) self.assertFalse(has_route_dfs(g, "F", "A")) # BFS Bidireccional # Construir grafo inverso explícito g_rev = Graph[str](directed=True) for u, v in edges: g_rev.add_edge(v, u) g_rev.add_vertex("Z") # Modo 1: con reverse_graph explícito self.assertTrue(has_route_bidirectional_bfs(g, g_rev, "A", "F")) self.assertFalse(has_route_bidirectional_bfs(g, g_rev, "F", "A")) self.assertFalse(has_route_bidirectional_bfs(g, g_rev, "A", "Z")) # Modo 2: auto-transpuesto mediante g.transpose() g_transposed = g.transpose() self.assertEqual(g_transposed.num_edges(), g.num_edges()) self.assertTrue(has_route_bidirectional_bfs(g, "A", "F")) self.assertFalse(has_route_bidirectional_bfs(g, "F", "A")) self.assertFalse(has_route_bidirectional_bfs(g, "A", "Z")) # Find all paths (DAG simple sin ciclos o con poda de visitados) dag = Graph[str](directed=True) dag.add_edge("S", "A") dag.add_edge("S", "B") dag.add_edge("A", "T") dag.add_edge("B", "T") all_paths = find_all_paths(dag, "S", "T") self.assertEqual(len(all_paths), 2) self.assertIn(["S", "A", "T"], all_paths) self.assertIn(["S", "B", "T"], all_paths) # --- DÍA 23: Árboles Binarios, Recorridos, CTCI 4.2 y CTCI 4.3 --- def test_dia_23_binary_tree_traversals_minimal_tree(self): # CTCI 4.2: Minimal Tree desde arreglo ordenado nums = [1, 2, 3, 4, 5, 6, 7] bst = sorted_array_to_minimal_bst(nums) self.assertIsNotNone(bst) self.assertEqual(bst.val, 4) self.assertEqual(tree_height(bst), 3) # In-Order de un BST reconstruye el arreglo ordenado original self.assertEqual(inorder_traversal(bst), nums) self.assertEqual(inorder_traversal_iterative(bst), nums) # Pre-Order y Post-Order recursivo vs iterativo pre = preorder_traversal(bst) self.assertEqual(pre, preorder_traversal_iterative(bst)) self.assertEqual(pre[0], 4) # Raíz es la primera post = postorder_traversal(bst) self.assertEqual(post, postorder_traversal_iterative(bst)) self.assertEqual(post[-1], 4) # Raíz es la última self.assertEqual(postorder_traversal_iterative(None), []) # CTCI 4.3: List of Depths (BFS y DFS deben ser idénticos) levels_bfs = list_of_depths_bfs(bst) levels_dfs = list_of_depths_dfs(bst) self.assertEqual(levels_bfs, [[4], [2, 6], [1, 3, 5, 7]]) self.assertEqual(levels_bfs, levels_dfs) # Casos borde: árbol vacío y 1 nodo self.assertIsNone(sorted_array_to_minimal_bst([])) self.assertEqual(inorder_traversal(None), []) single = sorted_array_to_minimal_bst([42]) self.assertIsNotNone(single) self.assertEqual(single.val, 42) self.assertEqual(tree_height(single), 1) # Serialización y deserialización nivel por nivel tree_list = [3, 9, 20, None, None, 15, 7] deserialized = build_tree_from_level_order(tree_list) self.assertIsNotNone(deserialized) self.assertEqual(tree_to_level_order(deserialized), tree_list) # --- DÍA 24: Validate BST (CTCI 4.5) y Check Balanced (CTCI 4.4) --- def test_dia_24_validate_bst_and_check_balanced(self): # 1. BST Válido valid_bst = build_tree_from_level_order([10, 5, 15, 2, 7, 12, 20]) self.assertTrue(is_valid_bst_bounds(valid_bst)) self.assertTrue(is_valid_bst_inorder(valid_bst)) # 2. BST Inválido: Falacia local comprobada # 10 # / \ # 5 15 # / \ # 6 20 # 6 < 15 y 6 < 20, localmente parece válido, pero 6 < 10 (viola subárbol derecho de la raíz) fallacy_tree = build_tree_from_level_order([10, 5, 15, None, None, 6, 20]) self.assertTrue(is_valid_bst_naive_fallacy(fallacy_tree)) # La comprobación ingenua cae en la trampa self.assertFalse(is_valid_bst_bounds(fallacy_tree)) # La solución óptima detecta el error self.assertFalse(is_valid_bst_inorder(fallacy_tree)) # 3. BST con duplicados (estrictamente inválido según definición de BST estándar) dups_tree = build_tree_from_level_order([10, 10, 15]) self.assertFalse(is_valid_bst_bounds(dups_tree)) self.assertFalse(is_valid_bst_inorder(dups_tree)) # Árbol vacío y nodo único self.assertTrue(is_valid_bst_bounds(None)) self.assertTrue(is_valid_bst_inorder(None)) self.assertTrue(is_valid_bst_bounds(TreeNode(99))) # 4. CTCI 4.4: Check Balanced # Árbol balanceado bal_tree = build_tree_from_level_order([3, 9, 20, None, None, 15, 7]) self.assertTrue(is_balanced(bal_tree)) self.assertTrue(is_balanced_naive(bal_tree)) is_bal, h = check_balanced_optimal(bal_tree) self.assertTrue(is_bal) self.assertEqual(h, 3) # Árbol no balanceado # 1 # / # 2 # / # 3 unbal_tree = TreeNode(1, TreeNode(2, TreeNode(3))) self.assertFalse(is_balanced(unbal_tree)) self.assertFalse(is_balanced_naive(unbal_tree)) is_bal_unbal, _ = check_balanced_optimal(unbal_tree) self.assertFalse(is_bal_unbal) # Árbol vacío es balanceado self.assertTrue(is_balanced(None)) # --- DÍA 25: Successor (CTCI 4.6) y Lowest Common Ancestor (CTCI 4.8) --- def test_dia_25_successor_and_lca(self): # 1. CTCI 4.6: In-Order Successor con punteros al padre # Construir BST con TreeNodeWithParent: # 20 # / \ # 10 30 # / \ # 5 15 # / # 12 n20 = TreeNodeWithParent(20) n10 = TreeNodeWithParent(10, parent=n20) n30 = TreeNodeWithParent(30, parent=n20) n20.left, n20.right = n10, n30 n5 = TreeNodeWithParent(5, parent=n10) n15 = TreeNodeWithParent(15, parent=n10) n10.left, n10.right = n5, n15 n12 = TreeNodeWithParent(12, parent=n15) n15.left = n12 # Sucesor de 10 es 12 (el más a la izquierda de su hijo derecho 15) s10 = inorder_successor_with_parent(n10) self.assertIsNotNone(s10) self.assertEqual(s10.val, 12) # Sucesor de 15 es 20 (sube por los ancestros hasta llegar por rama izquierda) s15 = inorder_successor_with_parent(n15) self.assertIsNotNone(s15) self.assertEqual(s15.val, 20) # Sucesor de 5 es 10 s5 = inorder_successor_with_parent(n5) self.assertIsNotNone(s5) self.assertEqual(s5.val, 10) # Sucesor del máximo (30) es None self.assertIsNone(inorder_successor_with_parent(n30)) # Sucesor sin puntero padre (LeetCode 285) bst_root = build_tree_from_level_order([20, 10, 30, 5, 15, None, None, None, None, 12, None]) # Buscamos target 15 target_15 = bst_root.left.right succ_no_p = inorder_successor_no_parent(bst_root, target_15) self.assertIsNotNone(succ_no_p) self.assertEqual(succ_no_p.val, 20) # 2. CTCI 4.8 / LC 236: Lowest Common Ancestor en árbol binario general # LCA de 5 y 12 es 10 lca1 = lca_binary_tree(bst_root, bst_root.left.left, bst_root.left.right.left) self.assertIsNotNone(lca1) self.assertEqual(lca1.val, 10) # LCA de 5 y 30 es 20 (la raíz) lca2 = lca_binary_tree(bst_root, bst_root.left.left, bst_root.right) self.assertIsNotNone(lca2) self.assertEqual(lca2.val, 20) # LCA donde uno es ancestro del otro (10 y 12 -> LCA es 10) lca3 = lca_binary_tree(bst_root, bst_root.left, bst_root.left.right.left) self.assertEqual(lca3.val, 10) # LCA con punteros padre (Set vs Óptimo O(1)) lca_p_set = lca_with_parent_pointers_set(n5, n12) lca_p_opt = lca_with_parent_pointers_optimal(n5, n12) self.assertEqual(lca_p_set, n10) self.assertEqual(lca_p_opt, n10) # LCA en BST (LC 235) lca_bst_res = lca_bst(bst_root, bst_root.left.left, bst_root.left.right.left) self.assertIsNotNone(lca_bst_res) self.assertEqual(lca_bst_res.val, 10) # 3. Trampa Clásica CTCI 4.8: Validación de existencia de nodos missing_q = TreeNode(999) self.assertIsNone(lca_binary_tree(bst_root, bst_root.left, missing_q)) self.assertIsNone(lca_binary_tree(bst_root, missing_q, bst_root.right)) self.assertIsNone(lca_binary_tree(bst_root, missing_q, TreeNode(888))) self.assertIsNone(lca_binary_tree(None, bst_root.left, bst_root.right)) # LCA en BST con nodos que no existen en el árbol self.assertIsNone(lca_bst(bst_root, TreeNode(25), TreeNode(35))) self.assertIsNone(lca_bst(bst_root, bst_root.left, missing_q)) self.assertIsNone(lca_bst(None, bst_root.left, bst_root.right)) # --- DÍA 26: Build Order / Topological Sort (CTCI 4.7) --- def test_dia_26_topological_sort_build_order(self): # Caso clásico de CTCI 4.7 # Proyectos: a, b, c, d, e, f # Dependencias: (a, d), (f, b), (b, d), (f, a), (d, c) projects = ["a", "b", "c", "d", "e", "f"] dependencies = [("a", "d"), ("f", "b"), ("b", "d"), ("f", "a"), ("d", "c")] order_kahn = build_order_kahn(projects, dependencies) order_dfs = build_order_dfs(projects, dependencies) # Verificar que todos los proyectos estén presentes self.assertEqual(set(order_kahn), set(projects)) self.assertEqual(set(order_dfs), set(projects)) # Verificar la invariante topológica para todas las aristas (u debe preceder a v) def _verify_topological(order: List[str]) -> bool: pos = {p: i for i, p in enumerate(order)} for u, v in dependencies: if pos[u] >= pos[v]: return False return True self.assertTrue(_verify_topological(order_kahn)) self.assertTrue(_verify_topological(order_dfs)) self.assertFalse(has_cycle_directed(projects, dependencies)) # Detección de Ciclo (dependencia circular) # a -> b -> c -> a cyclic_projects = ["a", "b", "c"] cyclic_deps = [("a", "b"), ("b", "c"), ("c", "a")] self.assertTrue(has_cycle_directed(cyclic_projects, cyclic_deps)) with self.assertRaises(ValueError): build_order_kahn(cyclic_projects, cyclic_deps) with self.assertRaises(ValueError): build_order_dfs(cyclic_projects, cyclic_deps) # Múltiples órdenes topológicos válidos indep_projects = ["A", "B"] all_orders = find_all_build_orders(indep_projects, []) self.assertEqual(len(all_orders), 2) self.assertIn(["A", "B"], all_orders) self.assertIn(["B", "A"], all_orders) # --- DÍA 27: Check Subtree (CTCI 4.10) y Paths with Sum (CTCI 4.12) --- def test_dia_27_subtree_and_paths_with_sum(self): # 1. CTCI 4.10: Check Subtree (LC 572) t1 = build_tree_from_level_order([3, 4, 5, 1, 2]) t2_sub = build_tree_from_level_order([4, 1, 2]) t3_not_sub = build_tree_from_level_order([4, 1, 3]) self.assertTrue(check_subtree(t1, t2_sub)) self.assertTrue(check_subtree_serialization(t1, t2_sub)) self.assertFalse(check_subtree(t1, t3_not_sub)) self.assertFalse(check_subtree_serialization(t1, t3_not_sub)) # Árbol vacío siempre es subárbol self.assertTrue(check_subtree(t1, None)) self.assertTrue(check_subtree_serialization(t1, None)) # Árbol no vacío no puede ser subárbol de None self.assertFalse(check_subtree(None, t2_sub)) self.assertFalse(check_subtree_serialization(None, t2_sub)) # 2. CTCI 4.12: Paths with Sum (LC 437) # Árbol de LeetCode 437: # 10 # / \ # 5 -3 # / \ \ # 3 2 11 # / \ \ # 3 -2 1 # Target sum = 8 # Caminos válidos: [5, 3], [5, 2, 1], [-3, 11] -> Total 3 lc437_tree = build_tree_from_level_order([10, 5, -3, 3, 2, None, 11, 3, -2, None, 1]) paths_opt = paths_with_sum_optimal(lc437_tree, 8) paths_naive = paths_with_sum_naive(lc437_tree, 8) self.assertEqual(paths_opt, 3) self.assertEqual(paths_naive, 3) # Encontrar los caminos explícitos all_paths = find_all_paths_with_sum(lc437_tree, 8) self.assertEqual(len(all_paths), 3) self.assertIn([5, 3], all_paths) self.assertIn([5, 2, 1], all_paths) self.assertIn([-3, 11], all_paths) # Casos borde: árbol vacío y sin coincidencias self.assertEqual(paths_with_sum_optimal(None, 8), 0) self.assertEqual(paths_with_sum_optimal(lc437_tree, 9999), 0) # --- DÍA 28: Dijkstra Shortest Path (Grokking Ch 7) --- def test_dia_28_dijkstra_shortest_path(self): # Grafo ponderado canónico de Grokking Algorithms Cap. 7 # Start -> A (6), Start -> B (2) # B -> A (3), B -> Fin (5) # A -> Fin (1) wg = WeightedGraph[str](directed=True) wg.add_edge("start", "A", 6) wg.add_edge("start", "B", 2) wg.add_edge("B", "A", 3) wg.add_edge("B", "fin", 5) wg.add_edge("A", "fin", 1) distances, parents = dijkstra_shortest_path(wg, "start") # La distancia mínima a 'fin' debe ser 6 (start -> B -> A -> fin = 2 + 3 + 1 = 6) # y NO 7 (start -> B -> fin = 7 o start -> A -> fin = 7) self.assertEqual(distances["fin"], 6.0) self.assertEqual(distances["A"], 5.0) self.assertEqual(distances["B"], 2.0) self.assertEqual(distances["start"], 0.0) # Reconstrucción del camino path = reconstruct_shortest_path(parents, "start", "fin") self.assertEqual(path, ["start", "B", "A", "fin"]) # Nodos no alcanzables wg.add_vertex("isla_desierta") dist2, parent2 = dijkstra_shortest_path(wg, "start") self.assertEqual(dist2["isla_desierta"], float("inf")) self.assertIsNone(reconstruct_shortest_path(parent2, "start", "isla_desierta")) # Error en aristas con peso negativo with self.assertRaises(ValueError): wg.add_edge("A", "B", -5) # Dijkstra en Grilla 2D (LeetCode 743 / Path with Minimum Cost) # Grilla 3x3: # [1, 3, 1] # [1, 5, 1] # [4, 2, 1] # Camino óptimo: (0,0)->(1,0)->(1,1)... o (0,0)->(0,1)->(0,2)->(1,2)->(2,2): # 1 -> 3 -> 1 -> 1 -> 1 = 7. # Mejor camino: (0,0)=1 -> (1,0)=1 -> (1,1) no -> (2,1)=2 -> (2,2)=1 = 1+1+4? no: # (0,0)=1 -> (1,0)=1 -> (1,1)=5 (7) # (0,0)=1 -> (0,1)=3 -> (0,2)=1 -> (1,2)=1 -> (2,2)=1 = 7 grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1], ] min_cost = dijkstra_grid_min_cost(grid, (0, 0), (2, 2)) self.assertEqual(min_cost, 7) # --- DÍA 24 Casos Borde: BST y Balance --- def test_dia_24_validate_bst_edge_cases(self): # Violación profunda en subárbol izquierdo (nodo mayor que un ancestro) # 20 # / # 10 # \ # 25 (25 > 20, inválido!) tree_violation = TreeNode(20, TreeNode(10, None, TreeNode(25))) self.assertFalse(is_valid_bst_bounds(tree_violation)) self.assertFalse(is_valid_bst_inorder(tree_violation)) # Árbol degenerado lineal válido (estrictamente creciente) # 1 -> 2 -> 3 -> 4 linear_bst = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4)))) self.assertTrue(is_valid_bst_bounds(linear_bst)) self.assertTrue(is_valid_bst_inorder(linear_bst)) # Pero no está balanceado self.assertFalse(is_balanced(linear_bst)) self.assertFalse(is_balanced_iterative(linear_bst)) # Estrés de Árbol Degenerado Profundo (N = 1200 > Python default recursion limit 1000) # Debe resolverse iterativamente sin RecursionError deep_curr = TreeNode(0) deep_root = deep_curr for i in range(1, 1200): deep_curr.right = TreeNode(i) deep_curr = deep_curr.right self.assertFalse(is_balanced(deep_root)) self.assertFalse(is_balanced_iterative(deep_root)) # Soporte de duplicados en BST según definición CTCI (left <= root < right) dup_left_tree = TreeNode(10, TreeNode(10), None) self.assertTrue(is_valid_bst_bounds(dup_left_tree, allow_duplicates=True)) self.assertFalse(is_valid_bst_bounds(dup_left_tree, allow_duplicates=False)) dup_right_tree = TreeNode(10, None, TreeNode(10)) self.assertFalse(is_valid_bst_bounds(dup_right_tree, allow_duplicates=True)) # --- DÍA 26 Casos Borde: Build Order --- def test_dia_26_build_order_edge_cases(self): # Proyectos independientes sin ninguna arista projects = ["X", "Y", "Z"] order = build_order_kahn(projects, []) self.assertEqual(set(order), {"X", "Y", "Z"}) # Auto-dependencia (self-loop: A depende de A) with self.assertRaises(ValueError): build_order_kahn(["A"], [("A", "A")]) # Cadena lineal: A -> B -> C -> D chain_projects = ["A", "B", "C", "D"] chain_deps = [("A", "B"), ("B", "C"), ("C", "D")] self.assertEqual(build_order_kahn(chain_projects, chain_deps), ["A", "B", "C", "D"]) # Error por nodo inexistente en dependencias (Kahn y find_all_build_orders) with self.assertRaises(KeyError): build_order_kahn(["A", "B"], [("A", "C")]) with self.assertRaises(KeyError): find_all_build_orders(["A", "B"], [("A", "C")]) # --- DÍA 27 Casos Borde: Subtree y Paths with Sum --- def test_dia_27_paths_with_sum_edge_cases(self): # Nodo único igual a target_sum single_target = TreeNode(5) self.assertEqual(paths_with_sum_optimal(single_target, 5), 1) self.assertEqual(paths_with_sum_naive(single_target, 5), 1) # Nodos negativos y suma cero: 1 -> -1 -> 1 -> -1 # Caminos que suman 0: [1, -1] (2 veces), [-1, 1], [1, -1, 1, -1] -> varios cancel_tree = TreeNode(1, TreeNode(-1, TreeNode(1, TreeNode(-1)))) self.assertEqual(paths_with_sum_optimal(cancel_tree, 0), paths_with_sum_naive(cancel_tree, 0)) # Árbol con todos negativos: -2 -> -3 (target -5) neg_tree = TreeNode(-2, TreeNode(-3)) self.assertEqual(paths_with_sum_optimal(neg_tree, -5), 1) # T2 más grande que T1 nunca puede ser subárbol t_small = TreeNode(1) t_large = TreeNode(1, TreeNode(2), TreeNode(3)) self.assertFalse(check_subtree(t_small, t_large)) self.assertFalse(check_subtree_serialization(t_small, t_large)) # --- DÍA 28 Casos Borde: Dijkstra --- def test_dia_28_dijkstra_edge_cases(self): wg = WeightedGraph[str](directed=True) wg.add_edge("A", "B", 10) wg.add_vertex("C") # Desconectado # Origen desconocido with self.assertRaises(KeyError): dijkstra_shortest_path(wg, "INEXISTENTE") # Origen igual a target dist, parents = dijkstra_shortest_path(wg, "A", target="A") self.assertEqual(dist["A"], 0.0) self.assertEqual(reconstruct_shortest_path(parents, "A", "A"), ["A"]) # Grid 1x1 self.assertEqual(dijkstra_grid_min_cost([[42]]), 42) # Grid con costos negativos debe lanzar ValueError with self.assertRaises(ValueError): dijkstra_grid_min_cost([[1, -2], [3, 4]]) def test_dia_22_graph_transpose_and_bidirectional(self): # Transpuesto en grafo dirigido g = Graph[str](directed=True) g.add_edge("X", "Y") g.add_edge("Y", "Z") gt = g.transpose() self.assertEqual(gt.get_neighbors("Z"), ["Y"]) self.assertEqual(gt.get_neighbors("Y"), ["X"]) self.assertEqual(gt.get_neighbors("X"), []) # BFS Bidireccional autónomo (sin reverse_graph manual) self.assertTrue(has_route_bidirectional_bfs(g, "X", "Z")) self.assertFalse(has_route_bidirectional_bfs(g, "Z", "X")) def test_dia_23_postorder_traversal_iterative(self): # Árbol complejo: [1, 2, 3, 4, 5, 6, 7] # Post-order: 4, 5, 2, 6, 7, 3, 1 root = TreeNode( 1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)), ) self.assertEqual( postorder_traversal_iterative(root), [4, 5, 2, 6, 7, 3, 1] ) self.assertEqual( postorder_traversal_iterative(root), postorder_traversal(root) ) self.assertEqual(postorder_traversal_iterative(None), []) self.assertEqual(postorder_traversal_iterative(TreeNode(99)), [99]) def test_dia_24_deep_degenerate_tree_balance(self): # Árbol profundamente degenerado de 1500 nodos (supera recursionlimit de Python 1000) curr = TreeNode(0) root = curr for i in range(1, 1500): curr.right = TreeNode(i) curr = curr.right # No debe lanzar RecursionError y debe retornar False self.assertFalse(is_balanced_iterative(root)) self.assertFalse(is_balanced(root)) def test_dia_25_lca_missing_nodes(self): # Validación de inexistencia según CTCI 4.8 (evitar falsos positivos) root = TreeNode(10, TreeNode(5), TreeNode(15)) p = root.left # 5 (existe) q_missing = TreeNode(999) # 999 (NO existe) self.assertIsNone(lca_binary_tree(root, p, q_missing)) self.assertIsNone(lca_binary_tree(root, q_missing, root.right)) self.assertIsNone(lca_binary_tree(root, TreeNode(1), TreeNode(2))) # BST LCA con nodos faltantes self.assertIsNone(lca_bst(root, TreeNode(1), TreeNode(2))) self.assertIsNone(lca_bst(root, p, q_missing)) def test_dia_27_find_all_paths_edge_cases(self): # Casos borde en búsqueda explícita de todos los caminos self.assertEqual(find_all_paths_with_sum(None, 10), []) single = TreeNode(7) self.assertEqual(find_all_paths_with_sum(single, 7), [[7]]) self.assertEqual(find_all_paths_with_sum(single, 8), []) # Árbol con ceros consecutivos: 0 -> 0 (target 0) # Caminos válidos: [0] (raíz), [0] (hijo), [0, 0] (ambos) zeros_tree = TreeNode(0, TreeNode(0)) zero_paths = find_all_paths_with_sum(zeros_tree, 0) self.assertEqual(len(zero_paths), 3) self.assertIn([0], zero_paths) self.assertIn([0, 0], zero_paths) def test_dia_28_dijkstra_negative_weight_rejection(self): # Dijkstra prohíbe pesos negativos tanto en grafos generales como en grillas wg = WeightedGraph[str](directed=True) with self.assertRaises(ValueError): wg.add_edge("U", "V", -1.0) with self.assertRaises(ValueError): dijkstra_grid_min_cost([[0, -1], [2, 3]]) # --- SEMANA 5: REFUERZO, EVALUACIÓN Y CONSOLIDACIÓN GLOBAL (DÍAS 29 AL 35) --- # --- DÍA 29: Arrays, Strings, Two Pointers & Sliding Window --- def test_dia_29_sliding_window_longest_substring(self): # LC 3: Longest Substring Without Repeating Characters self.assertEqual(length_of_longest_substring("abcabcbb"), 3) self.assertEqual(length_of_longest_substring("bbbbb"), 1) self.assertEqual(length_of_longest_substring("pwwkew"), 3) self.assertEqual(length_of_longest_substring(""), 0) self.assertEqual(length_of_longest_substring(" "), 1) self.assertEqual(length_of_longest_substring("au"), 2) self.assertEqual(length_of_longest_substring("dvdf"), 3) self.assertEqual(length_of_longest_substring("abba"), 2) self.assertEqual(length_of_longest_substring("tmmzuxt"), 5) # Variante reconstructiva de cadena self.assertEqual(longest_substring_without_repeating(""), "") self.assertEqual(longest_substring_without_repeating("bbbbb"), "b") self.assertIn( longest_substring_without_repeating("abcabcbb"), ["abc", "bca", "cab"], ) self.assertEqual(len(longest_substring_without_repeating("tmmzuxt")), 5) def test_dia_29_container_with_most_water(self): # LC 11: Container With Most Water self.assertEqual(max_area_container([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49) self.assertEqual(max_area_container([1, 1]), 1) self.assertEqual(max_area_container([4, 3, 2, 1, 4]), 16) self.assertEqual(max_area_container([1, 2, 1]), 2) self.assertEqual(max_area_container([]), 0) self.assertEqual(max_area_container([5]), 0) self.assertEqual(max_area_container([5, 5, 5, 5]), 15) # Variante diagnóstica con índices area, l, r = max_area_container_indices([1, 8, 6, 2, 5, 4, 8, 3, 7]) self.assertEqual(area, 49) self.assertEqual((l, r), (1, 8)) self.assertEqual(max_area_container_indices([]), (0, -1, -1)) self.assertEqual(max_area_container_indices([10]), (0, -1, -1)) # --- DÍA 30: Linked Lists In-Place & Heaps --- def test_dia_30_reverse_linked_list_ii(self): # LC 92: Reverse Linked List II head = build_linked_list([1, 2, 3, 4, 5]) res = reverse_between(head, 2, 4) self.assertEqual(to_list(res), [1, 4, 3, 2, 5]) # Inversión de lista completa head2 = build_linked_list([1, 2, 3]) self.assertEqual(to_list(reverse_between(head2, 1, 3)), [3, 2, 1]) # Caso borde: un solo nodo head3 = build_linked_list([5]) self.assertEqual(to_list(reverse_between(head3, 1, 1)), [5]) # Caso borde: left == right head4 = build_linked_list([1, 2, 3]) self.assertEqual(to_list(reverse_between(head4, 2, 2)), [1, 2, 3]) # Caso borde: inversión en la cabeza (left = 1) head5 = build_linked_list([10, 20, 30]) self.assertEqual(to_list(reverse_between(head5, 1, 2)), [20, 10, 30]) # Caso borde: lista vacía self.assertIsNone(reverse_between(None, 1, 2)) def test_dia_30_merge_k_sorted_lists(self): # LC 23: Merge k Sorted Lists (Min-Heap vs Divide & Conquer) lists_data = [[1, 4, 5], [1, 3, 4], [2, 6]] expected = [1, 1, 2, 3, 4, 4, 5, 6] # Min-Heap heap_heads = [build_linked_list(l) for l in lists_data] res_heap = merge_k_lists_heap(heap_heads) self.assertEqual(to_list(res_heap), expected) # Divide & Conquer dc_heads = [build_linked_list(l) for l in lists_data] res_dc = merge_k_lists_divide_and_conquer(dc_heads) self.assertEqual(to_list(res_dc), expected) # Casos borde self.assertIsNone(merge_k_lists_heap([])) self.assertIsNone(merge_k_lists_divide_and_conquer([])) self.assertIsNone(merge_k_lists_heap([None, None])) self.assertIsNone(merge_k_lists_divide_and_conquer([None, None])) # Mezcla con nodos vacíos intercalados mixed_heap = [None, build_linked_list([3]), None, build_linked_list([1, 2])] self.assertEqual(to_list(merge_k_lists_heap(mixed_heap)), [1, 2, 3]) mixed_dc = [None, build_linked_list([3]), None, build_linked_list([1, 2])] self.assertEqual(to_list(merge_k_lists_divide_and_conquer(mixed_dc)), [1, 2, 3]) # --- DÍA 31: Stacks, Queues & Monotonic Stack --- def test_dia_31_largest_rectangle_histogram(self): # LC 84: Largest Rectangle in Histogram self.assertEqual(largest_rectangle_area([2, 1, 5, 6, 2, 3]), 10) self.assertEqual(largest_rectangle_area([2, 4]), 4) self.assertEqual(largest_rectangle_area([2, 2, 2, 2]), 8) self.assertEqual(largest_rectangle_area([1, 2, 3, 4, 5]), 9) self.assertEqual(largest_rectangle_area([5, 4, 3, 2, 1]), 9) self.assertEqual(largest_rectangle_area([7]), 7) self.assertEqual(largest_rectangle_area([0, 0, 0]), 0) self.assertEqual(largest_rectangle_area([]), 0) # Variante diagnóstica area, left, right, h = largest_rectangle_area_details([2, 1, 5, 6, 2, 3]) self.assertEqual(area, 10) self.assertEqual(h, 5) self.assertEqual((left, right), (2, 3)) self.assertEqual(largest_rectangle_area_details([]), (0, -1, -1, 0)) def test_dia_31_decode_string(self): # LC 394: Decode String self.assertEqual(decode_string("3[a]2[bc]"), "aaabcbc") self.assertEqual(decode_string("3[a2[c]]"), "accaccacc") self.assertEqual(decode_string("2[abc]3[cd]ef"), "abcabccdcdcdef") self.assertEqual(decode_string("abc3[cd]xyz"), "abccdcdcdxyz") self.assertEqual(decode_string("10[a]"), "aaaaaaaaaa") self.assertEqual(decode_string(""), "") self.assertEqual(decode_string("leetcode"), "leetcode") # --- DÍA 32: Árboles Binarios & BST --- def test_dia_32_build_tree_preorder_inorder(self): # LC 105: Construct Binary Tree from Preorder and Inorder Traversal preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] root = build_tree_preorder_inorder(preorder, inorder) self.assertIsNotNone(root) self.assertEqual(preorder_traversal(root), preorder) self.assertEqual(inorder_traversal(root), inorder) # Un solo nodo single_root = build_tree_preorder_inorder([1], [1]) self.assertIsNotNone(single_root) self.assertEqual(single_root.val, 1) self.assertIsNone(single_root.left) self.assertIsNone(single_root.right) # Árbol degenerado a la izquierda left_skewed = build_tree_preorder_inorder([3, 2, 1], [1, 2, 3]) self.assertEqual(preorder_traversal(left_skewed), [3, 2, 1]) self.assertEqual(inorder_traversal(left_skewed), [1, 2, 3]) # Árbol degenerado a la derecha right_skewed = build_tree_preorder_inorder([1, 2, 3], [1, 2, 3]) self.assertEqual(preorder_traversal(right_skewed), [1, 2, 3]) self.assertEqual(inorder_traversal(right_skewed), [1, 2, 3]) # Casos inválidos / vacíos self.assertIsNone(build_tree_preorder_inorder([], [])) self.assertIsNone(build_tree_preorder_inorder([1], [1, 2])) def test_dia_32_max_path_sum(self): # LC 124: Binary Tree Maximum Path Sum root1 = TreeNode(1, TreeNode(2), TreeNode(3)) self.assertEqual(max_path_sum(root1), 6) root2 = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))) self.assertEqual(max_path_sum(root2), 42) # Todos negativos root_neg = TreeNode(-3) self.assertEqual(max_path_sum(root_neg), -3) root_neg2 = TreeNode(-2, TreeNode(-1)) self.assertEqual(max_path_sum(root_neg2), -1) # Camino con curvatura en subárbol que no incluye la raíz principal sub = TreeNode(10, TreeNode(20), TreeNode(30)) root_deep = TreeNode(-100, sub, TreeNode(-50)) self.assertEqual(max_path_sum(root_deep), 60) # Vacío self.assertEqual(max_path_sum(None), 0) # --- DÍA 33: Grafos, BFS & Dijkstra --- def test_dia_33_word_ladder(self): # LC 127: Word Ladder con BFS Bidireccional begin = "hit" end = "cog" words = ["hot", "dot", "dog", "lot", "log", "cog"] self.assertEqual(ladder_length(begin, end, words), 5) # end_word no está en el diccionario self.assertEqual( ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]), 0 ) # No existe ruta válida self.assertEqual(ladder_length("hit", "cog", ["hot", "dog", "cog"]), 0) # begin_word == end_word self.assertEqual(ladder_length("hit", "hit", ["hit"]), 1) # Un solo salto directo self.assertEqual(ladder_length("a", "c", ["a", "b", "c"]), 2) def test_dia_33_cheapest_flights_k_stops(self): # LC 787: Cheapest Flights Within K Stops n = 4 flights = [ [0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200], ] # Con k = 1 parada: 0 -> 1 -> 3 cuesta 100 + 600 = 700 self.assertEqual(find_cheapest_price(n, flights, 0, 3, 1), 700) self.assertEqual(find_cheapest_price_bellman_ford(n, flights, 0, 3, 1), 700) self.assertEqual(find_cheapest_price_dijkstra(n, flights, 0, 3, 1), 700) # Con k = 2 paradas: 0 -> 1 -> 2 -> 3 cuesta 100 + 100 + 200 = 400 self.assertEqual(find_cheapest_price(n, flights, 0, 3, 2), 400) self.assertEqual(find_cheapest_price_bellman_ford(n, flights, 0, 3, 2), 400) self.assertEqual(find_cheapest_price_dijkstra(n, flights, 0, 3, 2), 400) # Con k = 0 paradas hacia el destino 3: imposible self.assertEqual(find_cheapest_price(n, flights, 0, 3, 0), -1) # Vuelo directo con k = 0 flights2 = [[0, 1, 100], [1, 2, 100], [0, 2, 500]] self.assertEqual(find_cheapest_price(3, flights2, 0, 2, 0), 500) self.assertEqual(find_cheapest_price(3, flights2, 0, 2, 1), 200) # --- DÍA 34: Simulacro Completo de Entrevista FAANG --- def test_dia_34_lru_cache(self): # LC 146: LRU Cache cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) self.assertEqual(cache.get(1), 1) cache.put(3, 3) # Debe desalojar clave 2 self.assertEqual(cache.get(2), -1) cache.put(4, 4) # Debe desalojar clave 1 self.assertEqual(cache.get(1), -1) self.assertEqual(cache.get(3), 3) self.assertEqual(cache.get(4), 4) # Actualizar clave existente cache.put(4, 40) self.assertEqual(cache.get(4), 40) # Capacidad 1 c1 = LRUCache(1) c1.put(10, 100) self.assertEqual(c1.get(10), 100) c1.put(20, 200) self.assertEqual(c1.get(10), -1) self.assertEqual(c1.get(20), 200) # Capacidad inválida with self.assertRaises(ValueError): LRUCache(0) def test_dia_34_course_schedule_ii_and_rubric(self): # LC 210: Course Schedule II (Kahn y DFS) num_courses = 4 prereqs = [[1, 0], [2, 0], [3, 1], [3, 2]] order_k = find_order_kahn(num_courses, prereqs) order_d = find_order_dfs(num_courses, prereqs) self.assertEqual(len(order_k), 4) self.assertEqual(len(order_d), 4) for dest, src in prereqs: self.assertLess(order_k.index(src), order_k.index(dest)) self.assertLess(order_d.index(src), order_d.index(dest)) # Detección de ciclo cycle_prereqs = [[1, 0], [0, 1]] self.assertEqual(find_order_kahn(2, cycle_prereqs), []) self.assertEqual(find_order_dfs(2, cycle_prereqs), []) # Sin prerrequisitos self.assertEqual(set(find_order_kahn(3, [])), {0, 1, 2}) self.assertEqual(set(find_order_dfs(3, [])), {0, 1, 2}) # Evaluación de la rúbrica de entrevista perfect_scores = { "clarification": 15, "edge_cases": 15, "diagrams_and_trace": 20, "pseudocode_and_complexity": 15, "code_quality": 20, "dry_run": 15, } res_perfect = evaluate_mock_interview(perfect_scores) self.assertEqual(res_perfect["total_score"], 100.0) self.assertEqual(res_perfect["level"], "Strong Hire (Senior / L5)") self.assertTrue(res_perfect["passed"]) weak_scores = {"clarification": 5, "edge_cases": 5} res_weak = evaluate_mock_interview(weak_scores) self.assertEqual( res_weak["level"], "No Hire (Requiere mayor preparación Paper-First)", ) self.assertFalse(res_weak["passed"]) # --- DÍA 35: Examen Teórico Global de Consolidación & Seniority --- def test_dia_35_global_evaluation_and_seniority(self): # 1. Banco de preguntas questions = get_all_questions() self.assertEqual(len(questions), 25) for q in questions: self.assertIn("id", q) self.assertIn("category", q) self.assertIn("question", q) self.assertIn("key_concept", q) categories = {q["category"] for q in questions} self.assertGreaterEqual(len(categories), 5) # 2. Matriz de Seniority matrix = get_seniority_matrix() self.assertIn("Junior (L3)", matrix) self.assertIn("Mid-Level (L4)", matrix) self.assertIn("Senior (L5)", matrix) self.assertIn("Staff / Principal (L6+)", matrix) # 3. Motor de evaluación: 100% aciertos all_correct = {i: True for i in range(1, 26)} eval_100 = evaluate_student_answers(all_correct) self.assertEqual(eval_100["percentage"], 100.0) self.assertEqual(eval_100["seniority_level"], "Staff / Principal (L6+)") self.assertTrue(eval_100["passed"]) self.assertEqual(len(eval_100["recommendations"]), 0) # 88% aciertos (22/25) -> Senior senior_answers = {i: (i <= 22) for i in range(1, 26)} eval_senior = evaluate_student_answers(senior_answers) self.assertEqual(eval_senior["percentage"], 88.0) self.assertEqual(eval_senior["seniority_level"], "Senior (L5)") self.assertTrue(eval_senior["passed"]) self.assertGreater(len(eval_senior["recommendations"]), 0) # 40% aciertos (10/25) -> Junior junior_answers = {i: (i <= 10) for i in range(1, 26)} eval_junior = evaluate_student_answers(junior_answers) self.assertEqual(eval_junior["percentage"], 40.0) self.assertEqual(eval_junior["seniority_level"], "Junior (L3)") self.assertFalse(eval_junior["passed"]) # --- SEMANA 5 CASOS BORDE Y ESTRÉS PROFUNDO --- def test_dia_29_sliding_window_two_pointers_edge_cases(self): # Cadena repetitiva extensa (500 caracteres iguales) self.assertEqual(length_of_longest_substring("x" * 500), 1) self.assertEqual(longest_substring_without_repeating("x" * 500), "x") # Caracteres especiales y Unicode special_str = "áéíóú!@#áé" self.assertEqual(length_of_longest_substring(special_str), 8) # Container With Most Water con terreno plano o decreciente self.assertEqual(max_area_container([0, 0, 0, 0]), 0) self.assertEqual(max_area_container([10, 9, 8, 7, 6]), 24) area, l, r = max_area_container_indices([10, 9, 8, 7, 6]) self.assertEqual((area, l, r), (24, 0, 4)) def test_dia_30_linked_lists_heaps_edge_cases(self): head = build_linked_list([1, 2, 3]) # Límites inválidos deben lanzar ValueError with self.assertRaises(ValueError): reverse_between(head, 0, 2) with self.assertRaises(ValueError): reverse_between(head, 2, 1) # Nodo único single = build_linked_list([42]) self.assertEqual(to_list(reverse_between(single, 1, 1)), [42]) # Merge k lists con números negativos neg_lists = [ build_linked_list([-10, -5, 0]), build_linked_list([-20, -15, 10]), ] merged_heap = merge_k_lists_heap(neg_lists) self.assertEqual(to_list(merged_heap), [-20, -15, -10, -5, 0, 10]) # Merge k lists con lista única one_list = [build_linked_list([1, 2, 3])] self.assertEqual(to_list(merge_k_lists_divide_and_conquer(one_list)), [1, 2, 3]) def test_dia_31_monotonic_stack_dual_queue_edge_cases(self): # Alturas idénticas self.assertEqual(largest_rectangle_area([4, 4, 4, 4]), 16) # Valle profundo self.assertEqual(largest_rectangle_area([3, 1, 3]), 3) # Ceros intercalados self.assertEqual(largest_rectangle_area([2, 0, 2]), 2) # Decode string sin multiplicador explícito ("[a]" -> "a") self.assertEqual(decode_string("[a]"), "a") # Decode string profundamente anidado self.assertEqual(decode_string("2[2[2[a]]]"), "aaaaaaaa") # Decode string sin corchetes self.assertEqual(decode_string("abcdef"), "abcdef") def test_dia_32_trees_edge_cases_and_deep_recursion(self): # Elementos no coincidentes entre preorder e inorder deben retornar None (no KeyError) self.assertIsNone(build_tree_preorder_inorder([1, 2], [3, 4])) self.assertIsNone(build_tree_preorder_inorder_recursive([1, 2], [3, 4])) # Elementos duplicados no permitidos self.assertIsNone(build_tree_preorder_inorder([1, 1], [1, 1])) # Inmunidad contra RecursionError en árbol degenerado profundo (N = 1500 > límite 1000) deep_p = list(range(1500)) deep_i = list(range(1500)) tree_deep = build_tree_preorder_inorder_iterative(deep_p, deep_i) self.assertIsNotNone(tree_deep) # Max path sum iterativo sobre árbol profundo sin RecursionError curr = deep_root = TreeNode(1) for _ in range(1200): curr.right = TreeNode(1) curr = curr.right self.assertEqual(max_path_sum(deep_root), 1201) self.assertEqual(max_path_sum_iterative(deep_root), 1201) # Todos valores negativos en árbol neg_tree = TreeNode(-10, TreeNode(-20), TreeNode(-30)) self.assertEqual(max_path_sum(neg_tree), -10) def test_dia_33_word_ladder_cheapest_flights_edge_cases(self): # Longitudes heterogéneas en diccionario no deben quebrar ladder_length words_hetero = ["hot", "dot", "dog", "lot", "log", "cog", "toolong", "x"] self.assertEqual(ladder_length("hit", "cog", words_hetero), 5) # Longitud begin != end debe retornar 0 self.assertEqual(ladder_length("short", "longer", ["short", "longer"]), 0) # LC 787: Destino inalcanzable self.assertEqual( find_cheapest_price(3, [[0, 1, 100]], 0, 2, 1), -1, ) # LC 787: Grafo denso con K alto - comparación Bellman-Ford vs Dijkstra dense_flights = [ [0, 1, 5], [1, 2, 5], [2, 3, 5], [3, 4, 5], [0, 2, 12], [1, 3, 12], [2, 4, 12], [0, 4, 30], ] self.assertEqual( find_cheapest_price_bellman_ford(5, dense_flights, 0, 4, 4), find_cheapest_price_dijkstra(5, dense_flights, 0, 4, 4), ) self.assertEqual(find_cheapest_price(5, dense_flights, 0, 4, 4), 20) def test_dia_34_faang_mock_deep_dag_and_lru_edge_cases(self): # DAG lineal profundo de 1500 cursos (supera recursionlimit de 1000) n = 1500 chain_prereqs = [[i + 1, i] for i in range(n - 1)] order_dfs = find_order_dfs(n, chain_prereqs) self.assertEqual(len(order_dfs), n) self.assertEqual(order_dfs, list(range(n))) order_kahn = find_order_kahn(n, chain_prereqs) self.assertEqual(order_kahn, list(range(n))) # Prerrequisitos con índices fuera de rango retornan lista vacía self.assertEqual(find_order_kahn(3, [[10, 0]]), []) self.assertEqual(find_order_dfs(3, [[10, 0]]), []) # LRUCache: sobrescritura y capacidad mínima cache = LRUCache(1) cache.put(1, 10) cache.put(1, 20) self.assertEqual(cache.get(1), 20) cache.put(2, 30) self.assertEqual(cache.get(1), -1) self.assertEqual(cache.get(2), 30) def test_dia_35_seniority_boundaries_and_questions_audit(self): # 1. Unicidad e integridad de IDs del banco de preguntas questions = get_all_questions() ids = [q["id"] for q in questions] self.assertEqual(len(ids), 25) self.assertEqual(set(ids), set(range(1, 26))) # 2. Umbrales continuos de seniority # 0 aciertos -> Junior eval_0 = evaluate_student_answers({}) self.assertEqual(eval_0["percentage"], 0.0) self.assertEqual(eval_0["seniority_level"], "Junior (L3)") # 60% (15/25) -> Mid-Level eval_mid = evaluate_student_answers({i: (i <= 15) for i in range(1, 26)}) self.assertEqual(eval_mid["percentage"], 60.0) self.assertEqual(eval_mid["seniority_level"], "Mid-Level (L4)") # 96% (24/25) -> Staff eval_staff = evaluate_student_answers({i: (i <= 24) for i in range(1, 26)}) self.assertEqual(eval_staff["percentage"], 96.0) self.assertEqual(eval_staff["seniority_level"], "Staff / Principal (L6+)") # ========================================================================= # SEMANA 6: Algoritmos Voraces (Greedy), Backtracking & Programación Dinámica # ========================================================================= # ========================================================================= # SEMANA 6: Algoritmos Voraces (Greedy), Backtracking & Programación Dinámica # ========================================================================= # --- DÍA 36: Algoritmos Voraces (Greedy) --- def test_dia_36_greedy_set_cover(self): # Grokking Ch 8: Set Cover Greedy Approximation universe = {"wa", "or", "id", "nv", "ut", "ca", "az"} stations = { "kone": {"id", "nv", "ut"}, "ktwo": {"wa", "id", "mt"}, "kthree": {"or", "nv", "ca"}, "kfour": {"nv", "ut"}, "kfive": {"ca", "az"}, } chosen = set_cover_greedy(universe, stations) covered_states = set() for st in chosen: covered_states.update(stations[st]) self.assertTrue(universe.issubset(covered_states)) self.assertLessEqual(len(chosen), 5) # Casos borde Set Cover self.assertEqual(set_cover_greedy(set(), stations), set()) # Universo con elemento imposible de cubrir partial = set_cover_greedy({"imposible", "wa"}, stations) self.assertIn("ktwo", partial) def test_dia_36_interval_scheduling_and_erase_overlap(self): # 1. Interval Scheduling Maximization intervals = [(1, 4), (2, 3), (3, 5), (1, 2)] scheduled = interval_scheduling(intervals) self.assertEqual(len(scheduled), 3) self.assertEqual(scheduled, [(1, 2), (2, 3), (3, 5)]) self.assertEqual(interval_scheduling([]), []) self.assertEqual(interval_scheduling([(1, 5)]), [(1, 5)]) # 2. LC 435: Erase Overlap Intervals original = [[1, 2], [2, 3], [3, 4], [1, 3]] original_copy = [list(x) for x in original] self.assertEqual(erase_overlap_intervals(original), 1) # Verificar que erase_overlap_intervals NO muta la lista original del llamador self.assertEqual(original, original_copy) self.assertEqual(erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]), 2) self.assertEqual(erase_overlap_intervals([[1, 2], [2, 3]]), 0) self.assertEqual(erase_overlap_intervals([]), 0) self.assertEqual(erase_overlap_intervals([[1, 5]]), 0) # Intervalos negativos self.assertEqual(erase_overlap_intervals([[-50, -20], [-30, -10], [-10, 10]]), 1) def test_dia_36_jump_game_i_and_ii(self): # LC 55: Jump Game self.assertTrue(can_jump([2, 3, 1, 1, 4])) self.assertFalse(can_jump([3, 2, 1, 0, 4])) self.assertTrue(can_jump([0])) self.assertTrue(can_jump([2, 0, 0])) self.assertFalse(can_jump([])) # LC 45: Jump Game II self.assertEqual(jump([2, 3, 1, 1, 4]), 2) self.assertEqual(jump([2, 3, 0, 1, 4]), 2) self.assertEqual(jump([0]), 0) self.assertEqual(jump([1, 2, 3]), 2) # Caso inalcanzable protegido self.assertEqual(jump([0, 2, 3]), -1) # --- DÍA 37: Backtracking Fundamental (CTCI 8.4 & 8.9) --- def test_dia_37_power_set_subsets_and_dups(self): # CTCI 8.4: Power Set (3 enfoques) nums = [1, 2, 3] sub_bt = subsets_backtracking(nums) sub_casc = subsets_cascading(nums) sub_bits = subsets_bit_manipulation(nums) self.assertEqual(len(sub_bt), 8) self.assertEqual(len(sub_casc), 8) self.assertEqual(len(sub_bits), 8) set_bt = {tuple(sorted(s)) for s in sub_bt} set_casc = {tuple(sorted(s)) for s in sub_casc} set_bits = {tuple(sorted(s)) for s in sub_bits} self.assertEqual(set_bt, set_casc) self.assertEqual(set_bt, set_bits) self.assertIn((), set_bt) self.assertIn((1, 2, 3), set_bt) # Casos borde self.assertEqual(subsets_backtracking([]), [[]]) self.assertEqual(subsets_cascading([]), [[]]) self.assertEqual(subsets_bit_manipulation([]), [[]]) self.assertEqual(len(subsets_backtracking([42])), 2) # LC 90: Subsets II con duplicados podados sub_dups = subsets_with_dup([1, 2, 2]) self.assertEqual(len(sub_dups), 6) expected_dups = sorted([[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]) self.assertEqual(sorted([sorted(s) for s in sub_dups]), expected_dups) self.assertEqual(subsets_with_dup([]), [[]]) def test_dia_37_generate_parentheses(self): # CTCI 8.9 & LC 22: Generate Parentheses & Balance Check p1 = generate_parentheses(1) self.assertEqual(p1, ["()"]) p2 = generate_parentheses(2) self.assertEqual(sorted(p2), sorted(["(())", "()()"])) p3 = generate_parentheses(3) self.assertEqual(len(p3), 5) # Catalan C_3 = 5 for s in p3: self.assertTrue(is_valid_parens_combination(s)) p4 = generate_parentheses(4) self.assertEqual(len(p4), 14) # Catalan C_4 = 14 for s in p4: self.assertTrue(is_valid_parens_combination(s)) self.assertEqual(generate_parentheses(0), []) self.assertEqual(generate_parentheses(-2), []) # Balance helper self.assertTrue(is_valid_parens_combination("((()))")) self.assertTrue(is_valid_parens_combination("()()()")) self.assertFalse(is_valid_parens_combination(")(")) self.assertFalse(is_valid_parens_combination("(()")) self.assertFalse(is_valid_parens_combination("())(")) # --- DÍA 38: Backtracking Avanzado (CTCI 8.7, 8.8 & 8.12) --- def test_dia_38_permutations_with_and_without_dups(self): # 1. CTCI 8.7: Permutations without Dups (LC 46) perms = permute_unique_elements([1, 2, 3]) self.assertEqual(len(perms), 6) self.assertEqual(len(set(tuple(p) for p in perms)), 6) self.assertEqual(permute_unique_elements([]), [[]]) self.assertEqual(permute_unique_elements([5]), [[5]]) perms_str = permute_string_without_dups("abc") self.assertEqual(len(perms_str), 6) self.assertEqual(permute_string_without_dups(""), [""]) # 2. CTCI 8.8: Permutations with Dups (LC 47) perms_dups = permute_with_duplicates([1, 1, 2]) self.assertEqual(len(perms_dups), 3) self.assertEqual( sorted(perms_dups), sorted([[1, 1, 2], [1, 2, 1], [2, 1, 1]]), ) perms_all_same = permute_with_duplicates([1, 1, 1]) self.assertEqual(perms_all_same, [[1, 1, 1]]) perms_two_pairs = permute_with_duplicates([2, 2, 1, 1]) self.assertEqual(len(perms_two_pairs), 6) # 4! / (2! * 2!) = 6 str_dups = permute_string_with_dups("aab") self.assertEqual(sorted(str_dups), sorted(["aab", "aba", "baa"])) self.assertEqual(permute_string_with_dups(""), [""]) def test_dia_38_n_queens_solutions(self): # CTCI 8.12 & LC 51/52: N-Queens self.assertEqual(solve_n_queens(1), [["Q"]]) self.assertEqual(solve_n_queens(2), []) self.assertEqual(solve_n_queens(3), []) self.assertEqual(total_n_queens(2), 0) self.assertEqual(total_n_queens(3), 0) # N = 4: exactamente 2 soluciones válidas boards_4 = solve_n_queens(4) self.assertEqual(len(boards_4), 2) self.assertEqual(total_n_queens(4), 2) for board in boards_4: self.assertEqual(len(board), 4) for row in board: self.assertEqual(len(row), 4) self.assertEqual(row.count("Q"), 1) # N = 8: exactamente 92 soluciones canónicas self.assertEqual(total_n_queens(8), 92) # --- DÍA 39: DP 1D y 2D (CTCI 8.1 & 8.2) --- def test_dia_39_triple_step_memo_and_tab(self): # CTCI 8.1: Triple Step (Memo vs Tabulation O(1)) expected_steps = {0: 1, 1: 1, 2: 2, 3: 4, 4: 7, 5: 13, 10: 274} for n, expected in expected_steps.items(): self.assertEqual(triple_step_memo(n), expected) self.assertEqual(triple_step_tab(n), expected) # Casos negativos self.assertEqual(triple_step_memo(-5), 0) self.assertEqual(triple_step_tab(-5), 0) # Equivalencia en rango amplio for n in range(16): self.assertEqual(triple_step_memo(n), triple_step_tab(n)) # Robustez con n grande sin RecursionError self.assertEqual(triple_step_memo(950), triple_step_tab(950)) def test_dia_39_unique_paths_and_robot_grid(self): # 1. LC 62: Unique Paths sin obstáculos self.assertEqual(unique_paths(3, 7), 28) self.assertEqual(unique_paths(3, 2), 3) self.assertEqual(unique_paths(7, 3), 28) self.assertEqual(unique_paths(1, 1), 1) self.assertEqual(unique_paths(0, 5), 0) # 2. LC 63: Unique Paths con obstáculos grid_obs = [ [0, 0, 0], [0, 1, 0], [0, 0, 0], ] self.assertEqual(unique_paths_with_obstacles(grid_obs), 2) self.assertEqual(unique_paths_with_obstacles([[0, 1], [0, 0]]), 1) # Inicio o fin bloqueado self.assertEqual(unique_paths_with_obstacles([[1, 0], [0, 0]]), 0) self.assertEqual(unique_paths_with_obstacles([[0, 0], [0, 1]]), 0) self.assertEqual(unique_paths_with_obstacles([]), 0) # 3. CTCI 8.2: Robot in a Grid (Ruta con coordenadas) path = robot_in_a_grid(grid_obs) path_rec = robot_in_a_grid_recursive(grid_obs) path_iter = robot_in_a_grid_iterative(grid_obs) self.assertIsNotNone(path) self.assertEqual(path, path_rec) self.assertEqual(path, path_iter) self.assertEqual(path[0], (0, 0)) self.assertEqual(path[-1], (2, 2)) for r, c in path: self.assertEqual(grid_obs[r][c], 0) # Grilla bloqueada sin salida blocked_grid = [ [0, 1], [1, 0], ] self.assertIsNone(robot_in_a_grid(blocked_grid)) self.assertIsNone(robot_in_a_grid_recursive(blocked_grid)) self.assertIsNone(robot_in_a_grid_iterative(blocked_grid)) self.assertIsNone(robot_in_a_grid([[1]])) self.assertEqual(robot_in_a_grid([[0]]), [(0, 0)]) # Grilla grande (500x500) inmune a RecursionError large_grid = [[0] * 500 for _ in range(500)] large_path = robot_in_a_grid(large_grid) self.assertIsNotNone(large_path) self.assertEqual(len(large_path), 999) self.assertEqual(large_path[0], (0, 0)) self.assertEqual(large_path[-1], (499, 499)) # --- DÍA 40: Knapsack 0/1 & Subset Sum (Grokking Ch 9 & LC 416) --- def test_dia_40_knapsack_01_table_optimized_memo(self): # Grokking Ch 9: Knapsack 0/1 clásico weights = [1, 4, 3] values = [1500, 3000, 2000] capacity = 4 val_table, dp_matrix = knapsack_01_table(weights, values, capacity) val_opt = knapsack_01_optimized(weights, values, capacity) val_memo = knapsack_01_memo(weights, values, capacity) val_items, selected = knapsack_01_items(weights, values, capacity) self.assertEqual(val_table, 3500) self.assertEqual(val_opt, 3500) self.assertEqual(val_memo, 3500) self.assertEqual(val_items, 3500) self.assertEqual(selected, [0, 2]) # Caso clásico: Capacidad 5, Pesos [2, 3, 4], Valores [6, 10, 12] -> items 0 y 1 (6+10=16) self.assertEqual(knapsack_01_optimized([2, 3, 4], [6, 10, 12], 5), 16) self.assertEqual(knapsack_01_memo([2, 3, 4], [6, 10, 12], 5), 16) self.assertEqual(knapsack_01_optimized([2, 3, 4], [6, 10, 12], 0), 0) # Validación de excepciones with self.assertRaises(ValueError): knapsack_01_optimized([1, 2], [10], 5) with self.assertRaises(ValueError): knapsack_01_memo([1, 2], [10], 5) with self.assertRaises(ValueError): knapsack_01_optimized([1], [10], -1) def test_dia_40_partition_equal_subset_sum(self): # LC 416: Partition Equal Subset Sum self.assertTrue(can_partition_equal_subset_sum([1, 5, 11, 5])) self.assertFalse(can_partition_equal_subset_sum([1, 2, 3, 5])) self.assertTrue(can_partition_equal_subset_sum([2, 2, 2, 2])) self.assertFalse(can_partition_equal_subset_sum([100])) self.assertFalse(can_partition_equal_subset_sum([])) self.assertFalse(can_partition_equal_subset_sum([1, 2, 4])) # Suma impar 7 # Reconstrucción de subconjuntos particionados parts = find_partition_subsets([1, 5, 11, 5]) self.assertIsNotNone(parts) sub1, sub2 = parts self.assertEqual(sum(sub1), sum(sub2)) self.assertEqual(sum(sub1), 11) self.assertEqual(sorted(sub1 + sub2), [1, 5, 5, 11]) self.assertIsNone(find_partition_subsets([1, 2, 3, 5])) # --- DÍA 41: Coin Change & Unbounded Knapsack (CTCI 8.11 & LC 322) --- def test_dia_41_coin_change_min_coins(self): # LC 322: Coin Change (Mínimo número de monedas) self.assertEqual(coin_change_min_coins([1, 2, 5], 11), 3) # 5 + 5 + 1 self.assertEqual(coin_change_min_coins_memo([1, 2, 5], 11), 3) self.assertEqual(coin_change_min_coins([2], 3), -1) self.assertEqual(coin_change_min_coins_memo([2], 3), -1) self.assertEqual(coin_change_min_coins([1], 0), 0) self.assertEqual(coin_change_min_coins_memo([1], 0), 0) self.assertEqual(coin_change_min_coins([1], -5), -1) self.assertEqual(coin_change_min_coins([186, 419, 83, 408], 6249), 20) # Reconstrucción de camino de monedas path = coin_change_min_coins_path([1, 2, 5], 11) self.assertIsNotNone(path) self.assertEqual(len(path), 3) self.assertEqual(sum(path), 11) self.assertIsNone(coin_change_min_coins_path([2], 3)) self.assertEqual(coin_change_min_coins_path([1], 0), []) def test_dia_41_coin_change_ways_combinations_permutations(self): # 1. CTCI 8.11 & LC 518: Coin Change 2 (Combinaciones) self.assertEqual(coin_change_ways([1, 2, 5], 5), 4) self.assertEqual(coin_change_ways([2], 3), 0) self.assertEqual(coin_change_ways([10], 10), 1) self.assertEqual(coin_change_ways([1, 2, 5], 0), 1) # Validación con Memoization Top-Down canónico CTCI 8.11 for amt in range(12): self.assertEqual( coin_change_ways([1, 2, 5], amt), coin_change_memo([1, 2, 5], amt), ) # Cantidad grande (amount = 1500): prueba de fuego anti-RecursionError ways_1500 = coin_change_memo([1, 5, 10, 25], 1500) self.assertEqual(ways_1500, 470516) self.assertEqual(ways_1500, coin_change_ways([1, 5, 10, 25], 1500)) # 2. LC 377: Permutaciones ordenadas (Combination Sum IV) self.assertEqual(coin_change_ways([1, 2], 3), 2) self.assertEqual(coin_change_permutations([1, 2], 3), 3) self.assertEqual(coin_change_permutations([1, 2, 3], 4), 7) # --- DÍA 42: Secuencias y Matrices DP (Grokking Ch 9 & CTCI 8.13) --- def test_dia_42_longest_common_subsequence_and_substring(self): # 1. Grokking Ch 9 & LC 1143: LCS 2D vs Rolling Array vs Memo s1, s2 = "abcde", "ace" self.assertEqual(longest_common_subsequence(s1, s2), 3) self.assertEqual(longest_common_subsequence_optimized(s1, s2), 3) self.assertEqual(longest_common_subsequence_memo(s1, s2), 3) self.assertEqual(longest_common_subsequence("abc", "abc"), 3) self.assertEqual(longest_common_subsequence("abc", "def"), 0) self.assertEqual(longest_common_subsequence("", "abc"), 0) # Reconstrucción de la cadena LCS self.assertEqual(get_lcs_string("blue", "clues"), "lue") self.assertEqual(get_lcs_string("AGGTAB", "GXTXAYB"), "GTAB") self.assertEqual(get_lcs_string("abc", "xyz"), "") # 2. Grokking Ch 9: Longest Common Substring (Contigua) len_sub, sub_str = longest_common_substring("hish", "fish") self.assertEqual(len_sub, 3) self.assertEqual(sub_str, "ish") len_sub2, sub_str2 = longest_common_substring("vista", "hastavista") self.assertEqual(len_sub2, 5) self.assertEqual(sub_str2, "vista") self.assertEqual(longest_common_substring("abc", "xyz"), (0, "")) def test_dia_42_longest_increasing_subsequence(self): # LC 300: Longest Increasing Subsequence (LIS O(N log N) vs O(N^2)) test_nums = [10, 9, 2, 5, 3, 7, 101, 18] self.assertEqual(length_of_lis(test_nums), 4) self.assertEqual(length_of_lis_dp(test_nums), 4) test_nums_2 = [0, 1, 0, 3, 2, 3] self.assertEqual(length_of_lis(test_nums_2), 4) self.assertEqual(length_of_lis_dp(test_nums_2), 4) self.assertEqual(length_of_lis([7, 7, 7, 7]), 1) self.assertEqual(length_of_lis_dp([7, 7, 7, 7]), 1) self.assertEqual(length_of_lis([]), 0) self.assertEqual(length_of_lis_dp([]), 0) def test_dia_42_stack_of_boxes_dp_and_memo(self): # CTCI 8.13: Stack of Boxes (w, h, d estrictamente decrecientes) boxes = [(5, 6, 7), (4, 5, 6), (6, 7, 8), (2, 3, 4)] max_h = stack_of_boxes(boxes) max_h_memo = stack_of_boxes_memo(boxes) self.assertEqual(max_h, 21) self.assertEqual(max_h_memo, 21) max_h_path, path_boxes = stack_of_boxes_with_path(boxes) self.assertEqual(max_h_path, 21) self.assertEqual(len(path_boxes), 4) self.assertEqual(path_boxes, [(6, 7, 8), (5, 6, 7), (4, 5, 6), (2, 3, 4)]) # Cajas no compatibles por dimensión idéntica en ancho conflict_boxes = [(5, 5, 5), (5, 4, 4)] self.assertEqual(stack_of_boxes(conflict_boxes), 5) self.assertEqual(stack_of_boxes_memo(conflict_boxes), 5) self.assertEqual(stack_of_boxes([]), 0) self.assertEqual(stack_of_boxes_memo([]), 0) self.assertEqual(stack_of_boxes_with_path([]), (0, [])) # --- SEMANA 6 CASOS BORDE Y ESTRÉS PROFUNDO --- def test_dia_36_to_42_semana_6_edge_cases_and_stress(self): # 1. Estrés LIS O(N log N) con 1000 elementos import random random.seed(42) large_arr = [random.randint(0, 10000) for _ in range(1000)] lis_len = length_of_lis(large_arr) self.assertGreater(lis_len, 10) self.assertLess(lis_len, 1000) # 2. Triple Step con N grande (precisión de enteros arbitrarios en Python) large_steps = triple_step_tab(30) self.assertEqual(large_steps, 53798080) # 3. N-Queens N=8 validación de ausencia de ataques solutions_8 = solve_n_queens(8) self.assertEqual(len(solutions_8), 92) for sol in solutions_8[:5]: queen_cols = [] for r, row_str in enumerate(sol): c = row_str.index("Q") queen_cols.append(c) # Validar que no hay columnas ni diagonales repetidas self.assertEqual(len(set(queen_cols)), 8) self.assertEqual(len(set(r - c for r, c in enumerate(queen_cols))), 8) self.assertEqual(len(set(r + c for r, c in enumerate(queen_cols))), 8) # 4. LCS sobre cadenas idénticas largas str_50 = "ABCDEFGHIJ" * 5 self.assertEqual(longest_common_subsequence(str_50, str_50), 50) self.assertEqual(longest_common_subsequence_optimized(str_50, str_50), 50) self.assertEqual(get_lcs_string(str_50, str_50), str_50) # --- SEMANA 7: DÍA 43 - Manipulación de Bits Fundamentos (CTCI Cap 5 P1 & LC) --- def test_dia_43_bit_manipulation_fundamentos(self): # 1. Bloques fundamentales de bits num = 0b1010 # 10 self.assertEqual(get_bit(num, 0), 0) self.assertEqual(get_bit(num, 1), 1) self.assertEqual(get_bit(num, 2), 0) self.assertEqual(get_bit(num, 3), 1) self.assertEqual(set_bit(num, 0), 0b1011) self.assertEqual(set_bit(num, 2), 0b1110) self.assertEqual(clear_bit(num, 1), 0b1000) self.assertEqual(clear_bit(num, 3), 0b0010) self.assertEqual(update_bit(num, 0, 1), 0b1011) self.assertEqual(update_bit(num, 1, 0), 0b1000) # 2. Limpieza de rangos val = 0b11111111 # 255 self.assertEqual(clear_bits_msb_through_i(val, 4), 0b00001111) self.assertEqual(clear_bits_i_through_0(val, 3), 0b11110000) # 3. CTCI 5.1: Insertion n = 0b10000000000 # 1024 m = 0b10011 # 19 self.assertEqual(insertion(n, m, 2, 6), 0b10001001100) # 1100 self.assertEqual(insertion(0, 0b11, 0, 1), 0b11) self.assertEqual(insertion(0, 0b11111, 0, 1), 0b11) # M truncado a la ventana self.assertEqual(insertion(0xFFFFFFFF, 0, 30, 31), 0x3FFFFFFF) # Bits 30-31 en 0 self.assertEqual(insertion(1 << 40, 0b11, 2, 4), (1 << 40) | (0b11 << 2)) with self.assertRaises(ValueError): insertion(n, m, 5, 2) # j < i # 4. LeetCode 191: Number of 1 Bits (Brian Kernighan) self.assertEqual(count_one_bits(0), 0) self.assertEqual(count_one_bits(1), 1) self.assertEqual(count_one_bits(11), 3) # 1011_2 self.assertEqual(count_one_bits(128), 1) self.assertEqual(count_one_bits(0xFFFFFFFF), 32) # 5. LeetCode 338: Counting Bits (DP) self.assertEqual(count_bits(0), [0]) self.assertEqual(count_bits(2), [0, 1, 1]) self.assertEqual(count_bits(5), [0, 1, 1, 2, 1, 2]) self.assertEqual(count_bits(-1), []) # 6. LeetCode 136: Single Number self.assertEqual(single_number([2, 2, 1]), 1) self.assertEqual(single_number([4, 1, 2, 1, 2]), 4) self.assertEqual(single_number([1]), 1) with self.assertRaises(ValueError): single_number([]) # 7. LeetCode 268: Missing Number self.assertEqual(missing_number([3, 0, 1]), 2) self.assertEqual(missing_number([0, 1]), 2) self.assertEqual(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]), 8) # --- SEMANA 7: DÍA 44 - Manipulación de Bits Avanzada & Memoria Acotada (CTCI Cap 5 P2 & 10.8) --- def test_dia_44_bit_manipulation_avanzada(self): # 1. CTCI 5.3: Flip Bit to Win self.assertEqual(flip_bit_to_win(1775), 8) # 11011101111_2 -> 8 self.assertEqual(flip_bit_to_win(0), 1) self.assertEqual(flip_bit_to_win(0xFFFFFFFF), 32) self.assertEqual(flip_bit_to_win(7), 4) # 111_2 -> 1111_2 = 4 self.assertEqual(flip_bit_to_win(0b110111001111), 6) # 11 + 1 + 111 = 6 self.assertEqual(flip_bit_to_win(0b11001111), 5) # 1 + 1111 = 5 # 2. CTCI 5.6: Conversion / Hamming Distance self.assertEqual(conversion_distance(29, 15), 2) # 11101 vs 01111 -> 2 bits self.assertEqual(conversion_distance(0, 0), 0) self.assertEqual(conversion_distance(1, 2), 2) # 01 vs 10 -> 2 bits self.assertEqual(conversion_distance(0, 0xFFFFFFFF), 32) # 3. CTCI 5.7: Pairwise Swap self.assertEqual(pairwise_swap(23), 43) # 00010111 -> 00101011 = 43 self.assertEqual(pairwise_swap(0), 0) self.assertEqual(pairwise_swap(0xAAAAAAAA), 0x55555555) self.assertEqual(pairwise_swap(0x55555555), 0xAAAAAAAA) # 4. CTCI 10.8: BitVector y Find Duplicates en Memoria Acotada bv = BitVector(100) self.assertFalse(bv.get(0)) self.assertFalse(bv.get(42)) bv.set(42) self.assertTrue(bv.get(42)) self.assertFalse(bv.get(41)) bv.clear(42) self.assertFalse(bv.get(42)) # Errores de límites with self.assertRaises(IndexError): bv.get(100) with self.assertRaises(IndexError): bv.set(-1) with self.assertRaises(ValueError): BitVector(-5) self.assertGreater(bv.memory_bytes(), 0) # Find Duplicates con BitVector stream = [1, 2, 3, 4, 2, 5, 6, 3, 7, 8, 1, 32000, 32000] dups = find_duplicates_bit_vector(stream, max_val=32000) self.assertEqual(dups, [2, 3, 1, 32000]) # --- SEMANA 7: DÍA 45 - Sorting & Searching: Rotaciones y Búsqueda Dispersa (CTCI Cap 10 P1) --- def test_dia_45_sorting_searching_rotated(self): # 1. CTCI 10.1 & LC 88: Sorted Merge back-to-front a = [2, 5, 8, 0, 0, 0] b = [1, 3, 7] sorted_merge(a, b, 2) self.assertEqual(a, [1, 2, 3, 5, 7, 8]) # Caso B vacío a2 = [1, 2, 3] sorted_merge(a2, [], 2) self.assertEqual(a2, [1, 2, 3]) # Caso LC 88 nums1 = [1, 2, 3, 0, 0, 0] merge_sorted_array_leetcode(nums1, 3, [2, 5, 6], 3) self.assertEqual(nums1, [1, 2, 2, 3, 5, 6]) # 2. CTCI 10.3 / LC 33: Search in Rotated Array nums_rot = [4, 5, 6, 7, 0, 1, 2] self.assertEqual(search_rotated_array(nums_rot, 0), 4) self.assertEqual(search_rotated_array(nums_rot, 3), -1) self.assertEqual(search_rotated_array(nums_rot, 4), 0) self.assertEqual(search_rotated_array(nums_rot, 2), 6) # Arreglo con duplicados (LC 81) self.assertIn(search_rotated_array([2, 5, 6, 0, 0, 1, 2], 0), [3, 4]) self.assertEqual(search_rotated_array([2, 5, 6, 0, 0, 1, 2], 3), -1) self.assertEqual(search_rotated_array([1, 0, 1, 1, 1], 0), 1) # Arreglo de 1 elemento y vacío self.assertEqual(search_rotated_array([1], 1), 0) self.assertEqual(search_rotated_array([1], 2), -1) self.assertEqual(search_rotated_array([], 5), -1) # 3. LeetCode 153: Find Minimum in Rotated Sorted Array self.assertEqual(find_min_rotated([3, 4, 5, 1, 2]), 1) self.assertEqual(find_min_rotated([4, 5, 6, 7, 0, 1, 2]), 0) self.assertEqual(find_min_rotated([11, 13, 15, 17]), 11) self.assertEqual(find_min_rotated([1]), 1) with self.assertRaises(ValueError): find_min_rotated([]) # 4. CTCI 10.5: Sparse Search sparse = ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""] self.assertEqual(sparse_search(sparse, "ball"), 4) self.assertEqual(sparse_search(sparse, "at"), 0) self.assertEqual(sparse_search(sparse, "car"), 7) self.assertEqual(sparse_search(sparse, "dad"), 10) self.assertEqual(sparse_search(sparse, "egg"), -1) self.assertEqual(sparse_search(["", "", ""], "ball"), -1) self.assertEqual(sparse_search([], "ball"), -1) self.assertEqual(sparse_search(sparse, ""), -1) # --- SEMANA 7: DÍA 46 - Matrix Search, Stream Ranking & Peaks/Valleys (CTCI Cap 10 P2) --- def test_dia_46_matrix_search_rank_stream(self): # 1. LeetCode 74: Search a 2D Matrix (Estrictamente ordenada) m1 = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] self.assertTrue(matrix_search_sorted_2d(m1, 3)) self.assertFalse(matrix_search_sorted_2d(m1, 13)) self.assertTrue(matrix_search_sorted_2d([[1]], 1)) self.assertFalse(matrix_search_sorted_2d([], 1)) self.assertFalse(matrix_search_sorted_2d([[]], 1)) # 2. CTCI 10.9 & LC 240: Search a 2D Matrix II (Filas y Columnas independientes) m2 = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30], ] self.assertTrue(matrix_search_2d(m2, 5)) self.assertFalse(matrix_search_2d(m2, 20)) self.assertEqual(matrix_search_2d_coords(m2, 5), (1, 1)) self.assertIsNone(matrix_search_2d_coords(m2, 100)) self.assertFalse(matrix_search_2d([], 5)) # 3. CTCI 10.10: Rank from Stream (BST Aumentado) tracker = RankTracker() stream = [5, 1, 4, 4, 5, 9, 7, 13, 3] for x in stream: tracker.track(x) self.assertEqual(tracker.get_rank_of_number(1), 0) self.assertEqual(tracker.get_rank_of_number(3), 1) self.assertEqual(tracker.get_rank_of_number(4), 3) self.assertEqual(tracker.get_rank_of_number(13), 8) self.assertEqual(tracker.get_rank_of_number(100), -1) # No existe # Tracker vacío empty_tracker = RankTracker() self.assertEqual(empty_tracker.get_rank_of_number(5), -1) # 4. CTCI 10.11: Peaks and Valleys arr = [5, 3, 1, 2, 3] pv = peaks_and_valleys(list(arr)) self.assertEqual(len(pv), len(arr)) # Validar propiedad alternante de picos en posiciones impares for i in range(1, len(pv), 2): self.assertGreaterEqual(pv[i], pv[i - 1]) if i + 1 < len(pv): self.assertGreaterEqual(pv[i], pv[i + 1]) # Casos borde self.assertEqual(peaks_and_valleys([]), []) self.assertEqual(peaks_and_valleys([1]), [1]) pv2 = peaks_and_valleys([1, 2]) self.assertGreaterEqual(pv2[1], pv2[0]) # --- SEMANA 7: DÍA 47 - Tries (Prefix Trees) y Autocompletado (LC 208 & 211) --- def test_dia_47_tries_prefix_trees_wildcards(self): # 1. LeetCode 208: Implement Trie trie = Trie() trie.insert("apple") self.assertTrue(trie.search("apple")) self.assertFalse(trie.search("app")) self.assertTrue(trie.starts_with("app")) trie.insert("app") self.assertTrue(trie.search("app")) # Conteo y prefijos trie.insert("app") self.assertEqual(trie.count_words_equal("app"), 2) self.assertEqual(trie.count_words_equal("apple"), 1) self.assertEqual(trie.count_words_equal("banana"), 0) self.assertEqual(trie.count_words_starting_with("app"), 3) # Autocompletado trie.insert("application") words = trie.find_words_with_prefix("app") self.assertEqual(words, ["app", "apple", "application"]) self.assertEqual(trie.find_words_with_prefix("xyz"), []) # Borrado limpio con poda self.assertTrue(trie.delete("apple")) self.assertFalse(trie.search("apple")) self.assertTrue(trie.search("app")) self.assertFalse(trie.delete("nonexistent")) # Borrado con prefijos compartidos en orden inverso trie2 = Trie() trie2.insert("car") trie2.insert("card") self.assertTrue(trie2.delete("car")) self.assertFalse(trie2.search("car")) self.assertTrue(trie2.search("card")) self.assertTrue(trie2.delete("card")) self.assertFalse(trie2.search("card")) self.assertFalse(trie2.starts_with("car")) # Inserción y búsqueda vacía trie.insert("") self.assertFalse(trie.search("")) self.assertTrue(trie.starts_with("")) # 2. LeetCode 211: WordDictionary con Comodín '.' wd = WordDictionary() wd.add_word("bad") wd.add_word("dad") wd.add_word("mad") self.assertFalse(wd.search("pad")) self.assertTrue(wd.search("bad")) self.assertTrue(wd.search(".ad")) self.assertTrue(wd.search("b..")) self.assertFalse(wd.search("b...")) self.assertTrue(wd.search("...")) self.assertFalse(wd.search("..")) self.assertFalse(wd.search("....")) # --- SEMANA 7: DÍA 48 - Disjoint Set Union (DSU / Union-Find) (LC 547 & 684) --- def test_dia_48_union_find_disjoint_set_union(self): # 1. Clase DisjointSetUnion dsu = DisjointSetUnion(5) self.assertEqual(dsu.count_components(), 5) self.assertFalse(dsu.connected(0, 1)) self.assertTrue(dsu.union(0, 1)) self.assertEqual(dsu.count_components(), 4) self.assertTrue(dsu.connected(0, 1)) self.assertEqual(dsu.get_component_size(0), 2) # Ciclo / unión redundante self.assertFalse(dsu.union(0, 1)) self.assertEqual(dsu.count_components(), 4) # Uniones transitivas dsu.union(1, 2) self.assertTrue(dsu.connected(0, 2)) self.assertEqual(dsu.get_component_size(2), 3) # Errores de límites with self.assertRaises(IndexError): dsu.find(10) with self.assertRaises(IndexError): dsu.find(-1) with self.assertRaises(ValueError): DisjointSetUnion(-1) # 2. LeetCode 547: Number of Provinces provinces1 = [[1, 1, 0], [1, 1, 0], [0, 0, 1]] self.assertEqual(find_circle_num(provinces1), 2) provinces2 = [[1, 0, 0], [0, 1, 0], [0, 0, 1]] self.assertEqual(find_circle_num(provinces2), 3) self.assertEqual(find_circle_num([]), 0) # 3. LeetCode 684: Redundant Connection edges1 = [[1, 2], [1, 3], [2, 3]] self.assertEqual(find_redundant_connection(edges1), [2, 3]) edges2 = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] self.assertEqual(find_redundant_connection(edges2), [1, 4]) self.assertEqual(find_redundant_connection([]), []) # Caso crítico: etiquetas de nodos no contiguas o dispersas (máximo > len(edges)) edges_sparse = [[1, 4], [4, 5], [1, 5]] self.assertEqual(find_redundant_connection(edges_sparse), [1, 5]) # 4. LeetCode 261: Graph Valid Tree self.assertTrue(valid_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])) self.assertFalse(valid_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) # Ciclo self.assertFalse(valid_tree(4, [[0, 1], [2, 3]])) # Disconexo self.assertFalse(valid_tree(4, [[0, 1]])) # Faltan aristas self.assertTrue(valid_tree(1, [])) # Árbol de un solo nodo self.assertFalse(valid_tree(2, [[0, 5]])) # Arista con nodo fuera de rango self.assertFalse(valid_tree(2, [[-1, 0]])) # Arista con nodo negativo # --- SEMANA 7: DÍA 49 - Cierre Magistral, Bitwise Trie & Kruskal MST (LC 421 & Grokking Ch 10/11) --- def test_dia_49_cierre_magistral_consolidacion_semana_7(self): # 1. LeetCode 421: Maximum XOR of Two Numbers in an Array nums1 = [3, 10, 5, 25, 2, 8] self.assertEqual(find_maximum_xor(nums1), 28) # 5 ^ 25 = 28 nums2 = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70] self.assertEqual(find_maximum_xor(nums2), 127) self.assertEqual(find_maximum_xor([0]), 0) self.assertEqual(find_maximum_xor([]), 0) # 2. Grokking Algorithms Ch 10 & 11: Kruskal MST edges = [ (0, 1, 1), (1, 2, 2), (0, 2, 3), (2, 3, 4), (1, 3, 5), ] cost, mst = kruskal_mst(4, edges) self.assertEqual(cost, 7) self.assertEqual(len(mst), 3) # Grafo disconexo disconnected_edges = [(0, 1, 10)] d_cost, d_mst = kruskal_mst(3, disconnected_edges) self.assertEqual(d_cost, -1) self.assertEqual(d_mst, []) # Grafo con aristas con endpoints fuera de rango edges_out_of_bounds = [(0, 1, 1), (1, 2, 2), (0, 99, 100)] cost_oob, mst_oob = kruskal_mst(3, edges_out_of_bounds) self.assertEqual(cost_oob, 3) self.assertEqual(len(mst_oob), 2) # Casos base self.assertEqual(kruskal_mst(1, []), (0, [])) self.assertEqual(kruskal_mst(0, []), (0, [])) # 3. Evaluador de Maestría de Semana 7 (Seniority FAANG Ready) perfect_scores = { "bit_manipulation": 20, "advanced_sorting_searching": 20, "tries_prefix_trees": 20, "dsu_union_find": 20, "system_scale_and_v8": 20, } res_perfect = evaluate_semana_7_mastery(perfect_scores) self.assertEqual(res_perfect["total_score"], 100.0) self.assertTrue(res_perfect["passed"]) self.assertIn("L5 FAANG Ready", res_perfect["level"]) mid_scores = { "bit_manipulation": 16, "advanced_sorting_searching": 16, "tries_prefix_trees": 15, "dsu_union_find": 16, "system_scale_and_v8": 15, } res_mid = evaluate_semana_7_mastery(mid_scores) self.assertEqual(res_mid["total_score"], 78.0) self.assertTrue(res_mid["passed"]) self.assertIn("L4 FAANG Ready", res_mid["level"]) # --- SEMANA 7: CASOS BORDE Y ESTRÉS PROFUNDO --- def test_dia_43_to_49_semana_7_edge_cases_and_stress(self): # 1. Estrés Bitwise Trie con 500 números pseudo-aleatorios import random random.seed(43) sample_nums = [random.randint(0, 1000000) for _ in range(500)] max_xor_val = find_maximum_xor(sample_nums) self.assertGreater(max_xor_val, 500000) # 2. Estrés DSU con 2000 nodos y componentes conectadas dsu_large = DisjointSetUnion(2000) for i in range(1999): dsu_large.union(i, i + 1) self.assertEqual(dsu_large.count_components(), 1) self.assertTrue(dsu_large.connected(0, 1999)) self.assertEqual(dsu_large.get_component_size(1000), 2000) # 3. BitVector a gran escala (32,000 bits) bv_large = BitVector(32000) test_positions = [0, 1, 31, 32, 33, 1023, 1024, 15000, 31999] for pos in test_positions: bv_large.set(pos) for pos in test_positions: self.assertTrue(bv_large.get(pos)) self.assertFalse(bv_large.get(15001)) self.assertFalse(bv_large.get(2)) # 4. RankTracker en stream con valores ordenados inversamente tracker = RankTracker() for x in range(100, 0, -1): tracker.track(x) self.assertEqual(tracker.get_rank_of_number(50), 49) self.assertEqual(tracker.get_rank_of_number(1), 0) self.assertEqual(tracker.get_rank_of_number(100), 99) # --- SEMANA 8: DÍA 50 - Trapping Rain Water (CTCI 17.21 / LC 42 Hard) --- def test_dia_50_trapping_rain_water(self): # 1. Casos estándar de LeetCode 42 height1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] self.assertEqual(trap_rain_water_two_arrays(height1), 6) self.assertEqual(trap_rain_water_monotonic_stack(height1), 6) self.assertEqual(trap_rain_water_two_pointers(height1), 6) height2 = [4, 2, 0, 3, 2, 5] self.assertEqual(trap_rain_water_two_arrays(height2), 9) self.assertEqual(trap_rain_water_monotonic_stack(height2), 9) self.assertEqual(trap_rain_water_two_pointers(height2), 9) # 2. Casos de terreno plano, creciente, decreciente en todos los enfoques for h_flat in ([3, 3, 3, 3], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1]): self.assertEqual(trap_rain_water_two_arrays(h_flat), 0) self.assertEqual(trap_rain_water_monotonic_stack(h_flat), 0) self.assertEqual(trap_rain_water_two_pointers(h_flat), 0) # 3. Valle simple en V y doble pico self.assertEqual(trap_rain_water_two_pointers([5, 0, 5]), 5) self.assertEqual(trap_rain_water_two_arrays([5, 0, 5]), 5) self.assertEqual(trap_rain_water_monotonic_stack([5, 0, 5]), 5) self.assertEqual(trap_rain_water_two_pointers([3, 0, 2, 0, 4]), 7) self.assertEqual(trap_rain_water_two_arrays([3, 0, 2, 0, 4]), 7) self.assertEqual(trap_rain_water_monotonic_stack([3, 0, 2, 0, 4]), 7) # 4. Casos límite (listas cortas y vacías) en los 3 algoritmos for short_h in ([], [1], [2, 3]): self.assertEqual(trap_rain_water_two_arrays(short_h), 0) self.assertEqual(trap_rain_water_monotonic_stack(short_h), 0) self.assertEqual(trap_rain_water_two_pointers(short_h), 0) # 5. Variante diagnóstica details = trap_rain_water_details(height1) self.assertEqual(details["total_water"], 6) self.assertEqual(details["peak_index"], 7) # Bar with height 3 self.assertEqual(len(details["water_per_column"]), len(height1)) empty_details = trap_rain_water_details([]) self.assertEqual(empty_details["total_water"], 0) # --- SEMANA 8: DÍA 51 - Monotonic Deque & Sliding Window Maximum (LC 239 Hard) --- def test_dia_51_monotonic_deque_sliding_window(self): # 1. LeetCode 239: Sliding Window Maximum nums1 = [1, 3, -1, -3, 5, 3, 6, 7] k1 = 3 expected_max = [3, 3, 5, 5, 6, 7] self.assertEqual(max_sliding_window(nums1, k1), expected_max) self.assertEqual(max_sliding_window([1], 1), [1]) self.assertEqual(max_sliding_window([1, -1], 1), [1, -1]) self.assertEqual(max_sliding_window([9, 11], 2), [11]) self.assertEqual(max_sliding_window([4, -2], 2), [4]) # 2. Casos de borde self.assertEqual(max_sliding_window([], 3), []) self.assertEqual(max_sliding_window([1, 2, 3], 0), []) self.assertEqual(max_sliding_window([1, 2, 3], 5), [3]) self.assertEqual(max_sliding_window([3, 3, 3, 3], 2), [3, 3, 3]) self.assertEqual(min_sliding_window([3, 3, 3, 3], 2), [3, 3, 3]) self.assertEqual(max_sliding_window([5, 4, 3, 2, 1], 3), [5, 4, 3]) self.assertEqual(min_sliding_window([1, 2, 3, 4, 5], 3), [1, 2, 3]) # 3. Sliding Window Minimum (Monotonic Deque Creciente) expected_min = [-1, -3, -3, -3, 3, 3] self.assertEqual(min_sliding_window(nums1, k1), expected_min) # 4. Variante de Telemetría (Extremos Simultáneos y Rango de Amplitud) extremes = sliding_window_extremes(nums1, k1) self.assertEqual(extremes["maxima"], expected_max) self.assertEqual(extremes["minima"], expected_min) expected_ranges = [mx - mn for mx, mn in zip(expected_max, expected_min)] self.assertEqual(extremes["ranges"], expected_ranges) self.assertEqual(sliding_window_extremes([], 3)["ranges"], []) # 5. Prueba directa de la clase MonotonicDeque (Máximos y Mínimos) m_deq_max = MonotonicDeque(is_max=True) self.assertTrue(m_deq_max.is_empty()) with self.assertRaises(IndexError): m_deq_max.get_extreme_index() arr_test = [10, 20, 15] m_deq_max.push(arr_test, 0) self.assertEqual(m_deq_max.get_extreme_index(), 0) m_deq_max.push(arr_test, 1) # 20 desaloja a 10 self.assertEqual(m_deq_max.get_extreme_index(), 1) m_deq_max.push(arr_test, 2) # 15 se ubica detrás de 20 self.assertEqual(m_deq_max.get_extreme_index(), 1) m_deq_max.pop_out_of_window(left_boundary=2) # Desaloja 20 (índice 1) self.assertEqual(m_deq_max.get_extreme_index(), 2) m_deq_min = MonotonicDeque(is_max=False) m_deq_min.push(arr_test, 0) # 10 self.assertEqual(m_deq_min.get_extreme_index(), 0) m_deq_min.push(arr_test, 1) # 20 >= 10 -> queda detrás self.assertEqual(m_deq_min.get_extreme_index(), 0) m_deq_min.pop_out_of_window(left_boundary=1) # Desaloja 10 (índice 0) self.assertEqual(m_deq_min.get_extreme_index(), 1) # --- SEMANA 8: DÍA 52 - Fenwick Tree / BIT (LC 307) --- def test_dia_52_fenwick_tree_binary_indexed_tree(self): # 1. Construcción Lineal O(N) y Consultas de Rango arr = [1, 3, 5, 7, 9, 11] bit = FenwickTree(arr) self.assertEqual(bit.query_prefix(6), 36) self.assertEqual(bit.query_prefix(3), 9) # 1 + 3 + 5 self.assertEqual(bit.query_range(1, 3), 15) # 3 + 5 + 7 self.assertEqual(bit.query_range(0, 5), 36) # 2. Actualización puntual en O(log N) bit.update(index_0based=1, val=10) # [1, 10, 5, 7, 9, 11] (delta = +7) self.assertEqual(bit.query_range(1, 3), 22) # 10 + 5 + 7 self.assertEqual(bit.query_prefix(6), 43) # 3. Binary Lifting en O(log N) sobre BIT weights = [2, 4, 6, 8, 10] # Prefijos: [2, 6, 12, 20, 30] bit_pos = FenwickTree(weights) self.assertEqual(bit_pos.lower_bound(1), 0) self.assertEqual(bit_pos.lower_bound(6), 1) self.assertEqual(bit_pos.lower_bound(10), 2) self.assertEqual(bit_pos.lower_bound(25), 4) self.assertEqual(bit_pos.lower_bound(30), 4) self.assertEqual(bit_pos.lower_bound(50), 5) # Fuera de rango -> self.n self.assertEqual(bit_pos.lower_bound(0), 0) self.assertEqual(bit_pos.lower_bound(-5), 0) # 4. Solución LeetCode 307 NumArrayBIT num_array = NumArrayBIT([1, 3, 5]) self.assertEqual(num_array.sumRange(0, 2), 9) num_array.update(1, 2) # [1, 2, 5] self.assertEqual(num_array.sumRange(0, 2), 8) # 5. Errores y Casos Límite with self.assertRaises(IndexError): bit.add(0, 10) # 1-based no admite <= 0 with self.assertRaises(IndexError): bit.update(-1, 5) with self.assertRaises(IndexError): bit.query_range(-1, 2) with self.assertRaises(IndexError): bit.query_range(0, 100) self.assertEqual(bit.query_range(4, 2), 0) # left > right retorna 0 with self.assertRaises(ValueError): FenwickTree(-5) with self.assertRaises(TypeError): FenwickTree("invalid") # type: ignore # 6. FenwickTree vacío y de tamaño cero empty_bit = FenwickTree([]) self.assertEqual(empty_bit.n, 0) self.assertEqual(empty_bit.query_prefix(0), 0) self.assertEqual(empty_bit.lower_bound(5), 0) zero_bit = FenwickTree(0) self.assertEqual(zero_bit.n, 0) # --- SEMANA 8: DÍA 53 - Segment Tree (LC 307 & Range Min/Max) --- def test_dia_53_segment_tree(self): # 1. Segment Tree para Sumas arr = [1, 3, 5, 7, 9, 11] st_sum = SegmentTree(arr, mode="sum") self.assertEqual(st_sum.query(0, 5), 36) self.assertEqual(st_sum.query(1, 3), 15) # 3 + 5 + 7 st_sum.update(1, 10) # [1, 10, 5, 7, 9, 11] self.assertEqual(st_sum.query(1, 3), 22) self.assertEqual(st_sum.query(0, 5), 43) # 2. Segment Tree para Mínimos y Máximos arr_vals = [5, 2, 8, 1, 9, 3] st_min = SegmentTree(arr_vals, mode="min") self.assertEqual(st_min.query(0, 2), 2) self.assertEqual(st_min.query(2, 4), 1) st_min.update(3, 10) # [5, 2, 8, 10, 9, 3] self.assertEqual(st_min.query(2, 4), 8) st_max = SegmentTree(arr_vals, mode="max") self.assertEqual(st_max.query(0, 3), 8) self.assertEqual(st_max.query(2, 5), 9) # Modo min y max con valores negativos neg_st_min = SegmentTree([-10, -50, 20, -5, 100], mode="min") self.assertEqual(neg_st_min.query(0, 4), -50) self.assertEqual(neg_st_min.query(2, 4), -5) neg_st_max = SegmentTree([-10, -50, 20, -5, 100], mode="max") self.assertEqual(neg_st_max.query(0, 4), 100) self.assertEqual(neg_st_max.query(0, 1), -10) # 3. LeetCode 307: NumArraySegmentTree num_arr_st = NumArraySegmentTree([1, 3, 5]) self.assertEqual(num_arr_st.sumRange(0, 2), 9) num_arr_st.update(1, 2) self.assertEqual(num_arr_st.sumRange(0, 2), 8) # 4. RangeMinMaxSegmentTree (Doble Consulta Simultánea) rmm = RangeMinMaxSegmentTree([12, 5, 7, 19, 3, 8]) self.assertEqual(rmm.query_min_max(0, 5), (3, 19)) self.assertEqual(rmm.query_min_max(1, 3), (5, 19)) rmm.update(4, 25) # [12, 5, 7, 19, 25, 8] self.assertEqual(rmm.query_min_max(0, 5), (5, 25)) # RangeMinMaxSegmentTree con un solo elemento y con negativos rmm_single = RangeMinMaxSegmentTree([-42]) self.assertEqual(rmm_single.query_min_max(0, 0), (-42, -42)) rmm_single.update(0, 99) self.assertEqual(rmm_single.query_min_max(0, 0), (99, 99)) # 5. Casos de borde empty_st = SegmentTree([], mode="sum") self.assertEqual(empty_st.query(0, 0), 0) with self.assertRaises(ValueError): SegmentTree(arr, mode="invalid_mode") with self.assertRaises(IndexError): st_sum.update(100, 1) # --- SEMANA 8: DÍA 54 - Kadane 1D, Circular & CTCI 17.24 Max Submatrix 2D --- def test_dia_54_kadane_1d_circular_max_submatrix(self): # 1. Kadane 1D Estándar (LC 53) nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4] max_s, start, end = kadane_1d(nums1) self.assertEqual(max_s, 6) self.assertEqual(nums1[start : end + 1], [4, -1, 2, 1]) # Todos negativos all_neg = [-5, -2, -8, -1, -4] s_neg, st_neg, end_neg = kadane_1d(all_neg) self.assertEqual(s_neg, -1) self.assertEqual(st_neg, 3) self.assertEqual(end_neg, 3) with self.assertRaises(ValueError): kadane_1d([]) # 2. LeetCode 918: Maximum Sum Circular Subarray self.assertEqual(max_subarray_sum_circular([1, -2, 3, -2]), 3) self.assertEqual(max_subarray_sum_circular([5, -3, 5]), 10) # Da la vuelta: 5 + 5 self.assertEqual(max_subarray_sum_circular([-3, -2, -3]), -2) # Caso todos negativos self.assertEqual(max_subarray_sum_circular([3, -1, 2, -1]), 4) self.assertEqual(max_subarray_sum_circular([1, 2, 3]), 6) self.assertEqual(max_subarray_sum_circular([-5]), -5) self.assertEqual(max_subarray_sum_circular([]), 0) # 3. CTCI 17.24: Max Submatrix 2D matrix = [ [1, 2, -1, -4, -20], [-8, -3, 4, 2, 1], [3, 8, 10, 1, 3], [-4, -1, 1, 7, -6], ] res = max_submatrix_2d(matrix) self.assertEqual(res["max_sum"], 29) self.assertEqual(max_submatrix_sum(matrix), 29) self.assertEqual(res["r1"], 1) self.assertEqual(res["r2"], 3) self.assertEqual(res["c1"], 1) self.assertEqual(res["c2"], 3) # Matriz degenerada 1xN (vector fila) row_mat = [[-2, 1, -3, 4, -1, 2, 1, -5, 4]] res_row = max_submatrix_2d(row_mat) self.assertEqual(res_row["max_sum"], 6) self.assertEqual(res_row["submatrix"], [[4, -1, 2, 1]]) # Matriz degenerada Nx1 (vector columna) col_mat = [[-2], [1], [-3], [4], [-1], [2], [1], [-5], [4]] res_col = max_submatrix_2d(col_mat) self.assertEqual(res_col["max_sum"], 6) self.assertEqual(res_col["submatrix"], [[4], [-1], [2], [1]]) # Matriz con todos los elementos negativos neg_mat = [[-9, -8], [-5, -2]] res_neg_mat = max_submatrix_2d(neg_mat) self.assertEqual(res_neg_mat["max_sum"], -2) self.assertEqual(res_neg_mat["submatrix"], [[-2]]) # Matriz 1x1 self.assertEqual(max_submatrix_sum([[-5]]), -5) # Matriz vacía self.assertEqual(max_submatrix_sum([]), 0) self.assertEqual(max_submatrix_2d([])["submatrix"], []) # --- SEMANA 8: DÍA 55 - Aritmética Numérica de Alto Rendimiento (LC 204, CTCI 17.9, LC 50) --- def test_dia_55_high_performance_arithmetic(self): # 1. Criba de Eratóstenes y Count Primes (LC 204) primes_10 = sieve_of_eratosthenes(10) self.assertEqual(primes_10, [2, 3, 5, 7]) self.assertEqual(sieve_of_eratosthenes(2), []) self.assertEqual(sieve_of_eratosthenes(1), []) self.assertEqual(count_primes(10), 4) self.assertEqual(count_primes(0), 0) self.assertEqual(count_primes(1), 0) self.assertEqual(count_primes(2), 0) self.assertEqual(count_primes(3), 1) self.assertEqual(count_primes(100), 25) # Validación cruzada exhaustiva count_primes(n) == len(sieve(n)) para n in 0..50 for n_val in range(50): self.assertEqual(count_primes(n_val), len(sieve_of_eratosthenes(n_val))) # 2. CTCI 17.9: Kth Multiple (factores 3, 5, 7) expected_ctci = [1, 3, 5, 7, 9, 15, 21, 25, 27, 35] for k_idx, val in enumerate(expected_ctci, 1): self.assertEqual(get_kth_multiple_ctci(k_idx), val) with self.assertRaises(ValueError): get_kth_multiple_ctci(0) # LeetCode 264: Ugly Numbers II (factores 2, 3, 5) self.assertEqual(nth_ugly_number_lc(1), 1) self.assertEqual(nth_ugly_number_lc(10), 12) self.assertEqual(nth_ugly_number_lc(11), 15) # 3. Exponenciación Rápida Binaria (LC 50) self.assertAlmostEqual(binary_pow(2.0, 10), 1024.0) self.assertAlmostEqual(binary_pow(2.1, 3), 9.261) self.assertAlmostEqual(binary_pow(2.0, -2), 0.25) self.assertAlmostEqual(binary_pow(-2.0, -3), -0.125) self.assertAlmostEqual(binary_pow(0.0, 5), 0.0) self.assertAlmostEqual(binary_pow(7.5, 0), 1.0) with self.assertRaises(ZeroDivisionError): binary_pow(0.0, -1) # 4. Exponenciación Modular Rápida self.assertEqual(modular_pow(2, 10, 1000), 24) self.assertEqual(modular_pow(3, 7, 13), 3) # 2187 % 13 = 3 self.assertEqual(modular_pow(5, 0, 7), 1) self.assertEqual(modular_pow(0, 5, 7), 0) self.assertEqual(modular_pow(0, 0, 7), 1) self.assertEqual(modular_pow(10, 5, 1), 0) with self.assertRaises(ValueError): modular_pow(2, -3, 5) # --- SEMANA 8: DÍA 56 - LFU Cache (LC 460 Hard) & Certificación Staff --- def test_dia_56_lfu_cache_and_final_certification(self): # 1. LeetCode 460 Hard: LFU Cache cache = LFUCache(2) cache.put(1, 1) cache.put(2, 2) self.assertEqual(cache.get(1), 1) # freq(1) = 2 cache.put(3, 3) # Capacidad alcanzada. freq(2)=1, freq(1)=2 -> desaloja clave 2 self.assertEqual(cache.get(2), -1) self.assertEqual(cache.get(3), 3) # freq(3) = 2 cache.put(4, 4) # freq(1)=2, freq(3)=2. Desempate LRU: clave 1 fue usada antes que 3 -> desaloja clave 1 self.assertEqual(cache.get(1), -1) self.assertEqual(cache.get(3), 3) self.assertEqual(cache.get(4), 4) # Actualización de clave existente incrementa frecuencia cache.put(4, 40) self.assertEqual(cache.get(4), 40) # Capacidad 0 zero_cache = LFUCache(0) zero_cache.put(1, 1) self.assertEqual(zero_cache.get(1), -1) # Prueba de desempate LRU con 3 elementos en la misma frecuencia cache3 = LFUCache(3) cache3.put(1, 10) cache3.put(2, 20) cache3.put(3, 30) # Promover todos a frecuencia 2 self.assertEqual(cache3.get(1), 10) self.assertEqual(cache3.get(2), 20) self.assertEqual(cache3.get(3), 30) # Inserción con capacidad llena desaloja clave 1 (LRU de freq 2) cache3.put(4, 40) self.assertEqual(cache3.get(1), -1) self.assertEqual(cache3.get(2), 20) self.assertEqual(cache3.get(3), 30) self.assertEqual(cache3.get(4), 40) # Actualizaciones repetidas protegen la clave ante desalojos cache_protect = LFUCache(2) for val in range(10): cache_protect.put(1, val) # freq de 1 se dispara a 10 cache_protect.put(2, 200) # freq de 2 = 1 cache_protect.put(3, 300) # Desaloja a 2 por tener freq menor self.assertEqual(cache_protect.get(2), -1) self.assertEqual(cache_protect.get(1), 9) self.assertEqual(cache_protect.get(3), 300) # 2. Evaluación y Certificación de Seniority Staff (56 Días) perfect_scores = { "trapping_rain_water_two_pointers": 15.0, "monotonic_deque": 15.0, "fenwick_tree_bit": 15.0, "segment_tree": 15.0, "kadane_2d_ctci": 15.0, "high_performance_arithmetic": 10.0, "lfu_cache_design": 15.0, } res_staff = evaluate_staff_mastery(perfect_scores) self.assertEqual(res_staff["total_score"], 100.0) self.assertTrue(res_staff["passed"]) self.assertIn("L6 Staff", res_staff["level"]) senior_scores = { "trapping_rain_water_two_pointers": 13.0, "monotonic_deque": 13.0, "fenwick_tree_bit": 13.0, "segment_tree": 13.0, "kadane_2d_ctci": 12.0, "high_performance_arithmetic": 8.0, "lfu_cache_design": 12.0, } res_senior = evaluate_staff_mastery(senior_scores) self.assertEqual(res_senior["total_score"], 84.0) self.assertTrue(res_senior["passed"]) self.assertIn("L5 Senior", res_senior["level"]) # --- SEMANA 8: CASOS BORDE Y ESTRÉS PROFUNDO --- def test_dia_50_to_56_semana_8_edge_cases_and_stress(self): import random import itertools random.seed(56) # 1. Estrés Fenwick Tree vs Segment Tree en 1,000 operaciones dinámicas n_elem = 500 initial_arr = [random.randint(1, 100) for _ in range(n_elem)] bit_stress = FenwickTree(initial_arr) st_stress = SegmentTree(initial_arr, mode="sum") for _ in range(1000): if random.random() < 0.5: idx = random.randint(0, n_elem - 1) new_val = random.randint(1, 100) bit_stress.update(idx, new_val) st_stress.update(idx, new_val) else: l = random.randint(0, n_elem - 1) r = random.randint(l, n_elem - 1) sum_bit = bit_stress.query_range(l, r) sum_st = st_stress.query(l, r) self.assertEqual(sum_bit, sum_st) # 2. Estrés Monotonic Deque con 5,000 elementos y ventana grande large_stream = [random.randint(-1000, 1000) for _ in range(5000)] k_window = 100 res_max_deq = max_sliding_window(large_stream, k_window) self.assertEqual(len(res_max_deq), 5000 - k_window + 1) for check_idx in (0, 1000, 2500, 4800): if check_idx + k_window <= len(large_stream): window_slice = large_stream[check_idx : check_idx + k_window] self.assertEqual(res_max_deq[check_idx], max(window_slice)) # 3. Estrés Trapping Rain Water: Meseta amplia con valles múltiples terrain = [0] + [random.randint(1, 20) for _ in range(200)] + [0] res_arrays = trap_rain_water_two_arrays(terrain) res_stack = trap_rain_water_monotonic_stack(terrain) res_pointers = trap_rain_water_two_pointers(terrain) self.assertEqual(res_arrays, res_stack) self.assertEqual(res_stack, res_pointers) # 4. Estrés LFU Cache: Secuencia de 500 accesos concurrentes lfu_stress = LFUCache(10) for i in range(500): key = random.randint(1, 25) if random.random() < 0.6: lfu_stress.put(key, i) else: lfu_stress.get(key) self.assertLessEqual(lfu_stress.size, 10) # 5. Validación cruzada de RangeMinMaxSegmentTree vs SegmentTree min/max arr_rmm = [random.randint(-500, 500) for _ in range(100)] rmm_tree = RangeMinMaxSegmentTree(arr_rmm) st_tree_min = SegmentTree(arr_rmm, mode="min") st_tree_max = SegmentTree(arr_rmm, mode="max") for _ in range(200): ql = random.randint(0, 99) qr = random.randint(ql, 99) res_min, res_max = rmm_tree.query_min_max(ql, qr) self.assertEqual(res_min, st_tree_min.query(ql, qr)) self.assertEqual(res_max, st_tree_max.query(ql, qr)) # 6. Validación cruzada de FenwickTree.lower_bound contra sumas acumuladas lineales w_rand = [random.randint(1, 20) for _ in range(50)] bit_lb = FenwickTree(w_rand) prefix_acc = list(itertools.accumulate(w_rand)) for t_query in range(0, sum(w_rand) + 10): got_lb = bit_lb.lower_bound(t_query) if t_query <= 0: expected_lb = 0 else: expected_lb = len(w_rand) for pos_idx, val_acc in enumerate(prefix_acc): if val_acc >= t_query: expected_lb = pos_idx break self.assertEqual(got_lb, expected_lb) # --- SEMANA 9: DÍA 57 - KNN, Métricas Vectoriales y LC 973 --- def test_dia_57_knn_vector_distances(self): # 1. Distancia Euclidiana y Manhattan v1 = [0.0, 0.0] v2 = [3.0, 4.0] self.assertAlmostEqual(euclidean_distance(v1, v2), 5.0) self.assertAlmostEqual(manhattan_distance(v1, v2), 7.0) self.assertAlmostEqual(euclidean_distance([1.0, 2.0], [1.0, 2.0]), 0.0) with self.assertRaises(ValueError): euclidean_distance([1.0], [1.0, 2.0]) with self.assertRaises(ValueError): euclidean_distance([], []) # 2. Similitud y Distancia Coseno # Vectores colineales en la misma dirección -> sim = 1.0 self.assertAlmostEqual(cosine_similarity([1.0, 2.0, 3.0], [2.0, 4.0, 6.0]), 1.0) self.assertAlmostEqual(cosine_distance([1.0, 2.0, 3.0], [2.0, 4.0, 6.0]), 0.0) # Vectores ortogonales -> sim = 0.0 self.assertAlmostEqual(cosine_similarity([1.0, 0.0], [0.0, 1.0]), 0.0) # Vectores opuestos -> sim = -1.0 self.assertAlmostEqual(cosine_similarity([1.0, 0.0], [-1.0, 0.0]), -1.0) with self.assertRaises(ValueError): cosine_similarity([0.0, 0.0], [1.0, 2.0]) # 3. Normalización Min-Max data = [[10.0, 100.0], [20.0, 200.0], [30.0, 100.0]] norm_data, mins, maxs = min_max_normalize(data) self.assertEqual(mins, [10.0, 100.0]) self.assertEqual(maxs, [30.0, 200.0]) self.assertEqual(norm_data[0], [0.0, 0.0]) self.assertEqual(norm_data[1], [0.5, 1.0]) self.assertEqual(norm_data[2], [1.0, 0.0]) # 4. Clasificador KNN train_x = [[1.0, 1.0], [1.2, 1.1], [5.0, 5.0], [5.2, 5.1]] train_y = ["Cat", "Cat", "Dog", "Dog"] self.assertEqual(knn_classify(train_x, train_y, [1.1, 1.0], k=1), "Cat") self.assertEqual(knn_classify(train_x, train_y, [5.1, 5.0], k=3), "Dog") self.assertEqual(knn_classify(train_x, train_y, [1.1, 1.0], k=3, weighted=True), "Cat") with self.assertRaises(ValueError): knn_classify(train_x, train_y, [1.0, 1.0], k=10) # 5. Regresor KNN reg_x = [[1.0], [2.0], [3.0], [10.0]] reg_y = [10.0, 20.0, 30.0, 100.0] self.assertAlmostEqual(knn_regress(reg_x, reg_y, [2.0], k=1), 20.0) self.assertAlmostEqual(knn_regress(reg_x, reg_y, [1.5], k=2, weighted=False), 15.0) # 6. LeetCode 973: K Closest Points to Origin pts1 = [[1, 3], [-2, 2]] k1 = 1 res1 = k_closest_points_to_origin(pts1, k1) self.assertEqual(res1, [[-2, 2]]) pts2 = [[3, 3], [5, -1], [-2, 4]] k2 = 2 res2 = k_closest_points_to_origin(pts2, k2) # Distancias al cuadrado: (3,3)->18, (5,-1)->26, (-2,4)->20. Los 2 más cercanos son (3,3) y (-2,4) res2_tuples = {tuple(p) for p in res2} self.assertEqual(res2_tuples, {(3, 3), (-2, 4)}) # --- SEMANA 9: DÍA 58 - Bloom Filter y HyperLogLog (LC 705) --- def test_dia_58_bloom_filter_hyperloglog(self): # 1. Filtro de Bloom bf = BloomFilter.create_optimal(expected_items=500, false_positive_rate=0.01) self.assertGreater(bf.size, 1000) self.assertGreaterEqual(bf.k, 3) items_to_add = [f"user_{i}@example.com" for i in range(300)] for item in items_to_add: bf.add(item) # Cero falsos negativos garantizado for item in items_to_add: self.assertTrue(bf.contains(item)) # Tasa teórica de falsos positivos self.assertLess(bf.theoretical_false_positive_rate(), 0.05) # Falsos positivos empíricos test_items = [f"random_unknown_item_{i}" for i in range(500)] false_positives = sum(1 for item in test_items if bf.contains(item)) # No debe superar el 5% de falsos positivos self.assertLessEqual(false_positives / 500.0, 0.05) with self.assertRaises(ValueError): BloomFilter(0, 5) with self.assertRaises(ValueError): BloomFilter.create_optimal(100, 1.5) # 2. HyperLogLog hll = HyperLogLog(b=6) # 64 buckets unique_count = 1000 for i in range(unique_count): hll.add(f"item_{i}") # Insertar duplicados para comprobar que no inflan la cardinalidad if i % 3 == 0: hll.add(f"item_{i}") est = hll.count() # Con 64 buckets el error estándar es ~1.04 / sqrt(64) = 13% # Verificamos que la estimación esté dentro de un margen razonable (±25%) self.assertTrue(750 <= est <= 1350, f"Estimación {est} fuera de rango para 1000 items") # Corrección de rango pequeño (Linear Counting) hll_small = HyperLogLog(b=6) for i in range(5): hll_small.add(f"small_{i}") small_est = hll_small.count() self.assertAlmostEqual(small_est, 5.0, delta=1.5) with self.assertRaises(ValueError): HyperLogLog(b=2) # 3. ProbabilisticHashSet (LC 705) phs = ProbabilisticHashSet(capacity=50) phs.add(10) phs.add(20) self.assertTrue(phs.contains(10)) self.assertTrue(phs.contains(20)) self.assertFalse(phs.contains(30)) phs.remove(10) self.assertFalse(phs.contains(10)) self.assertTrue(phs.contains(20)) # --- SEMANA 9: DÍA 59 - Inverted Index & TF-IDF Search Engine --- def test_dia_59_inverted_index_tfidf(self): # 1. Tokenización tokens = tokenize("¡Hola, Mundo! Algoritmos en Python 3.13") self.assertEqual(tokens, ["hola", "mundo", "algoritmos", "en", "python", "3", "13"]) # 2. Delta Encoding y Decoding postings = [10, 15, 23, 25, 40] deltas = delta_encode(postings) self.assertEqual(deltas, [10, 5, 8, 2, 15]) self.assertEqual(delta_decode(deltas), postings) self.assertEqual(delta_encode([]), []) self.assertEqual(delta_decode([]), []) with self.assertRaises(ValueError): delta_encode([10, 8, 12]) # No creciente with self.assertRaises(ValueError): delta_decode([10, -2, 5]) # Delta negativo # 3. Intersección y Unión de Postings p1 = [1, 3, 5, 7, 9] p2 = [2, 3, 6, 7, 10] self.assertEqual(intersect_postings(p1, p2), [3, 7]) self.assertEqual(union_postings(p1, p2), [1, 2, 3, 5, 6, 7, 9, 10]) # 4. Índice Invertido idx = InvertedIndex() idx.add_document(1, "Estructuras de datos y algoritmos en Python") idx.add_document(2, "Algoritmos de busqueda y grafos") idx.add_document(3, "Programacion dinamica y estructuras de datos") self.assertEqual(idx.search_and(["algoritmos", "grafos"]), [2]) self.assertEqual(idx.search_and(["estructuras", "datos"]), [1, 3]) self.assertEqual(idx.search_and(["python", "grafos"]), []) self.assertEqual(idx.search_or(["python", "grafos"]), [1, 2]) with self.assertRaises(ValueError): idx.add_document(1, "Texto repetido") # 5. TF-IDF Search Engine corpus = { 101: "el algoritmo de quicksort divide y venceras", 102: "algoritmos de busqueda binaria y divide y venceras", 103: "grafos y busqueda en anchura bfs", } engine = TFIDFSearchEngine() engine.fit(corpus) results = engine.search("divide venceras", top_k=2) self.assertGreater(len(results), 0) # Los documentos 101 y 102 deben tener las puntuaciones más altas top_doc_id = results[0][0] self.assertIn(top_doc_id, [101, 102]) # Documento que no contiene el término no recibe puntuación results_bfs = engine.search("bfs", top_k=5) self.assertEqual(results_bfs[0][0], 103) # --- SEMANA 9: DÍA 60 - SimHash, LSH y LC 187 --- def test_dia_60_simhash_lsh(self): # 1. Distancia de Hamming a nivel de bits self.assertEqual(hamming_distance_bits(0b1011, 0b1000), 2) self.assertEqual(hamming_distance_bits(0b1111, 0b1111), 0) self.assertEqual(hamming_distance_bits(0, 0xFFFFFFFFFFFFFFFF), 64) # 2. SimHash text1 = "python es un lenguaje de programacion interpretado de alto nivel y tipado dinamico con soporte para algoritmos" text2 = "python es un lenguaje de programacion interpretado de alto nivel y tipado dinamico con soporte para algoritmos avanzados" # 1 palabra agregada text3 = "los agujeros negros son regiones del espacio tiempo donde la gravedad es tan fuerte que nada escapa" sh1 = SimHash(text1, shingle_size=2) sh2 = SimHash(text2, shingle_size=2) sh3 = SimHash(text3, shingle_size=2) self.assertEqual(sh1.distance(sh1), 0) # Documentos similares tienen distancia pequeña dist_similar = sh1.distance(sh2) dist_different = sh1.distance(sh3) self.assertLess(dist_similar, dist_different) self.assertTrue(sh1.is_duplicate(sh2, max_distance=6)) self.assertFalse(sh1.is_duplicate(sh3, max_distance=6)) # 3. SimHash LSH lsh = SimHashLSH(hash_bits=64, max_distance=6) lsh.insert(1, sh1) lsh.insert(2, sh3) dups1 = lsh.query_duplicates(sh2) self.assertIn(1, dups1) self.assertNotIn(2, dups1) with self.assertRaises(ValueError): lsh.insert(1, sh1) # 4. LeetCode 187: Repeated DNA Sequences s1 = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" expected1 = ["AAAAACCCCC", "CCCCCAAAAA"] self.assertEqual(find_repeated_dna_sequences(s1), expected1) s2 = "AAAAAAAAAAAAA" expected2 = ["AAAAAAAAAA"] self.assertEqual(find_repeated_dna_sequences(s2), expected2) self.assertEqual(find_repeated_dna_sequences("ACGT"), []) # --- SEMANA 9: DÍA 61 - Aritmética Teórica de Knuth & Diffie-Hellman --- def test_dia_61_extended_euclid_diffie_hellman(self): # 1. Euclides Canónico self.assertEqual(knuth_gcd(48, 18), 6) self.assertEqual(knuth_gcd(-48, 18), 6) self.assertEqual(knuth_gcd(0, 5), 5) self.assertEqual(knuth_gcd(17, 13), 1) # 2. Euclides Extendido (Bézout Identity) test_pairs = [(48, 18), (101, 13), (35, 15), (7, 0), (240, 46)] for a, b in test_pairs: g, x, y = extended_gcd(a, b) self.assertEqual(g, knuth_gcd(a, b)) self.assertEqual(a * x + b * y, g) # 3. Inverso Multiplicativo Modular # 3 * 4 = 12 ≡ 1 (mod 11) self.assertEqual(mod_inverse(3, 11), 4) # 10 * 12 = 120 ≡ 1 (mod 17) self.assertEqual(mod_inverse(10, 17), 12) # 7 * 8 = 56 ≡ 1 (mod 11) self.assertEqual(mod_inverse(7, 11), 8) with self.assertRaises(ValueError): mod_inverse(6, 9) # gcd(6, 9) = 3 != 1 with self.assertRaises(ValueError): mod_inverse(3, 1) # m <= 1 # 4. Solución de Ecuaciones Diofánticas # 4x + 6y = 10 -> solución existe porque gcd(4, 6)=2 divide a 10 sol = solve_diophantine(4, 6, 10) self.assertIsNotNone(sol) x0, y0 = sol self.assertEqual(4 * x0 + 6 * y0, 10) # 4x + 6y = 11 -> no existe solución entera self.assertIsNone(solve_diophantine(4, 6, 11)) # 5. LeetCode 365: Water and Jug Problem self.assertTrue(can_measure_water(3, 5, 4)) self.assertFalse(can_measure_water(2, 6, 5)) self.assertTrue(can_measure_water(1, 2, 3)) self.assertTrue(can_measure_water(0, 0, 0)) self.assertFalse(can_measure_water(3, 5, 9)) # target > x + y # 6. LeetCode 372: Super Pow self.assertEqual(super_pow(2, [3]), 8) self.assertEqual(super_pow(2, [1, 0]), 1024) self.assertEqual(super_pow(1, [4, 3, 3, 8, 5, 2]), 1) self.assertEqual(super_pow(2147483647, [2, 0, 0]), pow(2147483647, 200, 1337)) # 7. Intercambio de Claves Diffie-Hellman p = 23 # Primo g = 5 # Generador alice = DiffieHellmanParty(p, g, private_key=6) bob = DiffieHellmanParty(p, g, private_key=15) pub_alice = alice.generate_public_key() pub_bob = bob.generate_public_key() secret_alice = alice.compute_shared_secret(pub_bob) secret_bob = bob.compute_shared_secret(pub_alice) self.assertEqual(secret_alice, secret_bob) # --- SEMANA 9: DÍA 62 - Consistent Hashing & Rate Limiting --- def test_dia_62_consistent_hashing_token_bucket(self): # 1. Consistent Hash Ring ring = ConsistentHashRing(num_replicas=30) ring.add_node("server_alpha") ring.add_node("server_beta") ring.add_node("server_gamma") keys = [f"user_session_{i}" for i in range(300)] dist = ring.get_distribution(keys) # Todos los servidores deben recibir una porción equilibrada for srv in ["server_alpha", "server_beta", "server_gamma"]: self.assertGreater(dist[srv], 20, f"{srv} recibió muy pocas claves: {dist[srv]}") # Remover un servidor ring.remove_node("server_beta") dist_after = ring.get_distribution(keys) self.assertNotIn("server_beta", dist_after) self.assertEqual(sum(dist_after.values()), 300) empty_ring = ConsistentHashRing() self.assertIsNone(empty_ring.get_node("any_key")) # 2. Token Bucket Rate Limiter tb = TokenBucketRateLimiter(capacity=3.0, refill_rate=1.0, current_time=0.0) # Consumir 3 fichas disponibles self.assertTrue(tb.allow_request(1.0, current_time=0.0)) self.assertTrue(tb.allow_request(1.0, current_time=0.0)) self.assertTrue(tb.allow_request(1.0, current_time=0.0)) # Cubo vacío -> rechazar self.assertFalse(tb.allow_request(1.0, current_time=0.0)) # Avanzar 1 segundo -> 1 ficha recargada self.assertTrue(tb.allow_request(1.0, current_time=1.0)) self.assertFalse(tb.allow_request(1.0, current_time=1.0)) # 3. Leaky Bucket Rate Limiter lb = LeakyBucketRateLimiter(capacity=2, leak_rate=1.0, current_time=0.0) self.assertTrue(lb.allow_request(current_time=0.0)) self.assertTrue(lb.allow_request(current_time=0.0)) self.assertFalse(lb.allow_request(current_time=0.0)) # Lleno # Después de 1.5s gotea 1.5 unidades -> permite nueva solicitud self.assertTrue(lb.allow_request(current_time=1.5)) # 4. LeetCode 359: Logger Rate Limiter logger = LoggerRateLimiter() self.assertTrue(logger.should_print_message(1, "foo")) self.assertTrue(logger.should_print_message(2, "bar")) self.assertFalse(logger.should_print_message(3, "foo")) self.assertFalse(logger.should_print_message(8, "bar")) self.assertFalse(logger.should_print_message(10, "foo")) self.assertTrue(logger.should_print_message(11, "foo")) # 5. LeetCode 362: Hit Counter counter = HitCounter() counter.hit(1) counter.hit(2) counter.hit(3) self.assertEqual(counter.get_hits(4), 3) counter.hit(300) self.assertEqual(counter.get_hits(300), 4) self.assertEqual(counter.get_hits(301), 3) # El hit en t=1 expira # --- SEMANA 9: DÍA 63 - Super Egg Drop (LC 887/1884) & Consolidación --- def test_dia_63_super_egg_drop_and_week_9_consolidation(self): # 1. CTCI Cap. 6 / LeetCode 1884 (2 Eggs) self.assertEqual(two_egg_drop(1), 1) self.assertEqual(two_egg_drop(2), 2) self.assertEqual(two_egg_drop(6), 3) self.assertEqual(two_egg_drop(100), 14) with self.assertRaises(ValueError): two_egg_drop(0) # 2. LeetCode 887 Hard (Super Egg Drop con K huevos) # K=1 huevo -> N movimientos self.assertEqual(super_egg_drop_dp_binary_search(1, 10), 10) self.assertEqual(super_egg_drop_moves_dp(1, 10), 10) # K=2 huevos, N=6 pisos -> 3 movimientos self.assertEqual(super_egg_drop_dp_binary_search(2, 6), 3) self.assertEqual(super_egg_drop_moves_dp(2, 6), 3) # K=3 huevos, N=14 pisos -> 4 movimientos self.assertEqual(super_egg_drop_dp_binary_search(3, 14), 4) self.assertEqual(super_egg_drop_moves_dp(3, 14), 4) # Prueba de alta escala con Moves DP (imposible con DP ingenua O(K*N^2)) self.assertEqual(super_egg_drop_moves_dp(2, 100), 14) self.assertEqual(super_egg_drop_moves_dp(5, 10000), 18) # 3. Banco de Preguntas de Consolidación questions = get_week_9_questions() self.assertEqual(len(questions), 12) for q in questions: self.assertIn("id", q) self.assertIn("topic", q) self.assertIn("question", q) self.assertIn("key_concept", q) # 4. Evaluación de Maestría de Semana 9 perfect_scores = { "knn_vector_distances": 15.0, "bloom_filter_hyperloglog": 15.0, "inverted_index_tfidf": 15.0, "simhash_lsh": 15.0, "extended_euclid_diffie_hellman": 15.0, "consistent_hashing_rate_limiting": 15.0, "super_egg_drop": 10.0, } res_staff = evaluate_week_9_mastery(perfect_scores) self.assertEqual(res_staff["total_score"], 100.0) self.assertTrue(res_staff["passed"]) self.assertIn("Staff", res_staff["level"]) senior_scores = { "knn_vector_distances": 12.0, "bloom_filter_hyperloglog": 12.0, "inverted_index_tfidf": 12.0, "simhash_lsh": 12.0, "extended_euclid_diffie_hellman": 12.0, "consistent_hashing_rate_limiting": 12.0, "super_egg_drop": 8.0, } res_senior = evaluate_week_9_mastery(senior_scores) self.assertEqual(res_senior["total_score"], 80.0) self.assertTrue(res_senior["passed"]) self.assertIn("Senior", res_senior["level"]) # --- SEMANA 9: CASOS BORDE Y ESTRÉS PROFUNDO --- def test_dia_57_to_63_semana_9_edge_cases_and_stress(self): import random random.seed(63) # 1. Validación cruzada de Super Egg Drop: Moves DP vs Binary Search DP en 15 pares for _ in range(15): k = random.randint(1, 4) n = random.randint(1, 35) self.assertEqual(super_egg_drop_moves_dp(k, n), super_egg_drop_dp_binary_search(k, n)) # 2. Estrés de Identidad de Bézout con números gigantes en Euclides Extendido for _ in range(50): a = random.randint(1, 1000000) b = random.randint(1, 1000000) g, x, y = extended_gcd(a, b) self.assertEqual(a * x + b * y, g) self.assertEqual(g, knuth_gcd(a, b)) # 3. Estrés de Inverted Index Delta Encoding con 500 IDs crecientes current = random.randint(1, 10) large_postings = [current] for _ in range(499): current += random.randint(1, 20) large_postings.append(current) self.assertEqual(delta_decode(delta_encode(large_postings)), large_postings) # 4. Estrés de Consistent Hashing con 10 servidores y 2,000 claves ring = ConsistentHashRing(num_replicas=100) for i in range(10): ring.add_node(f"node_{i}") stress_keys = [f"session_token_{random.randint(1, 1000000)}" for _ in range(2000)] dist = ring.get_distribution(stress_keys) self.assertEqual(len(dist), 10) for node, count in dist.items(): # Cada nodo debe recibir entre el 5% y el 20% del total (~10% ideal) self.assertGreater(count, 50, f"Nodo {node} sub-utilizado con {count} claves") self.assertLess(count, 450, f"Nodo {node} sobrecargado con {count} claves") # 5. Caso Borde KNN Regress: Múltiples vecinos idénticos a distancia 0 con valores distintos self.assertAlmostEqual(knn_regress([[1.0], [1.0]], [10.0, 20.0], [1.0], k=2, weighted=True), 15.0) self.assertAlmostEqual(knn_regress([[2.0], [2.0], [2.0]], [3.0, 6.0, 9.0], [2.0], k=3, weighted=True), 6.0) self.assertGreaterEqual(cosine_distance([1.0, 1.0, 1.0], [1.0, 1.0, 1.0]), 0.0) # 6. Caso Borde Inverted Index: Inserción de documentos con IDs desordenados idx_unordered = InvertedIndex() idx_unordered.add_document(10, "apple banana") idx_unordered.add_document(5, "apple cherry") self.assertEqual(idx_unordered.get_postings("apple"), [5, 10]) self.assertEqual(delta_encode(idx_unordered.get_postings("apple")), [5, 5]) self.assertEqual(idx_unordered.search_and(["apple", "banana"]), [10]) self.assertEqual(idx_unordered.search_or(["banana", "cherry"]), [5, 10]) with self.assertRaises(ValueError): idx_unordered.add_document(-1, "negative doc id") # 7. Caso Borde Hit Counter: Consultas con timestamps anteriores a eventos registrados (futuro) hc_edge = HitCounter() hc_edge.hit(350) self.assertEqual(hc_edge.get_hits(300), 0) self.assertEqual(hc_edge.get_hits(350), 1) # 8. Caso Borde Consistent Hash Ring: Clave con hash que coincide exactamente con la posición de un nodo ring_exact = ConsistentHashRing( num_replicas=1, hash_fn=lambda x: 100 if x == "srvA#vnode0" else (200 if x == "srvB#vnode0" else 100) ) ring_exact.add_node("srvA") ring_exact.add_node("srvB") self.assertEqual(ring_exact.get_node("key_at_100"), "srvA") # 9. Caso Borde Rate Limiters: Validación de tokens negativos y cero tb_edge = TokenBucketRateLimiter(capacity=5.0, refill_rate=1.0) with self.assertRaises(ValueError): tb_edge.allow_request(0.0) with self.assertRaises(ValueError): tb_edge.allow_request(-2.0) # 10. Caso Borde Super Pow: Módulo 1 y módulo no positivo self.assertEqual(super_pow(2, [3], mod=1), 0) with self.assertRaises(ValueError): super_pow(2, [3], mod=0) with self.assertRaises(ValueError): super_pow(2, [3], mod=-5) # 11. Caso Borde SimHash LSH: Partición de bandas cuando hash_bits % num_bands != 0 lsh_uneven = SimHashLSH(hash_bits=64, max_distance=4) # 5 bandas: 13, 13, 13, 13, 12 bits self.assertEqual(lsh_uneven.num_bands, 5) self.assertEqual(sum(w for _, w in lsh_uneven.band_slices), 64) with self.assertRaises(ValueError): SimHashLSH(hash_bits=4, max_distance=5) def test_dia_57_to_63_semana_9_adversarial_and_stress(self): # 1. Prueba de Doble Hashing con stride controlado en Bloom Filter bf = BloomFilter(size_in_bits=100, num_hashes=5) indices = bf._hashes("adversarial_test_key") self.assertEqual(len(indices), 5) for idx in indices: self.assertTrue(0 <= idx < 100) # 2. Inverted Index con 100 documentos en orden aleatorio import random random.seed(99) idx_stress = InvertedIndex() doc_ids = list(range(100)) random.shuffle(doc_ids) words_pool = ["cpu", "gpu", "tpu", "ram", "ssd", "nvme"] for d_id in doc_ids: chosen = random.sample(words_pool, 3) idx_stress.add_document(d_id, " ".join(chosen)) for w in words_pool: postings = idx_stress.get_postings(w) # Postings deben estar estrictamente crecientes for i in range(1, len(postings)): self.assertGreater(postings[i], postings[i - 1]) # Delta encode / decode debe ser idempotente self.assertEqual(delta_decode(delta_encode(postings)), postings) # 3. Diffie-Hellman con números primos más grandes (p=7919) p_large = 7919 g_large = 7 alice = DiffieHellmanParty(p_large, g_large, private_key=1234) bob = DiffieHellmanParty(p_large, g_large, private_key=5678) self.assertEqual( alice.compute_shared_secret(bob.generate_public_key()), bob.compute_shared_secret(alice.generate_public_key()) ) # --- SEMANA 10: DÍA 64 - Regular Expression Matching (LC 10 Hard) & Wildcard Matching (LC 44 Hard) --- def test_dia_64_regular_expression_matching(self): # 1. Casos canónicos de LeetCode 10 (Regex Matching) self.assertFalse(is_match_regex("aa", "a")) self.assertTrue(is_match_regex("aa", "a*")) self.assertTrue(is_match_regex("ab", ".*")) self.assertTrue(is_match_regex("aab", "c*a*b")) self.assertFalse(is_match_regex("mississippi", "mis*is*p*.")) self.assertTrue(is_match_regex("", "a*b*c*")) self.assertTrue(is_match_regex("", "")) self.assertFalse(is_match_regex("ab", ".*c")) self.assertTrue(is_match_regex("aaa", "ab*a*c*a")) # 2. Validación cruzada de equivalencia: 2D DP vs Memoization vs 1D Space-Optimized test_cases = [ ("aa", "a"), ("aa", "a*"), ("ab", ".*"), ("aab", "c*a*b"), ("mississippi", "mis*is*p*."), ("", "a*b*c*"), ("", ""), ("aaa", "a*a"), ("bbbba", ".*a*a"), ] for s, p in test_cases: ans_2d = is_match_regex(s, p) ans_memo = is_match_regex_memo(s, p) ans_1d = is_match_regex_1d(s, p) self.assertEqual(ans_2d, ans_memo, f"Fallo en memo para s='{s}', p='{p}'") self.assertEqual(ans_2d, ans_1d, f"Fallo en 1D para s='{s}', p='{p}'") # 3. LeetCode 44 (Wildcard Matching para contraste conceptual) self.assertTrue(is_match_wildcard("aa", "*")) self.assertFalse(is_match_wildcard("cb", "?a")) self.assertTrue(is_match_wildcard("adceb", "*a*b")) self.assertFalse(is_match_wildcard("acdcb", "a*c?b")) self.assertTrue(is_match_wildcard("", "*")) self.assertTrue(is_match_wildcard("", "")) # 4. Validaciones de patrones inválidos with self.assertRaises(ValueError): is_match_regex("a", "*a") with self.assertRaises(ValueError): is_match_regex("a", "a**") # 5. Feedback pedagógico fb_correct = analyze_regex_feedback("aab", "c*a*b", True) self.assertTrue(fb_correct["is_correct"]) fb_wrong = analyze_regex_feedback("aab", "c*a*b", False) self.assertFalse(fb_wrong["is_correct"]) self.assertGreater(len(fb_wrong["feedback"]), 0) # --- SEMANA 10: DÍA 65 - Accounts Merge (LC 721) & Word Search II (LC 212) --- def test_dia_65_accounts_merge_and_word_search_ii(self): # 1. Accounts Merge (LC 721 Medium) accounts_1 = [ ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["John", "johnsmith@mail.com", "john00@mail.com"], ["Mary", "mary@mail.com"], ["John", "johnnybravo@mail.com"], ] merged_1 = accounts_merge(accounts_1) self.assertEqual(len(merged_1), 3) self.assertEqual( merged_1[0], ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"], ) self.assertEqual(merged_1[1], ["John", "johnnybravo@mail.com"]) self.assertEqual(merged_1[2], ["Mary", "mary@mail.com"]) # Cadena transitiva de fusiones: A-B, B-C, C-D transitive_accounts = [ ["Alex", "a@mail.com", "b@mail.com"], ["Alex", "b@mail.com", "c@mail.com"], ["Alex", "c@mail.com", "d@mail.com"], ] merged_transitive = accounts_merge(transitive_accounts) self.assertEqual(len(merged_transitive), 1) self.assertEqual( merged_transitive[0], ["Alex", "a@mail.com", "b@mail.com", "c@mail.com", "d@mail.com"], ) self.assertEqual(accounts_merge([]), []) # 2. DSU de Día 65 dsu = Dia65DSU(5) self.assertEqual(dsu.num_components, 5) self.assertTrue(dsu.union(0, 1)) self.assertTrue(dsu.union(1, 2)) self.assertFalse(dsu.union(0, 2)) # Ya conectados self.assertEqual(dsu.find(0), dsu.find(2)) self.assertEqual(dsu.num_components, 3) with self.assertRaises(ValueError): Dia65DSU(0) # 3. Word Search II (LC 212 Hard) con Trie y poda board = [ ["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"], ] words = ["oath", "pea", "eat", "rain"] found_words = find_words(board, words) self.assertEqual(found_words, ["eat", "oath"]) # Evitar reutilización de la misma celda board_small = [["a", "b"], ["c", "d"]] self.assertEqual(find_words(board_small, ["abcb"]), []) self.assertEqual(find_words([["a"]], ["a", "b"]), ["a"]) self.assertEqual(find_words([], ["word"]), []) # 4. Feedback DSU fb_dsu = analyze_dsu_trie_feedback(5, [(0, 1), (1, 2)], 3) self.assertTrue(fb_dsu["is_correct"]) # --- SEMANA 10: DÍA 66 - Constrained Subsequence Sum (LC 1425) & Trapping Rain Water 2D (LC 407) --- def test_dia_66_constrained_subsequence_sum_and_trapping_rain_water_2d(self): # 1. Constrained Subsequence Sum (LC 1425 Hard) self.assertEqual(constrained_subset_sum([10, 2, -10, 5, 20], 2), 37) self.assertEqual(constrained_subset_sum([-1, -2, -3], 1), -1) self.assertEqual(constrained_subset_sum([10, -2, -10, -5, 20], 2), 23) self.assertEqual(constrained_subset_sum([42], 5), 42) with self.assertRaises(ValueError): constrained_subset_sum([], 2) with self.assertRaises(ValueError): constrained_subset_sum([1, 2, 3], 0) # 2. Trapping Rain Water II (LC 407 Hard) height_map_1 = [ [1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1], ] self.assertEqual(trap_rain_water_2d(height_map_1), 4) # Cuenco 5x5 con valle interior bowl_5x5 = [ [3, 3, 3, 3, 3], [3, 2, 2, 2, 3], [3, 2, 1, 2, 3], [3, 2, 2, 2, 3], [3, 3, 3, 3, 3], ] # Borde exterior es 3. Celdas interiores: ocho celdas de altura 2 atrapan 1 cada una (8), celda central de altura 1 atrapa 2 (2) -> Total 10 self.assertEqual(trap_rain_water_2d(bowl_5x5), 10) # Matriz pequeña (< 3x3) no atrapa nada self.assertEqual(trap_rain_water_2d([[1, 2], [3, 4]]), 0) self.assertEqual(trap_rain_water_2d([]), 0) # 3. Feedback Range Queries fb_rq = analyze_range_query_feedback([10, 2, -10, 5, 20], 2, 37) self.assertTrue(fb_rq["is_correct"]) # --- SEMANA 10: DÍA 67 - Distributed Rate Limiter & Log Deduplicator --- def test_dia_67_distributed_rate_limiter_and_log_deduplicator(self): # 1. Distributed Rate Limiter con Consistent Hashing d_limiter = DistributedRateLimiter( capacity_per_client=5.0, refill_rate_per_client=1.0, num_vnodes=50, ) d_limiter.add_node("node_alpha") d_limiter.add_node("node_beta") d_limiter.add_node("node_gamma") node_client1 = d_limiter.get_responsible_node("client_101") self.assertIn(node_client1, {"node_alpha", "node_beta", "node_gamma"}) # Determinismo de mapeo self.assertEqual(d_limiter.get_responsible_node("client_101"), node_client1) # Consumo de fichas allowed, n_resp = d_limiter.allow_request("client_101", tokens=3.0, current_time=100.0) self.assertTrue(allowed) self.assertEqual(n_resp, node_client1) allowed2, _ = d_limiter.allow_request("client_101", tokens=3.0, current_time=100.0) self.assertFalse(allowed2) # Solo quedaban 2 fichas # Recarga perezosa simulada tras 3 segundos (+3 fichas -> total 5 fichas) allowed3, _ = d_limiter.allow_request("client_101", tokens=3.0, current_time=103.0) self.assertTrue(allowed3) # Remover nodo d_limiter.remove_node("node_alpha") self.assertNotIn("node_alpha", d_limiter.node_buckets) empty_limiter = DistributedRateLimiter() with self.assertRaises(RuntimeError): empty_limiter.get_responsible_node("c1") # 2. Simple Bloom Filter bf = SimpleBloomFilter(size_bits=1000, num_hashes=3) self.assertFalse(bf.contains("msg_alpha")) bf.add("msg_alpha") self.assertTrue(bf.contains("msg_alpha")) # 3. Log Deduplicator con Bloom Filter + Simhash dedup = LogDeduplicator(hash_bits=64, max_hamming_distance=6) # Log nuevo res1 = dedup.process_log("log_1", "Database connection timeout at 192.168.1.100") self.assertEqual(res1["status"], "NEW") # Duplicado exacto (detectado por Bloom Filter) res2 = dedup.process_log("log_2", "Database connection timeout at 192.168.1.100") self.assertEqual(res2["status"], "EXACT_DUPLICATE") self.assertEqual(res2["hamming_distance"], 0) # Cuasi-duplicado (detectado por Simhash con distancia <= 6) res3 = dedup.process_log("log_3", "Database connection timeout at 192.168.1.101") self.assertEqual(res3["status"], "NEAR_DUPLICATE") self.assertEqual(res3["matched_id"], "log_1") self.assertLessEqual(res3["hamming_distance"], 6) # Log completamente nuevo y no relacionado res4 = dedup.process_log("log_4", "User payment authorized with transaction token XYZ") self.assertEqual(res4["status"], "NEW") self.assertEqual(dedup.stats["exact_duplicates"], 1) self.assertEqual(dedup.stats["near_duplicates"], 1) self.assertEqual(dedup.stats["unique_logs"], 2) # --- SEMANA 10: DÍA 68 - Gran Simulacro Onsite FAANG Staff (LC 269 & LC 480) --- def test_dia_68_staff_mock_interview_alien_order_and_median_sliding_window(self): # 1. Alien Dictionary (LC 269 Hard) words_valid = ["wrt", "wrf", "er", "ett", "rftt"] order = alien_order(words_valid) self.assertEqual(len(order), 5) # Validar precedencias: w antes de e, e antes de r, r antes de t, t antes de f pos = {char: i for i, char in enumerate(order)} self.assertLess(pos["w"], pos["e"]) self.assertLess(pos["e"], pos["r"]) self.assertLess(pos["r"], pos["t"]) self.assertLess(pos["t"], pos["f"]) self.assertEqual(alien_order(["z", "x"]), "zx") self.assertEqual(alien_order(["z", "x", "z"]), "") # Ciclo dirigido self.assertEqual(alien_order(["abc", "ab"]), "") # Prefijo inválido self.assertEqual(alien_order(["z"]), "z") self.assertEqual(alien_order([]), "") # 2. Sliding Window Median (LC 480 Hard) nums1 = [1, 3, -1, -3, 5, 3, 6, 7] k1 = 3 medians1 = median_sliding_window(nums1, k1) self.assertEqual(medians1, [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]) nums2 = [1, 2, 3, 4, 2, 3, 1, 4, 2] k2 = 4 medians2 = median_sliding_window(nums2, k2) self.assertEqual(len(medians2), len(nums2) - k2 + 1) # Primer ventana: [1, 2, 3, 4] -> (2 + 3)/2 = 2.5 self.assertEqual(medians2[0], 2.5) self.assertEqual(median_sliding_window([5, 2, 8], 1), [5.0, 2.0, 8.0]) self.assertEqual(median_sliding_window([], 1), []) with self.assertRaises(ValueError): median_sliding_window([1, 2], 0) with self.assertRaises(ValueError): median_sliding_window([1, 2], 5) # 3. Rúbrica Onsite Staff res_strong = evaluate_staff_onsite_interview({ "clarification_and_boundaries": 15.0, "edge_cases_paper_first": 15.0, "structural_design_and_trace": 20.0, "algorithmic_correctness_and_complexity": 15.0, "production_grade_code_and_typing": 20.0, "dry_run_and_resilience": 15.0, }) self.assertEqual(res_strong["total_score"], 100.0) self.assertEqual(res_strong["level"], "Strong Hire (Staff / Principal L6+)") self.assertTrue(res_strong["passed"]) res_nohire = evaluate_staff_onsite_interview({ "clarification_and_boundaries": 5.0, "edge_cases_paper_first": 5.0, "structural_design_and_trace": 10.0, "algorithmic_correctness_and_complexity": 10.0, "production_grade_code_and_typing": 10.0, "dry_run_and_resilience": 5.0, }) self.assertEqual(res_nohire["total_score"], 45.0) self.assertEqual(res_nohire["level"], "No Hire (Preparación insuficiente para nivel Senior/Staff)") self.assertFalse(res_nohire["passed"]) # --- SEMANA 10: DÍA 69 - Examen de Maestría de 30 Preguntas de Active Recall --- def test_dia_69_mastery_exam_active_recall_30_questions(self): questions = get_all_mastery_questions() self.assertEqual(len(questions), 30) # Verificar 5 categorías con 6 preguntas cada una cat_counts: Dict[str, int] = defaultdict(int) for q in questions: cat_counts[q["category"]] += 1 self.assertEqual(len(cat_counts), 5) for count in cat_counts.values(): self.assertEqual(count, 6) # 1. 100% de aciertos perfect_answers = {i: True for i in range(1, 31)} eval_perfect = evaluate_mastery_exam(perfect_answers) self.assertEqual(eval_perfect["total_correct"], 30) self.assertEqual(eval_perfect["percentage"], 100.0) self.assertEqual(eval_perfect["level"], "Staff / Principal (L6+)") self.assertTrue(eval_perfect["passed"]) self.assertEqual(len(eval_perfect["recommendations"]), 0) # 2. 25 aciertos (83.3% -> Senior) senior_answers = {i: (i <= 25) for i in range(1, 31)} eval_senior = evaluate_mastery_exam(senior_answers) self.assertEqual(eval_senior["total_correct"], 25) self.assertEqual(eval_senior["percentage"], 83.3) self.assertEqual(eval_senior["level"], "Senior (L5)") self.assertTrue(eval_senior["passed"]) self.assertGreater(len(eval_senior["recommendations"]), 0) # 3. 15 aciertos (50.0% -> Junior) junior_answers = {i: (i <= 15) for i in range(1, 31)} eval_junior = evaluate_mastery_exam(junior_answers) self.assertEqual(eval_junior["total_correct"], 15) self.assertEqual(eval_junior["percentage"], 50.0) self.assertEqual(eval_junior["level"], "Junior (L3)") self.assertFalse(eval_junior["passed"]) # --- SEMANA 10: DÍA 70 - Matriz de Certificación Final y Blueprint de Graduación --- def test_dia_70_final_curriculum_certification(self): self.assertEqual(len(CURRICULUM_WEEKS), 10) total_weight = sum(item["weight"] for item in CURRICULUM_WEEKS) self.assertAlmostEqual(total_weight, 100.0) # 1. Certificación Staff L6+ con 95% promedio staff_scores = {f"semana_{i}": 95.0 for i in range(1, 11)} cert_staff = evaluate_full_curriculum_certification(staff_scores) self.assertEqual(cert_staff["total_weighted_score"], 95.0) self.assertEqual(cert_staff["algorithmic_gpa"], 4.0) self.assertEqual(cert_staff["seniority_title"], "Staff / Principal Software Engineer (L6+)") self.assertTrue(cert_staff["certified"]) self.assertEqual(len(cert_staff["strengths"]), 10) self.assertEqual(len(cert_staff["areas_for_growth"]), 0) # 2. Certificación Senior L5 con 85% promedio senior_scores = {f"semana_{i}": 85.0 for i in range(1, 11)} cert_senior = evaluate_full_curriculum_certification(senior_scores) self.assertEqual(cert_senior["total_weighted_score"], 85.0) self.assertEqual(cert_senior["algorithmic_gpa"], 3.3) self.assertEqual(cert_senior["seniority_title"], "Senior Software Engineer (L5)") self.assertTrue(cert_senior["certified"]) # 3. Verificación del Blueprint blueprint = cert_staff["graduation_blueprint"] self.assertIn("whiteboard_protocol", blueprint) self.assertIn("spaced_repetition_calendar", blueprint) self.assertEqual(len(blueprint["whiteboard_protocol"]), 5) self.assertIn("D+30", blueprint["spaced_repetition_calendar"]) # --- SEMANA 10: CASOS BORDE Y ESTRÉS PROFUNDO --- def test_dia_64_to_70_semana_10_edge_cases_and_stress(self): import random import statistics random.seed(70) # 1. Estrés Regex Matching con patrón de múltiples comodines pattern_long = "a*b*c*d*e*f*g*h*" self.assertTrue(is_match_regex("", pattern_long)) self.assertTrue(is_match_regex("h", pattern_long)) self.assertTrue(is_match_regex("abdefgh", pattern_long)) self.assertFalse(is_match_regex("abzdefgh", pattern_long)) # 2. Validación cruzada de DualHeapMedianFinder vs statistics.median en 100 ventanas test_stream = [random.randint(-500, 500) for _ in range(100)] k_win = 7 custom_medians = median_sliding_window(test_stream, k_win) self.assertEqual(len(custom_medians), 100 - k_win + 1) for idx in range(len(custom_medians)): window = test_stream[idx : idx + k_win] expected_med = float(statistics.median(window)) self.assertAlmostEqual(custom_medians[idx], expected_med, places=5) # 3. Estrés Constrained Subsequence Sum con 300 elementos nums_stress = [random.randint(-100, 100) for _ in range(300)] k_stress = 10 res_css = constrained_subset_sum(nums_stress, k_stress) self.assertIsInstance(res_css, int) # La suma máxima debe ser al menos el máximo elemento individual self.assertGreaterEqual(res_css, max(nums_stress)) # 4. Estrés Accounts Merge con 30 cuentas interconectadas en cadena chain_accounts = [] for i in range(30): chain_accounts.append([ "User", f"mail_{i}@domain.com", f"mail_{i+1}@domain.com" ]) merged_chain = accounts_merge(chain_accounts) self.assertEqual(len(merged_chain), 1) self.assertEqual(len(merged_chain[0]), 32) # Nombre "User" + 31 emails únicos (0..30) # 5. Estrés Distributed Rate Limiter con 5 servidores y 100 clientes dist_lim = DistributedRateLimiter(num_vnodes=80) for srv_id in range(5): dist_lim.add_node(f"server_{srv_id}") assignments: Dict[str, int] = defaultdict(int) for client_id in range(100): node = dist_lim.get_responsible_node(f"user_client_{client_id}") assignments[node] += 1 self.assertEqual(len(assignments), 5) # Cada uno de los 5 servidores debe recibir entre 5 y 45 clientes for srv, count in assignments.items(): self.assertGreater(count, 5, f"Servidor {srv} desbalanceado a la baja ({count})") self.assertLess(count, 45, f"Servidor {srv} sobrecargado ({count})") # --- SEMANA 10: AUDITORÍA ADVERSARIAL Y VALIDACIÓN DE LÍMITES --- def test_dia_64_to_70_semana_10_adversarial_validation(self): # 1. Día 64: Excepciones de patrones inválidos en Memoization y 1D DP with self.assertRaises(ValueError): is_match_regex_memo("a", "*a") with self.assertRaises(ValueError): is_match_regex_memo("a", "a**") with self.assertRaises(ValueError): is_match_regex_1d("a", "*a") with self.assertRaises(ValueError): is_match_regex_1d("a", "a**") # 2. Día 65: Casos borde de Accounts Merge y Word Search II # Cuentas con mismo nombre pero conjuntos de emails disjuntos disjoint_same_name = [ ["John", "a@mail.com"], ["John", "b@mail.com"], ] merged_disjoint = accounts_merge(disjoint_same_name) self.assertEqual(len(merged_disjoint), 2) # Cuentas duplicadas idénticas dup_accounts = [ ["John", "a@mail.com"], ["John", "a@mail.com"], ] self.assertEqual(accounts_merge(dup_accounts), [["John", "a@mail.com"]]) # Cuenta sin emails self.assertEqual(accounts_merge([["Empty"]]), []) # Word Search II: palabra más larga que las celdas del tablero board_tiny = [["a", "b"], ["c", "d"]] self.assertEqual(find_words(board_tiny, ["abcde"]), []) # Inserción de cadena vacía en WordSearchTrie trie_empty = WordSearchTrie() trie_empty.insert("") self.assertEqual(len(trie_empty.root.children), 0) # 3. Día 66: Constrained Subsequence Sum y Trapping Rain Water 2D # Arreglo con solo valores negativos: debe retornar el mayor (menos negativo) self.assertEqual(constrained_subset_sum([-20, -5, -15], 2), -5) self.assertEqual(constrained_subset_sum([-10], 1), -10) # Terreno montañoso (centro más alto que el contorno): 0 agua atrapada mountain = [ [5, 5, 5], [5, 10, 5], [5, 5, 5], ] self.assertEqual(trap_rain_water_2d(mountain), 0) # Terreno plano: 0 agua atrapada flat_grid = [[4, 4, 4], [4, 4, 4], [4, 4, 4]] self.assertEqual(trap_rain_water_2d(flat_grid), 0) # 4. Día 67: Validaciones de constructores y matched_id en duplicados exactos with self.assertRaises(ValueError): DistributedRateLimiter(num_vnodes=0) with self.assertRaises(ValueError): DistributedRateLimiter(capacity_per_client=-1.0) with self.assertRaises(ValueError): DistributedRateLimiter(refill_rate_per_client=0.0) with self.assertRaises(ValueError): SimpleBloomFilter(size_bits=0) with self.assertRaises(ValueError): SimpleBloomFilter(num_hashes=-1) with self.assertRaises(ValueError): LogDeduplicator(hash_bits=0) with self.assertRaises(ValueError): LogDeduplicator(max_hamming_distance=-1) # matched_id en duplicado exacto dedup_exact = LogDeduplicator() r1 = dedup_exact.process_log("first_log", "Fatal kernel panic at sector 0x88") self.assertEqual(r1["status"], "NEW") r2 = dedup_exact.process_log("second_log", "Fatal kernel panic at sector 0x88") self.assertEqual(r2["status"], "EXACT_DUPLICATE") self.assertEqual(r2["matched_id"], "first_log") # 5. Día 68: DualHeapMedianFinder k <= 0 y Alien Order con palabras duplicadas with self.assertRaises(ValueError): DualHeapMedianFinder(0) with self.assertRaises(ValueError): DualHeapMedianFinder(-3) self.assertEqual(alien_order(["apple", "apple"]), "aple") self.assertEqual(median_sliding_window([99], 1), [99.0]) self.assertEqual(median_sliding_window([7, 7, 7, 7], 3), [7.0, 7.0]) # 6. Día 69: Mastery exam con respuestas vacías e IDs foráneos eval_empty = evaluate_mastery_exam({}) self.assertEqual(eval_empty["total_correct"], 0) self.assertEqual(eval_empty["percentage"], 0.0) self.assertEqual(eval_empty["level"], "Junior (L3)") self.assertFalse(eval_empty["passed"]) eval_alien_ids = evaluate_mastery_exam({9999: True, -1: True}) self.assertEqual(eval_alien_ids["total_correct"], 0) # 7. Día 70: Clamping de puntajes y límites de GPA scores_out_of_bounds = {f"semana_{i}": 150.0 for i in range(1, 11)} cert_clamped = evaluate_full_curriculum_certification(scores_out_of_bounds) self.assertEqual(cert_clamped["total_weighted_score"], 100.0) self.assertEqual(cert_clamped["algorithmic_gpa"], 4.0) # Senior Staff (90.0) cert_senior_staff = evaluate_full_curriculum_certification({f"semana_{i}": 91.0 for i in range(1, 11)}) self.assertEqual(cert_senior_staff["algorithmic_gpa"], 3.8) self.assertEqual(cert_senior_staff["seniority_title"], "Senior Staff Software Engineer (L5+)") # Mid-Level (70.0) cert_mid = evaluate_full_curriculum_certification({f"semana_{i}": 70.0 for i in range(1, 11)}) self.assertEqual(cert_mid["algorithmic_gpa"], 2.5) self.assertEqual(cert_mid["seniority_title"], "Mid-Level Software Engineer (L4)") # Junior (<65.0) cert_junior = evaluate_full_curriculum_certification({f"semana_{i}": 40.0 for i in range(1, 11)}) self.assertEqual(cert_junior["algorithmic_gpa"], 1.5) self.assertEqual(cert_junior["seniority_title"], "Junior Software Engineer (L3)") self.assertFalse(cert_junior["certified"]) if __name__ == "__main__": unittest.main()